Nonlocality and Conflicting Interest Games
Authors: Anna Pappa1,2, Niraj Kumar1,3, Thomas Lawson1, Miklos Santha2,4, Shengyu Zhang5, Eleni Diamanti1, Iordanis Kerenidis2,4
1LTCI, CNRS–Télécom ParisTech, Paris, France,
2LIAFA, CNRS–Université Paris 7, France,
3Indian Institute of Technology, Kanpur, India,
4CQT, National University of Singapore, Singapore,
5Department of Computer Science and Engineering and ITCSC, The Chinese University of Hong Kong, Shatin, Hong Kong.
Nonlocality is a fundamental property of quantum mechanics that has puzzled researchers since the early formulations of quantum theory. Consider two parties, Alice and Bob, with inputs xA and xB respectively, who are positioned far from each other, and are asked to produce one output each (yA for Alice and yB for Bob). Even if the two players have pre-agreed on some local hidden variables, there exist quantum correlations that cannot be reproduced by any such set of variables [1,2]. These correlations allow the two parties to perform several computational tasks more efficiently, e.g. they can win specific games with probabilities strictly higher than allowed by any classical theory.
Till now, all known examples of quantum games considered players that have common interests, meaning that they either jointly win or lose the game. A famous such example is the CHSH game [3; CHSH stands for first letters of last names of the authors of this paper], where the players win if their outputs are different when both input bits are equal to 1, and if they are the same otherwise. It can be shown that classical resources provide a winning probability of 0.75, while the sharing of a maximally entangled pair can boost the winning probability to approximately 0.85. Another important type of games is conflicting interest games. A typical example is the “Battle of the Sexes”, where Alice and Bob want to meet, but Alice wants to go to the ballet, while Bob prefers theater. In case both go to the ballet, Alice is very pleased and Bob is fine with it; if they go to the theater, Bob is very pleased and Alice is fine with it, while if they go to different places, they are both very unhappy.
In our recent work , we examine whether the nonlocal feature of quantum mechanics can offer an advantage similar to the one observed in the CHSH game, but for games with conflicting interests. In order to observe a quantum advantage, we will study games with incomplete information (or Bayesian games), where each party receives some input unknown to the other party . We present a Bayesian game with conflicting interests, and we show that there exist quantum strategies with average payoff for the two players strictly higher than that allowed by any classical strategy. The payoffs of the players for different inputs can be viewed as a table: the rows correspond to the outputs/actions of Alice (yA), while the columns to the outputs/actions of Bob (yB).
Finally, we have demonstrated our game in practice, using the commercial entangled photon source quED by QuTools and taking a large number of independent runs of the game, in order to estimate each player’s average payoff. We found that the joint payoff is 1.246, which is well above the classical bound of 1.125, and slightly below the maximum value allowed by quantum strategies (1.28), because of experimental noise.
In conclusion, we demonstrated that the nonlocal feature of quantum mechanics can offer an advantage in a scenario where the two parties have conflicting interests. We examined a Bayesian game that attains higher payoffs for both players when using quantum advice compared to any classical strategy, and we experimentally verified the quantum advantage, by playing the game using a commercial photon source.
 John Bell, "On the Einstein Podolsky Rosen paradox". Physics, 1, 195-200 (1964). Full Article.
 Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, Stephanie Wehner, “Bell nonlocality”, Review of Modern Physics, 86, 419 (2014). Abstract.
 John F. Clauser, Michael A. Horne, Abner Shimony, Richard A. Holt, “Proposed Experiment to Test Local Hidden-Variable Theories”. Physical Review Letters, 23, 880–884 (1969). Abstract.
 Anna Pappa, Niraj Kumar, Thomas Lawson, Miklos Santha, Shengyu Zhang, Eleni Diamanti, Iordanis Kerenidis, "Nonlocality and Conflicting Interest Games", Physical Review Letters, 114, 020401 (2015). Abstract.
 J. C. Harsanyi, Management Science, 14 (3), 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III) (1967/1968).
 Richard Cleve, Peter Høyer, Ben Toner, John Watrous, "Consequences and limits of nonlocal strategies", Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 236–249 (2004). Full Article.