Abstract
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.
Introduction
In multi-agent systems, the outcome of a game is determined by the Nash Equilibrium (NE). However, a game's natural equilibrium might be undesirable—it could be "unfair" (favoring one player), overly complex for humans to implement, or involve pure strategies that make a game predictable.
The Game Modification Problem explores how a third party (a "game designer" or an "adversary") can change the reward function of a two-player zero-sum Markov game to "install" a target policy profile as the unique equilibrium. Crucially, this must be achieved with the minimum possible change to the original rewards. While previous work has addressed pure strategies, this paper tackles the more complex problem of installing mixed (stochastic) strategies as the unique equilibrium.
Theoretical Foundations for Uniqueness
Uniqueness is vital because if multiple equilibria exist, players might coordinate on a different one than the target. The paper defines two core conditions for uniqueness:
- SIISOW (Switch-In Indifferent, Switch-Out Worse): Players should be indifferent between any actions within their equilibrium support but strictly worse off if they switch to an action outside that support.
- INV (Invertibility): A specific matrix related to the equilibrium support must be invertible.
The Relax and Perturb (RAP) Algorithm
To solve the modification problem, the authors propose the Relax and Perturb (RAP) algorithm, which operates in two stages:
- Relax: It first solves a convex optimization problem (often a Linear Program) that satisfies the SIISOW conditions but ignores the non-convex INV condition. This provides a "near-optimal" reward matrix that might have multiple equilibria.
- Perturb: It then adds a tiny, structured random perturbation to the rewards. This perturbation ensures the INV condition is met—and thus the target equilibrium becomes unique—with probability 1, while only negligibly increasing the modification cost.
Extended Rock-Paper-Scissors (eRPS)
The perturbation step utilizes a novel construction called the Extended Rock-Paper-Scissors (eRPS) game. It can be scaled to any number of actions and always has a unique, customizable mixed strategy equilibrium with a value of zero. This serves as a template to break ties in other games without shifting the equilibrium point.
Experimental Results and Scalability
The RAP algorithm is provably asymptotically optimal; as safety margins decrease, the cost converges to the theoretical minimum. The algorithm was evaluated on:
- Toy Games: Classic examples like Two-finger Morra and Rock-Paper-Scissors-Fire-Water.
- Synthetic Benchmarks: Randomly generated Markov games with up to 512 actions and horizons.
The algorithm is highly efficient, handling Markov games with millions of variables in approximately 10 seconds on a standard laptop. In practical tests, the authors demonstrated the ability to modify an unfair game into a fair one while maintaining the original equilibrium with minimal changes to the payoff matrix.
Limitations and Future Work
While powerful, the current framework is limited to two-player zero-sum games. Future research directions include extending the method to general-sum or multi-agent games, exploring modifications to transition probabilities instead of just rewards, and addressing scenarios where players must learn the game from observations (data poisoning).
Summary updated