Computing strategies that account for a player’s own future mistakes

A strategy can look optimal only because it assumes flawless decisions later. In sequential games, that assumption matters even when mistakes become vanishingly unlikely. A new paper by Sam Ganzfried presents an algorithm for computing an equilibrium refinement that explicitly accounts for such mistakes at each decision.

The paper, Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games, was submitted to arXiv on November 4, 2026. This first-version preprint offers a mathematical tractability result, not experimental evidence about human behavior or measured improvements in deployed systems.

What counts as a worse mistake?

Ordinary Nash equilibrium can leave behavior arbitrary after histories assigned zero probability. Refinements based on “trembles” instead consider strategies in which every available action has positive probability, then examine what survives as those probabilities shrink.

Ganzfried studies extensive-form proper equilibrium in the agent normal form. An information set—a collection of situations the acting player cannot distinguish—is treated as a separate decision-making agent sharing that player’s payoff. To compare two actions there, all other local choices remain fixed, including the same player’s future behavior.

The precise restriction is that an action with a strictly lower expected payoff must receive at most epsilon times the probability of a better action, where epsilon is positive and below one. An exact proper equilibrium is a limit of such fully mixed profiles as epsilon approaches zero. Equal-payoff actions need not be arbitrarily ranked.

That differs from normal-form properness, which ranks complete contingent plans. It also differs from quasi-properness, which evaluates choices using optimal subsequent play by the acting player rather than holding that player’s future mistakes fixed.

A small example with a consequential distinction

The paper illustrates the difference with a game in which only Player 1 makes decisions; Player 2 receives the negative payoff. Player 1 can choose Out and receive 1, or choose In and then select G for 1 or B for 0.

With any positive probability of subsequently choosing B, In yields less than Out. Agent-form properness therefore drives the initial choice toward Out, while specifying G if the second decision is reached. By contrast, the paper constructs a normal-form proper family converging to In followed by G. Under optimal continuation, In and Out both yield 1, so that behavior is also compatible with quasi-properness.

This is a formal counterexample separating equilibrium concepts, not an observed tendency for people to avoid risky decisions. It explains why existing algorithms for neighboring refinements do not automatically solve this problem.

How the algorithm works

At each information set with m actions, the method starts from normalized weights proportional to 1, epsilon, and successive powers through epsilon to the power m minus one. It allows all permutations of those weights and all mixtures of those permutations—a geometric object called a permutahedron. Maximizing a local payoff over this set enforces the required probability penalty for inferior actions.

Listing every permutation would be costly. Instead, the algorithm represents the restrictions using a scaled doubly stochastic matrix, introducing m squared nonnegative auxiliary variables per information set. It embeds these constraints in sequence form, which tracks players’ action-sequence realization weights rather than enumerating complete plans. A constrained zero-sum saddle point then delivers an epsilon-proper profile.

The exact answer requires more than selecting a tiny numerical epsilon. The proof constructs a rational threshold below which relevant determinants retain their signs, selects a feasible linear-system basis that persists throughout that interval, and represents its solution using rational functions.

Finally, it takes limits of behavioral probabilities as ratios of realization weights. This order matters: both the weight of reaching a decision and the weight of taking an action there may approach zero. Their ratio can still determine a definite continuation; taking separate limits would lose that information.

What the result establishes—and what it does not

The theorem covers finite, explicitly represented two-player zero-sum game trees with perfect recall and rational payoffs and chance probabilities. It promises a deterministic algorithm with running time polynomial in the input’s binary length, producing one exact equilibrium with rational behavioral probabilities of polynomial total encoding length. The paper also proves that the output is a Nash equilibrium of the original two-player game.

Polynomial complexity here is not a practical speed guarantee: it is measured against the explicit tree, not a more compressed description. The paper reports no implementation benchmarks, does not establish strongly polynomial time, and leaves efficient implementation to future work. General-sum games and enumeration of all proper equilibria are outside its result.

There is also a substantive modeling boundary. If chance makes an information set impossible to reach, all unconditional action values there coincide. The algorithm still specifies behavior, but claims no conditional optimality there. Nor does the author claim this refinement is universally superior to alternatives. The advance is exact computation for a particular classical model of mistakes, not validation of that model as a description of economic behavior.