Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The economics of information transmission

Penélope Hernàndez Rojas, Olivier Gossner, Abraham Neyman

Published Jan 1, 2002• 0 citations
OpenAlex

Abstract

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.

Related papers

Optimal use of communication resources with Markovian Payoff functions

Nicola Wittur

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.

•Sep 1, 2018•0 citations

State Information in Bayesian Games

Paul Cuff

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.

arXiv:0911.0874•Nov 4, 2009•4 citations

A Cryptographic Solution to a Game Theoretic Problem

Yevgeniy Dodis, Shai Halevi, Tal Rabin

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

•Jan 1, 2000•43 citations

How Quantum Entanglement Helps to Coordinate Non-Communicating Players

G.V. Klimovitch

We consider a coalitional game with the same payoff for all players. To maximize the payoff, the players need to use one collective strategy, if all players are in certain states, and the other strategy otherwise. The current state of each player changes according to external conditions and is not known to the other players. In one example of such a game, quantum entanglement between players results in the optimal payoff thrice the maximal payoff for unentangled players.

arXiv:quant-ph/0405093•May 17, 2004•1 citation

High probability guarantees in repeated games: Theory and applications in information theory

Payam Delgosha, Amin Gohari, Mohammad Akbarpour

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.

arXiv:1509.08571•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•5 citations

Quadratic Privacy-Signaling Games and Payoff Dominant Equilibria

Ertan Kazıklı, Sinan Gezici, Serdar Yüksel

We consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•3 citations
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.
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.
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.
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 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 consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.