Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913478272352256 |
|---|---|
| author | Wu, Young McMahan, Jeremy Chen, Yiding Chen, Yudong Zhu, Xiaojin Xie, Qiaomin |
| author_facet | Wu, Young McMahan, Jeremy Chen, Yiding Chen, Yudong Zhu, Xiaojin Xie, Qiaomin |
| contents | 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. The code for our algorithm is available at https://github.com/YoungWu559/game-modification . |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_00582 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value Wu, Young McMahan, Jeremy Chen, Yiding Chen, Yudong Zhu, Xiaojin Xie, Qiaomin Computer Science and Game Theory Artificial Intelligence 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. The code for our algorithm is available at https://github.com/YoungWu559/game-modification . |
| title | Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value |
| topic | Computer Science and Game Theory Artificial Intelligence |
| url | https://arxiv.org/abs/2311.00582 |