State-Constrained Zero-Sum Differential Games with One-Sided Information

• URL: http://arxiv.org/abs/2403.02741v2
• Date: Tue, 4 Jun 2024 17:26:30 GMT
• Title: State-Constrained Zero-Sum Differential Games with One-Sided Information
• Authors: Mukesh Ghimire, Lei Zhang, Zhe Xu, Yi Ren,
• Abstract summary: We study zero-sum differential games with state constraints and one-sided information. Our contribution is an extension to games with state constraints and the derivation of the primal and dual subdynamic principles necessary for computing behavioral strategies.
• Score: 19.964883571758502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study zero-sum differential games with state constraints and one-sided information, where the informed player (Player 1) has a categorical payoff type unknown to the uninformed player (Player 2). The goal of Player 1 is to minimize his payoff without violating the constraints, while that of Player 2 is to violate the state constraints if possible, or to maximize the payoff otherwise. One example of the game is a man-to-man matchup in football. Without state constraints, Cardaliaguet (2007) showed that the value of such a game exists and is convex to the common belief of players. Our theoretical contribution is an extension of this result to games with state constraints and the derivation of the primal and dual subdynamic principles necessary for computing behavioral strategies. Different from existing works that are concerned about the scalability of no-regret learning in games with discrete dynamics, our study reveals the underlying structure of strategies for belief manipulation resulting from information asymmetry and state constraints. This structure will be necessary for scalable learning on games with continuous actions and long time windows. We use a simplified football game to demonstrate the utility of this work, where we reveal player positions and belief states in which the attacker should (or should not) play specific random deceptive moves to take advantage of information asymmetry, and compute how the defender should respond.

Related papers

• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• Adversarial Knapsack and Secondary Effects of Common Information for Cyber Operations [0.9378911615939924]
  We formalize a dynamical network control game for Capture the Flag (CTF) competitions and detail the static game for each time step. We define the Adversarial Knapsack optimization problems as a system of interacting Weighted Knapsack problems. Common awareness of the scenario, rewards, and costs will set the stage for a non-cooperative game.
  arXiv  Detail & Related papers  (2024-03-16T03:41:12Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
  arXiv  Detail & Related papers  (2023-01-22T16:54:06Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving [31.29335755664997]
  emphEx ante correlation is becoming the mainstream approach for emphsequential adversarial team games, where a team of players faces another team in a zero-sum game. This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games. We propose a new, suitable game representation that we call emphteam-public-information, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state.
  arXiv  Detail & Related papers  (2022-06-18T10:02:08Z)
• Public Information Representation for Adversarial Team Games [31.29335755664997]
  adversarial team games reside in the asymmetric information available to the team members during the play. Our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one.
  arXiv  Detail & Related papers  (2022-01-25T15:07:12Z)
• Rigidity for Monogamy-of-Entanglement Games [0.6091702876917281]
  We study the prototypical example of a game where the referee measures in either the computational or Hadamard basis. We show that this game satisfies a rigidity property similar to what is known for some nonlocal games. We also show rigidity for multiple copies of the game played in parallel.
  arXiv  Detail & Related papers  (2021-11-15T20:59:17Z)
• Fictitious play in zero-sum stochastic games [1.9143447222638694]
  We present a novel variant of fictitious play dynamics combining classical play with Q-learning for games. We analyze its convergence properties in two-player zero-sum games.
  arXiv  Detail & Related papers  (2020-10-08T19:06:45Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.