Computational Social Choice Team(Talk by Stanisław Jerzy Kazmierowski, University of Warsaw).

【Team】Computational Social Choice Team
【Date】2026/November/9(Monday) 16:00-17:00(JST)
【Speaker】Talk by Stanisław Jerzy Kazmierowski, University of Warsaw

Title:Computing Equilibria in Conflicts with Multiple Battlefields

Abstract:
Conflicts with multiple battlefields model situations in which competitors allocate limited resources across several simultaneous contests. In the discrete-resource setting, the number of possible allocations can grow exponentially, making equilibrium computation challenging. Nevertheless, for the classical Colonel Blotto game, efficient algorithms are known that exploit two key structural properties: payoffs are additive across battlefields, and each battlefield conflict is constant-sum.

In this talk, I will discuss what happens when these assumptions are relaxed. The first departure is the Colonel Blotto game with costs, where players may incur costs for obtaining and assigning resources. Although costs destroy the apparent constant-sum structure, I will show that the game can be transformed into a strategically equivalent fixed-budget Blotto game with one additional battlefield, yielding polynomial-time Nash-equilibrium computation. The second departure concerns non-additive conflicts with multiple battlefields. I will present hardness results for best-response computation, together with a practical equilibrium-computation method based on symmetrization, a polynomial-time clash-matrix algorithm for payoff computation, and the double-oracle algorithm.