Seminar (Master): Algorithmic Game Theory and Mechanism Design
General Information
Course instructors: Andreas S. Schulz, Alexander Grosz, and Chiara Vanoli
The presentations will take place in room 02.04.011.
- How bad is it that drivers can choose their own route in a street network? (Selfish Routing)
- What's the best bidding strategy at an online auction? ((Combinatorial) Auctions)
- How difficult is it to find an equilibrium in a game? (Computing in Games)
- How are online ads being sold? (Sponsored Search Auctions)
- Can you strategize in democratic voting? Do better voting rules exist? (Social Choice, Voting Rules)
- How do you cut a cake? (Fair Division)
- Whose kidney is going to be transplanted? (Matching under Preferences)
All of these question can be posed in the fields of algorithmic game theory and mechanism design, where strategic agents interact directly or indirectly with each other by some game or mechanism.
In this seminar, students are going to discuss a selected topic each and thereby encounter a variety of questions, methods and applications.
Schedule
| April 20th | Finish the suggested self-study chapters |
| April 26th | Send us your preference list of topics (see below) |
| July 6th | Send us a draft of your presentation to receive feedback |
| July 13th 14:00 | First day of seminar presentations (Topics E, G, I, J) |
| July 20th 14:00 | Second day of seminar presentations (Topics C, D, H, K) |
Topics
We suggest the following papers. If you want to present another paper, please reach out to us in the first week of the course.
- A: Abernethy et al.: Fast Convergence of Fictitious Play for Diagonal Payoff Matrices [DOI]
- B: Gilboa, Zemel: Nash and correlated equilibria: Some complexity considerations [DOI], Conitzer, Sandholm Complexity Results about Nash Equilibria [IJCAI03]
- C: Gupta et al.: Popular Matching in Roommates Setting is NP-hard [DOI]
- D: Ashlagi et al.: Mix and match: A strategyproof mechanism for multi-hospital kidney exchange [DOI]
- E: Ahunbay, Lucier, Vetta: Two-Buyer Sequential Multiunit Auctions with No Overbidding [DOI]
- F: Christodoulou et al.: Resource-Aware Protocols for Network Cost-Sharing Games [DOI]
- G: Scheffler et al.: Equilibria in Routing Games with Edge Priorities [DOI]
- H: Cavallo, Sviridenko, Wilkens: Matching Auctions for Search and Native Ads [DOI]
- I: Behnezhad et al.: From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games [DOI]
- J: Brustle et al.: One Dollar Each Eliminates Envy [DOI]
- K: Deng, Qi, Saberi: Algorithmic Solutions for Envy-Free Cake Cutting [DOI]
Literature
- Nisan et al. Algorithmic Game Theory
- Roughgarden Twenty Lectures on Algorithmic Game Theory
- Brandt et al. Handbook of Computational Social Choice
- Selected research papers in AGT and MD, see Topics section