Author
Mikhail Atallah, Marina Blanton, Keith Frikken, and Jiangtao Li
Abstract
Participants in e-commerce and other forms of online collaborations tend to be selfish and rational, and therefore game theory has been recognized as particularly relevant to this area, especially when combined with notions from computational complexity and cryptography. In many common games, the joint strategy of the players is described by a list of pairs of actions, and one of those pairs is chosen according to a specified correlated probability distribution. In traditional game theory, it is a trusted third party mediator that carries out the random selection, and reveals to each player that player's recommended action from the selected pair. In such games that have a correlated equilibrium, each player follows the mediator's recommendation because deviating from it cannot increase a player's expected payoff. Dodis et al. described a two-party protocol that eliminates, through cryptographic means, the third party mediator: Such games are replaced with games that do not require a third party mediator and have a computational Nash equilibrium. The protocol of Dodis et al. was designed and works well for a uniform distribution, but can be quite inefficient if applied to non-uniform distributions. Teague has subsequently built on this work and extended it to the case where the probabilistic strategy no longer assigns equal probabilities to all the pairs of moves, i.e., a pair can now have an associated probability that is much smaller (or larger) than the probability of other pairs. Our present paper improves on the work of Teague by providing an exponentially more efficient protocol for the same problem. The protocol uses tools that are of independent interest and that improve the round-complexity of recently presented protocols unrelated to the presently considered game-theoretic framework.
