Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
This work addresses game design and adversarial manipulation in multi-agent systems, offering a method to control equilibrium outcomes, which is incremental as it builds on existing game theory concepts.
The paper tackles the problem of modifying a zero-sum Markov game's reward function to make a target policy profile the unique Nash equilibrium with a desired value range, while minimizing modification cost. It provides conditions for feasibility and proposes an efficient convex optimization algorithm with random perturbation to achieve near-optimal cost.
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 .