$2 \times 2$ Zero-Sum Games with Commitments and Noisy Observations
- URL: http://arxiv.org/abs/2211.01703v3
- Date: Thu, 11 May 2023 08:29:01 GMT
- Title: $2 \times 2$ Zero-Sum Games with Commitments and Noisy Observations
- Authors: Ke Sun, Samir M. Perlaza, and Alain Jean-Marie
- Abstract summary: The equilibrium of a $2times2$ zero-sum game is shown to always exist.
Observering the actions of the leader is shown to be either beneficial or immaterial for the follower.
The payoff at the equilibrium of this game is upper bounded by the payoff at the Stackelberg equilibrium (SE) in pure strategies.
- Score: 1.9654639120238482
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper, $2\times2$ zero-sum games are studied under the following
assumptions: $(1)$ One of the players (the leader) commits to choose its
actions by sampling a given probability measure (strategy); $(2)$ The leader
announces its action, which is observed by its opponent (the follower) through
a binary channel; and $(3)$ the follower chooses its strategy based on the
knowledge of the leader's strategy and the noisy observation of the leader's
action. Under these conditions, the equilibrium is shown to always exist.
Interestingly, even subject to noise, observing the actions of the leader is
shown to be either beneficial or immaterial for the follower. More
specifically, the payoff at the equilibrium of this game is upper bounded by
the payoff at the Stackelberg equilibrium (SE) in pure strategies; and lower
bounded by the payoff at the Nash equilibrium, which is equivalent to the SE in
mixed strategies.Finally, necessary and sufficient conditions for observing the
payoff at equilibrium to be equal to its lower bound are presented. Sufficient
conditions for the payoff at equilibrium to be equal to its upper bound are
also presented.
Related papers
- Learning to Charge More: A Theoretical Study of Collusion by Q-Learning Agents [9.053163124987535]
We provide the first theoretical explanation for this behavior in infinite repeated games.<n>We show that when the game admits both a one-stage Nash equilibrium price and a collusive-enabling price, firms learn to consistently charge supracompetitive prices.
arXiv Detail & Related papers (2025-05-28T22:18:35Z) - Games played by Exponential Weights Algorithms [0.0]
We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate.
We show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1.
arXiv Detail & Related papers (2024-07-09T08:49:51Z) - Quantum Cournot model based on general entanglement operator [0.0]
The relationship between the degree of entanglement of the initial state of the game and the payoff values in Nash equilibrium is ambiguous.
In a quantum duopoly based on the initial state of a game that depends on one squeezing parameter, the maximum possible payoff in Nash equilibrium cannot be reached when the value of the phase parameter is greater than zero.
arXiv Detail & Related papers (2024-06-23T08:24:17Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
Non-concave games introduce significant game-theoretic and optimization challenges.
We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria.
We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
arXiv Detail & Related papers (2024-03-13T01:51:30Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller.
Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
arXiv Detail & Related papers (2023-12-19T11:34:10Z) - Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics [23.722837647516357]
Consider a decision-maker that can pick one out of $K$ actions to control an unknown system, for $T$ turns.
The dynamics of the system are unknown to the decision-maker, which can only observe a noisy reward at the end of every turn.
Existing bandit algorithms, either adversarial, achieve linear (tau) regret for this problem.
We present a novel algorithm that knows to switch an action quickly if it is not worth it to wait until the equilibrium is reached.
arXiv Detail & Related papers (2023-02-27T10:47:15Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating.
The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way.
We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
arXiv Detail & Related papers (2023-02-20T16:05:04Z) - Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution
Concept over Nash Equilibria [61.093297204685264]
An effective approach in multiagent reinforcement learning is to consider the learning process of agents and influence their future policies.
This new solution concept is general such that standard solution concepts, such as a Nash equilibrium, are special cases of active equilibria.
We analyze active equilibria from a game-theoretic perspective by closely studying examples where Nash equilibria are known.
arXiv Detail & Related papers (2022-10-28T14:45:39Z) - $O(T^{-1})$ Convergence of Optimistic-Follow-the-Regularized-Leader in
Two-Player Zero-Sum Markov Games [10.915751393257011]
We find an $O(T-1)$-approximate Nash equilibrium in $T$ for two-player zero-sum Markov games with full information.
This improves the $tildeO(T-5/6)$ convergence rate recently shown in the paper Zhang et al (2022).
arXiv Detail & Related papers (2022-09-26T05:35:44Z) - Safe Equilibrium [1.7132914341329848]
The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally.
We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability.
We prove that a safe equilibrium exists in all strategic-form games, and prove that its computation is PPAD-hard.
arXiv Detail & Related papers (2022-01-12T01:45:51Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples.
This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
arXiv Detail & Related papers (2021-02-23T05:11:07Z) - On Information Asymmetry in Competitive Multi-Agent Reinforcement
Learning: Convergence and Optimality [78.76529463321374]
We study the system of interacting non-cooperative two Q-learning agents.
We show that this information asymmetry can lead to a stable outcome of population learning.
arXiv Detail & Related papers (2020-10-21T11:19:53Z) - No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
We study the dynamics of "follow-the-regularized-leader" (FTRL)
We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL.
This result has significant implications for predicting the outcome of a learning process.
arXiv Detail & Related papers (2020-10-19T13:49:06Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.