A Genetic Algorithm approach to Asymmetrical Blotto Games with Heterogeneous Valuations

Abstract:

Blotto Games are a popular model of multi-dimensional strategic resource allocation. Two players allocate resources in different battlefields in an auction setting. While competition with equal budgets is well understood, little is known about strategic behavior under asymmetry of resources, as this situation is hardly solvable with analytical methods. We introduce a genetic algorithm, a search heuristic inspired from biological evolution, interpreted as a mechanism of social learning, to solve this problem. Through multi-agent reinforcement learning, the algorithm evaluates the performance of random initial strategies. Most performant strategies are combined to create more performant strategies. Mutations allow the algorithm to efficiently scan the space of possible strategies, and consider a wide diversity of deviations. Iterating this process improves strategies until no profitable deviation exists. This method allows to identify optimal solutions to problems involving very large strategy spaces, such as Blotto games. We show that our genetic algorithm converges to the analytical Nash equilibrium of the symmetric Blotto game. We present the solution concept it provides for asymmetrical Blotto games. It notably sees the emergence of ``guerilla warfare'' strategies, consistent with empirical and experimental findings. The player with less resources learns to concentrate its resources to compensate for the asymmetry of competition. When players value battlefields heterogeneously, counter strategies and bidding focus is obtained in equilibrium. These features are consistent with empirical and experimental findings, and provide a learning foundation for their existence. These results open towards a more complete characterization of solutions in strategic resource allocation games. It places genetic algorithms as a search method of interest in game theoretical problems, to achieve further theoretical and operational achievements.