Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
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.
Cite
Text
Wu et al. "Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value." International Conference on Machine Learning, 2024.Markdown
[Wu et al. "Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/wu2024icml-minimally/)BibTeX
@inproceedings{wu2024icml-minimally,
title = {{Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value}},
author = {Wu, Young and Mcmahan, Jeremy and Chen, Yiding and Chen, Yudong and Zhu, Jerry and Xie, Qiaomin},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {53730-53756},
volume = {235},
url = {https://mlanthology.org/icml/2024/wu2024icml-minimally/}
}