Semidefinite network games: multiplayer minimax and complementarity problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911320614371328 |
|---|---|
| author | Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios |
| author_facet | Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios |
| contents | Network games provide a powerful framework for modeling agent interactions in networked systems, where players are represented by nodes in a graph and their payoffs depend on the actions taken by their neighbors. Extending the framework of network games, we introduce and study semidefinite network games. In this model, each player selects a positive semidefinite matrix with trace equal to one, known as a density matrix, to engage in a two-player game with every neighboring node. The player's payoff is the cumulative payoff acquired from these edge games. Initially, we focus on the zero-sum setting, where the sum of all players' payoffs is equal to zero. We establish that, in this class of games, Nash equilibria can be characterized as the projection of a spectrahedron. Furthermore, we show that determining whether a semidefinite network game is a zero-sum game is equivalent to deciding if the value of a semidefinite program is zero. Beyond the zero-sum case, we characterize Nash equilibria as the solutions of a semidefinite linear complementarity problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_20333 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Semidefinite network games: multiplayer minimax and complementarity problems Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios Optimization and Control Computer Science and Game Theory 52A20, 68Q25, 90C22, 91A43, 91A81 Network games provide a powerful framework for modeling agent interactions in networked systems, where players are represented by nodes in a graph and their payoffs depend on the actions taken by their neighbors. Extending the framework of network games, we introduce and study semidefinite network games. In this model, each player selects a positive semidefinite matrix with trace equal to one, known as a density matrix, to engage in a two-player game with every neighboring node. The player's payoff is the cumulative payoff acquired from these edge games. Initially, we focus on the zero-sum setting, where the sum of all players' payoffs is equal to zero. We establish that, in this class of games, Nash equilibria can be characterized as the projection of a spectrahedron. Furthermore, we show that determining whether a semidefinite network game is a zero-sum game is equivalent to deciding if the value of a semidefinite program is zero. Beyond the zero-sum case, we characterize Nash equilibria as the solutions of a semidefinite linear complementarity problem. |
| title | Semidefinite network games: multiplayer minimax and complementarity problems |
| topic | Optimization and Control Computer Science and Game Theory 52A20, 68Q25, 90C22, 91A43, 91A81 |
| url | https://arxiv.org/abs/2310.20333 |