The Computational Complexity of Variational Inequalities and Applications in Game Theory
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910687232524288 |
|---|---|
| author | Kapron, Bruce M. Samieefar, Koosha |
| author_facet | Kapron, Bruce M. Samieefar, Koosha |
| contents | We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-completeness. Examining applications in computational game theory, we specifically focus on two key concepts: resilient Nash equilibrium, and multi-leader-follower games -- domains traditionally known for the absence of general solutions. In the presence of standard assumptions and relaxation techniques, we formulate problem versions for such games that are expressible in terms of variational inequalities, ultimately leading to proofs of PPAD-completeness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04392 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Computational Complexity of Variational Inequalities and Applications in Game Theory Kapron, Bruce M. Samieefar, Koosha Computational Complexity Computer Science and Game Theory 68Q17 F.2 We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-completeness. Examining applications in computational game theory, we specifically focus on two key concepts: resilient Nash equilibrium, and multi-leader-follower games -- domains traditionally known for the absence of general solutions. In the presence of standard assumptions and relaxation techniques, we formulate problem versions for such games that are expressible in terms of variational inequalities, ultimately leading to proofs of PPAD-completeness. |
| title | The Computational Complexity of Variational Inequalities and Applications in Game Theory |
| topic | Computational Complexity Computer Science and Game Theory 68Q17 F.2 |
| url | https://arxiv.org/abs/2411.04392 |