Sharp Bounds for Selector Advice and Oblivious Equilibrium Search
Abstract
Ko's tournament argument recognizes a P-selective language with quadratic advice. We determine the leading coefficient in the selector-query model. On $n$-bit inputs, $n^2/4+O(n)$ ordinary advice bits and $n$ nonadaptive comparisons suffice. Some cuts require $n^2/4-O(n\log n)$ bits even for randomized decoders with adaptive access to individual-degree-two extensions. At degree one the exact fixed advice width is $n+1$. Assuming exponential hardness in $\mathrm E$ against SAT-gate circuits, the quarter bound holds in deterministic polynomial time for every P-selective language. The same fixed point determines the cost of searching for an approximate equilibrium before seeing the payoffs. In an $N$-action symmetric constant-sum game with payoffs in $[0,1]$, let $P$ be the best worst-case probability that one game-independent proposal is an additive $ε$-Nash equilibrium. For each fixed $0<ε<1/2$, \[ -\log_2 P=(1+o(1))\, \frac{(\log_2 N)^2}{4[1-H_2(1/2+ε)]}. \] The algorithm draws uniform actions and proposes their empirical distribution for both players. The lower bound allows arbitrary mixed profiles and $N^{o(1)}$ adaptive payoff inspections before the proposal. For all symmetric two-player games, including general-sum games, the sharp exponent is $(\ln 2/8+o(1))(\log_2 N)^2/ε^2$ when $ε\to0$ and $\log(1/ε)=o(\log N)$. For security strategies in arbitrary zero-sum games the exponent is four times larger, and sampling an optimal strategy attains it. The common mechanism counts successful tuples. A fixed point makes them capture constant sampling probability while controlling a power moment of their distribution.