 2019 - 2020 | |||||||||||||||||||||||||||||
 |
 |
||||||||||||||||||||||||||||
| 0368-4483 | Algorithmic Game Theory | ||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| FACULTY OF EXACT SCIENCES | |||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
University credit hours: 3.0
Course description
Algorithmic Game Theory
Instructor: Prof. Michal Feldman
Time & Place: Wednesday, 2-5pm (place TBA)
Prerequisites: probability theory, algorithms, complexity
Tentative list of topics:
Introduction to algorithms and games
Two-player zero-sum games (Minmax theorem)
Regret minimization and correlated equilibrium
Nash equilibrium
Mixed equilibrium and Nash theorem
Pure equilibrium
Equilibrium existence
Congestion games
Quality of equilibrium: price of anarchy and smoothness
Social choice and Mechanism Design
Introduction to social choice
Mechanism design without money (and approximation)
Social welfare maximization (VCG)
Combinatorial auctions
Revenue maximization (optimal mechanisms)
Markets and pricing
Walrasian equilibrium
First and second welfare theorems
Ascending price auctions
Course requirements and grading:
Problem sets (possibly including grading)
Final project (either a research project or a survey) – max 10 pages (possibly including presentation)
Scribe notes
Some references
- Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007. http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf
- Shoham and Leyton-Browm, Multiagent systems, Cambridge, 2008. http://www.masfoundations.org/
- Surveys:
- Roughgarden, Algorithmic game theory (2012), http://theory.stanford.edu/~tim/papers/cacm.pdf
Roughgarden, An algorithmic game theory primer (2008) http://theory.stanford.edu/~tim/papers/tcs08.pdf
Shoham, Communications of the ACM, Computer Science and Game Theory, http://robotics.stanford.edu/~shoham/www%20papers/CSGT-CACM080417.pdf
Halpern. Computer science and game theory: a brief survey
http://www.cs.cornell.edu/home/halpern/papers/csgt.pdf
http://www.cs.cornell.edu/home/halpern/papers/csgt.pdf