We introduce a “high-probability” framework for repeated games with incomplete information. In our non-equilibrium setting, players aim to guarantee a certain payoff with high probability, rather than in expected value. We provide a high-probability counterpart of the classical result of Mertens and Zamir for the zero-sum repeated games. Any payoff that can be guaranteed with high probability can be guaranteed in expectation, but the reverse is not true. Hence, unlike the average payoff case where the payoff guaranteed by each player is the negative of the payoff by the other player, the two guaranteed payoffs would differ in the high-probability framework. One motivation for this framework comes from information transmission systems, where it is customary to formulate problems in terms of asymptotically vanishing probability of error. Finally, we introduce compound arbitrarily varying channels, and use the high-probability framework to study this problem.
We introduce a “high-probability” framework for repeated games with incomplete information. In our non-equilibrium setting, players aim to guarantee a certain payoff with high probability, rather than in expected value. We provide a high-probability counterpart of the classical result of Mertens and Zamir for the zero-sum repeated games. Any payoff that can be guaranteed with high probability can be guaranteed in expectation, but the reverse is not true. Hence, unlike the average payoff case where the payoff guaranteed by each player is the negative of the payoff by the other player, the two guaranteed payoffs would differ in the high-probability framework. One motivation for this framework comes from information transmission systems, where it is customary to formulate problems in terms of asymptotically vanishing probability of error. Finally, we introduce compound arbitrarily varying channels, and use the high-probability framework to study this problem.
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.
Two-player zero-sum repeated games are well understood. Computing the value of such a game is straightforward. Additionally, if the payoffs are dependent on a random state of the game known to one, both, or neither of the players, the resulting value of the game has been analyzed under the framework of Bayesian games. This investigation considers the optimal performance in a game when a helper is transmitting state information to one of the players. Encoding information for an adversarial setting (game) requires a different result than rate-distortion theory provides. Game theory has accentuated the importance of randomization (mixed strategy), which does not find a significant role in most communication modems and source coding codecs. Higher rates of communication, used in the right way, allow the message to include the necessary random component useful in games.
Quantum entanglement has been recently demonstrated as a useful resource in conflicting-interest games of incomplete information between two players, Alice and Bob [Pappa et al., Phys. Rev. Lett. 114, 020401 (2015)]. The general setting for such games is that of correlated strategies where the correlation between competing players is established through a trusted common adviser; however, players need not reveal their input to the adviser. So far, the quantum advantage in such games has been revealed in a restricted sense. Given a quantum correlated equilibrium strategy, one of the players can still receive a higher than quantum average payoff with some classically correlated equilibrium strategy. In this work, by considering a class of asymmetric Bayesian games, we show the existence of games with quantum correlated equilibrium where the average payoff of both the players exceeds the respective individual maximum for each player over all classically correlated equilibriums.
Our work is based on the model proposed in the paper “Optimal Use of Communication Resources” by Olivier Gossner, Penelope Hernandez and Abraham Neyman, [6]. We propose two models that consider an alteration of the payoff function in [6]. The general setup is as follows. A repeated game is played between a team of two players, consisting of a forecaster and an agent, and nature. We assume that the forecaster and the agent share the same payoff function. The forecaster, contrary to the agent, is able to observe future states of nature that have an impact on the team’s payoff. A given pair of strategies for the players induces a sequence of actions and thus implements an average distribution on the actions of interest, i.e., on those actions that determine the payoff. We let the team’s stage payoff not only depend on actions played in one stage, but on actions played in two consecutive stages. We introduce two models that vary w.r.t. the specification of the payoff function and the actions played by nature, with the aim of characterizing the implementable average distributions. This characterization is achieved through an information inequality based on the entropy function, called the information constraint. It expresses a key feature of the strategies of the players, namely the fact that the information used by the agent cannot exceed the amount of information sent by the forecaster. In each model we develop an information constraint that characterizes the implementable distributions as follows. On the one hand, we show that every implementable distribution fulfills the information constraint. And on the other hand, we prove that a certain set of distributions that fulfill the designated information constraint is implementable.
We consider game theory from the perspective of quantum algorithms. Strategies in classical game theory are either pure (deterministic) or mixed (probabilistic). While not every two-person zero-sum finite game has an equilibrium in the set of pure strategies, von Neumann showed that there is always an equilibrium at which each player follows a mixed strategy. A mixed strategy deviating from the equilibrium strategy cannot increase a player's expected payoff. We show by example, however, that a player who implements a quantum strategy can increase his expected payoff, and explain the relation to efficient quantum algorithms.
We outline the general construction of three-player games with incomplete information which fulfil the following conditions: (i) symmetry with respect to the permutations of players; (ii) the existence of an upper bound for total payoff resulting from Bell inequalities; (iii) the existence of both fair and unfair Nash equilibria saturating this bound. Conditions (i)–(iii) imply that we are dealing with conflicting interest games. An explicit example of such a game is given. A quantum counterpart of this game is considered. It is obtained by keeping the same utilities but replacing classical advisor by a quantum one. It is shown that the quantum game possesses only fair equilibria with strictly higher payoffs than in the classical case. This implies that quantum nonlocality can be used to resolve the conflict between the players.