Diese Webseite ist archiviert, da die Arbeitsgruppe zur RWTH Aachen wechselte.

zurück zur Übersicht


Logbuch Algorithmische Spieltheorie - Sommer 2018


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

    Material und Literatur:
    • Folien Mechanismen ohne Geld, Seiten 37-54.
    • 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)

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

    Material und Literatur:
    • Folien Mechanismen ohne Geld, Seiten 22-36.
    • 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)

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

  • 28.06.2018:
    Ansteigende Auktionen, Substitutionsbewertung, Walras-Gleichgewicht, Spektrumsauktionen, Deferred-Allocation Regel

    Material und Literatur:
    • Folien Mechanismen als Spiele, Seiten 21-33.
    • Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Kapitel 11)
    • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 8)

  • 26.06.2018:
    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-20.
    • 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.

  • 21.06.2018:
    Wettbewerbsfaktor von Random-Threshold ist O(log k), Parallele-Sekretäre 2e-kompetitiv für Waldauktionen, Verteilungsmodell, Prophet Mechanismus 2-kompetitiv für Ein-Gut-Auktion, Erweiterung auf Ertragsmaximierung, Expected-Margin-Thresholds 2-kompetitiv für Matroidauktionen.

    Material und Literatur:
    • Folien Sekretäre und Propheten, Seiten 12-38.
    • Babaioff, Kleinberg, Immorlica. Matroids, Secretary Problems, and Online Mechanisms. SODA 2007.
    • Krengel, Sucheston. On Semiamarts, Amarts, and Processes with Finite Value. Adv. in Prob. Related Topics 4:197-266, 1978.
    • Kleinberg, Weinberg. Matroid Prophet Inequalities. STOC 2012.

  • 19.06.2018:
    Online Auktionen, Random-Order Modell, Sekretär-Mechanismus für die Ein-Gut Auktion anreizkompatibel und e-kompetitiv, Matroide, Matroidauktion, Random-Threshold-Mechanismus für die Matroidauktion anreizkompati­bel und O(log k)-kompetitiv.

    Material und Literatur:
    • Folien Sekretäre und Propheten, Seiten 1-20.
    • Freeman. The Secretary Problem and its Extensions: A Review. Intl. Stat. Rev. 51(2):189-206, 1983.
    • Babaioff, Kleinberg, Immorlica. Matroids, Secretary Problems, and Online Mechanisms. SODA 2007.
    • Hajiaghayi, Kleinberg, Parkes. Adaptive Limited-Supply Online Auctions. EC 2004.
    • 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.

  • 14.06.2018:
    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 76-95.
    • 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)

  • 12.06.2018:
    Approximationsalgorithmen und Mechanism Design, Rucksackauktion, Greedy-Algorithmus monoton und 2-approximativ, klassisches Approximationsschema ist nicht monoton, Anpassung des Schemas, volles Approximationsschema monoton und (1+ε)-approximativ, Revelationsprinzip

    • Folien Entwurf anreizkompatibler Mechanismen, Seiten 53-76.
    • Mu'Alem, Nisan. Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. Games and Economic Behavior 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. (Kapitel 9)
    • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 4)

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

    Material und Literatur:
    • Folien Entwurf anreizkompatibler Mechanismen, Seiten 23-52.
    • 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)

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

    Material und Literatur:

  • 24.05.2018:
    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, Preis der Stabilität, Fair-Sharing-Spiele, Preis der Anarchie und Stabilität in Fair-Sharing-Spielen.

    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)
    • 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.

  • 22.05.2018:
    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 43-60.
    • 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)

  • 17.05.2018:
    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 20-42.
    • 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)

  • 15.05.2018:
    Online Lernen, Experten-Problem, Greedy, Definition No-Regret Algorithmen, Randomized Weighted Majority mit Regretgarantie, Einsatz in Spielen und grob-korrelierte Gleichgewichte

    Material und Literatur:
    • Folien Online Lernen, Seiten 1-19.
    • 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)

  • 08.05.2017:
    Stabiles Matching, kreisende Verbesserungsfolgen, Deferred-Acceptance Algorithmus, schwache Kreisfreiheit, zufällige Verbesserungsfolgen, exponentielle Konvergenzzeit, Konvergenzverhalten von Blocking-Pair-Dynamiken für lokal stabiles Matching

    Material und Literatur:
    • Folien Reine Nash-Gleichgewichte, Seiten 75-88.
    • Folien Lokal stabiles Matching.
    • 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
    • Hoefer. Local Matching Dynamics in Social Networks. Inf. Comput. 222:20-35, 2013.
    • Hoefer, Wagner. Locally Stable Marriage with Strict Preferences. SIAM J. Disc. Math. 31(1):283-316, 2017.

  • 03.05.2018:
    PLS-Reduktionen, PLS-Vollständigkeit, Beispiele POS-NAE-kSAT und MaxCut, PLS-Vollständigkeit von reinen Nash-Gleichgewichten in allgemeinen Auslastungsspielen, Ordinale Potenzialspiele, stabiles Matching, Interpretation als Spiel, gewichtetes stabiles Matching, lexikografische Potenzialfunktion.

    • Folien Reine Nash-Gleichgewichte, Seiten 44-74.
    • 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)
    • 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.

  • 26.04.2018:
    Approximative Gleichgewichte, symmetrische Auslastungsspiele, α-sprungbeschränkte Latenzen, Konvergenzzeit der relativen ε-Nash-Dynamik, Komplexitätsklasse PLS für lokale Suchprobleme, PLS-Vollständigkeit

    Material und Literatur:
    • Folien Reine Nash-Gleichgewichte, Seiten 30-44.
    • Chien, Sinclair. Convergence to Approximate Nash Equilibria in Congestion Games. Games and Economic Behavior 71(2):315-327, 2011.
    • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.
    • Johnson, Papadimitriou, Yannakakis. How easy is local search? J. Computer & System Sciences 37(1):79-100, 1988.
    • Roughgarden. Twenty Lectures on Algorithmic Game Theory, 2016. (Kapitel 16 und 19)

  • 24.04.2018:
    Auslastungsspiele, exakte Potenzialfunktion, Potenzialspiele und Isomorphie, Konvergenzzeit von Verbesserungsfolgen, Singleton-Spiele.

    Material und Literatur:
    • Folien Reine Nash-Gleichgewichte, Seiten 1-29.
    • 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.
    • Ackermann, Röglin, Vöcking. On the Impact of Combinatorial Structure in Congestion Games. J. ACM 55(6), 2008.

  • 19.04.2018:
    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 44-60.
    • 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)

  • 17.04.2018:
    Beispiele für gemischte Nash-Gleichgewichte, Existenz von gemischten Nash-Gleichgewichten (Satz von Nash), Beweisidee mit Fixpunktsatz von Brouwer, Komplexitätsklasse PPAD, END-OF-LINE Problem, Spernersches Lemma, Nash ist in PPAD

    Material und Literatur:
    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.

  • 12.04.2018:
    Einführung in die Spieltheorie, dominante Strategien, Pareto-Optimum, 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:

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

    Aus technischen Gründen fand leider keine Videoaufzeichnung statt.

    Material und Literatur:
    • Folien Organisatorisches und 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.