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
answer honestly.
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.
- Networks, crowds, and markets: Reasoning about a highly connected world. Easley and Kleinburg, to appear.
- pdf copy of complete draft here