Algorithmic game theory (NDMI098) - lecture

Time of the lecture: Thursday 10:40am, in the room S9.

Instructor: Martin Balko. E-mail: balko (AT) kam.mff.cuni.cz

Tutorials:
Information:
up
  • 2/2, C+Ex, 5 E-Credits
  • Annotation: An introduction to algorithmic game theory, a relatively new field whose objective is to study formal models of strategic environments and to design effective algorithms for them. This introductory course covers basic concepts and methods that are illustrated with several practical applications. To successfully pass the course, it is recommended to know basics from complexity theory.
  • Exam:
    • The dates are in SIS. The exam is oral with a written preparation, the total time is 3 hours.
    • I will ask about two topics, one survey question and one with proofs. The questions will be selected from the topics that we covered (see the list of lectures below). Everything is included in the lecture notes.
    • Example of the exam assignment: [PDF].
  • Literature:
    • Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic game theory. Cambridge University Press, Cambridge, 2007.
    • Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, Cambridge, 2016.
    • Kevin Leyton-Brown and Yoav Shoham. Essentials of game theory, volume 3 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston, VT, 2008.
    • Jiří Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. Springer-Verlag New York, Inc., 2006.
  • Lecture notes: [PDF] (last update: 11.1.2024)
    • The lecture notes are still under construction. If you notice any mistake or place for improvement, please, let me know by e-mail.
Lectures:
up
  • First lecture (5.10.2023):
    • Introduction, information about the course,
    • normal-form games, Nash equilibria (pure and mixed), examples of normal-form games,
    • Nash's theorem and preparation for its proof using Brouwer's fixed point theorem,
    • presentation [PDF].
  • Second lecture (12.10.2023):
    • Proof of Nash's theorem,
    • Pareto optimality,
    • the Minimax theorem and preparations for its proof using the duality in linear programming,
    • presentation [PDF].
  • Third lecture (19.10.2023):
    • Proof of the Minimax theorem based on the duality of linear programming,
    • best response condition,
    • brute-force algorithm to find all Nash equilibria,
    • preliminaries from geometry,
    • presentation [PDF].
  • Fourth lecture (26.10.2023):
    • Best response polyhedra,
    • best response polytopes,
    • Lemke–Howson algorithm and a proof of its correctness,
    • presentation [PDF].
  • Fifth lecture (2.11.2023):
    • The lecture is cancelled (Dean's day).
  • Sixth lecture (9.11.2023):
    • Complexity classes FNP and PPAD,
    • NASH being FNP-complete implies NP = coNP (without proof),
    • the END-OF-THE-LINE problem,
    • NASH is PPAD-complete (without proof),
    • epsilon-Nash equilibria,
    • quasi-polynomial time algorithm for finding epsilon-Nash equilibria (without proof),
    • correlated equilibria and their properties,
    • linear program for finding correlated equilibria,
    • presentation [PDF].
  • Seventh lecture (16.11.2023):
    • Regret minimization, introduction of the formal model, external regret,
    • large comparison classes cannot yield good bound on external regret,
    • greedy algorithm and its cumulative loss,
    • Randomized greedy algorithm and its cumulative loss,
    • polynomial weights algorithm and its cumulative loss,
    • presentation [PDF].
  • Eighth lecture (23.11.2023):
    • No-regret dynamics,
    • proof of the Minimax theorem using regret minimization,
    • coarse correlated equilibria,
    • convergence to coarse correlated equilibria with no-regret dynamics,
    • presentation [PDF].
  • Ninth lecture (30.11.2023):
    • Internal regret and swap regret,
    • black-box reduction producing good bounds on swap regret using algorithms with good bounds on external regret,
    • no-swap-regret dynamics and its convergence to correlated equilibria (withoout proof),
    • games in extensive form, perfect and imperfect-information games and their examples,
    • presentation [PDF].
  • Tenth lecture (7.12.2023):
    • Pure, mixed, and behavioral strategies in extensive games,
    • games of perfect recall and Kuhn's theorem (without proof),
    • sequence form of extensive games,
    • computing equilibria in two-player extensive games,
    • presentation [PDF].
  • Eleventh lecture (14.12.2023):
    • Mechanism design,
    • single-item auctions,
    • first-price auction, Vickrey auction,
    • DSIC property, Vickrey auction is awesome,
    • single-item environments, sponsored-search auctions,
    • statement of Myerson's lemma,
    • applications of Myerson's lemma (single-item auctions and sponsored-search auctions),
    • presentation [PDF].
  • Twelfth lecture (21.12.2023):
    • Sketch of the proof of Myerson's lemma,
    • Knapsack auctions,
    • almost optimal greedy algorithm for Knapsack auctions (with a sketch of the proof of correctness),
    • presentation [PDF].
  • Thirteenth lecture (4.1.2024):
    • Revenue maximization,
    • Bayesian model and expected revenue,
    • maximizing expected revenue = maximizing expected virtual social surplus,
    • maximizing revenue in single-item auctions and further extensions,
    • presentation [PDF].
  • Fourteenth lecture (11.1.2024):
    • Bulow–Klemperer Theorem,
    • multi-parameter environments and their examples,
    • VCG mechanism,
    • Revelation principle,
    • presentation [PDF].
Valid XHTML 1.0 Transitional