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

  • 2024-06-05 17:09:46
  • Young Wu, Jeremy McMahan, Yiding Chen, Yudong Chen, Xiaojin Zhu, Qiaomin Xie
  • 0


We study the game modification problem, where a benevolent game designer or amalevolent adversary modifies the reward function of a zero-sum Markov game sothat a target deterministic or stochastic policy profile becomes the uniqueMarkov perfect Nash equilibrium and has a value within a target range, in a waythat minimizes the modification cost. We characterize the set of policyprofiles that can be installed as the unique equilibrium of some game, andestablish sufficient and necessary conditions for successful installation. Wepropose an efficient algorithm, which solves a convex optimization problem withlinear constraints and then performs random perturbation, to obtain amodification plan with a near-optimal cost.


Quick Read (beta)

loading the full paper ...