## Special Topics in Algorithmic Game Theory (MA5226)

#### TUM, Department of Mathematics, SS 2018

**Lecturer**: Yiannis Giannakopoulos
**Teaching Assistant**: Diogo Poças
**Weekly hours**: 2+1 (4+2 over 7 weeks)
ECTS credits: 5

### News

- The date/time of the (regular)
**final exam**has been announced (see below, in the “Schedule” section).*The registration period is between May 14 – June 8, 2018. Make sure to register for the exam in time!* - We have updated exercise 2.2;
*make sure to work on the latest version of Exercise Sheet 2* - There will be
**no class on Wed 25.04**, due to the*Fachschaftsvollversammlung*. Hand in your solutions to Exercise Sheet 2 during that day’s office hours (or via email). - The first exercise sheet has been posted (see “Exercises” section below). Exercises are going to be published in this web page every Wednesday;
*make sure to check it regularly!* - Registration for the course is now open at TUMonline.

### Schedule

**Duration:** April 11, 2018 – May 25, 2018 *(Tutorials start on April 20)*

Class Type | Day | Time | Room | Lecturer |
---|---|---|---|---|

Lecture |
Wednesday | 10:15 – 11.45 | MI 02.04.011 | Υ. Giannakopoulos |

Friday | 10:15 – 11.45 | MI 02.04.011 | Υ. Giannakopoulos | |

Tutorial |
Friday | 12:15 – 13.45 | MI 02.04.011 | D. Poças |

**Office hours:** Wednesdays & Fridays, 13:00–15:00, Room 02.04.061 (for the duration of the course); or after email appointment.

**Exam:** Friday, June 15, 2018 – 16:15 – Interims 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, Scheduling Unrelated Machines, 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,

*. 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,*

**this is**still**a theory course****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 11.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.
- 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 13.04)*Basics of Mechanism Design: First- and second-price auctions, DSIC truthfulness. Sponsored search auctions.*Reading: [20LAGT, Lecture 2] Further reading:**Lecture 3**(Wed 18.04)*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.
- [AGT, Sections 9.4.1,9.4.2 and 9.5.4–9.5.6]

- Theorem 14.6.1 and its proof, from Anna Karlin’s and Yuval Peres’s book
**Lecture 4**(Fri 20.04)*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**(Fri 27.04)*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”.

**Lecture 6**(Wed 02.05)*(Non-atomic) selfish routing: Price of Anarchy and the Pigou bound.*Reading: [20LAGT, Lecture 11] Further reading:- An 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 04.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 09.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 11.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.

**Lecture 10**(Wed 16.05)*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.

### 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 Diogo); in the latter case, *make sure to submit your work as a single file.*

**Sheet 1**(due Wed 18.04)*[Solution hints]***Sheet 2**(due Wed 25.04)*[Solution hints]***Sheet 3**(due Wed 02.05)*[Solution hints]***Sheet 4**(due Wed 09.05)*[Solution hints]***Sheet 5**(due Wed 16.05)*[Solution hints]***Sheet 6**(due Wed 23.05)