CS60025 Algorithmic Game Theory - Winter 2019


Instructor:

 Palash Dey

Teaching Assistants:

 Satendra Kumar (satendra.cse@gmail.com)
Pradyumna Kumar Bishoyi (pradyumna.iiitk@gmail.com)

Course overview:
 Game theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), and strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann and Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology and even to inspection regimes for arms control.

Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification and model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics and computing have received extensive attention. These include electronic auctions, and more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet.

Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments.


Prerequisites:
 Knowledge of probability theory, discrete mathematics, and algorithm design is required.

Classes:
 Venue: CSE-119. Timings: Monday (8:00-9:50 AM), Tuesday (12:05-1:00 PM)

Grading:
2 Class tests: 10%, 3 assignments: 10%, Mid-semester: 30%, Final: 50%

Announcements: Lectures:
Running lecture notes: here

Assignments:

15 July 1. Normal Form Games, Selfishness, Common Knowledge, Intelligence, Diminant Strategy
16 July 2. Pure Strategy Nash Equilibrium, Mixed Strategy Nash Equilibrium, Best Response
22 July 3. Matrix Games
23 July 4. Matrix Games cont.
29 July 5. Potential Games, Best Response Dynamics
30 July 6. Computing PSNE for Congestion Games, PLS Completeness
5 August 7. PLS Completeness of Symmetric Congestion Games, FNP, TFNP, PPAD, Sperner's Lemma
6 August 8. Overview of PPAD Hardness Nash Problem, Algorithm to Compute 1/2-Approximate MSNE of a Mimatrix Game, Correlated Equilibrium
12 August No Class -- Holiday
13 August No Class -- Class Test
19 August 9. Coarse Correlated Equilibrium, No-Regret Dynamics
20 August 10. Swap-Regret
26 August 11. Yao's Lemma, Lower Bound for Randomized Sorting Algorithm, Price of Anarchy, Selfish Routing
27 August No class -- Institute Convocation
2 September 12. Selfish Routing, Selfish Load Balancing
3 September 13. Bayesian Games
9 September 14. Extensive Form Game, Revision
10 September No class -- Institute holiday
16, 17, 23, 24 September No class -- Midsemester Examination
30 September 15. Introduction to Mechanism Design, DSIC, BIC, Revelation Principle, Pareto Optimality, Non-dictatorship, Individual Rationality
1 October 16. Gibbard-Satterthwaite Theorem: Statement and Implications
7, 8 October No class -- Institute holidays
14 October 17. Proof of Gibbard-Satterthwaite Theorem
15 October 18. Quasilinear Environment, VCG Mechanism
21 October 19. VCG Mechanism cont., Robert's Theorem, Mechanism Design in Single Parameter Envronment
28 October 20. Algorithmic Mechanism Design, Stable Matching
29 October 21. Stable Matching cont.
4 November 22. Stable Matching, House Allocation Problem



References:
  1. Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007 (available for free from here).
  2. Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.
  3. Game Theory and Mechanism Design by Y. Narahari (equivalent lecture notes are available here).