Search Results for « Zero-sum Imperfect Information Games »

Sequentialdecision-making under imperfect information is naturally modeled as an extensive-form game, where the Nash equilibrium serves as the predominant solution concept for two-player zero-sum settings. Counterfactual regret minimization (CFR) is a widely used framework for this purpose, iteratively reducing regret through regret matching so that the average strategy approaches a Nash equilibrium. However, the convergence efficiency of CFR remains a practical challenge. In this work, we refine and reformulate an advantage-based exponential weighting scheme, Exponential CFR (ExpCFR), which accelerates convergence by allocating greater attention to highly profitable actions during the regret-accumulation process. Building on this heuristic, we further introduce Pob-CFR, a framework that integrates population-based evolutionary training with CFR. Pob-CFR maintains a diverse population of heterogeneous CFR variants, periodically evaluating them by exploitability and replacing underperforming individuals with the elite to synchronize strategy exploration. Systematic evaluations across five benchmark games demonstrate that these methods accelerate early-to-mid convergence compared to standard CFR baselines. Furthermore, within the evaluated benchmarks, the relative advantage of the population-based architecture appears more evident in the games with larger strategic complexity.

We consider bi-matrix games between a row player and a column player. The row player’s pay-off depends on a part that is determined by the strategy choices of both players plus a part that depends solely on what is chosen by the column player plus another part that depends solely on what is chosen by the row player. Similarly, the column player’s pay-off depends on a part that is determined by the strategy choices of both players plus a part that depends solely on what is chosen by the row player plus another part that depends solely on what is chosen by the column player. The sum of the parts of the payoffs that simultaneously depend on the strategies of both players is equal to zero. We call such games, additively-separable partially zero-sum bi-matrix games. We show that a strategy profile is an equilibrium for such a game if and only if it is an equilibrium for the two-person additively-separable sum game obtained by ignoring the part of the pay-offs determined by the strategy chosen by the opponent. Thus, an equilibrium for the kind of game we introduce here exists and the set of equilibria of any such game is equal to the projection of the set of solutions of a corresponding linear programming problem into the set of all strategy profiles. In the special case, where the pay-offs to a player in an additively-separable partially zero-sum bi-matrix game do not include a part that solely depends on the player’s own strategy, the set of equilibria for such games coincide with the set of equilibria for the matrix (zero-sum) game determined entirely by interdependent pay-offs.