**Lecturer**: Yiannis Giannakopoulos

**Tutorials**: Diogo Poças, Alexandros Tsigonias-Dimitriadis

**Weekly hours**: 2+1 (4+2 over 7 weeks)

ECTS credits: 5

- There will be
**no 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 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.

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

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.

- 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)

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,

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

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).

**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:**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]

- Theorem 14.6.1 and its proof, from Anna Karlin’s and Yuval Peres’s book
**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:- 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”.

**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)