Abstract

Although Game Theory and Cryptography seem to have some similar scenarios in common, it is very rare to find instances where tools from one area are applied in the other. In this work we use cryptography to solve a game theoretic problem. The problem that we discuss arises naturally in the game theory area of two-party strategic games. In these games there are two players. Each player decides on a ``move'' (according to some strategy), and then the players execute the game, i.e. the two players make their moves simultaneously. Once these moves are played each player receives a payoff, which depends on both moves. Each player only cares to maximize its payoff.

In the game theory literature it was shown that higher payoffs can be achieved by the players if they use correlated strategies. This is enabled through the introduction of a trusted third party (a ``mediator''), who assists the players in choosing their move. Though now the property of the game being a two player game is lost. It is natural to ask whether a game can exist which would be a two player game yet maintain the high payoffs which the mediator aided strategy offered.

We answer this question affirmatively. We extend the game by adding an initial step in which the two players communicate and then they proceed to execute the game as usual. For this extended game we can prove (informally speaking) the following: any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded and can communicate before playing the game.

We obtain an efficient solution to the above game-theoretic problem, by providing a cryptographic protocol to the following Correlated Element Selection problem. Both Alice and Bob know a list of pairs (a_1,b_1)...(a_n,b_n) (possibly with repetitions), and they want to pick a random index i such that Alice learns only a_i and Bob learns only b_i. We believe that this problem has other applications, beyond our application to game theory. Our solution is quite efficient: it has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs.