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

Optimal use of communication resources with Markovian Payoff functions

Nicola Wittur

Published Sep 1, 2018• 0 citations
OpenAlex

Abstract

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.

Related papers

The economics of information transmission

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

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.

•Jan 1, 2002•0 citations

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•4 citations

INFORMATION GAMES

Yu Kai

In a game each player holds a strategy based upon the actions that he can actually take. The quality and the quantity of the feasible actions are determined by his ability or power in the game. Generally every player has no information on the others' powers, so it is one of the most important problems for them to know the powers. We treat such unknown games, played periodically, from the view point of information theory. We discuss both non-cooperative and cooperative games and prove some sufficient conditions under which a player can get the full information on the other players' powers from sequential observations on the states. In two person games we show also optimal strategies with respect to the information.

Bulletin of informatics and cybernetics•Mar 1, 1982•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

Information Compression in Dynamic Information Disclosure Games

Dengwang Tang, Vijay Subramanian

We consider a two-player dynamic information design problem for a game played between a principal and a receiver on top of a Markovian system controlled by the receiver’s actions. The principal strategically obtains and shares some information about the underlying system with the receiver in order to influence their actions, and agents’ instantaneous rewards depend only on the system state and receiver actions. In our game, both players have long-term objectives, and the principal sequentially commits to their strategies instead of at the beginning-at every turn the principal can choose randomized experiments to observe the system partially. The principal can share details about the experiments to the receiver. In our analysis the truthful disclosure rule is assumed-the principal is required to truthfully announce each experiment detail and result to the receiver immediately after the result is revealed. Based on the received information, when its their turn the receiver takes an action which influences the state of the underlying system. Using a constructive backward inductive procedure, we show that there exists a Perfect Bayesian Equilibrium in this game where both agents play Canonical Belief Based (CBB) strategies using a compressed version of their information, rather than their full information, to choose experiments (for the principal) or actions (for the receiver).

arXiv:2403.12204•IEEE Conference on Decision and Control (CDC)•Dec 16, 2024•0 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•3 citations
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.
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.
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.
In a game each player holds a strategy based upon the actions that he can actually take. The quality and the quantity of the feasible actions are determined by his ability or power in the game. Generally every player has no information on the others' powers, so it is one of the most important problems for them to know the powers. We treat such unknown games, played periodically, from the view point of information theory. We discuss both non-cooperative and cooperative games and prove some sufficient conditions under which a player can get the full information on the other players' powers from sequential observations on the states. In two person games we show also optimal strategies with respect to the information.
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.
We consider a two-player dynamic information design problem for a game played between a principal and a receiver on top of a Markovian system controlled by the receiver’s actions. The principal strategically obtains and shares some information about the underlying system with the receiver in order to influence their actions, and agents’ instantaneous rewards depend only on the system state and receiver actions. In our game, both players have long-term objectives, and the principal sequentially commits to their strategies instead of at the beginning-at every turn the principal can choose randomized experiments to observe the system partially. The principal can share details about the experiments to the receiver. In our analysis the truthful disclosure rule is assumed-the principal is required to truthfully announce each experiment detail and result to the receiver immediately after the result is revealed. Based on the received information, when its their turn the receiver takes an action which influences the state of the underlying system. Using a constructive backward inductive procedure, we show that there exists a Perfect Bayesian Equilibrium in this game where both agents play Canonical Belief Based (CBB) strategies using a compressed version of their information, rather than their full information, to choose experiments (for the principal) or actions (for the receiver).