References & Citations
Computer Science > Computer Science and Game Theory
Title: Efficient Method for Finding Optimal Strategies in Chopstick Auctions with Uniform Objects Values
(Submitted on 25 Mar 2024)
Abstract: 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.
Submission history
From: Stanisław Kaźmierowski [view email][v1] Mon, 25 Mar 2024 14:19:48 GMT (230kb,D)
Link back to: arXiv, form interface, contact.