Equilibrium Identification and Selection in Finite Games

Finite games provide a framework to model simultaneous competitive decisions among a finite set of players (competitors), each choosing from a finite set of strategies. Potential applications include decisions on competitive production volumes, over capacity decisions to location selection among competitors. The predominant solution concept for finite games is the identification of a Nash equilibrium. We are interested in larger finite games, which cannot efficiently be represented in normal form. For these games, there are algorithms capable of identifying a single equilibrium or all pure equilibria (which may fail to exist in general), however, they do not enumerate all equilibria and cannot select the most likely equilibrium. We propose a solution method for finite games, in which we combine sampling techniques and equilibrium selection theory within one algorithm that determines all equilibria and identifies the most probable equilibrium. We use simultaneous column-and-row generation, by dividing the n-player finite game into a MIP-master problem, capable of identifying equilibria in a sample, and two subproblems tasked with sampling (i) best-responses and (ii) additional solution candidates. We show algorithmic performance in two-and three-player knapsack and facility location and design games and highlight differences in solutions between the proposed approach and state of the art, enabling decision makers in competitive scenarios to base their actions on the most probable equilibrium.

Automated summary

Finite games provide a framework for modeling competitive decisions, and we propose a solution method that combines sampling techniques and equilibrium selection theory to determine all equilibria and identify the most probable equilibrium. Our algorithm shows promising performance in various games.