Course Content
1) Overview of games and equilibria concepts: Overview of games (including graphical games), utility, strategy, payoff and solution concepts (pure strategy, mixed strategy, and correlated equilibria), extensive form games and subgame perfect equilibria. (3 lectures)
2) Algorithms and complexity of finding equilibria: Basics of linear programming and local search, Lemke-Howson algorithm, complexity classes - PLS, PPAD, TFNP. (8 lectures)
3) Inefficiency of equilibria: Inefficiency of equilibria overview, potential function, network formation games, selfish routing, price of anarchy, selfish load balancing. (10 lectures)
4) Adaptive decision making: Binary prediction problem, weighted majority algorithm, sequential adaptive decision making, multiplicative-weights update algorithm, adaptive decision making and zero-sum games. (6 lectures)
5) Market Design: Matching markets (two-sided and one-sided): equilibria and clearing prices, random priority mechanism, probabilistic serial mechanism, top trading cycle, Hylland-Zeckhauser solution, trading networks, exchange networks. (15 lectures)
Possible overlap with other courses: There is some unavoidable overlap (in parts (1) and (5) of above plan) with CS5614 (Game Theory and Mechanism Design) and newly proposed course Multiagent Systems. However, the content of this course is completely different for the most part and the overlap is less than 20%. So, the students who credit those courses may be allowed to credit this course provided they have the prerequisites covered.
Learning Outcomes
- Develop concepts related to games and markets, such as strategy, payoff, equilibria, clearing price, etc.
- Learn different algorithms for solving games and markets, and become familiar with relevant complexity classes.
Text/Reference Books
- Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay Vazirani. Cambridge University Press (ISBN: 978-0521872829).
- Twenty Lectures on Algorithmic Game Theory, Tim Roughgarden, Cambridge University Press. (ISBN: 978-1316624791)
- Networks, Crowds, and Markets: Reasoning about a Highly Connected World, David Easley and John Kleinberg, Cambridge University Press. (ISBN: 978-0521195331)
- Game Theory, Alive, Anna Karlin, Yuval Peres. American Mathematical Society (ISBN:978-1470419820)
- Online and Matching-Based Market Design, Echenique, Immorlica, Vazirani, Cambridge University Press.
- Multiagent Systems, Yoav Shoham Kevin Leyton-Brown , Cambridge University Press (ISBN: 978-0521899437
Past Offerings
Course Metadata
| Item | Details |
|---|---|
| Course Title | Topics in Algorithmic Game Theory and Market Design |
| Course Code | CS6008 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Srimanta Bhattacharya |
| Approved on | Senate of IIT Palakkad |
| Course status | New |