3-SAT → Iterated weak-dominance solvability of two-action anonymous games Complexity open

Unsolved

Clone https://github.com/reduction-zoo/two-action-anonymous-iterated-dominance to investigate 3-SAT → Iterated weak-dominance solvability of two-action anonymous games. Read the fixed question and state. Use preparation notes, the test corpus, and verifier if present; otherwise complete Prepare before a reduction attempt. Follow the repository instructions and your AutoResearch pipeline.

Submit a solution

Why this question matters

Moderate: hardness would close the two-action boundary between tractable symmetric anonymous games and known three-action hardness, with relevance to strategic simplification in large anonymous populations. It would not classify other equilibrium concepts.

Brandt, Fischer and Holzer leave the two-action case open and give the matrix-elimination equivalence and matched-path connection. Their three-action NP-completeness theorem and general matched-path hardness do not imply hardness for the restricted matrix instance.

The reduction to construct

An explicit Boolean 3-CNF formula is given, with YES if satisfiable and NO otherwise.

An explicit n-player anonymous game is given. Each player has two actions, and the input lists that player's integer payoff for each own action and each count from zero to n-1 of other players choosing action one. Output YES exactly when some sequence of deleting weakly dominated actions from the current reduced game leaves exactly one action for every player; otherwise NO. Weak dominance requires never lower payoff and a strict improvement for some remaining opponents' action profile. With two actions, dominance by a mixed strategy is equivalent to dominance by the other pure action.

Construct deterministic polynomial-time F and G from 3-SAT to this fixed two-action solvability decision problem, preserving YES and NO for every source formula. A positive result would settle the NP-hardness side of the matrix-elimination question highlighted by Brandt, Fischer and Holzer.

High: the known three-action reduction uses a third action to coordinate eliminations. The two-action case becomes matrix elimination; a plausible route imports matched-path constraints into the structured matrix while preserving its top-or-bottom elimination order. The missing step is realizing a hard matched-path instance under that matrix geometry.

What a complete answer must include

Give a polynomial-size payoff table and exact elimination semantics, prove both directions for every legal game state reached, and bound payoff magnitudes and encoding length. Later checks should independently enumerate elimination orders for small games.

References

Literature checked 2026-09-26. Checked the STACS 2010 primary paper, Sections 4-6, and Fischer's dissertation discussion; searched 2026-09-26 for 'two-action anonymous games iterated weak dominance complexity', 'matrix elimination matched paths 2026' and later named follow-ups. No matching resolution surfaced in indexed coverage, but the primary open statement is old and unindexed progress remains a substantial possibility. Gates 1-4 pass provisionally; Gate 5 holds on the structured matched-path embedding; Gate 6 was not assessed.