## Algorithmic game theory

Instructor: Dr. Meghyn Bienvenu

K2 (Vertiefung), Modulbereich Theorie

Summer semester 2010

Di 10-12, MZH 1460

### Course description

Algorithmic game theory lies at the intersection of economics and theoretical computer science.
This course provides a brief introduction to this growing field of research.

Tentative list of topics:
• basics of game theory
• definition of strategic games
• examples of strategic games
• pure and mixed strategies
• solution concepts (dominant strategies, Nash equilibrium, etc.)
• computational aspects of game equilibria
• finding Nash equilibria in zero-sum 2-player games
• finding Nash equilibria in general 2-player games
• complexity of computing Nash equilibria, the class PPAD
• inefficiency of equilibria
• concepts of price of anarchy and price of stability
• class of selfish routing games, examples
• bounds on price of anarchy in routing games
• automated mechanism design
• basic social choice theory
• impossibility results: Arrow, Gibbard Satterwaithe
• properties of different types of auctions
• Vickrey-Clarke-Groves mechanism
• stable matching problems

### Announcements

18.05.10: Makeup class will be held on May 25 from 8:30-10 in room MZH 3150.

27.04.10: Class cancelled on 11.05.10. A makeup class will be scheduled for last week of May.

### Evaluation

Either an oral exam, or homework + Fachgespräch.

Oral exams will be about 45 minutes long and may cover any material presented
in the lecture or in the homework. During the first five minutes of the exam,
students will have the option of discussing a subject of their choice.

Exams and Fachgespräch will both be held between September 7th and September 24th.
Students should contact Meghyn by email to set up an appointment for an exam.

Students must complete the evaluation form for the course (available here) and bring it
with them to their exam. I will only look at the form after assigning a grade, so please

### Slides

• Part 1: Introduction to Game Theory (pdf)
• Part 2: Computational Aspects of Equilibria (pdf, LP input)
• Part 3: Inefficiency of Equilibria (pdf)
• Part 4: Social Choice and Mechanism Design (pdf)

### Homework assignments

• Homework 1. Due date: 27.04 at start of lecture.
• Homework 2. Due date: 25.05 at start of lecture (10:15).
• Homework 3. Due date: 08.06 at start of lecture (10:15).
• Homework 4. Due date: 29.06 at start of lecture (10:15).
• Homework 5. Due date: 06.07 at start of lecture (10:15).

### Bibliography

• Algorithmic Game Theory. Nisan, Roughgarden, Tardos, and Vazirani (Eds.), 2007.
• non-printable pdf copy available here
• Multiagent systems. Shoham and Leyton-Brown, 2009.
• pdf copy available here
• Networks, crowds, and markets: Reasoning about a highly connected world. Easley and Kleinburg, to appear.
• pdf copy of complete draft here