General Information

Course instructors: Andreas S. Schulz, Alexander Grosz

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.

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 13 Profit Maximization in Mechanism Design
• F: AGT Chapter 16 Online Mechanisms
• G: AGT Chapter 18 Routing Games
• H: AGT Chapter 19 Network Formation Games
• I: AGT Chapter 20 Selfish Load Balancing
• J: AGT Chapter 28 Sponsored Search Auctions
• K: HSC Chapter 2 Introduction to the Theory of Voting
• L: 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)