Nash equilibria in semidefinite games and Lemke-Howson paths
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913892494475264 |
|---|---|
| author | Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios |
| author_facet | Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios |
| contents | We consider an algorithmic framework for two-player non-zero-sum semidefinite games, where each player's strategy is a positive semidefinite matrix with trace one. We formulate the computation of Nash equilibria in such games as semidefinite complementarity problems and develop symbolic-numeric techniques to trace generalized Lemke-Howson paths. These paths generalize the piecewise affine-linear trajectories of the classical Lemke-Howson algorithm for bimatrix games, replacing them with nonlinear curve branches governed by eigenvalue complementarity conditions.
A key feature of our framework is the introduction of event points, which correspond to curve singularities. We analyze the local behavior near these points using Puiseux series expansions. We prove the smoothness of the curve branches under suitable non-degeneracy conditions and establish connections between our approach and both the classical combinatorial and homotopy-theoretic interpretations of the Lemke-Howson algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11940 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nash equilibria in semidefinite games and Lemke-Howson paths Ickstadt, Constantin Theobald, Thorsten Tsigaridas, Elias Varvitsiotis, Antonios Optimization and Control Computer Science and Game Theory 90C22, 90C33, 91A05, 91A81, 65H14 We consider an algorithmic framework for two-player non-zero-sum semidefinite games, where each player's strategy is a positive semidefinite matrix with trace one. We formulate the computation of Nash equilibria in such games as semidefinite complementarity problems and develop symbolic-numeric techniques to trace generalized Lemke-Howson paths. These paths generalize the piecewise affine-linear trajectories of the classical Lemke-Howson algorithm for bimatrix games, replacing them with nonlinear curve branches governed by eigenvalue complementarity conditions. A key feature of our framework is the introduction of event points, which correspond to curve singularities. We analyze the local behavior near these points using Puiseux series expansions. We prove the smoothness of the curve branches under suitable non-degeneracy conditions and establish connections between our approach and both the classical combinatorial and homotopy-theoretic interpretations of the Lemke-Howson algorithm. |
| title | Nash equilibria in semidefinite games and Lemke-Howson paths |
| topic | Optimization and Control Computer Science and Game Theory 90C22, 90C33, 91A05, 91A81, 65H14 |
| url | https://arxiv.org/abs/2506.11940 |