Computer Science – Computer Science and Game Theory
Scientific paper
2011-04-10
Computer Science
Computer Science and Game Theory
13 pages
Scientific paper
A correlated equilibrium is a fundamental solution concept in game theory that enjoys many desirable properties. However, it requires a trusted mediator, which is a major drawback in many practical applications. A computational solution to this problem was proposed by Dodis, Halevi and Rabin. They extended the original game by adding an initial communication stage and showed that any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded. In this paper, we show that if the players can communicate via a quantum channel before the game, then any correlated equilibrium for 2-player games can be achieved, without a trusted mediator and unconditionally. This provides another example of a major advantage of quantum information processing. 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 q, such that the expected payoff for both players in q 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.
Kerenidis Iordanis
Zhang Shengyu
No associations
LandOfFree
A quantum protocol for sampling correlated equilibria unconditionally and without a mediator does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A quantum protocol for sampling correlated equilibria unconditionally and without a mediator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quantum protocol for sampling correlated equilibria unconditionally and without a mediator will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-316397