Algorithms & Complexity

Group

Research

Teaching

Theses

back to main page

Logbook Algorithmic Game Theory - Winter 2019/20

• 13.02.2020:
  Research trends in algorithmic game theory

  
  

• 11.02.2020:
  Games in financial networks, edge- and coin-ranking strategies, calculating clearing states, strong PoS=1 for coin-ranking, PoA unbounded.

  Literature:
  • Notes Credit Networks.
  • Slides Credit Networks (slides).
  • Bertschinger, Hoefer, Schmand. Strategic Payments in Financial Networks. ITCS 2020.



• 06.02.2020:
  Distribution model, Prophet mechanism 2-competitive for single-item auctions, extension to revenue maximization, Expected-Margin-Thresholds mechanism 2-competitive for matroid auctions

  Literature:
  • Slides Secretaries and Prophets, pages 47-62.
  • Krengel, Sucheston. On Semiamarts, Amarts, and Processes with Finite Value. Adv. in Prob. Related Topics 4:197-266, 1978.
  • Kleinberg, Weinberg. Matroid Prophet Inequalities and Applications to Multi-Dimensional Mechanism Design. Games Econom. Behav. 113:97-105, 2019.



• 04.02.2020:
  Matroid auction, graphic matroids, Random-Threshold mechanism for matroid auctions is incentive compatible and O(log k)-competitive, Parallel-Secretaries mechanism is incentive compatible and 2e-competitive for graphic matroids

  Literature:
  • Slides Secretaries and Prophets, pages 34-46.
  • Babaioff, Kleinberg, Immorlica. Matroids, Secretary Problems, and Online Mechanisms. SODA 2007.
  • Korula, Pal. Algorithms for Secretary Problems on Graphs and Hypergraphs. ICALP 2009.
  • Lachish. O(log log rank)-Competitive Algorithm for the Matroid Secretary Problem. FOCS 2014.
  • Feldman, Svensson, Zenklusen. A Simple O(log log rank)-Competitive Algorithm for the Matroid Secretary Problem. Math. Oper. Res. 43(2):638-650, 2018.



• 30.01.2020:
  Online-VCG mechanism is incentive compatible and e-competitive. Matroid auction, graphic matroids, Random-Threshold mechanism for matroid auctions is incentive compatible and O(log k)-competitive.

  Literature:
  • Slides Secretaries and Prophets, pages 25-36.
  • Reiffenhäusser. An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. SODA 2019.
  • Babaioff, Kleinberg, Immorlica. Matroids, Secretary Problems, and Online Mechanisms. SODA 2007.



• 28.01.2020:
  Online auctions, random-order model, Secretary mechanism for single-item auctions is incentive compatible and e-competitive, multi-item auctions with unit-demand bidders, Online-VCG mechanism is incentive compatible and e-competitive.

  Literature:
  • Slides Secretaries and Prophets, pages 1-25.
  • Freeman. The Secretary Problem and its Extensions: A Review. Intl. Stat. Rev. 51(2):189-206, 1983.
  • Hajiaghayi, Kleinberg, Parkes. Adaptive Limited-Supply Online Auctions. EC 2004.
  • Reiffenhäusser. An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. SODA 2019.



• 23.01.2020:
  Random serial dictatorship, kidney exchange, stable matching, incentive compatibility of Deferred-Acceptence for the active side

  Material und Literatur:
  • Slides Social Choice, pages 36-54.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Chapters 14.1 and 14.2)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 10)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016 (Chapter 10)



• 21.01.2020:
  House allocation, Top-Trading-Cycles, incentive compatibility and core

  Literature:
  • Slides Social Choice, pages 28-35.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Chapters 14.3.2, 14.3.3)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 10)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016 (Chapter 9.4)



• 16.01.2020:
  Four different social choice functions and their properties, Gibbard-Satterthwaite theorem, single-peaked preferences, and k-th order mechanisms

  Literature:
  • Slides Social Choice, pages 14-27.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Chapter 2.8)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)



• 14.01.2020:
  Voting, majority rule for 2 candidates, Condorcet paradox, plurality rule, incentive compatibility, dictatorships, Arrow theorem

  Literature:
  • Slides Social Choice, pages 1-13.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Chapters 1.2, 2.1, 2.2)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 9)



• 17.12.2019:
  Optimal mechanisms for single-parameter domains, virtual values, regular distributions, interpretation with reservation prices, Vickrey vs. optimal auctions, Bulow-Klemperer theorem

  Literature:
  • Slides Designing Incentive-Compatible Mechanisms, pages 76-94.
  • Myerson. Optimal Auction Design. Math. Oper. Res. 6(1):58-83, 1981.
  • Bulow, Klemperer. Auctions versus Negotiations. Amer. Econom. Rev. 86(1):180-194, 1996.
  • Kirkegaard. A Short Proof of the Bulow-Klemperer Auctions vs. Negotiations Result. Econom. Theory 28(2):449-452, 2006.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Chapters 5 and 6)



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

  • Slides Designing Incentive-Compatible Mechanisms, pages 52-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)



• 10.12.2019:
  Affine maximizers, Roberts Theorem, single-parameter domain, monotonicity, Myersons Lemma

  Literature:
  • Slides Designing Incentive-Compatible Mechanisms, pages 21-51.
  • 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)



• 05.12.2019:
  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)



• 28.11.2019:
  Temporal congestion games and their variants: unweighted and weighted players, FIFO and non-preemptive global ranking. Existence and complexity of computing Nash equilibria.

  Literature:
  • Notes Temporal Congestion Games
  • Hoefer, Mirrokni, Röglin, Teng. Competitive Routing over Time. Theor. Comput. Sci. 412(39):5420–5432, 2011.



• 26.11.2019:
  Price of stability, cost sharing games with equal sharing, price of anarchy and stability of equal-sharing games. Competitive routing over time

  Literature:
  • Slides Prices of Anarchy and Stability, pages 45-50.
  • Notes Temporal Congestion Games
  • 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.
  • Hoefer, Mirrokni, Röglin, Teng. Competitive Routing over Time. Theor. Comput. Sci. 412(39):5420–5432, 2011.



• 21.11.2019:
  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

  Literature:
  • Slides Prices of Anarchy and Stability, pages 21-44.
  • 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)



• 19.11.2019:
  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.



• 14.11.2019:
  Broadcast game, concave games, online convex optimization, GIGA algorithm, GIGA is no-regret algorithm, socially concave games, no-regret behavior converges to mixed Nash equilibrium in socially concave games.

  Literature:
  • Slides Learning and Correlated Equilibria, pages 43-69.
  • Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003.
  • Even-Dar, Mansour, Nadav. On the Convergence of Regret Minimization Dynamics in Concave Games. STOC 2009.
  • Rosen. Existence and Uniqueness of Equilibrium Points for Concave n-Person Games. Econometrica 33(3):520-534, 1965.



• 12.11.2019:
  No-regret learning in 2-player zero-sum games, proof of Minimax Theorem, convergence on average in hindsight and pointwise convergence of the actual strategies, adaptive RWM algorithm with convergence time

  Literature:
  • Slides Learning and Correlated Equilibria, pages 20-42.
  • Freund, Schapire. Adaptive Game Playing using Multiplicative Weights. Games Econom. 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)



• 07.11.2019:
  Expert problem, Greedy is bad, definition no-regret algorithm, Randomized Weighted Majority with regret guarantee, application in games leads to coarse-correlated equilibra

  Literature:
  • Slides Learning and Correlated Equilibria, pages 1-19.
  • 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)



• 05.11.2019:
  Stable matching, ordinal potential, correlated stable matching is ordinal potential game; general stable matching has cyclic improvement sequences, Deferred-Acceptance algorithm, weak acyclicity, randomized better-response dynamics

  Literature:
  • Slides Pure Nash Equilibria, pages 50-86.
  • 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



• 31.10.2019:
  PLS, PLS-reductions, MaxCut, PLS-completeness of computing pure Nash equilibria in congestion games, weighted congestion games, potential function for affine delay functions

  Literature:
  • Slides Pure Nash Equilibria, pages 32-49.
  • Notes Weighted Congestion Games.
  • 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. (Kapitel 19)
  • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.
  • Goemans, Mirrokni, Vetta. Sink Equilibria and Convergence. FOCS 2005.
  • Fotakis, Kontogiannis, Spirakis. Selfish Unsplittable Flows. Theor. Comput. Sci. 348(2-3):226–239, 2005.
  • Harks, Klimm. On the Existence of Pure Nash Equilibira in Weighted Congestion Games. Math. Oper. Res. 37(3):419-436, 2012.



• 29.10.2019:
  Singleton congestion games, convergence time of improvement sequences in singleton congestion games, approximative Nash equilibria, symmetric congestion games, α-bounded jump, convergence time of the relative ε-dynamics

  Literature:
  • Slides Pure Nash Equilibria, pages 20-31.
  • Ieong, McGrew, Nudelman, Shoham, Sun. Fast and Compact: A Simple Class of Congestion Games. AAAI 2005.
  • Chien, Sinclair. Convergence to Approximate Nash Equilibria in Congestion Games. Games Econom. Behav. 71(2):315-327, 2011.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 16)



• 24.10.2019:
  Congestion games, Rosenthal's potential function, exact potential games.

  Literature:
  • Slides Pure Nash Equilibria, pages 1-19.
  • Monderer, Shapley. Potential Games. Games and Economic Behavior 14:1124-1143, 1996.



• 22.10.2019:
  PPAD, END-OF-LINE problem, Nash is in PPAD, triangle coloring, Sperner's Lemma. 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 28-61.
  • Slides for Sperner's Lemma
  • Sperner's Lemma in German: Video from the 80s, general result on Wikipedia.
  • 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)



• 17.10.2019:
  Example games and mixed Nash equilibria, 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

  Literature:
  • Slides Strategic Games and Nash Equilibrium, pages 18-43.
  • 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.



• 15.10.2019:
  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 virtually 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)