{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:06:44Z","timestamp":1742962004434,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_2","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"3-11","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic Game Theory: A Snapshot"],"prefix":"10.1007","author":[{"given":"Christos H.","family":"Papadimitriou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"Adler, I., Daskalakis, C., Papadimitriou, C.H.: Manuscript (2009)"},{"issue":"3","key":"2_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"K.J. Arrow","year":"1954","unstructured":"Arrow, K.J., Debreu, G.: Existence of equilibria for a competitive economy. Econometrica\u00a022(3), 265\u2013290 (1954)","journal-title":"Econometrica"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Hajiaghayi, M., Ligett, K., Roth, A.: Regret minimization and the price of total anarchy. In: STOC (2008)","DOI":"10.1145\/1374376.1374430"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Immorlica, N., Kalai, A.T., Mirrokni, V.S., Papadimitriou, C.H.: The myth of the folk theorem. In: STOC 2008, pp. 365\u2013372 (2008)","DOI":"10.1145\/1374376.1374429"},{"key":"2_CR5","volume-title":"Contributions to the Theory of Games","author":"G.W. Brown","year":"1950","unstructured":"Brown, G.W., von Neumann, J.: Solutions of games by differential equations. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games, Princeton University Press, Princeton (1950)"},{"key":"2_CR6","unstructured":"Buchfuhrer, D., Umans, C.: Limits on the social welfare of maximal-in-range auction mechanisms (manuscript, 2009)"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Dai, D., Du, Y., Teng, S.: Settling the complexity of Arrow-Debreu equilibria in markets with linearly separable utilities (manuscript, 2009)","DOI":"10.1109\/FOCS.2009.29"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: FOCS (2006)","DOI":"10.1109\/FOCS.2006.69"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Codenotti, B., Saberi, A., Varadarajan, K., Ye, Y.: Leontief economies encode nonzero sum two-player games. In: Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2006)","DOI":"10.1145\/1109557.1109629"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Cole, R., Fleischer, L.: Fast-converging tatonnement algorithms for one-time and ongoing market problems. In: Proceedings of the 40th annual ACM Symposium on Theory of Computing, STOC (2008)","DOI":"10.1145\/1374376.1374422"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Daskalakis, C.: The complexity of approximating a Nash equilibrium (submitted, 2009)","DOI":"10.1145\/1461928.1461951"},{"key":"2_CR12","unstructured":"Daskalakis, C., Frongillo, R., Pierrakos, G., Papadimitriou, C.H., Valiant, G.: In preparation (2009)"},{"key":"#cr-split#-2_CR13.1","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC 2006 (2006);","DOI":"10.1145\/1132516.1132527"},{"key":"#cr-split#-2_CR13.2","unstructured":"SIAM Journal on Computing, special issue for 2006 STOC (to appear)"},{"issue":"2","key":"2_CR14","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"58","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. CACM\u00a058(2), 89\u201397 (2009)","journal-title":"CACM"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS\u2019s for Nash equilibrium. In: STOC (2009)","DOI":"10.1145\/1536414.1536427"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On a network generalization of the minmax theorem. In: Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-02930-1_35"},{"key":"2_CR17","unstructured":"Fabrikant, A., Papadimitriou, C.H.: The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. In: SODA 2008, pp. 844\u2013853 (2008)"},{"key":"2_CR18","unstructured":"Friedmand, E.J., Shenker, S.J.: Learning and implementation on the Internet, Working paper (1997)"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1006\/game.1999.0738","volume":"29","author":"Y. Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior\u00a029, 79\u2013103 (1999)","journal-title":"Games and Economic Behavior"},{"key":"2_CR20","volume-title":"Contributions to the Theory of Games","author":"D. Gale","year":"1950","unstructured":"Gale, D., Kuhn, H.W., Tucker, A.W.: On symmetric games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games, Princeton University Press, Princeton (1950)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink Equilibria and Convergence. In: FOCS 2005, pp. 142\u2013154 (2005)","DOI":"10.1109\/SFCS.2005.68"},{"key":"2_CR22","volume-title":"A General Theory of Equilibrium Selection in Games","author":"J.C. Harsanyi","year":"1982","unstructured":"Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. MIT Press Classis, Cambridge (1982)"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Hart, S., Mansour, Y.: The communication complexity of uncoupled Nash equilibrium procedures. In: STOC 2007 (2007)","DOI":"10.1145\/1250790.1250843"},{"issue":"5","key":"2_CR24","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1111\/1468-0262.00153","volume":"68","author":"S. Hart","year":"2000","unstructured":"Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica\u00a068(5), 1127\u20131150 (2000)","journal-title":"Econometrica"},{"key":"2_CR25","unstructured":"Kannan, R., Theobald, T.: Games of fixed rank: A hierarchy of bimatrix games. In: SODA (2007)"},{"key":"2_CR26","unstructured":"Karlin, A.R., Kempe, D., Tamir, T.: Frugality of truthful mechanisms. In: FOCS (2005)"},{"key":"2_CR27","unstructured":"Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical Models for Game Theory. In: UAI (2001)"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Piliouras, G., Tardos, \u00c9.: Multiplicative updates outperform generic no-regret learning in congestion games. In: STOC (2009)","DOI":"10.1145\/1536414.1536487"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: SIGKDD (2003)","DOI":"10.1145\/956750.956769"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-49116-3_38","volume-title":"STACS 99","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999, vol.\u00a01563, pp. 404\u2013413. Springer, Heidelberg (1999)"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Lipton, R., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: ACM EC (2003)","DOI":"10.1145\/779928.779933"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Montanari, A., Saberi, A.: Convergence to Equilibrium in Local Interaction Games (2008)","DOI":"10.1109\/FOCS.2009.64"},{"key":"2_CR33","unstructured":"Mossel, E., Papadimitriou, C.H., Schapira, M., Singer, Y.: Combinatorial Auctions: VC v. VCG (submitted, 2009)"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative Games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic Mechanism Design. In: STOC (1999)","DOI":"10.1145\/301250.301287"},{"key":"2_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)"},{"key":"2_CR37","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Computing correlated equilibria in multiplayer games. In: STOC (2005)","DOI":"10.1145\/1060590.1060598"},{"key":"#cr-split#-2_CR38.1","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing equilibria in multi-player games. In: SODA 2005 (2005);","DOI":"10.1145\/1060590.1060598"},{"key":"#cr-split#-2_CR38.2","unstructured":"J.ACM (full version, 2008)"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Schapira, M., Singer, Y.: On the hardness of being truthful. In: FOCS (2008)","DOI":"10.1109\/FOCS.2008.54"},{"key":"2_CR40","unstructured":"Papadimitriou, C.H., Valiant, G.: Selfish routers and the price of anarchy (submitted, 2009)"},{"key":"2_CR41","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On complexity as bounded rationality (extended abstract). In: STOC 1994, pp. 726\u2013733 (1994)","DOI":"10.1145\/195058.195445"},{"key":"2_CR42","unstructured":"Papadimitriou, C.H., Yannakakis, M.: An impossibility theorem for price adjustment mechanisms (manuscript, 2009)"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Robinson, J.: An iterative method of solving a game. Annals of Mathematics (1951)","DOI":"10.2307\/1969530"},{"key":"2_CR44","unstructured":"Royal Swedish Academy of Sciences Mechanism Design Theory (2007), http:\/\/nobelprize.org\/nobelprizes\/economics\/laureates\/2007\/ecoadv07.pdf"},{"key":"2_CR45","volume-title":"Selfish Routing","author":"T. Roughgarden","year":"2002","unstructured":"Roughgarden, T.: Selfish Routing. MIT Press, Cambridge (2002)"},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? JACM (2002)","DOI":"10.1145\/506147.506153"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC (2009)","DOI":"10.1145\/1536414.1536485"},{"key":"2_CR48","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","volume":"100","author":"J. Neumann von","year":"1928","unstructured":"von Neumann, J.: Zur Theorie der Gesellschaftsspiele. Math. Annalen\u00a0100, 295\u2013320 (1928)","journal-title":"Math. Annalen"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:54:42Z","timestamp":1558407282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}