Multi-Player Zero-Sum Markov Games with Networked Separable Interactions
We study a new class of Markov games, (multi-player) zero-sum Markov Games with Networked separable interactions (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where the payoffs of the auxiliary...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153885 |
| _version_ | 1826213829618434048 |
|---|---|
| author | Park, Chanwoo |
| author2 | Ozdaglar, Asuman |
| author_facet | Ozdaglar, Asuman Park, Chanwoo |
| author_sort | Park, Chanwoo |
| collection | MIT |
| description | We study a new class of Markov games, (multi-player) zero-sum Markov Games with Networked separable interactions (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where the payoffs of the auxiliary games associated with each state are zero-sum and have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov stationary CCE in infinite-horizon discounted zero-sum NMGs is PPAD-hard, unless the underlying network has a “star topology”. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov non-stationary NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results. |
| first_indexed | 2024-09-23T15:55:29Z |
| format | Thesis |
| id | mit-1721.1/153885 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:55:29Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1538852024-03-22T03:07:36Z Multi-Player Zero-Sum Markov Games with Networked Separable Interactions Park, Chanwoo Ozdaglar, Asuman Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We study a new class of Markov games, (multi-player) zero-sum Markov Games with Networked separable interactions (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent sequential decision-making. We define a zero-sum NMG as a model where the payoffs of the auxiliary games associated with each state are zero-sum and have some separable (i.e., polymatrix) structure across the neighbors over some interaction network. We first identify the necessary and sufficient conditions under which an MG can be presented as a zero-sum NMG, and show that the set of Markov coarse correlated equilibrium (CCE) collapses to the set of Markov Nash equilibrium (NE) in these games, in that the product of per-state marginalization of the former for all players yields the latter. Furthermore, we show that finding approximate Markov stationary CCE in infinite-horizon discounted zero-sum NMGs is PPAD-hard, unless the underlying network has a “star topology”. Then, we propose fictitious-play-type dynamics, the classical learning dynamics in normal-form games, for zero-sum NMGs, and establish convergence guarantees to Markov stationary NE under a star-shaped network structure. Finally, in light of the hardness result, we focus on computing a Markov non-stationary NE and provide finite-iteration guarantees for a series of value-iteration-based algorithms. We also provide numerical experiments to corroborate our theoretical results. S.M. 2024-03-21T19:13:33Z 2024-03-21T19:13:33Z 2024-02 2024-02-21T17:10:17.314Z Thesis https://hdl.handle.net/1721.1/153885 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Park, Chanwoo Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title | Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title_full | Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title_fullStr | Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title_full_unstemmed | Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title_short | Multi-Player Zero-Sum Markov Games with Networked Separable Interactions |
| title_sort | multi player zero sum markov games with networked separable interactions |
| url | https://hdl.handle.net/1721.1/153885 |
| work_keys_str_mv | AT parkchanwoo multiplayerzerosummarkovgameswithnetworkedseparableinteractions |