Ostrovski's transition-combinatorics conjecture for fictitious play

At least 12 years old · documented by

Let a bimatrix game have a unique, completely mixed Nash equilibrium, and let B ⁣RA\mathcal{B\!R}_A and B ⁣RB\mathcal{B\!R}_B denote the players' best-response correspondences. Assume the game has the stated transition combinatorics; in particular, suppose

B ⁣RA(ej)≠B ⁣RA(ej′)for all j≠j′,B ⁣RB(ei)≠B ⁣RB(ei′)for all i≠i′.\mathcal{B\!R}_A(e_j)\ne\mathcal{B\!R}_A(e_{j'})\quad\text{for all }j\ne j',\qquad \mathcal{B\!R}_B(e_i)\ne\mathcal{B\!R}_B(e_{i'})\quad\text{for all }i\ne i'.

Ostrovski's conjecture. Under these conditions, the Nash equilibrium does not Pareto dominate typical fictitious-play orbits. This conjecture gives a sufficient transition-combinatorial condition under which equilibrium is not expected to dominate typical fictitious-play behavior in payoff terms. The supplied text gives no resolution.

References

Primary source

Georg Ostrovski and Sebastian van Strien, “Payoff Performance of Fictitious Play”, arXiv:1308.4049 (2014).

Progress summary

Refreshed
Open

No proof, counterexample, or other public progress has been found; the conjecture remains open.

Ostrovski and van Strien stated the conjecture in their work on fictitious-play payoff performance, where it appears as Conjecture 5.45.4. It asserts that, under the specified transition-combinatorial conditions, equilibrium does not Pareto dominate typical fictitious-play orbits.

Current status (as of September 2026): The conjecture remains unsettled; no proof, counterexample, or claimed resolution is recorded in the retrieved sources.

Sources

Solutions 0

No solutions have been posted yet.