Abstract
A correlated equilibrium is a fundamental solution concept in game theory that enjoys many desirable mathematical and algorithmic properties: it can achieve more fair and higher payoffs than a Nash equilibrium and it can be efficiently computed for a vast class of games. However, it requires a trusted mediator to assist the players in sampling their moves, which is a major drawback in many practical applications.
A computational solution to this problem was proposed by Dodis, Halevi and Rabin [DHR00]. They extended the original game by adding a preamble stage, where the players communicate with each other and then they perform the original game. For this extended game, they show that the players can achieve payoffs at least as high as in any correlated equilibrium, provided that the players are computationally bounded and can communicate before the game.
The introduction of cryptography with computational security in game theory is of great interest both from a theoretical and more importantly from a practical point of view. However, the main game-theoretic question remained open: can we achieve any correlated equilibrium for 2-player games without a trusted mediator and also unconditionally?
In this paper, we provide a positive answer to this question. We show that if the players can communicate via a quantum channel before the game, then for 2-player games, payoffs at least as high as in any correlated equilibrium can be achieved, without a trusted mediator and unconditionally. This provides another example of a major advantage of quantum information processing: quantum communication enables players to achieve a real correlated equilibrium unconditionally, a task which is impossible in the classical world.
More precisely, we prove that for any correlated equilibrium p of a strategic game G, there exists an extended game (with a quantum communication initial stage) Q with an efficiently computable approximate Nash equilibrium σ, such that the expected payoff for both players in σ is at least as high as in p.
The main cryptographic tool used in the construction is the quantum weak coin flipping protocol of Mochon [Moc07].
Most of the work was done when the authors visited Centre of Quantum Technologies (CQT), Singapore in early January, 2011, under the support of CQT. I.K.’s research was also supported by French projects ANR-09-JCJC-0067-01, ANR-08-EMER-012 and the project QCS (grant 255961) of the E.U. S.Z.’s research was supported by China Basic Research Grant 2011CBA00300 (sub-project 2011CBA00301), Research Grants Council of Hong Kong (Project no. CUHK418710, CUHK419011), and benefited from research trips under the support of China Basic Research Grant 2007CB807900 (sub-project 2007CB807901).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 53–62 (2006)
Aumann, R.: Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics 1, 67–96 (1974)
Bárány, I.: Fair distribution protocols or how the players replace fortune. Mathematics of Operations Research 17, 327–340 (1992)
Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player nash equilibria. Journal of the ACM 56(3) (2009)
Chailloux, A., Kerenidis, I.: Optimal quantum strong coin flipping. In: The 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 527–533 (2009)
Daskalakis, C., Goldberg, P., Papadimitriou, C.: Computing a nash equilibrium is PPAD-complete. SIAM Journal on Computing 39(1), 195–259 (2009)
Dodis, Y., Halevi, S., Rabin, T.: A Cryptographic Solution to a Game Theoretic Problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112–130. Springer, Heidelberg (2000)
Feigenbaum, J., Shenker, S.: Distributed algorithmic mechanism design: recent results and future directions. In: Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 1–13 (2002)
Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 585–595 (2005)
Kitaev, A.: Quantum coin-flipping. Presentation at The 6th Workshop on Quantum Information Processing, QIP 2003 (2003)
Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely fair SFE and coalition-safe cheap talk. In: Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, pp. 1–10 (2004)
Lo, H.-K.: Insecurity of quantum secure computations. Physical Review A 56(2) (1997)
Mochon, C.: Quantum weak coin flipping with arbitrarily small bias. arXiv:0711.4114 (2007)
Nash, J.: Non-cooperative games. The Annals of Mathematics 54(2), 286–295 (1951)
Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. Journal of the ACM 55(3) (2008)
von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press (1944)
Vazirani, V., Nisan, N., Roughgarden, T., Tardos, É.: Algorithmic Game Theory. Cambridge University Press (2007)
Zhang, S.: Quantum strategic game theory. In: Proceedings of the 3rd Innovations in Theoretical Computer Science, pp. 39–59 (2012); earlier at arXiv:1012.5141 and QIP 2011
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kerenidis, I., Zhang, S. (2013). A Quantum Protocol for Sampling Correlated Equilibria Unconditionally and without a Mediator. In: Iwama, K., Kawano, Y., Murao, M. (eds) Theory of Quantum Computation, Communication, and Cryptography. TQC 2012. Lecture Notes in Computer Science, vol 7582. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35656-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-35656-8_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35655-1
Online ISBN: 978-3-642-35656-8
eBook Packages: Computer ScienceComputer Science (R0)