Apply crytography to achieve optimality in a game-theoretic problem

Abstract

We aim to use cryptography to solve a game-theoretic problem which is prevalent in the area of two party strategic games. The standard game-theoretic solutions concept for such games is that of a Nash equilibrium: a pair of “self-enforcing” strategies which makes each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payoffs can be much higher when a trusted third party i.e. a “mediator” assists in choosing their moves (correlated equilibria), than when each play has to choose its move on its own (Nash Equilibria). It is natural to ask whether there exists a mechanism (cryptographic protocol) that eliminates the need for the mediator yet allows the players to maintain the high payoffs offered by mediator-assisted strategies. We answer this question by extending the original game by adding an initial step in which the two players communicate, and then proceed to execute the game as usual. By incorporating our cryptographic protocol into a game-theoretic setting, we hope to highlight some interesting parallels between cryptographic protocols and two-party games. An interesting aspect of our work is the synergy achieved between cryptographic algorithms and game-theoretic problems: By implementing the cryptographic protocol in the game theoretic problem, we gain in the game theory front by eliminating the need for the mediator; we also gain on the cryptography front: for instance, we eliminate the problem of early stopping.