We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Equilibrium Identification and Selection in Finite Games.
- Authors
Crönert, Tobias; Minner, Stefan
- Abstract
Decision-making under simultaneous competition Hardly any decision is made in isolation and most decision makers are dealing with fierce competition when trying to find the optimal decision for their problem. The expected outcome of such a competitive problem setting or the individually optimal course of action for each competitor is not evident. In a finite game, a finite set of decision makers simultaneously select their action from a finite set of strategies. In "Equilibrium identification and selection in finite games", T. Crönert and S. Minner propose a solution approach enumerating all equilibria and selecting the most likely equilibrium in finite games. The approach is targeted toward large finite games that cannot be efficiently represented in normal form. They apply their algorithm to two- and three-player knapsack and facility location and design games. Their numerical experiments show that prior approaches identifying a single equilibrium can result in unlikely outcomes. 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. Funding: T. Crönert received financial support from Deutsche Forschungsgemeinschaft (AdONE GRK2201 (project number 277991500)). Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2413.
- Subjects
DEUTSCHE Forschungsgemeinschaft; EQUILIBRIUM; NASH equilibrium; STATISTICAL decision making; GAMES; PRODUCTION quantity
- Publication
Operations Research, 2024, Vol 72, Issue 2, p816
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.2022.2413