Seminar (Bachelor): Algorithmic Game Theory and Mechanism Design
General Information
Course instructors: 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 20 | Finish the suggested self-study chapters |
| April 26 | Send us your preference list of topics (see below) |
| A week before your presentation | Send us a draft of your presentation to receive feedback |
| May 25, 14:30 | Seminar presentations of topics A and E |
| June 15, 14:30 | Seminar presentations of topics B and D |
| June 29, 14:30 | Seminar presentations of topics G and H |
| July 6, 14:30 | Seminar presentation of topic F |
Topics
Selected chapters from the books given in the Literature section:
- A: AGT Chapter 3 Equilibrium Computation for Two-Player Games in Strategic and Extensive Form
- B: AGT Chapter 4 Learning, Regret Minimization, and Equilibria
- C: AGT Chapter 5 Combinatorial Algorithms for Market Equilibria
- D: AGT Chapter 10 Mechanism Design without Money, Tim Roughgarden Twenty Lectures on Algorithmic Game Theory Lecture 10
- E: AGT Chapter 11 Combinatorial Auctions
- F: AGT Chapter 13 Profit Maximization in Mechanism Design
- G: AGT Chapter 15 Cost Sharing
- H: AGT Chapter 16 Online Mechanisms
- I: AGT Chapter 18 Routing Games
- J: AGT Chapter 19 Network Formation Games
- K: AGT Chapter 20 Selfish Load Balancing
- L: AGT Chapter 28 Sponsored Search Auctions
- M: HSC Chapter 2 Introduction to the Theory of Voting
- N: HSC Chapter 13 Classic Cake Cutting Algorithms
Literature
- Nisan et al. Algorithmic Game Theory (AGT)
- Roughgarden Twenty Lectures on Algorithmic Game Theory
- Brandt et al. Handbook of Computational Social Choice (HSC)