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 (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. 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. 1
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 (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. 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. 1
We revisit the question of whether cryptographic protocols can replace correlated equilibria mediators in two-player strategic games. This problem was first addressed by Dodis, Halevi and Rabin (CRYPTO 2000), who suggested replacing the mediator with a secure protocol and proved that their solution is stable in the Nash equilibrium (NE) sense, provided that the players are computationally bounded. We show that there exist two-player games for which no cryptographic protocol can implement the mediator in a sequentially rational way; that is, without introducing empty threats. This explains why all solutions so far were either sequentially unstable, or were restricted to a limited class of correlated equilibria (specifically, those that do not dominate any NE, and hence playing them does not offer a clear advantage over playing any NE). In the context of computational NE, we classify necessary and sufficient cryptographic assumptions for implementing a mediator that allows to achieve a given utility profile of a correlated equilibrium. The picture that emerges is somewhat different than the one arising in semi-honest secure two-party computation. Specifically, while in the latter case every functionality is either “complete" (i.e., implies Oblivious Transfer) or “trivial " (i.e., can be securely computed unconditionally), in the former there exist some “intermediate " utility profiles whose implementation is equivalent to the existence of one-way functions. 1
We revisit the question of whether cryptographic protocols can replace correlated equilibria mediators in two-player strategic games. This problem was first addressed by Dodis, Halevi and Rabin (CRYPTO 2000), who suggested replacing the mediator with a secure protocol and proved that their solution is stable in the Nash equilibrium (NE) sense, provided that the players are computationally bounded. We show that there exist two-player games for which no cryptographic protocol can implement the mediator in a sequentially rational way; that is, without introducing empty threats. This explains why all solutions so far were either sequentially unstable, or were restricted to a limited class of correlated equilibria (specifically, those that do not dominate any NE, and hence playing them does not offer a clear advantage over playing any NE). In the context of computational NE, we classify necessary and sufficient cryptographic assumptions for implementing a mediator that allows to achieve a given utility profile of a correlated equilibrium. The picture that emerges is somewhat different than the one arising in semi-honest secure two-party computation. Specifically, while in the latter case every functionality is either “complete” (i.e., implies Oblivious Transfer) or “trivial” (i.e., can be securely computed unconditionally), in the former there exist some “intermediate” utility profiles whose implementation is equivalent to the existence of one-way functions. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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. 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, a trusted third party mediator carries out this random selection, and reveals to each player its recommended action.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, Halevi, and Rabin [1] described a two-party protocol that eliminates, through cryptographic means, the third party mediator. That protocol was designed and works well for a uniform distribution, but can be quite inefficient if applied to non-uniform distributions. Teague [2] 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. Our present paper improves on the work of Teague by providing, for the same problem, a protocol whose worst-case complexity is exponentially better. The protocol also uses tools that are of independent interest.
Abstract. A common problem in many markets is that competing firms cannot plan joint business strategies which are socially beneficial, as each firm has its own preferable business strategy which would yield higher profits for it and lower profits for the others. The solution to this problem becomes complex because each firm need not stick to its commitment to follow the pre-designated strategy. Game theory suggests to us a way to enforce this commitment, as when every player chooses his actions according to his observation of the value of a common public signal and, assuming that the others do not deviate, no player is willing to deviate from his recommended strategy. The players do not deviate from their recommended strategy as playing them would yield them a much higher expected pay-off than playing individually. The common public channel can be a trusted external mediator which may send each player his recommended strategy. This mediator can be simulated by a cryptographic protocol, which all the players agree to implement. This problem of suggesting the protocol is known as the Correlated Element Selection Problem. The first two-player protocol was proposed by Dodis et. al[1] in Crypto 2000. The extension of the two-player protocol to an n-player protocol is highly prone to collusions, as two firms can collude and cheat the rest of the firms. The main contribution of the paper is the first n-player collusion free protocol for the correlated element selection problem that does not use hardware primitives. We assume that players are honest but curious. 1
Abstract. In many markets, it can be beneficial for competing firms to coordinate their actions. However, such arrangements usually have the problem that nobody has an incentive to adhere to the agreement. In this paper we investigate a way for two companies to communicate together and agree on a coordinated strategy in such a way that both participants have an incentive to keep to the agreement. We provide a more efficient solution to the game theoretic problem solved by Dodis, Halevi and Rabin in [DHR00]: two selfish rational parties want to select one of a list of pairs, according to some probability distribution, so that one party learns the first element and the other learns the second, and neither gains any other information. In game theory terms, the problem is to achieve a correlated equilibrium without the trusted mediator. Our solution is more efficient than [DHR00] in terms of the probability distribution. 1
It is a well known phenomenon that communication between a group of
players affects the set of equilibria of a repeated game. This communication
can be costly. Its cost may be measured in terms of complexity, or payoffs.
In particular, a payoff cost of communication occurs when players communicate
through their actions, and one is interested in characterizing the optimal
communication.
We study a class of games that models the communication cost of online
coordination. For example: A sequence X = (X(t)) of zeroes and ones is chosen
at random, and announced to a player, the seer, but not to his teammate, the
follower. A repeated game then proceeds in which the follower and the seer
choose actions Y (t) and Z(t) in {0, 1} at stage t, and their (common) stage
payoff is 1 whenever X(t) = Y (t) = Z(t).
We address the question of the optimal communication level from the seer
to the follower in order to maximize payoffs. We characterize this level using
the notion of entropy, and provide construction of optimal strategies for the
team: the seer and the follower. In particular, we prove that against a family
of i.i.d. random variables (1/2, 1/2), the maximum expected payoff v to the
team is the solution of the equation
H(x) + log(3) (1 - x) = 1;
where H is the entropy function and log is taken in basis 2. Moreover, we prove
the existence of pure strategies of the prophet and the seer that guarantee v
against all sequences X = X(t). Hence, the zero-sum game in which player I
is the Team (no correlation is allowed between its members), player II is the
opponent, and the payoff to I is as above, has a value, and this equals v. Our
result has direct implications for repeated games played by finite automata, or
by players with bounded recall.