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

arXiv:0911.0874

State Information in Bayesian Games

Paul Cuff

Published Nov 4, 2009• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0911.0874

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•5 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

Nonlocality, entanglement, and randomness in different conflicting interest Bayesian games

Hargeet Kaur, Atul Kumar

We analyse different Bayesian games where payoffs of players depend on the types of players involved in a two-player game. The dependence is assumed to commensurate with the CHSH game setting. For this, we consider two different types of each player (Alice and Bob) in the game, thus resulting in four different games clubbed together as one Bayesian game. Considering different combinations of common interest, and conflicting interest coordination and anti-coordination games, we find that quantum strategies are always preferred over classical strategies if the shared resource is a pure non-maximally entangled state. However, when the shared resource is a class of mixed state, then quantum strategies are useful only for a given range of the state parameter. Surprisingly, when all conflicting interest games (Battle of the Sexes game and Chicken game) are merged into the Bayesian game picture, then the best strategy for Alice and Bob is to share a set of non-maximally entangled pure states. We demonstrate that this set not only gives higher payoff than any classical strategy, but also outperforms a maximally entangled pure Bell state, mixed Werner states, and Horodecki states. We further propose the representation of a special class of Bell inequality- tilted Bell inequality, as a common as well as conflicting interest Bayesian game. We thereafter, study the effect of sharing an arbitrary two-qubit pure state and a class of mixed state as quantum resource in those games; thus verifying that non-maximally entangled states with high randomness help attain maximum quantum benefit. Additionally, we propose a general framework of a two-player Bayesian game for d-dimensions Bell-CHSH inequality, with and without the tilt factor.

Quantum Information and Computation•Sep 1, 2020•2 citations

Secure coordination with a two-sided helper

Sanket Satpathy, Paul Cuff

We investigate the problem of secure source coding with a two-sided helper in a game-theoretic framework. Alice (A) and Helen (H) view iid correlated information sequences Xnand Ynrespectively. Alice communicates to Bob (B) at rate R, while H broadcasts a message to both A and B at rate RH. Additionally, A and B share secret key K at rate R0that is independent of (Xn, Yn). An active adversary, Eve (E) sees all communication links while having access to a (possibly degraded) version of the past information. We characterize the rate-payoff region for this problem. We also solve the problem when the link from A to B is private. Our work recovers previous results of Schieler-Cuff and Kittichokechai et al.

arXiv:1404.7164•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•10 citations

Playing Bayesian Games with General Quantum Advice

Xiaozhen Ge, Zairong Xi

The correlations, established through quantum sources, have been demonstrated to outperform classical ones in the game theory. As shown in the game firstly proposed in [Phys. Rev. Lett. 114, 020401 (2015)], the considered conflicting Bayesian game can be converted into a common interest one and end in a better solution than all classical possible when the players share a maximally entangled state. In this paper, motivated by the possible constraints on the states in practical applications, we would like to discuss more general quantum advice and analyze the effects on the aforementioned Bayesian game.

Chinese Control Conference (CCC)•Jul 1, 2018•0 citations
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.
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.
We analyse different Bayesian games where payoffs of players depend on the types of players involved in a two-player game. The dependence is assumed to commensurate with the CHSH game setting. For this, we consider two different types of each player (Alice and Bob) in the game, thus resulting in four different games clubbed together as one Bayesian game. Considering different combinations of common interest, and conflicting interest coordination and anti-coordination games, we find that quantum strategies are always preferred over classical strategies if the shared resource is a pure non-maximally entangled state. However, when the shared resource is a class of mixed state, then quantum strategies are useful only for a given range of the state parameter. Surprisingly, when all conflicting interest games (Battle of the Sexes game and Chicken game) are merged into the Bayesian game picture, then the best strategy for Alice and Bob is to share a set of non-maximally entangled pure states. We demonstrate that this set not only gives higher payoff than any classical strategy, but also outperforms a maximally entangled pure Bell state, mixed Werner states, and Horodecki states. We further propose the representation of a special class of Bell inequality- tilted Bell inequality, as a common as well as conflicting interest Bayesian game. We thereafter, study the effect of sharing an arbitrary two-qubit pure state and a class of mixed state as quantum resource in those games; thus verifying that non-maximally entangled states with high randomness help attain maximum quantum benefit. Additionally, we propose a general framework of a two-player Bayesian game for d-dimensions Bell-CHSH inequality, with and without the tilt factor.
We investigate the problem of secure source coding with a two-sided helper in a game-theoretic framework. Alice (A) and Helen (H) view iid correlated information sequences Xnand Ynrespectively. Alice communicates to Bob (B) at rate R, while H broadcasts a message to both A and B at rate RH. Additionally, A and B share secret key K at rate R0that is independent of (Xn, Yn). An active adversary, Eve (E) sees all communication links while having access to a (possibly degraded) version of the past information. We characterize the rate-payoff region for this problem. We also solve the problem when the link from A to B is private. Our work recovers previous results of Schieler-Cuff and Kittichokechai et al.
The correlations, established through quantum sources, have been demonstrated to outperform classical ones in the game theory. As shown in the game firstly proposed in [Phys. Rev. Lett. 114, 020401 (2015)], the considered conflicting Bayesian game can be converted into a common interest one and end in a better solution than all classical possible when the players share a maximally entangled state. In this paper, motivated by the possible constraints on the states in practical applications, we would like to discuss more general quantum advice and analyze the effects on the aforementioned Bayesian game.