Special Topics in Algorithmic Game Theory (MA5226)

TUM, Department of Mathematics, SS 2019

Lecturer: Yiannis Giannakopoulos
Tutorials: Diogo Poças, Alexandros Tsigonias-Dimitriadis
Weekly hours: 2+1 (4+2 over 7 weeks)
ECTS credits: 5

News

• The date/time of the retake exam has been announced (see below).
• There will be a revision, “Q&A” class on Friday, June 28, 10:00-12:00 (in our regular room).
• The date/time of the (regular) final exam has been announced (see below). The registration period is between May 27 – June 30. Make sure to register for the exam on time! (at TUMonline)
• There will be no tutorial on Fri 07.06.
• There will be no lecture class on Wed 22.05. Hand in your solutions to Exercise Sheet 3 to Alexandros at the beginning of that day’s tutorial.
• There will be no lecture class on Wed 08.05, due to the Fachschaftsvollversammlung. Hand in your solutions to Exercise Sheet 1 to Alexandros at room 02.06.022B between 12:30–13:00 (or via email, until 13:00).
• The first exercise sheet has been posted. Exercises are going to be published in this web page every Friday; make sure to check it regularly!
• Registration for the course is now open at TUMonline.

Schedule

Lectures: April 24, 2019 – June 14, 2019
Tutorials: May 10, 2019 – June 19, 2019

Class Type	Day	Time	Room
Lecture	Wednesday	10:15 – 11.45	MI 02.10.011
	Friday	10:15 – 11.45	MI 02.04.011
Tutorials	Wednesday	12:15 – 13.45	MI 02.10.011
	Friday	12:15 – 13.45	MI 02.04.011

Office hours: Wednesdays & Fridays (on lecture days), 13:00–15:00, Room 02.04.061; or after email appointment.

Exam: Friday, July 5, 2019. 10:00 – 11:30. Mechanical Engineering Department, Ludwig-Burmester-Zeichensaal (1350).

Retake exam: Tuesday, October 8, 2019. 10:00 – 11:30. MI, Hörsaal 2.

Description

The main goal of this course is to highlight the intriguing interplay between optimality, simplicity, efficiency and robustness in the design and analysis of systems involving many different selfish strategic players, with an emphasis in the intersection between Economics and Theoretical Computer Science. Can we predict the possible outcomes of such dynamic situations? Can we motivate the players and design specific rules, so that those outcomes are stable and desirable? How well and how efficiently can we approximate the above objectives? These questions are very important and relevant in many modern, real-life applications, where the Internet has been established as the main platform for agent-interaction and computing.

We will demonstrate the above by focusing in some of the prototypical topics in the field of Algorithmic Game Theory, such as Optimal (Revenue-Maximizing) Auctions, the Price of Anarchy, Selfish Routing, Congestion and Potential Games, and Learning in Games such as Best-Response and No-Regret Dynamics.

The ambition of this class is to provide a crash course for beginning graduate or advanced-undergraduate students interested in getting a glimpse into the toolbox and the necessary fundamentals of some of the most important research areas within the field of Algorithmic Game Theory, after which they should feel comfortable to start following the related work on their own.

Prerequisites

• Fundamentals of Design & Analysis of Algorithms and Computational Complexity, e.g. MA2501 or similar
• Basics of Game Theory, e.g. IN2239 or similar (recommended, but not essential)

Related Courses

The overlap in the material of this course with that of other AGT courses offered at TUM, most notably IN2239 or IN2211, is minimal. In particular, this course is a natural follow-up to more fundamental Game Theory classes like IN2239, and can also complement nicely combinatorial Mechanism Design course like IN2211; if you have taken any of those courses in the past and enjoyed them, then this might be the right class for you! Also, as stated in the prerequisites above, some prior knowledge on the basics of Game Theory (as given, e.g., by IN2239), though not absolutely necessary (see below), will be an advantage.

---

Disclaimer: Prior knowledge of Game Theory is not essential for being able to follow this class. For example, game-theoretic primitives such as the notion of Nash equilibrium, are going to be introduced and used on-the-fly, on a need-to-know basis as part of the various topics described above. Nevertheless, this is still a theory course. As such, emphasis will be given in rigorousness and mathematical proofs, and the language and feel of algorithmic analysis and optimization will have a dominant presence throughout the lectures. So, mathematical maturity is essential and prior exposure or familiarity with the basic notions of subjects like the Design and Analysis of Algorithms, Discrete Mathematics and Optimization, Computational Complexity, Randomized/Approximation Algorithms, Probability and (Real) Analysis is highly recommended.

Please feel free to contact the lecturer beforehand to discuss any doubts you may have about your background.

---

Main References

The main textbook for our course will be:

• T. Roughgarden, “Twenty Lectures on Algorithmic Game Theory”, Cambridge University Press, 2016.

TUM students can get free electronic access to the book here (from within the Library’s network or via eAccess)

The following, known as “the AGT book”, is the standard reference text in the field. It might be slightly outdated at some specific topics by now, and mostly aimed towards researchers (rather than students), but it is still a classic, covers way more material and we will repeatedly point to it throughout this class.

• Nisan, Roughgarden, Tardos & Vazirani (Eds), “Algorithmic Game Theory”, Cambridge University Press, 2007.

The AGT book is available online here (under the “Resources” tab), free of charge.

For convenience, we will use the shorthands [20LAGT] and [AGT], respectively, to cite the two main references mentioned above.

Further references to additional texts and specific research papers will be given during the class, and supplementary lecture notes will be uploaded here when needed (see the detailed outline below after each lecture).

Outline of Lectures & References

• Lecture 1 (Wed 24.04) Introduction: Mechanism Design, Price of Anarchy, computation of equilibria.
  Reading: Supplementary notes, [20LAGT, Lecture 1]
  Further reading:
  • Video of the 2012 Olympics first controversial badminton match; related blog post; Wikipedia’s entry.
  • Some “real life” examples demonstrating Braess’s paradox: here and here.
  • Short-and-sweet overview articles about AGT: here and here.
  • Three interesting blog posts about Equilibria and Computational Complexity: here, here and here.
  • Play Rock-Paper-Scissors online, against an adaptive AI computer.
  • Quanta article on Nash equilibria (and Rock-Paper-Scissors)
  • Have you ever though about the interplay between Game Theory, Evolution and sex? Read here.
• Lecture 2 (Fri 26.04) Basics of Mechanism Design: First- and second-price auctions, DSIC truthfulness. Sponsored search auctions.
  Reading: [20LAGT, Lecture 2]
  Further reading:
  • Vickrey’s original paper
  • Two fundamental papers on sponsored search auctions, here and here.
  • [AGT, Sections 9.3.1, 9.3.2, 9.3.5] and [AGT, Chapter 28]
• Lecture 3 (Fri 03.05) Single-Parameter environments. Characterization of DSIC implementability: Myerson’s Lemma and the payment formula.
  Reading: Supplementary notes, [20LAGT, Lecture 3], [AGT, Theorem 9.39]
  Further reading:
  • Theorem 14.6.1 and its proof, from Anna Karlin’s and Yuval Peres’s book (highly recommended as an additional Game Theory reference textbook as well!).
  • An interesting discussion about the GSP mechanism for sponsored search auctions and its (non)truthfulness, a short blog post and a related presentation. You can also have a look at Wikipedia’s entry.
  • A very recent post in Google’s official Ad Manager blog on why they are switching to a first-price auction.
  • [AGT, Sections 9.4.1,9.4.2 and 9.5.4–9.5.6]
• Lecture 4 (Fri 10.05) Introduction to Bayesian Mechanism Design. The revenue-maximization objective. Regular distributions and virtual valuations. Equivalence between (expected) revenue maximization and virtual welfare maximization. Optimal Mechanisms; optimality of second-price with reserve for iid bidders.
  Reading: Supplementary notes, [20LAGT, Sections 5.1–5.2], [AGT, Sections 13.1–13.2]
  Further reading:
  • Roger Myerson’s seminal paper.
  • “Test your intuition”
  • Section 14.9 from the Karlin & Peres book.
  • Chapter 3 of Jason Hartline’s text “Mechanism Design and Approximation”.
• Lecture 5 (Wed 15.05) Simplicity vs optimality in auction design. The prophet inequality and second-price auctions with bidder-specific reserves. Prior-independent mechanisms and the Bulow-Klemperer theorem.
  Reading: [20LAGT, Lecture 6]
  Further reading:
  • The classic “Simple vs Optimal” paper of Hartline & Roughgarden.
  • The original Bulow & Klemperer paper.
  • “Algorithmic Pricing via Virtual Valuations” by Chawla, Hartline & Kleinberg.
  • Sections 4.1–4.5, 4.7 and Chapter 5 of Jason Hartline’s text “Mechanism Design and Approximation”.
  • “Dating mathematically”: Three blog posts explaining the secretary problem: here, here and here. Wikipedia’s article is here.
• Lecture 6 (Fri 17.05) (Non-atomic) selfish routing: Price of Anarchy and the Pigou bound.
  Reading: [20LAGT, Sections 11.1–11.4]
  Further reading:
  • A nice web article from the American Mathematical Society on the Price of Anarchy, and a blog post.
  • The seminal paper of Roughgarden & Tardos on the PoA of nonatomic selfish routing.
  • The original papers on the Pigou bound, here and here.
  • The classic paper of J. G. Wardrop on selfish routing and “equilibria”.
• Lecture 7 (Fri 24.05) Atomic selfish routing: Price of Anarchy, upper and lower bounds for affine cost functions.
  Reading: Supplementary notes, [20LAGT, Sections 12.4–12.5]
  Further reading:
  • The seminal paper of Koutsoupias & Papadimitriou, that introduced the Price of Anarchy notion.
  • The classic paper of Christodoulou & Koutsoupias for the PoA on atomic congestion games with affine costs. For the 5/2 lower bound example we saw in class, see also this paper.
  • As we briefly mentioned in class, the PoA of atomic games with polynomial cost functions, grows exponentially with respect to the maximum degree d of the polynomial. For exact PoA bound analysis with respect to d see this paper.
• Lecture 8 (Wed 29.05) Potential games. Congestion games and existence of pure Nash equilibria. Equilibrium refinement and Price of Stability bounds. Weighted congestion games and nonexistence of equilibria. Existence and uniqueness of equilibrium in nonatomic routing games.
  Reading: Supplementary notes, [20LAGT, Sections 13.2–13.3], [AGT, Sections 18.3, 19.3.2–19.3.3]
  Further reading:
  • The seminal papers of Rosenthal and Monderer & Shapley for potential games.
  • The study of the Price of Stability in atomic and nonatomic selfish routing games was initiated, respectively, by the works of Anshelevich et al. and Schulz & Moses.
  • The classic reference for nonatomic routing, including the existence/uniqueness of equilibria in such games, is the work of Beckmann et al.. For a more modern exposition, see Chapter 2 of Roughgarden’s “routing” book.
• Lecture 9 (Fri 31.05) Hierarchy of solution concepts; pure Nash equilibria (PNE), (mixed) Nash equilibria (MNE), correlated equilibria (CE), coarse correlated equilibria (CCE). CE and Linear Programming. PoA and PoS for different equilibrium concepts. Approximate pure Nash equilibria (\varepsilon-PNE).
  Reading: [20LAGT, Section 13.1 and Definition 16.2], [AGT, Sections 1.3 and 2.7]
  Further reading:
  • The seminal papers of John Nash on mixed equilibria, here and here.
  • Aumann’s paper on correlated equilibria.
  • The original paper on coarse correlated equilibria (although the actual term was coined later by Peyton Young).
  • For the computational complexity of finding (and optimizing over) CE see the paper by Papadimitriou and Roughgarden.
  • A blog post about CE.
  • For a generalization of Nash’s theorem to infinite games, see the paper of Glicksberg.
• Lecture 10 (Wed 05.06) Best-response dynamics; convergence in potential games. \varepsilon-Best-response dynamics; fast convergence to approximate PNE of congestion games.
  Reading: [20LAGT, Sections 16.1–16.3]
  Further reading:
  • The fast-convergence result to approximate PNE we analyzed in class is due to Chien & Sinclair.
  • For more about best-response graphs (briefly discussed in class) and walks on them, see the papers here and here.
• Lectures 11-12 (Fri 07.06 & Wed 12.06) Online decision making, regret minimization. No-regret algorithms; multiplicative-weights. No-regret dynamics: fast convergence to (approximate) CCE; convergence to MNE for 2-player, zero-sum games. Swap-regret; convergence to CE.
  Reading: [20LAGT, Sections 17.1, 17.2, 17.4.1, 17.4.2 and 18.1, 18.3]
  Further reading:
  • For an extensive overview of online learning (and its interplay with game equilibria), see the book of Cesa-Bianchi & Lugosi and Chapter 4 of [AGT] by Blum & Mansour.
  • Classic references for learning dynamics that converge to MNE (in 2-player, zero-sum games) are the papers of Hannan and Blackwell.
  • For more on the (swap-regret) dynamics that converge to CE, see the original papers of Foster & Vohra and Hart & Mas-Colell.
  • The Minimax Theorem is due to the great John von Neumann: if you know German, you can read his seminal paper; alternatively, see his book with O. Morgenstern that essentially founded the field of Game Theory.
• Lecture 13 (Fri 14.06) Overview of complexity classes related to computing PNE and MNE; FNP and TFNP. PLS and local search problems; local optima of MAX-CUT; (local) potential function minimization in congestion games and PLS-completeness. PPAD and MNE.
  Reading: [20LAGT, Chapter 19 (except the proofs of Theorems 19.4 and 19.6) and Sections 20.1, 20.2, 20.6]
  Further reading:
  • The standard reference of the theory of NP-completeness and reductions is Garey and Johnson. You should also be aware of the seminal paper of Karp with its 21 NP-complete problems.
  • Revisit the “further reading” list of Lecture 1 for complexity-related references.
  • Class TFNP was first defined by Megiddo & Papadimitriou, PLS by Johnson, Papadimitriou & Yannakakis, and PPAD by Papadimitriou.
  • The original paper on the PLS-completeness of computing PNE in congestion games is by Fabrikant, Papadimitriou & Talwar.
  • The original papers on the PPAD-completeness of computing MNE is by Daskalakis, Goldberg and Papadimitriou Chen, Deng & Teng. For a more compact version see this article.
  • To dig deeper into the theme of Complexity and Game Theory, have a look at these notes by Roughgarden.

Exercises

Instructions for handing-in your solutions: either bring them, in person, by the end of Wednesday’s lecture (to Yiannis), or send them via email (to Alexandros or Diogo, by 11:45); in the latter case, make sure to submit your work as a single file.

• Sheet 1 (due Wed 08.05) [Solution hints]
• Sheet 2 (due Wed 15.05) [Solution hints]
• Sheet 3 (due Wed 22.05) [Solution hints]
• Sheet 4 (due Wed 29.05) [Solution hints]
• Sheet 5 (due Wed 05.06) [Solution hints]
• Sheet 6 (due Wed 12.06) [Solution hints]