A Cryptographic Solution to a Game Theoretic Problem
A Cryptographic Solution to a Game Theoretic Problem
复制标题
DOI：
10.1007/3-540-44598-6_7
复制
发表时间：
2000-08
期刊：
影响因子：
--
通讯作者：
Y. Dodis;S. Halevi;T. Rabin
中科院分区：
文献类型：
--
作者：
Y. Dodis;S. Halevi;T. Rabin
在这项工作中，我们使用密码学来解决一个博弈论问题，这自然会出现在双方战略博弈领域。这类博弈的标准博弈论解决方案概念是均衡，这是一对“自我执行”策略，使每个玩家的策略成为另一个玩家策略的最佳反应。众所周知，对于许多游戏来说，当一个可信的第三方（“调解人”）帮助玩家选择他们的行动（相关均衡）时，预期的均衡收益可能会比每个玩家必须自己选择行动（纳什均衡）时高得多。人们自然会问，是否存在一种机制，既不需要中介人，又允许参与者保持中介人辅助策略带来的高回报。我们回答这个问题的前提是玩家在计算上是有界的，并且在玩游戏之前可以自由交流（所谓的“廉价谈话”）。我们解决方案的主要构建块是以下相关元素选择问题的有效密码协议，这是独立的兴趣。Alice和Bob都知道一个对列表（a1，b1）. (an，bn）（可能有重复），他们想选择一个随机索引，使得Alice只学习ai，Bob只学习bi。我们对这个问题的解决方案具有恒定的轮数，可以忽略的错误概率，并且只使用非常简单的零知识证明。然后，我们将展示如何将我们的cryptographicprotocol回到游戏理论设置，其中突出了一些有趣的相似之处密码协议和广泛的形式游戏。
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 anequilibrium, 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 payo.s 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 payo.s o.ered by mediator-assisted strategies. We answer this question a.rmatively 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 e.cient cryptographic protocol to the followingCorrelated Element Selectionproblem, which is of independent interest. Both Alice and Bob know a list of pairs (a1,b1)... (an,bn) (possibly with repetitions), and they want to pick arandomindexisuch that Alice learns onlyaiand Bob learns onlybi. 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 ourcryptographicprotocol back into agame-theoreticsetting, which highlights some interesting parallels between cryptographic protocols and extensive form games.