Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

zurück zur Übersicht

Logbuch Algorithmische Spieltheorie - Sommer 2017

• 18.07.2017:
  Fragestunde: Affine Maximierer, Matroide und Matroidspiele, grob-korrelierte Gleichgewichte, sozial-konkave Spiele

  
  

• 13.07.2017:
  Nierenaustausch, Maximum-Matching Mechanismus mit Prioritäten, Stabiles Matching, Deferred-Acceptance Algorithmus, männer- und frauenoptimale Matchings, Anreizkompatibilität (nur) für aktive Seite

  Aus unbekannten Gründen fand leider keine Videoaufzeichnung statt.

  Material und Literatur:
  • Folien Mechanismen ohne Geld, Seiten 36-55.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Kapitel 14.1 und 14.2)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 10)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016 (Kapitel 10)



• 11.07.2017:
  Präferenzen mit einem Scheitelpunkt, Ordnungs- und Median-Mechanismus, Charakterisierung anonymer anreizkompatibler Mechanismen; Hausallokation, Top-Trading-Cycles, Anreizkompatibilität und Kern des Spiels, Random-Serial-Dictatorship

  Material und Literatur:
  • Folien Mechanismen ohne Geld, Seiten 22-35.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Kapitel 14.3.2, 14.3.3)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 10)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016 (Kapitel 9)



• 06.07.2017:
  Wahlen, Mehrheitsregel für zwei Kandidiaten, Condorcet-Paradox, Pluralitätsregel, Anreizkompatibilität, Diktaturen, Satz von Arrow, Satz von Gibbard-Satterthwaite

  Material und Literatur:
  • Folien Mechanismen ohne Geld, Seiten 1-21.
  • Brandt, Conitzer, Endriss, Lang, Procaccia. Handbook of Computational Social Choice, 2016. (Kapitel 1.1, 1.2, 2.1, 2.2 und 2.8)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 9)



• 04.07.2017:
  Preis der Anarchie in der Zweitpreisauktion, Schwache Smoothness, Ansteigende Auktionen, Walras-Gleichgewicht, Spektrumsauktionen, Deferred-Allocation Regel

  Material und Literatur:
  • Folien Mechanismen als Spiele, Seiten 34-48.
  • Syrgkanis, Tardos. Composable and Efficient Mechanisms. STOC 2013
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 11)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 8)



• 29.06.2017:
  Preis der Anarchie in der Erstpreisauktion, Smoothness für Mechanismen, Preis der Anarchie für korrelierte Gleichgewichte, Kombinatorische Auktionen mit simultanen Gut-Geboten, Smoothness der Komposition von Mechanismen

  Material und Literatur:
  • Folien Mechanismen als Spiele, Seiten 18-33.
  • Syrgkanis, Tardos. Composable and Efficient Mechanisms. STOC 2013



• 27.06.2017:
  Sponsored Search Auktionen, Generalized-Second-Price (GSP), Mechanismen als Spiele, Existenz eines optimalen reinen Nash Gleichgewichts, Preis der Anarchie für reine und gemischte Nash-Gleichgewichte ohne Überbieten

  Material und Literatur:
  • Folien Mechanismen als Spiele, Seiten 1-17.
  • Edelman, Ostrovsky, Schwarz. Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords. Amer. Econ. Rev., 97(1):242-259, 2007.
  • Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, Lucier, Paes Leme, Tardos. Bounding the Inefficiency of Outcomes in Generalized Second Price Auctions. J. Econ. Theory 156:343-388, 2015.



• 20.06.2017:
  Kombinatorische Auktionen, Single-Minded Bewertungen, NP-Härte und Schwere der Approximation, Greedy-Mechanismus ist anreizkompatibel und liefert √m-Approximation

  Material und Literatur:
  • Folien Entwurf anreizkompatibler Mechanismen, Seiten 58-76.
  • Lehmann, O'Callaghan, Shoham. Truth revelation in approximately efficient combinatorial auctions. J. ACM 49(5):577-602, 2002.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 11)



• 13.06.2017:
  Optimale Mechanismen im Single-Parameter Bereich, virtuelle Werte, reguläre Verteilungen, Interpretation durch Reservationspreise, Vickrey vs. Optimale Auktion, Satz von Bulow-Klemperer

  Material und Literatur:
  • Folien Entwurf anreizkompatibler Mechanismen, Seiten 41-57.
  • Myerson. Optimal Auction Design. Math. Oper. Res. 6(1):58-83, 1981.
  • Bulow, Klemperer. Auctions versus Negotiations. Amer. Econ. Rev. 86(1):180-194, 1996.
  • Kirkegaard. A Short Proof of the Bulow-Klemperer Auctions vs. Negotiations Result. Econ. Theory 28(2):449-452, 2006.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 5 und 6)



• 08.06.2017:
  Affine Maximierer, Satz von Roberts, Single-Parameter Bereich, Monotonie, Myersons Lemma

  Material und Literatur:
  • Folien Entwurf anreizkompatibler Mechanismen, Seiten 23-40.
  • Myerson. Optimal Auction Design. Math. Oper. Res. 6(1):58-83, 1981.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 9)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 3)



• 06.06.2017:
  Vickrey Zweitpreisauktion, Anreizkompatibilität, VCG Mechanismen, Clarke-Regel, Beispiele

  Material und Literatur:
  • Folien Entwurf anreizkompatbiler Mechanismen, Seiten 1-21.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 9)



• 01.06.2017:
  Preis der Anarchie in linearen Auslastungsspielen, Definition (λ,μ)-smooth und Beweisschema, Preis der Anarchie für grob-korrelierte Gleichgewichte, dichte Spiele, Grenzen und Intuition des Schemas.

  Aus unbekannten Gründen fand leider keine Videoaufzeichnung statt.

  Material und Literatur:
  • Folien Preis der Anarchie.
  • 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. (Kapitel 14)



• 30.05.2017:
  No-Regret erzeugt grob-korrelierte Gleichgewichte, korrelierte Gleichgewichte, Swap-Regret, No-Swap-Regret erzeugt korrelierte Gleichgewichte, Black-Box-Entwurf von No-Swap-Regret Algorithmen.

  Material und Literatur:
  • Folien Online Lernen, Seiten 62-78.
  • Blum, Mansour. From External to Internal Regret. J. Machine Learning Research 8:1307-1324, 2007.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 4)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 18)



• 23.05.2017:
  Online Konvexe Optimierung, GIGA Algorithmus, Satz von Zinkevich, Sozial konkave Spiele, Bandbreitenspiel, Konvergenz zum Nash-Gleichgewicht.

  Material und Literatur:
  • Folien Online Lernen, Seiten 40-61.
  • Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003.
  • Rosen. Existence and Uniqueness of Equilibrium Points for Concave n-Person Games. Econometrica, 33(3):520–534, 1965.
  • Even-Dar, Nadav, Mansour. On the Convergence of Regret Minimization Dynamics in Concave Games. STOC 2009.



• 18.05.2017:
  Online Lernen in Nullsummenspielen, Beweis des Minimax-Theorems, Konvergenz im Durchschnitt und Konvergenz in den Zeitschritten, Adaptiver RWM Algorithmus mit Konvergenzgarantie

  Material und Literatur:
  • Folien Online Lernen, Seiten 21-39.
  • Freund, Schapire. Adaptive Game Playing using Multiplicative Weights. Games and Economic Behavior 29:79–103, 1999.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 4)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 17)



• 16.05.2017:
  Online Lernen, Experten-Problem, Greedy, Randomized Greedy, Definition No-Regret Algorithmen, Randomized Weighted Majority mit Regretgarantie

  Material und Literatur:
  • Folien Online Lernen, Seiten 1-20.
  • Littlestone, Warmuth. The Weighted Majority Algorithm. Inf. Comput. 108(2):212–261, 1994.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 4)
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 17)



• 09.05.2017:
  Global Connection und Cost Sharing als Auslastungsspiel mit fallenden Latenzen, Komplexität von reinen Nash-Gleichgewichten, PoA und PoS für das Global-Connection Spiel, reine Nash-Gleichgewichte und PoS im Local-Connection Spiel.

  Material und Literatur:
  • Folien Netzwerkverbindungsspiele mit Beispiel zur Beste-Antwort-Dynamik.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 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.
  • Fabrikant, Luthra, Maneva, Papadimitriou, Shenker. On a network creation game. PODC 2003.



• 04.05.2017:
  Verkehrsmodell von Wardrop, Wardrop-Gleichgewichte, Existenz und Eindeutigkeit von Wardrop-Gleichgewichten, Braess-Paradoxon, Preise der Anarchie und Stabilität, Preis der Anarchie für lineare Latenzfunktionen.

  Material und Literatur:
  • Folien Braess-Paradoxon und der Preis der Anarchie.
  • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 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 and Economic Behavior 64(2):457-469, 2008.



• 02.05.2017:
  Spannbäume, Matroide, Matroidspiele, Konvergenzzeit von Beste-Antwort-Dynamik.

  Material und Literatur:
  • Folien Auslastungs- und Potenzialspiele, Seiten 30-48.
  • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.
  • Hintergrund zu Matroiden:
    A. Schrijver. Combinatorial Optimization, Polyhedra and Efficiency. Volume B, 2003. (Kapitel 39)



• 27.04.2017:
  Auslastungsspiele, Potenzialfunktion, Potenzialspiele und Isomorphie, Konvergenzzeit von Beste-Antwort-Dynamiken, Singleton-Spiele.

  Material und Literatur:
  • Folien Auslastungs- und Potenzialspiele, Seiten 1-29.
  • Monderer, Shapley. Potential Games. Games and Economic Behavior 14:1124-1143, 1996.
  • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.



• 25.04.2017:
  Nullsummenspiele mit 2 Spielern, optimale Strategien, Wert des Spiels (Minimax-Theorem), lineare Programme und starke Dualität, effiziente Berechnung von Nash-Gleichgewichten

  Material und Literatur:
  • Folien Strategische Spiele und Nash-Gleichgewichte, Seiten 45-66.
  • Owen. Game Theory, 2001. (Kapitel 1+2).
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 1.4)
  • von Neumann, Morgenstern. Theory of Games and Economic Behavior, 1944
  • Hintergrund zu Linearer Optimierung, Dualität, und Algorithmen:
    Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009. (Kapitel 29)



• 20.04.2017:
  Pareto-Optimalität, Existenz von gemischten Nash-Gleichgewichten (Satz von Nash), Beweis mit Fixpunktsatz von Brouwer, Komplexitätsklasse PPAD, END-OF-LINE, Sperner's Lemma, Nash ist in PPAD

  Material und Literatur:
  • Folien Strategische Spiele und Nash-Gleichgewichte, Seiten 18-44.
  • Sperner's Lemma -- Video aus den 80ern, in allgemeiner Form bei Wikipedia.
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 2)
  • Nash. Non-cooperative Games. Annals of Math. 54:195-259, 1951.
  
  In der Vorlesung wurde nur skizziert, dass man ein (approximatives) Nash-Gleichgewicht durch Lösen von bestimmten END-OF-LINE Instanzen finden kann, also Nash in PPAD ist. Es ist aber sogar PPAD-vollständig für Spiele mit nur 2 Spielern und damit so schwer wie das Finden von allgemeinen Fixpunkten (oder das Lösen von allgemeinen END-OF-LINE Instanzen):
  • 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.



• 18.04.2017:
  Organisatorisches, Einführung in die Spieltheorie, dominante Strategien, reines Nash-Gleichgewicht, gemischtes Nash-Gleichgewicht, Beispiele.

  Die vorgestellten Grundlagen der Spieltheorie finden sich in einer Vielzahl von Büchern und Skripten.

  Material und Literatur:
  • Folien Organisation und Strategische Spiele und Nash-Gleichgewichte, Seiten 1-17.
  • Owen. Game Theory, 2001. (Kapitel 1)
  • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 1)