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

Young Wu, Jeremy Mcmahan, Yiding Chen, Yudong Chen, Jerry Zhu, Qiaomin Xie
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:53730-53756, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v235-wu24t, title = {Minimally Modifying a {M}arkov Game to Achieve Any {N}ash Equilibrium and Value}, author = {Wu, Young and Mcmahan, Jeremy and Chen, Yiding and Chen, Yudong and Zhu, Jerry and Xie, Qiaomin}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {53730--53756}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/wu24t/wu24t.pdf}, url = {https://proceedings.mlr.press/v235/wu24t.html}, 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.} }
Endnote
%0 Conference Paper %T Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value %A Young Wu %A Jeremy Mcmahan %A Yiding Chen %A Yudong Chen %A Jerry Zhu %A Qiaomin Xie %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-wu24t %I PMLR %P 53730--53756 %U https://proceedings.mlr.press/v235/wu24t.html %V 235 %X 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.
APA
Wu, Y., Mcmahan, J., Chen, Y., Chen, Y., Zhu, J. & Xie, Q.. (2024). Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:53730-53756 Available from https://proceedings.mlr.press/v235/wu24t.html.

Related Material