mlsanityData to 14 Oct 2026

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

arXiv 2311.00582 ↗First posted 1 Nov 2023cs.GT cs.AIcited by 3

Not on the map. Why?

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 .

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

14 of 52 references.

References · 14

  1. 2017Cycles in adversarial regularized learningcited by 124
  2. 2020Adaptive Reward-Poisoning Attacks against Reinforcement Learningcited by 86
  3. 2020Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learningcited by 81
  4. 2019Policy Poisoning in Batch Reinforcement Learning and Controlcited by 70
  5. 2019Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signalscited by 50
  6. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
  7. 2020Policy Teaching in Reinforcement Learning via Environment Poisoning Attackscited by 24
  8. 2022Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learningcited by 21
  9. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 20
  10. 2022Admissible Policy Teaching through Reward Designcited by 12
  11. 2021Game Redesign in No-regret Game Playingcited by 8
  12. 2021Game Transformations That Preserve Nash Equilibria or Best-Response Setscited by 5
2 more
  1. 2020Algorithms in Multi-Agent Systems: A Holistic Perspective from Reinforcement Learning and Game Theorycited by 2
  2. 2023Data Poisoning to Fake a Nash Equilibrium in Markov Gamescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 1.

3 papers.

  1. 2024Inception: Efficiently Computable Misinformation Attacks on Markov Gamescited by 1
  2. 2025Optimally Installing Strict Equilibriacited by 0
  3. 2026Thompson Sampling for Learning in Zero-Sum Gamescited by 0