Asymmetric Optimal Mixing and Exact Payoff-Image Compression in Bimatrix Games: Approximation and Structural Consequences at the One-Third Frontier

Abstract

This paper develops an algorithmic framework for restricted optimal mixing in rational bimatrix games and studies its implications for approximate Nash equilibrium computation near the one-third frontier. The first main contribution identifies a new asymmetric tractability regime for optimal mixing over supplied candidate strategies. When the smaller candidate family has fixed size, the best mixture over the two candidate hulls can be approximated additively in deterministic polynomial time. The method discretizes only the smaller coefficient space and optimizes the opposite side exactly by rational linear programming. It also produces an explicit interval for the restricted optimum. The paper further shows that the Lipschitz bound used by the method is sharp and that the dependence on the discretization dimension is order-optimal within exhaustive metric-net approaches. The second main contribution introduces exact payoff-image compression. If a supplied candidate dictionary has low affine dimension after projection into strategically relevant payoff space, every mixture can be replaced by a mixture supported on only a small number of supplied candidates while preserving the same strategic payoff information. As a consequence, the compressed mixture preserves regret exactly against every opponent strategy. The compression is constructive and can be implemented using exact rational computation. The paper also develops exact fixed-anchor primal-dual completion results, payoff-sensitive stability bounds, equilibrium-separation results, and a threshold-interface theorem that identifies the remaining candidate-generation requirement needed to transform restricted optimal mixing into a universal strict sub-one-third approximation algorithm. As a concrete application, the study revisits the displayed matching-bound family of Chen et al. for the Deligkas-Fasoulakis-Markakis approximation rule. After enriching the candidate set with one midpoint best response, the relevant candidate hull contains an exact equilibrium, so the displayed family no longer forms a positive-regret obstruction for the richer enriched-hull rule. This does not contradict the original tightness result; rather, it shows that tightness of a prescribed mixing rule is different from obstruction of the entire candidate hull generated by the same search phase. A separate structural appendix develops architecture-specific diagnostics for possible Nash-hardness constructions, including common-kernel neighborhoods, bi-kernel separation, rectangular saddle collapse, selector calibration, sparse-defect dilution, and related conditional no-go results. The paper does not claim a universal strict sub-one-third algorithm, a matching hardness theorem at one third, or a resolution of the deterministic approximation threshold. Its principal contribution is a theory of asymmetric optimal mixing, exact strategic compression, and systematic analysis of candidate-hull geometry in bimatrix games.