{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:09:43Z","timestamp":1725491383334},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540752530"},{"type":"electronic","value":"9783540752547"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-75254-7_11","type":"book-chapter","created":{"date-parts":[[2007,9,12]],"date-time":"2007-09-12T07:10:25Z","timestamp":1189581025000},"page":"103-112","source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Verifying Game Equilibria"],"prefix":"10.1007","author":[{"given":"Emmanuel M.","family":"Tadjouddine","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/11559221_74","volume-title":"Multi-Agent Systems and Applications IV","author":"J. Deguet","year":"2005","unstructured":"Deguet, J., Demazeau, Y.: A complexity based feature to support emergence in MAS. In: P\u011bchou\u010dek, M., Petta, P., Varga, L.Z. (eds.) CEEMAS 2005. LNCS (LNAI), vol.\u00a03690, pp. 616\u2013619. Springer, Heidelberg (2005)"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48224-5_1","volume-title":"Automata, Languages and Programming","author":"C.H. Papadimitriou","year":"2001","unstructured":"Papadimitriou, C.H.: Game theory, algorithms, and the internet. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 1\u20133. Springer, Heidelberg (2001), http:\/\/www.cs.berkeley.edu\/~christos\/"},{"key":"11_CR3","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":"11_CR4","doi-asserted-by":"crossref","unstructured":"Daskalakis, K., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. Electronic Colloquium on Computational Complexity (ECCC)\u00a0115 (2005)","DOI":"10.1145\/1132516.1132527"},{"key":"11_CR5","unstructured":"Daskalakis, K., Papadimitriou, C.H.: Three-player games are hard. Electronic Colloquium on Computational Complexity (ECCC) 139 (2005)"},{"key":"11_CR6","unstructured":"Chen, X., Deng, X.: 3-NASH is PPAD-complete. Electronic Colloquium on Computational Complexity (ECCC) 134 (2005)"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player nash equilibrium. In: FOCS, pp. 261\u2013272 (2006)","DOI":"10.1109\/FOCS.2006.69"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci.\u00a048, 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1109\/IAT.2006.106","volume-title":"Proceedings of the 2006 IEEE\/WIC\/ACM International Conference on Intelligent Agent Technology","author":"F. Guerin","year":"2006","unstructured":"Guerin, F., Tadjouddine, E.M.: Realising common knowledge assumptions in agent auctions. In: Proceedings of the 2006 IEEE\/WIC\/ACM International Conference on Intelligent Agent Technology, Hong Kong, China, pp. 579\u2013586. ACM Press, New York (2006)"},{"key":"11_CR10","unstructured":"Vorobeychik, Y., Reeves, D.M., Wellman, M.P.: Automated mechanism design in infinite games of incomplete information: Framework and applications (2007), http:\/\/www.cscs.umich.edu\/events\/decentralization07\/Infinite%20Games%20of%Incomplete%20Information.pdf"},{"key":"11_CR11","unstructured":"Tadjouddine, E.M., Guerin, F.: Verifying dominant strategy equilibria in combinatorial auctions. In: CSD Report No AUCS\/TR0704, University of Aberdeen, Computing Sciences Department, Aberdeen, AB24 3UE, Scotland (2007), http:\/\/www.csd.abdn.ac.uk\/~fguerin\/DSE2007April.pdf"},{"key":"11_CR12","unstructured":"Van der Hoek, W.: Knowledge, rationality and action. In: AAMAS 2004. Proceedings of the AAMAS 2004, New York, USA (2004)"},{"key":"11_CR13","volume-title":"A Primer in Game Theory","author":"R. Gibbons","year":"1992","unstructured":"Gibbons, R.: A Primer in Game Theory. Prentice-Hall, Englewood Cliffs (1992)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1093\/logcom\/exi014","volume":"15","author":"M. Pauly","year":"2005","unstructured":"Pauly, M.: Programming and verifying subgame perfect mechanisms. Journal of Logic and Computation\u00a015, 295\u2013316 (2005)","journal-title":"Journal of Logic and Computation"},{"key":"11_CR15","unstructured":"Guerin, F.: An algorithmic approach to specifying and verifying subgame perfect equilibria. In: GTDT-2006. Proceedings of the Eighth Workshop on Game Theoretic and Decision Theoretic Agents, Hakodate, Japan. AAMAS 2006 (2006)"},{"key":"11_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4222-2","volume-title":"Temporal Verification of Reactive Systems (Safety)","author":"Z. Manna","year":"1995","unstructured":"Manna, Z., Pnueli, A.: Temporal Verification of Reactive Systems (Safety), vol.\u00a02. Springer, Heidelberg (1995)"},{"key":"11_CR17","unstructured":"Tadjouddine, E.M., Guerin, F.: Verifying equilibria in games of complete and perfect information represented by presburger formulas. In: Proceedings of the 2006 LOFT Conference, Liverpool, UK, pp. 219\u2013226 (2006)"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Jackson, D.: Automating first-order relational logic. In: SIGSOFT FSE, pp. 130\u2013139 (2000)","DOI":"10.1145\/357474.355063"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1145\/505145.505149","volume":"11","author":"D. Jackson","year":"2002","unstructured":"Jackson, D.: Alloy: A lightweight object modelling notation. ACM Trans. Softw. Eng. Methodol.\u00a011, 256\u2013290 (2002), http:\/\/alloy.mit.edu","journal-title":"ACM Trans. Softw. Eng. Methodol."},{"key":"11_CR20","first-page":"269","volume":"44","author":"D.C. Parkes","year":"2004","unstructured":"Parkes, D.C.: Auction design with costly preference elicitation. Annals of Mathematics and AI\u00a044, 269\u2013302 (2004)","journal-title":"Annals of Mathematics and AI"},{"key":"11_CR21","first-page":"253","volume-title":"UAI 2001","author":"M.J. Kearns","year":"2001","unstructured":"Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory. In: UAI 2001. Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pp. 253\u2013260. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2001)"},{"key":"11_CR22","unstructured":"Gottlob, G., Greco, G., Mancini, T.: Complexity of pure equilibria in bayesian games. In: Veloso, M.M. (ed.) IJCAI, pp. 1294\u20131299 (2007)"},{"key":"11_CR23","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.\u00a0H. Freeman And Company, New York (1979)"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1145\/352871.352898","volume-title":"ACM Conference on Electronic Commerce","author":"N. Nisan","year":"2000","unstructured":"Nisan, N., Ronen, A.: Computationally feasible VCG mechanisms. In: ACM Conference on Electronic Commerce, pp. 242\u2013252. ACM Press, New York (2000)"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.dss.2004.08.009","volume":"39","author":"A. Kothari","year":"2005","unstructured":"Kothari, A., Parkes, D.C., Suri, S.: Approximately-strategyproof and tractable multi-unit auctions. Decision Support Systems\u00a039, 105\u2013121 (2005) (Special issue dedicated to the Fourth ACM Conference on Electronic Commerce)","journal-title":"Decision Support Systems"}],"container-title":["Lecture Notes in Computer Science","Multi-Agent Systems and Applications V"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75254-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T03:51:30Z","timestamp":1684036290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75254-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540752530","9783540752547"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75254-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}