Master's Seminar: Algorithmic Game Theory and Mechanism Design
General Information
Course instructors: Andreas S. Schulz, Chiara Vanoli
The presentations will take place in seminar room 2906.DG.009 (local room number 6009).
- 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
Topics
We suggest the following papers. If you want to present another paper, please reach out to us by August 24th.
- A: Abernethy et al.: Fast Convergence of Fictitious Play for Diagonal Payoff Matrices [DOI]
- B: Berriaud, Constantinescu, Wattenhofer: Stable dinner party seating arrangements [DOI]
- 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: Aggarwal et al.: Selling joint ads: A regret minimization perspective [DOI]
- F: Finster, Goldberg, Lock: Competitive and revenue-optimal pricing with budgets [DOI]
- G: Feldman et al.: Budget-Feasible Contracts [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