1Computer Science Department, Columbia University
2Institute for Quantum Computing and School of Computer Science, University of Waterloo
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and exchange quantum information. In particular, we prove that the computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is, like the analogous problem for classical games, included in (and therefore complete for) the complexity class PPAD. Our main technical contribution, which facilitates this inclusion, is an extension of prior methods in computational game theory to strategy spaces that are characterized by semidefinite programs.
Featured image: A diagram of an interaction representing a multiple-turn quantum game.
► BibTeX data
► References
[1] David Meyer. “Quantum strategies”. Physical Review Letters 82, 1052–1055 (1999).
https://doi.org/10.1103/PhysRevLett.82.1052
[2] Jens Eisert, Martin Wilkens, and Maciej Lewenstein. “Quantum games and quantum strategies”. Physical Review Letters 83, 3077–3080 (1999).
https://doi.org/10.1103/PhysRevLett.83.3077
[3] John von Neumann and Oskar Morgenstern. “Theory of games and economic behavior”. Princeton University Press. (1953). third edition.
https://doi.org/10.1515/9781400829460
[4] John Nash. “Equilibrium points in n-person games”. Proceedings of the National Academy of Sciences 36, 48–49 (1950).
https://doi.org/10.1073/pnas.36.1.48
[5] John Nash. “Non-cooperative games”. PhD thesis. Princeton University. (1950).
[6] Hong Guo, Juheng Zhang, and Gary Koehler. “A survey of quantum games”. Decision Support Systems 46, 318–332 (2008).
https://doi.org/10.1016/j.dss.2008.07.001
[7] Steven van Enk and Rob Pike. “Classical rules in quantum games”. Physical Review A 66, 024306 (2002).
https://doi.org/10.1103/PhysRevA.66.024306
[8] Jinshan Wu. “A new mathematical representation of game theory I”. Unpublished manuscript, arXiv:quant-ph/0404159 (2004).
arXiv:quant-ph/0404159
[9] Jinshan Wu. “A new mathematical representation of game theory II”. Unpublished manuscript, arXiv:quant-ph/0405183 (2004).
arXiv:quant-ph/0405183
[10] Shengyu Zhang. “Quantum strategic game theory”. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Pages 39–59. (2012).
https://doi.org/10.1145/2090236.2090241
[11] Gus Gutoski and John Watrous. “Toward a general theory of quantum games”. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Pages 565–574. (2007).
https://doi.org/10.1145/1250790.1250873
[12] Giulio Chiribella, Giacomo D’Ariano, and Paolo Perinotti. “Quantum circuit architecture”. Physical Review Letters 101, 060401 (2008).
https://doi.org/10.1103/PhysRevLett.101.060401
[13] Giulio Chiribella, Giacomo D’Ariano, and Paolo Perinotti. “Theoretical framework for quantum networks”. Physical Review A 80, 022339 (2009).
https://doi.org/10.1103/PhysRevA.80.022339
[14] Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. “The complexity of computing a Nash equilibrium”. SIAM Journal on Computing 39, 195–259 (2009).
https://doi.org/10.1137/070699652
[15] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. “Settling the complexity of computing two-player Nash equilibria”. Journal of the ACM 56, 14 (2009).
https://doi.org/10.1145/1516512.1516516
[16] Christos Papadimitriou. “On the complexity of the parity argument and other inefficient proofs of existence”. Journal of Computer and system Sciences 48, 498–532 (1994).
https://doi.org/10.1016/S0022-0000(05)80063-7
[17] Kousha Etessami and Mihalis Yannakakis. “On the complexity of Nash equilibria and other fixed points”. SIAM Journal on Computing 39, 2531–2597 (2010).
https://doi.org/10.1137/080720826
[18] Kathleen Gibbons, Matthew Hoffman, and William Wootters. “Discrete phase space based on finite fields”. Physical Review A 70, 062101 (2004).
https://doi.org/10.1103/PhysRevA.70.062101
[19] David Gross. “Hudson’s theorem for finite-dimensional quantum systems”. Journal of Mathematical Physics 47, 122107 (2006).
https://doi.org/10.1063/1.2393152
[20] Sanjeev Arora and Boaz Barak. “Computational complexity: A modern approach”. Cambridge University Press. (2009).
https://doi.org/10.1017/CBO9780511804090
[21] Michael Nielsen and Isaac Chuang. “Quantum computation and quantum information”. Cambridge University Press. (2000).
https://doi.org/10.1017/CBO9780511976667
[22] Mark Wilde. “Quantum information theory”. Cambridge University Press. (2017). second edition.
https://doi.org/10.1017/9781316809976
[23] John Watrous. “Theory of quantum information”. Cambridge University Press. (2018).
https://doi.org/10.1017/9781316848142
[24] Glen Bredon. “Topology and geometry”. Volume 139 of Graduate Texts in Mathematics. Springer. (1993).
https://doi.org/10.1007/978-1-4757-6848-0
[25] Irving Glicksberg. “A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points”. Proceedings of the American Mathematical Society 3, 170–174 (1952).
https://doi.org/10.2307/2032478
[26] John Nash. “Non-cooperative games”. Annals of Mathematics, Second Series 54, 286–295 (1951).
https://doi.org/10.2307/1969529
[27] Martin Grötschel, Laszlo Lovász, and Alexander Schrijver. “Geometric algorithms and combinatorial optimization”. Springer–Verlag. (1988).
https://doi.org/10.1007/978-3-642-78240-4
[28] Carlton Lemke and Joseph Howson. “Equilibrium points of bimatrix games”. Journal of the Society for industrial and Applied Mathematics 12, 413–423 (1964).
https://doi.org/10.1137/0112033
Cited by
[1] Constantin Ickstadt, Thorsten Theobald, and Elias Tsigaridas, “Semidefinite games”, arXiv:2202.12035.
[2] Rafael Frongillo, “Quantum Information Elicitation”, arXiv:2203.07469.
[3] Rahul Jain, Georgios Piliouras, and Ryann Sim, “Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence”, arXiv:2211.01681.
The above citations are from SAO/NASA ADS (last updated successfully 2022-12-24 16:09:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2022-12-24 16:09:03).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
