Computing equilibria in conflicts with multiple battlefields and majoritarian objectives

Prelegent(ci)

Stanisław Kaźmierowski

Afiliacja

Instytut Informatyki, UW

Termin

2 grudnia 2021 10:15

Pokój

p. 4050

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

We consider computation of Nash equilibria in conflicts with multiple battlefields and majoritarian objectives. Conflicts with multiple battlefields are zero-sum two player games with succinct representation: the number of strategies of each player is exponential with respect to the size of the game description. The game is similar to the colonel Blotto game with one significant difference, that is the objective of each player is to win more than half of battlefields. The game, therefore, is not bilinear and the computational complexity of finding its Nash equilibria is currently unknown. We reduce the size of the game by considering symmetrized mixed strategies, which involve mixing on all the permutations of battlefields. We propose a polynomial time algorithm for computing payoffs for symmetrized mixed strategy profiles and use of the Multiplicative Weights Update algorithm for computing ε-equilibria of the game. Although still operating in exponential time with respect to the game parameters, these methods allow for computing significantly larger instances of the game than the LP based approach and are suitable for implementation on a computational cluster.

---