Efficient Method for Finding Optimal Strategies in Chopstick Auctions with Uniform Objects Values
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_ | 1866917621769699328 |
|---|---|
| author | Kaźmierowski, Stanisław Dziubiński, Marcin |
| author_facet | Kaźmierowski, Stanisław Dziubiński, Marcin |
| contents | We propose an algorithm for computing Nash equilibria (NE) in a class of conflicts with multiple battlefields with uniform battlefield values and a non-linear aggregation function. By expanding the symmetrization idea of Hart [9], proposed for the Colonel Blotto game, to the wider class of symmetric conflicts with multiple battlefields, we reduce the number of strategies of the players by an exponential factor. We propose a clash matrix algorithm which allows for computing the payoffs in the symmetrized model in polynomial time. Combining symmetrization and clash matrix algorithm with the double oracle algorithm we obtain an algorithm for computing NE in the models in question that achieves a significant speed-up as compared to the standard, LP-based, approach. We also introduce a heuristic to further speed up the process. Overall, our approach offers an efficient and novel method for computing NE in a specific class of conflicts, with potential practical applications in various fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16799 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Method for Finding Optimal Strategies in Chopstick Auctions with Uniform Objects Values Kaźmierowski, Stanisław Dziubiński, Marcin Computer Science and Game Theory 91A68 G.2.1; J.4 We propose an algorithm for computing Nash equilibria (NE) in a class of conflicts with multiple battlefields with uniform battlefield values and a non-linear aggregation function. By expanding the symmetrization idea of Hart [9], proposed for the Colonel Blotto game, to the wider class of symmetric conflicts with multiple battlefields, we reduce the number of strategies of the players by an exponential factor. We propose a clash matrix algorithm which allows for computing the payoffs in the symmetrized model in polynomial time. Combining symmetrization and clash matrix algorithm with the double oracle algorithm we obtain an algorithm for computing NE in the models in question that achieves a significant speed-up as compared to the standard, LP-based, approach. We also introduce a heuristic to further speed up the process. Overall, our approach offers an efficient and novel method for computing NE in a specific class of conflicts, with potential practical applications in various fields. |
| title | Efficient Method for Finding Optimal Strategies in Chopstick Auctions with Uniform Objects Values |
| topic | Computer Science and Game Theory 91A68 G.2.1; J.4 |
| url | https://arxiv.org/abs/2403.16799 |