The Game Changer Problem: Controlling Equilibria with Discrete Rewards
This work addresses the problem of controlling equilibria in games with discrete rewards, offering a sharper and more practical alternative to continuous reward redesign for game designers.
The paper introduces the game changer problem, where a designer modifies a game's reward matrix using a finite set of values to make a target action profile the unique equilibrium. It provides feasibility characterizations for two-player zero-sum and general-sum games, and develops efficient dynamic programming algorithms that outperform prior continuous reward redesign methods.
We introduce the game changer problem, where an external designer modifies a game's reward matrix to make a target pure action profile the unique equilibrium, subject to the constraint that all entries of the reward matrix come from a finite set. We give simple feasibility characterizations for two-player zero-sum games and general-sum games, and the discrete reward structure yields exact optimality and enables efficient dynamic programming algorithms, providing a sharper alternative to prior continuous reward redesign formulations based on linear programming.