Research map / Learning theory and algorithms / Submodular and game algorithms
State-Constrained Zero-Sum Differential Games with One-Sided Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves value existence for state-constrained zero-sum differential games with one-sided information and derives primal/dual subdynamic principles and a numerical backward-induction scheme (PICNN value networks, PINN reachable sets) demonstrated on an 8D man-to-man football matchup.
Problem
Zero-sum differential games where an informed player with a categorical type faces state constraints, and the uninformed player can exploit constraint violations; existing theory covered either state constraints or one-sided information, but not both, and value computation is hard due to belief-spac
Approach
Extends Cardaliaguet's one-sided-information differential game theory to state constraints by proving value existence and deriving primal and dual subdynamic principles, which give behavioral strategies that split beliefs (convexify the value) and a dual game for the uninformed player; the numerics use a PICNN to enforce belief convexity and a PINN to approximate the backward reachable set.
Key results
- Proves that the value exists (upper and lower values coincide) for state-constrained zero-sum differential games with one-sided information under stated assumptions.
- In the constrained football case study, P1 is shown to randomize and delay information release near equal-distance positions, with information-reveal delay and advantage visualized over starting positions (no single headline number reported).
- Convexification error is bounded by 2 d_P L, where d_P is the lattice spacing and L the Lipschitz constant of the convexified value.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a state constraint to the Hexner game | Hexner game · Simplified football game | state-constraint satisfaction | Helped |
| combine incomplete information with state constraints | Player 1 strategy · Simplified football game | randomized strategy use | Helped |
| use a belief-manipulating strategy instead of never splitting the belief | Player 1 · Simplified football game | payoff advantage | Mixed |
| keep P1 and P2 at equal distances from the possible targets | Player 1 · Simplified football game | information concealment | Helped |
Surprising findings
- With state constraints, the unconstrained Hexner strategy (reveal at t_r=0.4) is no longer valid; P1 instead uses random deceptive moves, since constraints and incomplete information both induce non-convexity of the value in belief.
Limitations
- Numerical approach suffers from curse of dimensionality, value discontinuity, and error propagation across backward induction steps.
- Case study is a simplified low-dimensional game with two discrete types; dual game has belief dimension I+1 and is harder to approximate.
- Full error/data-complexity analysis is left to future work.
Experimental setup
Benchmarks: Hexner's game (analytical solution) simplified 8D man-to-man football game
Metrics: average information-reveal delay advantage of belief-splitting strategy over non-revealing st critical time t_r
Baselines: Hexner's unconstrained analytical solution Hu et al. belief-space HJ formulation
Builds on: Cardaliaguet differential games with one-sided information Hexner's game De Meyer dual games PICNN
Closest papers by meaning
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.88)
- Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games (AAAI 2024 · similarity 0.87)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.87)
- Safe Exploitative Play with Untrusted Type Beliefs (NeurIPS 2024 · similarity 0.86)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.86)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.