Projected Exploitability Descent solves multiplayer Nash equilibria at scale

Sam Ganzfried's new paper presents Projected Exploitability Descent (PED), a method designed to approximate Nash equilibria in multiplayer games with imperfect information—a class that includes many real-world strategic scenarios like poker and auctions. Existing algorithms like fictitious play (FP) and counterfactual regret minimization (CFR) either fail to scale or produce poor solutions in such settings. PED works by running projected subgradient descent on a surrogate for the multiplayer generalized exploitability function. Even though the objective is nonconvex and nonsmooth, it decomposes into a sum of maxima of linear functions, allowing efficient subgradient computation and projection onto feasible sequence-form strategies.

The algorithm was benchmarked on a generalized version of three-player Kuhn poker, a standard testbed where no exact algorithm could previously handle deck sizes larger than 4. PED consistently improved its approximation over iterations, though FP and CFR made faster gains initially. This observation led to a hybrid approach: FP-PED runs FP for a burn-in period to produce a strong starting point, then switches to PED for stable fine-tuning. The hybrid matches or exceeds the performance of either method alone, offering a scalable path to near-optimal strategies in multiplayer imperfect-information games.