Algorithms & Complexity

Computer Science 1

Group

Research

Teaching

Misc

back to main page

Logbook Algorithmic Game Theory - Winter 2024/25

• Lecture 17 -- 10.12.2024:
  Voting, majority rule for 2 candidates, Condorcet paradox, plurality rule, incentive compatibility, dictatorships, Arrow theorem, properties of social choice functions, Gíbbard-Satterthwaite theorem, single-peaked preferences, k-th order mechanisms

  Literature:
  • Slides Social Choice, pages 1-20.
  • Fey. A Straightforward Proof of Arrow's Theorem. Econ. Bullet. 34(3):1792-1797, 2014.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Chapters 1.2, 2.1, 2.2, 2.8, 2.9)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)



• Lecture 16 -- 09.12.2024:
  Optimal mechanisms for single-parameter domains, virtual values, regular distributions, interpretation with reservation prices

  Literature:
  • Slides Designing Incentive-Compatible Mechanisms, pages 76-90.
  • Myerson. Optimal Auction Design. Math. Oper. Res. 6(1):58-83, 1981.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 5)



• Lecture 15 -- 03.12.2024:
  Revelation principle, approximation algorithms and mechanism design, knapsack auction, Greedy algorithm is monotone and 2-approximate, standard FPTAS with (1+ε)-approximation is not monotone, adjustment to monotone FPTAS

  • Slides Designing Incentive-Compatible Mechanisms, pages 50-75.
  • Mu'Alem, Nisan. Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. Games Econom. Behav. 64(2):612-631, 2008.
  • Briest, Krysta, Vöcking. Approximation Mechanisms for Utilitarian Mechanism Design. STOC 2005.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 4)



• Lecture 14 -- 02.12.2024:
  Direct characterization, affine maximizers, Roberts Theorem. Single-parameter domain, monotonicity, Myersons Lemma (Proof IC ⇒ f monotone, (IC ∧ f monotone) ⇒ payments, (f monotone ∧ payments) ⇒ IC).

  Literature:
  • Slides Designing Incentive-Compatible Mechanisms, pages 21-49.
  • Myerson. Optimal Auction Design. Math. Oper. Res. 6(1):58-83, 1981.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 3)



• Lecture 13 -- 26.11.2024:
  Vickrey second-price auction, incentive compatibility, VCG mechanisms, Clarke rule, examples

  Literature:
  • Slides Designing Incentive-Compatible Mechanisms, pages 1-20.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)



• Lecture 12 -- 25.11.2024:
  Price of stability, cost sharing games with equal sharing, price of anarchy and stability of equal-sharing games. Equal-sharing vs. arbitrary sharing.

  Literature:
  • Slides Prices of Anarchy and Stability, pages 45-68.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 19)
  • Anshelevich, Dasgupta, Kleinberg, Roughgarden, Tardos, Wexler. The Price of Stability for Network Design with Fair Cost Allocation. SIAM J. Comput. 38(4):1602-1623, 2008.
  • Anshelevich, Dasgupta, Tardos, Wexler. Near-Optimal Network Design with Selfish Agents. Theory Comput. 4(1):77-109, 2008.
  • Hoefer. Non-cooperative Tree Creation. Algorithmica 53(1):104-131, 2009.



• Lecture 11 -- 19.11.2024:
  Price of anarchy in affine congestion games, definition (λ,μ)-smoothness and proof template, price of anarchy for coarse-correlated equilibria, tight games, limits and intuition of smoothness. Price of stability, cost sharing games with equal sharing, upper bounds on prices of anarchy and stability in equal-sharing games.

  Literature:
  • Slides Prices of Anarchy and Stability, pages 22-49.
  • Awerbuch, Azar, Epstein. The Price of Routing Unsplittable Flow. SIAM J. Comput. 42(1):160–177, 2013.
  • Christodoulou, Koutsoupias. The Price of Anarchy of Finite Congestion Games. STOC 2005.
  • Blum, Hajiaghayi, Ligett, Roth. Regret Minimization and the Price of Total Anarchy. STOC 2008.
  • Roughgarden. Intrinsic Robustness of the Price of Anarchy. J. ACM 62(5):32:1–32:42, 2015.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 14)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 19)
  • Anshelevich, Dasgupta, Kleinberg, Roughgarden, Tardos, Wexler. The Price of Stability for Network Design with Fair Cost Allocation. SIAM J. Comput. 38(4):1602-1623, 2008.



• Lecture 10 -- 18.11.2024:
  Wardrop games, Wardrop equilibria, Braess paradox, prices of anarchy and stability, price of anarchy for linear latency functions, existence and uniqueness of Wardrop equilibria.

  Literature:
  • Slides Prices of Anarchy and Stability, pages 1-20.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 11)
  • Beckmann, McGuire, Winsten. Studies in the Economics of Transportation. Yale Univ. Press, 1956.
  • Roughgarden, Tardos. How bad is selfish routing? J. ACM 49(2):236-259, 2002.
  • Correa, Schulz, Stier-Moses. A Geometric Approach to the Price Anarchy in Nonatomic Congestion Games. Games Econom. Behav. 64(2):457-469, 2008.



• Lecture 9 -- 04.11.2024:
  Correlated equilibrium, definition, swap regret, no-swap-regret learning leads to correlated equilibria, master algorithm, consensus distribution, proof of correctness, recap equilibrium existence and computation.

  Literature:
  • Slides Learning and Correlated Equilibria, pages 43-60.
  • Blum, Mansour. From External to Internal Regret. J. Machine Learning Res. 8:1307-1324, 2007.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 18)



• Lecture 8 -- 29.10.2024:
  No-regret learning leads to (approximate) coarse-correlated equilibria. 2-player zero-sum games, proof of Minimax Theorem, convergence on average in hindsight vs. pointwise convergence of actual strategies, adaptive RWM algorithm with convergence time

  Literature:
  • Slides Learning and Correlated Equilibria, pages 18-42.
  • Freund, Schapire. Adaptive Game Playing using Multiplicative Weights. Games Econ. Behav. 29:79–103, 1999.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 4)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 17)



• Lecture 7 -- 28.10.2024:
  Recap stable matching, construction of short improvement sequences, convergence in the limit with probability 1. Expert problem, Greedy is bad, definition no-regret algorithm, Randomized Weighted Majority with regret guarantee, application in games leads to (approximate) coarse-correlated equilibra

  Literature:
  • Slides Pure Nash Equilibria, pages 75-79.
  • Slides Learning and Correlated Equilibria, pages 1-18.
  • Littlestone, Warmuth. The Weighted Majority Algorithm. Inf. Comput. 108(2):212–261, 1994.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 4)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 17)



• Lecture 6 -- 22.10.2024:
  Stable matching, ordinal potential, correlated stable matching is an ordinal potential game; general stable matching has cyclic improvement sequences, Deferred-Acceptance algorithm, construction of short improvement sequences

  Literature:
  • Slides Pure Nash Equilibria, pages 43-74.
  • Abraham, Levavi, Manlove, O'Malley. The Stable Roommates Problem with Globally Ranked Pairs. Internet Math. 5(4):493-515, 2008.
  • Mathieu. Self-Stabilization in Preference-Based Systems. Peer-to-Peer Networking and Applications 1(2):104-121, 2008.
  • Roth, Vande Vate. Random Paths to Stability. Econometrica 58(6):1475-1480, 1990.
  • Ackermann, Goldberg, Mirrokni, Röglin, Vöcking. Uncoordinated Two-Sided Matching Markets. SIAM J. Comput. 40(1):92-106, 2011



• Lecture 5 -- 21.10.2024:
  Convergence time in general congestion games, complexity of computing pure Nash equilibria, max-flow algorithm for symmetric network games, PLS, PLS-reductions, MaxCut, PLS-completeness of computing pure Nash equilibria in general congestion games. Recent developments (finding mixed equilibria in congestion games is complete for PLS ∩ PPAD)

  Literature:
  • Slides Pure Nash Equilibria, pages 29-42.
  • Matroid games are discussed here.
  • Johnson, Papadimitriou, Yannakakis. How easy is local search? J. Computer & System Sciences 37(1):79-100, 1988.
  • Fabrikant, Papadimitriou, Talwar. The Complexity of Pure Nash Equilibra. STOC 2004.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapter 19)
  • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.
  • Fearnley, Goldberg, Hollender, Savani. The Complexity of Gradient Descent: CLS = PPAD ∩ PLS. J. ACM 70(1), 2022.
  • Babichenko, Rubinstein. Settling the Complexity of Nash Equilibrium in Congestion Games. STOC 2021.



• Lecture 4 -- 15.10.2024:
  Congestion games, Rosenthal's potential function, exact potential games, singleton congestion games, convergence time of improvement sequences in singleton congestion games.

  Literature:
  • Slides Pure Nash Equilibria, pages 1-28.
  • Monderer, Shapley. Potential Games. Games and Economic Behavior 14:1124-1143, 1996.
  • Ieong, McGrew, Nudelman, Shoham, Sun. Fast and Compact: A Simple Class of Congestion Games. AAAI 2005.



• Lecture 3 -- 14.10.2024:
  Recap complexity of Nash equilibrium. 2-player zero-sum games, optimal strategies, value of the game (Minimax Theorem), linear programs and strong duality, efficient computation of mixed Nash equilibria

  Literature:
  • Slides Strategic Games and Nash Equilibrium, pages 40-65.
  • Owen. Game Theory, 2001. (Chapter 1+2).
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 1.4)
  • von Neumann, Morgenstern. Theory of Games and Economic Behavior, 1944
  • More on linear optimization, duality, and algorithms:
    Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009. (Chapter 29)



• Lecture 2 -- 08.10.2024:
  Pareto-optimality. Existence of mixed Nash equilibria (Nash theorem), proof with Brouwer's fixed point theorem, complexity class PPAD, END-OF-LINE problem, Nash is in PPAD, triangle coloring, Sperner's Lemma.

  Literature:
  • Slides Strategic Games and Nash Equilibrium, pages 18-40.
  • Slides for Sperner's Lemma
  • Sperner's Lemma in German: Video from the 80s, general result on Wikipedia.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 2)
  • Nash. Non-cooperative Games. Annals of Math. 54:195-259, 1951.
  
  In the lecture we only sketched the proof how to find mixed Nash equilibria by solving an END-OF-LINE problem, thereby showing that the problem is in in PPAD. Finding mixed Nash equilibria has also been shown to be PPAD-complete. Hence, by finding an approximate Nash equilibrium we can also solve END-OF-LINE or arbitrary Brouwer fixed point problems in polynomial time. This holds even for Nash equilibria in games with 2 players.
  • Goldberg, Daskalakis, Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39(1):195-259, 2009.
  • Chen, Deng, Teng. Settling the Complexity of Computing Two-Player Nash Equilibria. J. ACM 56(3), 2009.



• Lecture 1 -- 07.10.2024:
  Basic concepts of game theory, strategic games, dominant strategies, dominant strategy equilibrium, best response strategy, pure Nash equilibrium, mixed strategy, mixed best response, mixed Nash equilibrium.

  The material is standard and can be found in every book on game theory.

  Literature:
  • Slides General Information and Strategic Games and Nash Equilibrium, pages 1-17.
  • Owen. Game Theory, 2001. (Chapter 1)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 1)