# Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value

arXiv: https://arxiv.org/abs/2311.00582 · HTML: https://mlsanity.com/paper/2311.00582/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 14 of 14)

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Policy Poisoning in Batch Reinforcement Learning and Control](https://mlsanity.com/paper/1910.05821/) (2019)
- [Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signals](https://mlsanity.com/paper/1906.10571/) (2019)
- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks](https://mlsanity.com/paper/2011.10824/) (2020)
- [Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.13663/) (2022)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Admissible Policy Teaching through Reward Design](https://mlsanity.com/paper/2201.02185/) (2022)
- [Game Redesign in No-regret Game Playing](https://mlsanity.com/paper/2110.11763/) (2021)
- [Game Transformations That Preserve Nash Equilibria or Best-Response Sets](https://mlsanity.com/paper/2111.00076/) (2021)
- [Algorithms in Multi-Agent Systems: A Holistic Perspective from Reinforcement Learning and Game Theory](https://mlsanity.com/paper/2001.06487/) (2020)
- [Data Poisoning to Fake a Nash Equilibrium in Markov Games](https://mlsanity.com/paper/2306.08041/) (2023)

## Built on by (most cited first, 3 of 3)

- [Inception: Efficiently Computable Misinformation Attacks on Markov Games](https://mlsanity.com/paper/2406.17114/) (2024)
- [Optimally Installing Strict Equilibria](https://mlsanity.com/paper/2503.03676/) (2025)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

We study the game modification problem, where a benevolent game designer or a malevolent adversary modifies the reward function of a zero-sum Markov game so that a target deterministic or stochastic policy profile becomes the unique Markov perfect Nash equilibrium and has a value within a target range, in a way that minimizes the modification cost. We characterize the set of policy profiles that can be installed as the unique equilibrium of a game and establish sufficient and necessary conditions for successful installation. We propose an efficient algorithm that solves a convex optimization problem with linear constraints and then performs random perturbation to obtain a modification plan with a near-optimal cost. The code for our algorithm is available at https://github.com/YoungWu559/game-modification .