{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:21:41Z","timestamp":1725895301757},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642339950"},{"type":"electronic","value":"9783642339967"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33996-7_17","type":"book-chapter","created":{"date-parts":[[2012,10,6]],"date-time":"2012-10-06T07:27:01Z","timestamp":1349508421000},"page":"192-203","source":"Crossref","is-referenced-by-count":1,"title":["On the Communication Complexity of Approximate Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnoud","family":"Pastink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-77105-0_6","volume-title":"Internet and Network Economics","author":"H. Bosse","year":"2007","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New Algorithms for Approximate Nash Equilibria in Bimatrix Games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 17\u201329. Springer, Heidelberg (2007)"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Procs. of the 47th FOCS Symposium, pp. 261\u2013272. IEEE (2006)","DOI":"10.1109\/FOCS.2006.69"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X. Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56, 14:1\u201314:57 (2009)","journal-title":"J. ACM"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Sandholm, T.: Communication complexity as a lower bound for learning in games. In: Proceedings of the 21st ICML, pp. 24\u201332 (2004)","DOI":"10.1145\/1015330.1015351"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton Univ. Press (1963)","DOI":"10.7249\/R366"},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput.\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/11944874_27","volume-title":"Internet and Network Economics","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: A Note on Approximate Nash Equilibria. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 297\u2013306. Springer, Heidelberg (2006)"},{"key":"17_CR8","first-page":"283","volume":"7","author":"P.W. Goldberg","year":"2006","unstructured":"Goldberg, P.W.: Some discriminant-based PAC algorithms. Journal of Machine Learning Research\u00a07, 283\u2013306 (2006)","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"17_CR9","first-page":"107","volume":"69","author":"S. Hart","year":"2010","unstructured":"Hart, S., Mansour, Y.: How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. GEB\u00a069(1), 107\u2013126 (2010)","journal-title":"GEB"},{"issue":"301","key":"17_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association\u00a058(301), 13\u201330 (1963)","journal-title":"Journal of the American Statistical Association"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: 16th STOC, pp. 302\u2013311. ACM (1984)","DOI":"10.1145\/800057.808695"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0065-2458(08)60342-3","volume":"44","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: Communication complexity. Advances in Computers\u00a044, 331\u2013360 (1997)","journal-title":"Advances in Computers"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Procs. of the 4th ACM-EC, EC 2003, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"issue":"2","key":"17_CR14","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math.\u00a054(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"17_CR15","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. Mathematische Annalen\u00a0100, 295\u2013320 (1928)","journal-title":"Mathematische Annalen"},{"key":"17_CR16","unstructured":"Pastink, A.: Aspects of communication complexity for approximating Nash equilibria. MSc dissertation, Utrecht University (2012)"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-540-77105-0_8","volume-title":"Internet and Network Economics","author":"H. Tsaknakis","year":"2007","unstructured":"Tsaknakis, H., Spirakis, P.G.: An Optimization Approach for Approximate Nash Equilibria. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 42\u201356. Springer, Heidelberg (2007)"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing (preliminary report). In: 11th STOC, pp. 209\u2013213. ACM (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33996-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T04:09:38Z","timestamp":1557288578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33996-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642339950","9783642339967"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33996-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}