Research map / Reinforcement learning / MDPs and planning
Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
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.
Characterizes when a zero-sum Markov game's reward can be minimally modified so a target deterministic or stochastic policy profile is the unique MPE with a target value, and gives a convex-program-plus-random-perturbation algorithm (RAP / RAP-MG) with near-optimal cost.
Problem
Game modification: a third party alters the reward function of a zero-sum Markov game so that a target (possibly mixed) policy profile becomes the unique Markov perfect Nash equilibrium with game value in a target range, at minimum cost.
Approach
Uses an operational characterization of NE uniqueness (SIISOW plus an invertibility condition) to express uniqueness as linear constraints plus a spectral condition; relaxes the spectral constraint, solves the resulting linear/convex program, then adds a small random multiple of an Extended Rock-Paper-Scissors matrix to guarantee invertibility with probability one.
Key results
- Feasibility characterized: a target profile with equal support sizes is installable as unique MPE iff (-Hb, Hb) intersects the target value range (Markov case).
- RAP-MG yields cost converging to the optimum at a linear rate in the margins for piecewise-linear costs; in experiments convergence happened by margin 1e-4.
- Scale experiments with Gurobi: 512x512 normal-form games solved in roughly 10 seconds on a laptop.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Modify the payoffs to make the game fair while retaining the same unique NE | Simplified Two-finger Morra · Simplified Two-finger Morra | game value: -\frac{1}{12} -> 0 | Helped |
| Redesign the game to have a uniformly mixed NE | Rock-Paper-Scissors-Fire-Water · Rock-Paper-Scissors-Fire-Water | modification cost: 8 -> 4 | Helped |
Surprising findings
- Game value can never equal the reward bound b, since SIISOW requires a strict gap between the game value and off-support actions.
Limitations
- Transition probabilities are assumed fixed and cannot be modified by the third party.
- Only two-player zero-sum games with finite horizon are treated; general-sum games are left open.
- Rewards are assumed continuous; discrete reward values are left as future work.
Experimental setup
Benchmarks: two-finger Morra Rock-Paper-Scissors-Fire-Water random normal-form and Markov game instances
Metrics: modification cost (L1) running time convergence of cost to optimum
Baselines: Rock-Paper-Scissors-Spock-Lizard alternative game
Builds on: Markov perfect equilibrium Goldman-Tucker linear programming duality
Closest papers by meaning
- Cost Minimization for Equilibrium Transition (AAAI 2024 · similarity 0.88)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.87)
- Anytime-Constrained Equilibria in Polynomial Time (ICML 2025 · similarity 0.86)
- Approximate State Abstraction for Markov Games (AAAI 2025 · similarity 0.86)
- Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.85)
- Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization (ICLR 2024 · similarity 0.85)
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.