Yevgeniy Dodis,
Shaih Halevi and
Tal Rabin.

CRYPTO'00

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.

[ postscript ] [ back to Yevgeniy Dodis' research interests ]