A quantum protocol for sampling correlated equilibria unconditionally and without a mediator

Computer Science – Computer Science and Game Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-316397

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.