Counterfactual regret minimization (CFR), and the newest variant CFR+, have been a central component in several recent milestones in solving imperfect-information extensive-form games. Bowling et al. used CFR+ to near-optimally solve heads-up limit Texas hold’em. CFR variants, along with other scalability techniques, have been succesfully used to create AIs that beat professional poker players at the larger game of heads-up no-limit Texas hold’em.

As a generic term, correlated equilibrium denotes a family of solution concepts whereby a mediator that can recommend behavior, but not enforce it, complements the interaction of rational agents. Before the game starts, the mediator--also called a correlation device--samples a tuple of normal-form plans (one for each player) from a publicly known correlated distribution. The mediator then proceeds to privately ask each player whether they would like to commit to playing according to the plan that was sampled for them. Being part of an equilibrium, the correlated distribution must be such that no player can benefit from not following the recommendations, assuming all other players follow. Coarse correlated equilibrium differs from correlated equilibrium in that players must decide whether or not to commit to playing according to the recommendations of the mediator before observing such recommendations.

In recent years, computational studies on imperfect-information games have largely focused on two-player zero- sum games. In this specific setting, AI techniques have achieved remarkable results, such as defeating top human specialist professionals in heads-up no-limit Texas hold’em poker. Fewer results are known for settings with more than two players. Yet, many strategic interactions provide players with incentives to team up. In some cases, players may have a similar goal and may be willing to coordinate and share their final reward. Consider, as an illustration, the case of a poker game with three or more players, where all but one of them collude against an identified target player and will share the winnings after the game. In other settings, players might be forced to cooperate by the nature of the interaction itself. This is the case, for instance, in the card-playing phase of Bridge, where a team of two players, called the “defenders”, plays against a third player, the “declarer”. Situations of a team ganging up on a player are, of course, ubiquitous in many non-recreational applications as well, such as war where the colluders do not have time or means of communicating during battle, collusion in bidding, where communication during the auction is illegal, coordinated swindling in public, and so on.

Extensive-form games are a classical model of strategic interaction of rational agents, with a rich variety of important applications. Nash Equilibria (NEs), despite being the most celebrated solution concept in game theory, can be unsatisfactory if used to plan a strategy when playing against imperfectly-rational players in extensive-form games. This poses a problem, e.g., when designing an artificial intelligence bot playing against humans, as NEs may be unable to capitalize on opponents' mistakes in branches of the game tree that are not reached along the equilibrium path. Extensive-form perfect equilibria (EFPEs) are refinements of NEs. They benefit form the same strong theoretical guarantees of NEs, yet exhibit a better behavior that can often make a big difference in practice. In 2017, we proved that finding EFPEs in two-player games has—in theory—the same cost (in terms of computational complexity) as finding any unrefined Nash equilibrium, solving a long-standing theoretical problem and showing that EFPEs can have concrete potential. In follow-up work, we further reduced the gap between theory and practice by providing approximation methods and well-engineered exact methods for computing EFPEs. Unfortunately, the practical applicability of EPFEs today still lags behind theory. I propose to continue investigating theoretical and practical solutions that can push a wider adoption of EFPEs, hopefully to the point where there will be no reason not to prefer them over NEs.