## Abstract

In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing” strategies making 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 (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism 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 affirmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game. The main building block of our solution is an efficient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. 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}. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games.

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology - CRYPTO 2000 - 20th Annual International Cryptology Conference, Proceedings |

Editors | Mihir Bellare |

Publisher | Springer Verlag |

Pages | 112-130 |

Number of pages | 19 |

ISBN (Print) | 9783540445982 |

DOIs | |

State | Published - 2000 |

Event | 20th Annual International Cryptology Conference, CRYPTO 2000 - Santa Barbara, United States Duration: Aug 20 2000 → Aug 24 2000 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1880 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 20th Annual International Cryptology Conference, CRYPTO 2000 |
---|---|

Country/Territory | United States |

City | Santa Barbara |

Period | 8/20/00 → 8/24/00 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science