Regret-Based Nash Equilibrium Sorting Genetic Algorithm for Combinatorial Game Theory Problems with Multiple Players

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)

Abstract

We introduce a regret-based fitness assignment strategy for evolutionary algorithms to find Nash equilibria in noncooperative simultaneous combinatorial game theory problems where it is computationally intractable to enumerate all decision options of the players involved in the game. Applications of evolutionary algorithms to noncooperative simultaneous games have been limited due to challenges in guiding the evolutionary search toward equilibria, which are usually inferior points in the objective space. We propose a regret-based approach to select candidate decision options of the players for the next generation in a multipopulation genetic algorithm called Regret-Based Nash Equilibrium Sorting Genetic Algorithm (RNESGA). We show that RNESGA can converge to multiple Nash equilibria in a single run using two-and threeplayer competitive knapsack games and other games from the literature. We also show that pure payoff-based fitness assignment strategies perform poorly in three-player games.

Original languageEnglish (US)
Pages (from-to)1-32
Number of pages32
JournalEvolutionary Computation
Volume2022
DOIs
StatePublished - Aug 12 2022

All Science Journal Classification (ASJC) codes

  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Regret-Based Nash Equilibrium Sorting Genetic Algorithm for Combinatorial Game Theory Problems with Multiple Players'. Together they form a unique fingerprint.

Cite this