Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
Young Wu, Jeremy McMahan, Yiding Chen, Yudong Chen, Jerry Zhu, Qiaomin Xie
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.
BibTeX
@inproceedings{
wu2024minimally,
title={Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value},
author={Young Wu and Jeremy McMahan and Yiding Chen and Yudong Chen and Jerry Zhu and Qiaomin Xie},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
url={https://openreview.net/forum?id=ZtMqsSkIHX}
}