CS60025 Algorithmic Game Theory

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:

Question papers: final, midsem, second class test, first class test set 1, first class test set 2
Tutorial on October 19 at 10 AM in CSE 119
Second class test on October 22 at 12PM in CSE-119
Mid-semester examination on September 16, 2019 from 2 PM to 4 PM
Tutorial on August 6 at 5 PM (venue yet to be decided)
First class test on August 13 at 12PM in CSE-119
Please click here to join the course Google group. If you face any issue joining this group, please send an email to the TAs writing your name and roll number.

Lectures:
Lecture notes: here

Assignments:

Assignment 4 (here) is not for submission.
Assignment 3 (here) is due before 30 October 2019 midnight in my mail box in the Department.
Assignment 2 (here) is due before 10 September 2019 midnight in my mail box in the Department.
Assignment 1 (here) is due on July 30 in the class.

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:

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