betaFeedback

WorksComputer Science

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 nn-bit inputs, n2/4+O(n)n^2/4+O(n) ordinary advice bits and nn nonadaptive comparisons suffice. Some cuts require n2/4−O(nlog⁡n)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+1n+1. Assuming exponential hardness in E\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 NN-action symmetric constant-sum game with payoffs in [0,1][0,1], let PP be the best worst-case probability that one game-independent proposal is an additive εε-Nash equilibrium. For each fixed 0<ε<1/20<ε<1/2, −log⁡2P=(1+o(1)) (log⁡2N)24[1−H2(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 No(1)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⁡2N)2/ε2(\ln 2/8+o(1))(\log_2 N)^2/ε^2 when ε→0ε\to0 and log⁡(1/ε)=o(log⁡N)\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.

Introduction

A selector is an algorithm that chooses one of two strings and chooses a member of a language LL whenever either string belongs to LL. Suppose the algorithm runs in polynomial time. How much advice, common to all nn-bit inputs, suffices to decide membership in LL? Ko’s argument gives a short proof of a quadratic upper bound [14]. View the nn-bit strings as the vertices of a tournament, and direct each edge from the chosen string to the other one. Every member beats every nonmember. Among any remaining members, some vertex is beaten by at least half of them when equality counts. Store that vertex and repeat on the members it fails to certify. The resulting list of at most n+1n+1 names recognizes LL at length nn. Its cost comes from writing down nn bits per name.

Prior work. Selman introduced P-selective sets as the polynomial-time analogue of the semirecursive sets [22]. Ko’s quadratic bound has remained the deterministic upper bound. Nondeterministic interpreters do much better: Hemaspaandra and Torenvliet showed that n+1n+1 advice bits suffice for NP interpreters and that nn bits do not [12]. A linear deterministic bound therefore follows from P = NP, and Hemaspaandra, Hempel and Nickelsen derived it from the assumption that every P-selective language has an associative selector [11]. Domination numbers of tournaments save only a lower-order term: the bound of Szekeres and Szekeres [21, 18] gives n2−nlog⁡2n+O(n)n^2-n\log_2 n+O(n) bits. In the comparison model, our earlier work [5 Theorems 5.5 and 5.6] gave a lower bound with leading coefficient 1/41/4 for polynomially many adaptive Boolean queries and an unrestricted-time upper bound with coefficient 1/21/2.

We close this interval, extend the lower bound to algebraic queries of individual degree two, and bring the upper bound to polynomial time under a standard derandomization hypothesis. The hypothesis cannot be used to go further by any relativizing argument.

The model. Put N=2nN=2^n. A legal cut consists of a tournament EE on {0,1}n\{0,1\}^n and a marked set PP all of whose vertices beat every vertex outside PP. Write x≻yx\succ y for E(x,y)=1E(x,y)=1 and set E(x,x)=0E(x,x)=0. An asymmetric selector induces this table by sorting its two arguments before evaluating it. A decoder receives an input vertex, advice, and access to the table. Its program is independent of the marked tournament. An algebraic query specifies a finite field with its canonical encoding and a point of F2n\mathbb{F}^{2^n}. The answer is the value of one fixed polynomial per field agreeing with EE on the Boolean cube. Degree bounds are per variable. All queries are classical. Between queries we allow unrestricted computation except in results explicitly specifying polynomial time.

Theorem 1.1 (The ordinary advice threshold). Every legal cut has a zero-error decoder using n2/4+O(n)n^2/4+O(n) ordinary advice bits and at most nn nonadaptive Boolean comparisons. One computable decoder works for all lengths and cuts. Conversely, for each fixed randomized interpreter making polynomially many adaptive queries and every sufficiently large nn, some cut and some fixed degree-two extensions require n2/4−Oq(nlog⁡n)n^2/4-O_q(n\log n) ordinary advice bits for pointwise error 1/31/3.

Here Oq(⋅)O_q(\cdot) allows the constant to depend on the polynomial query bound. The advice in the lower bound may depend on the entire realized oracle, including its extensions, and the decoder’s computation between queries is unrestricted. The lower bound is therefore information-theoretic, and the upper bound matches it with Boolean comparisons alone.

Theorem 1.2 (Degree one). With direct access to the canonical multilinear extensions, deterministic polynomial time and n+1n+1 fixed-width advice bits suffice for exact recognition. This width is optimal even with the entire table available.

The decoder reads deg⁡+(x)\deg^+(x) from row evaluations: x∈Px\in P precisely when deg⁡+(x)≥N−∣P∣\deg^+(x)\ge N-|P|. One public odd prime greater than NN suffices for a single query; a uniform algorithm uses O(n/log⁡(n+1))O(n/\log(n+1)) small-prime queries. Thus multilinear access gives a deterministic decoder exactly the advice that NP interpreters need [12], while access of individual degree two already costs the full quarter. In the language of Aaronson and Wigderson [AW08], the advice complexity of selectors is a natural quantity on which algebraic query access of degree one and of degree two separate quadratically. Theorems 1.1 and 1.2 are proved in § 2, § 6 and § 7.

Oblivious equilibrium search. Suppose two players have NN actions each. Before seeing the payoffs, we choose a distribution on pairs of mixed strategies. What is the greatest probability with which one draw is an approximate Nash equilibrium, even for the worst game? The question measures the information needed to name a successful strategy. With access to the full payoff matrix an explicit zero-sum game can be solved by linear programming.

Daskalakis and Papadimitriou [DP09] called such procedures oblivious: the algorithm samples a fixed distribution on pairs of mixed strategies, and the game is used only to check whether the sample is an approximate equilibrium. Sampling arguments of Althöfer [2] and Lipton and Young [16] for zero-sum games, and of Lipton, Markakis and Mehta [17] for bimatrix games, give empirical strategies of length O(log⁡N/ϵ2)O(\log N/\epsilon^2). A uniform draw from the resulting list of profiles succeeds with probability at least 2−O(n2/ϵ2)2^{-O(n^2/\epsilon^2)}, where n=log⁡2Nn=\log_2 N. Babichenko, Barman and Peretz [4] studied simple approximate equilibria in games with many players.

Daskalakis and Papadimitriou [DP09, extended version, proof of Theorem 4, Claim 3] show that finding a δ\delta-well-supported equilibrium can require Ω(2(0.8−34δ)n2)\Omega(2^{(0.8-34\delta)n^2}) oblivious proposals in expectation for bimatrix games with payoffs in [−1,1][-1,1]. Setting the negative payoffs in their construction to zero gives the same coefficient 0.8−34ϵ0.8-34\epsilon for ordinary additive regret on our [0,1][0,1] scale (Remark A.7). Kothari and Mehta [13] proved a 2Ω(n2)2^{\Omega(n^2)} lower bound for ordinary regret at a sufficiently small fixed error, even with access to a sum-of-squares relaxation and a partial verification oracle. For symmetric constant-sum games we determine the sharp coefficient for every fixed 0<ϵ<1/20<\epsilon<1/2. It grows as (ln⁡2)/(8ϵ2)(\ln2)/(8\epsilon^2) as ϵ→0\epsilon\to0.

Theorem 1.3 (Equilibrium search). Let Pϵ(N)P_\epsilon(N) be the optimal worst-case success probability of one oblivious proposal for symmetric constant-sum games, normalized so Aij+Aji=1A_{ij}+A_{ji}=1 and Aij∈[0,1]A_{ij}\in[0,1]. Put n=log⁡2Nn=\log_2N and cϵ=1−H2(1/2+ϵ)c_\epsilon=1-H_2(1/2+\epsilon). For fixed 0<ϵ<1/20<\epsilon<1/2,

−log⁡2Pϵ(N)=n24cϵ+Oϵ(nlog⁡n).-\log_2 P_\epsilon(N)=\frac{n^2}{4c_\epsilon}+O_\epsilon(n\log n).

The same leading exponent holds for proposals with No(1)N^{o(1)} adaptive payoff queries, and for the logarithm of the smallest list that works for every game. If ϵ→0\epsilon\to0 and log⁡(1/ϵ)=o(n)\log(1/\epsilon)=o(n), the sharp exponent for oblivious proposals in the class of all symmetric bimatrix games is (ln⁡2/8+o(1))n2/ϵ2(\ln2/8+o(1))n^2/\epsilon^2.

The factor four has a direct comparison. A column strategy is ϵ\epsilon-secure in a value-1/21/2 game if every pure row earns at most 1/2+ϵ1/2+\epsilon against it. For this same task, with the value known, the logarithmic cost of oblivious search has leading term n2/(4cϵ)n^2/(4c_\epsilon) in symmetric constant-sum games and n2/cϵn^2/c_\epsilon in arbitrary zero-sum payoff matrices (Theorem A.3). The second exponent is what sampling an optimal strategy achieves, as in the arguments of Althöfer and of Lipton and Young, so their sampling is exactly optimal for oblivious search in zero-sum games. Symmetry saves a factor four, the same factor that separates Ko’s bound from Theorem 1.1.

The proof chooses a distribution on actions and a sample length rr together. With this distribution, at least half the samples give a secure strategy, and at least 2ϵr2−O(r)2^{\epsilon r^2-O(r)} different ordered samples succeed. This offsets cϵr2c_\epsilon r^2 of the nrnr bits needed to specify one sample. The worst length is near n/(2cϵ)n/(2c_\epsilon). Conversely, a tournament with a hidden set of about N\sqrt{N} winning actions makes this cost necessary even for proposals using arbitrary real probabilities. § 3 gives the sampler, and Appendix § 10 proves the lower bound and the extensions.

Bounded error and the cost of confidence. An ordinary advice word is fixed before the random tape is drawn, so repeating a bounded-error decoder on fresh coins reuses the same word. This is why the lower bound in Theorem 1.1 already holds at error 1/31/3. Advice that may depend on the realized public tape behaves differently: at constant error it permits linear advice [3]. How the cost of such advice, and of coherent quantum advice, grows as the error decreases is the subject of a separate paper. Nothing here depends on it.

Polynomial time. Let H denote the hypothesis that for some c>0c > 0 a Boolean function in E=DTIME⁡(2O(n))E = \operatorname{DTIME}(2^{O(n)}) requires circuits of size 2cn2^{cn} with SAT gates on all sufficiently large input lengths. Our efficient decoder uses the logarithmic-seed generator for SAT-gate tests supplied by this hypothesis [15, 23].

Theorem 1.4 (Efficient recognition under H). Under H, every P-selective language LL has a deterministic polynomial-time decoder using n2/4+OL(n)n^2/4 + O_L(n) ordinary advice bits. If the smaller nonempty side at length nn has KK vertices, the decoder makes at most ⌈log⁡2K⌉+1≤n\lceil\log_2 K\rceil+ 1 \le n nonadaptive selector comparisons.

The computable and polynomial-time decoders thus attain the same additive order above n2/4n^2/4. The constant hidden in OL(n)O_L(n) may depend on the fixed selector. Earlier conditional improvements of Ko’s bound assume P = NP or associative selectors. Theorem 1.4 needs only a circuit lower bound of the kind used to derandomize Arthur–Merlin protocols. The next theorem shows that this is the end of the line for arguments that treat the selector as an oracle.

Theorem 1.5 (Relativized sharpness). There are an oracle OO and a degree-two extension family O~\widetilde{O} of it such that HOH^O holds, every POP^O-selective language L′L' has a polynomial-time decoder relative to OO with n2/4+OL′(n)n^2/4 + O_{L'}(n) advice bits, and some POP^O-selective language is not in BPP⁡O~/⌊cn2⌋\operatorname{BPP}^{\widetilde{O}}/\lfloor cn^2\rfloor for any c<1/4c < 1/4.

Consequently no relativizing proof can derive advice (1/4−δ)n2(1/4-\delta)n^2 for P-selective languages from H, and neither can a proof that algebrizes in the sense of Aaronson and Wigderson [AW08] with extensions of individual degree two. Section 9 gives the construction; it is Theorem 9.1.

Where the quarter comes from

The strong components of a tournament are totally ordered, and a legal cut falls between two consecutive ones. Only the smaller of these two components matters.

Theorem 1.6 (Boundary components). For a nontrivial legal cut let BB be the size of the smaller of the two strong components adjacent to it, v=log⁡2Bv = \log_2 B and u=min⁡{v,n/2}u = \min\{v,n/2\}. A computable decoder uses u(n−u)+O(n)u(n-u) + O(n) advice bits. For every polynomial-query randomized decoder with degree-two access, every large nn and every 3≤B≤2n−13 \le B \le2^{n-1}, some cut with this boundary size requires u(n−u)−Oq(nlog⁡n)u(n-u)-O_q(n\log n) bits at error 1/31/3. For a P-selective language, a deterministic polynomial-time decoder needs n(⌊v⌋+1)+O(1)n(\lfloor v\rfloor+ 1) + O(1) bits unconditionally and u(n−u)+OL(n)u(n-u) + O_L(n) bits under H.

When log⁡n≪v=o(n)\log n \ll v = o(n) the cost is therefore (1+o(1))nv(1+o(1))nv, and it is attained in polynomial time with no hypothesis. The quarter coefficient already appears at B=2⌈n/2⌉B = 2^{\lceil n/2\rceil}, and larger boundary components do not raise it. The same exponent governs tournaments without any reference to advice (Section 4). In the worst case a random tt-subset of an NN-vertex tournament dominates with probability 2−(1/4+o(1))log⁡2(N/t)2^{-(1/4+o(1))\log^2(N/t)}, and every tournament on {0,1}n\{0,1\}^n has a dominating set of Kolmogorov complexity n2/4+O(n)n^2/4 + O(n), which is tight. The lower bound embeds the hard instances of Theorem 1.1 under a public block of padding vertices joined to them by two private edges (Section 8).

Orient the smaller side SS so that it beats its complement. A list of vertices of SS covers SS if every x∈Sx \in S equals or beats an entry. A uniform ambient rr-tuple has nrnr bits in its description. If at least 2r2−O(r)2^{r^2-O(r)} different tuples cover SS, its chance of being a cover is at least 2−r(n−r)−O(r)2^{-r(n-r)-O(r)}. A common list of candidate tuples can then serve all tournaments, and it costs only r(n−r)+O(n)r(n-r)+O(n) bits to name a cover in that list. The maximum of r(n−r)r(n-r) is n2/4n^2/4. The central point is to find a length rr at which both coverage and multiplicity hold.

For example, if a vertex loses to every other vertex of SS, every cover must contain it. Sampling uniformly from SS can take order ∣S∣|S| draws just to hit this one vertex. We give a vertex more weight when the current distribution of anchors is likely to miss it. If sν(x)s_\nu(x) is the miss probability, the fixed point has weights p(x)∝sν(x)Jp(x) \propto s_\nu(x)^J and uses a slight smoothing ν\nu of pp. The normalization chooses JJ so that r=⌈J⌉r=\lceil J\rceil independent samples cover with constant probability. The tournament identity also controls ∑xν(x)1+1/J\sum_x \nu(x)^{1+1/J}. Hölder’s inequality then turns probability mass on covers into the required count. Section 2 gives the proof.

The same count applies to any subtournament whose covers recognize the cut, in particular to a boundary component, which gives the upper bound in Theorem 1.6.

To recover a cover in polynomial time, testing whether an entire tuple covers SS would require certifying a statement about every vertex. Instead the decoder’s existence proof certifies how much of the remaining weight a short block of anchors covers. This is a lower bound on the size of a nondeterministically recognized set. One potential pays for uncovered weight and another for the total description length. A lower cutoff on vertex weights sets the block size: larger blocks save seeds, and the cutoff keeps the necessary counting precision inverse polynomial. The construction uses O(n/log⁡n)O(n/\log n) blocks. Their seed and length fields therefore cost OL(n)O_L(n) bits altogether. The decoder evaluates only the resulting short descriptions (Section 5).

Why the lower bound survives adaptive queries

Partition the vertices into 2m2^m buckets. Each contains a hidden vertex with a fair membership bit. Finding such a vertex in another bucket means locating its (n−m)(n-m)-bit suffix. An input’s label can remain ambiguous until it has been compared to several other hidden vertices. For ordinary advice, amplification reuses the word and forces the cost up to m(n−m)−Oq(nlog⁡n)m(n-m)-O_q(n\log n) bits. The balanced choice m=⌊n/2⌋m=\lfloor n/2\rfloor recovers the quarter.

An off-cube query may involve every entry of the table. We identify the Boolean positions at which changing one entry can affect the likelihood of its transcript. A degree-two polynomial that vanishes at all query points can mask the change at every other position. Factoring such a polynomial across the two endpoints of an edge shows that the transcript of qq queries can address at most 2q2q vertices. There is also a stronger conclusion across successive runs on the same oracle. If the earlier runs never addressed the current input, any newly visible edge from it must have its other endpoint addressed by the current run alone. This is the step that permits an error count across inputs despite the shared extension.

Open problems. The unconditional lower bounds concern access to a selector table and relativized languages. Without hypotheses, the ordinary advice complexity of P-selective languages with polynomial-time decoding remains between n+1n+1 bits, forced by [12], and n2−nlog⁡2n+O(n)n^2-n\log_2 n+O(n). Theorem 1.5 shows that closing the gap below n2/4n^2/4, even under H, requires a nonrelativizing argument. It is also open whether H can be replaced by a weaker derandomization hypothesis, for instance one that only fools nondeterministic circuits of a fixed polynomial size.

Counting covering tuples

Orient the side to be recognized so that it beats its complement, reversing all comparisons if needed. An anchor aa on this side certifies xx when x=ax=a or x≻ax \succ a. A list covers the side when it certifies each of its vertices. Checking a cover takes one nonadaptive comparison per anchor. All logarithms are base two except where ln is written.

We first give the fixed-point argument in a form that also applies to payoff deviations in games. The exponent is a variable in the fixed point. This allows the scores to exceed one before normalization.

References

  1. [2]Ingo Althöfer. On Sparse Approximations to Randomized Strategies and Convex Combinations. Linear Algebra and its Applications 199:339–355, 1994. https://doi.org/10.1016/0024-3795(94)90357–3.
  2. [3]Sebastian Ben Daniel. On the Advice Complexity of Tournaments. COCOON 2012, LNCS 7434, pp. 470–481, 2012. https://doi.org/10.1007/978–3–642–32241–9_40.
  3. [4]Yakov Babichenko, Siddharth Barman, and Ron Peretz. Simple Approximate Equilibria in Large Games. ACM Conference on Economics and Computation, pp. 753–770, 2014. https://doi.org/10.1145/2600057.2602873.
  4. [5]Sebastian Ben Daniel. Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors. arXiv:2609.31053, 2026. https://arxiv.org/abs/2609.31053.
  5. [6]Harry Buhrman, Troy Lee, and Dieter van Melkebeek. Language Compression and Pseudorandom Generators. Computational Complexity 14:247–274, 2005.DOI
  6. [7]Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual Dueling Bandits. Conference on Learning Theory, Proceedings of Machine Learning Research 40:563–587, 2015.arxiv.org/abs/1502.06362
  7. [9]Paul Erdős. On a Problem in Graph Theory. The Mathematical Gazette 47(361):220–223, 1963.DOI
  8. [10]Shafi Goldwasser and Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems. Proceedings of the 18th ACM Symposium on Theory of Computing, pp. 59–68, 1986.DOI
  9. [11]Lane A. Hemaspaandra, Harald Hempel, and Arfst Nickelsen. Algebraic Properties for Selector Functions. SIAM Journal on Computing 33(6):1309–1337, 2004.DOI
  10. [12]Lane A. Hemaspaandra and Leen Torenvliet. Optimal Advice. Theoretical Computer Science 154(2):367–377, 1996.
  11. [13]Pravesh K. Kothari and Ruta Mehta. Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium. Proceedings of the 50th ACM Symposium on Theory of Computing, 2018. https://arxiv.org/abs/1806.09426.
  12. [14]Ker-I Ko. On Self-Reducibility and Weak P-Selectivity. Journal of Computer and System Sciences 26(2):209–221, 1983.DOI
  13. [15]Adam R. Klivans and Dieter van Melkebeek. Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing 31(5):1501–1526, 2002. https://pages.cs.wisc.edu/~diet er/Research/r-gni.html.
  14. [16]Richard J. Lipton and Neal E. Young. Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory. Proceedings of the 26th ACM Symposium on Theory of Computing, pp. 734–740, 1994. https://doi.org/10.1145/195058.195447.
  15. [17]Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing Large Games Using Simple Strategies. Proceedings of the 4th ACM Conference on Electronic Commerce, pp. 36–41, 2003.DOI
  16. [18]Xiaoyun Lu, Da-Wei Wang, and C. K. Wong. On the bounded domination number of tournaments. Discrete Mathematics 220(1–3):257–261, 2000. https://doi.org/10.1016/S0012-365X(00)00029-7.
  17. [19]T. S. Motzkin and E. G. Straus. Maxima for Graphs and a New Proof of a Theorem of Turán. Canadian Journal of Mathematics 17:533–540, 1965. https://doi.org/10.4153/CJM-1965-053-6.
  18. [20]J. Barkley Rosser and Lowell Schoenfeld. Approximate Formulas for Some Functions of Prime Numbers. Illinois Journal of Mathematics 6(1):64–94, 1962. https://doi.org/10.1215/ijm/1255631807.
  19. [21]Esther Szekeres and George Szekeres. On a Problem of Schütte and Erdős. The Mathematical Gazette 49(369):290–293, 1965. https://doi.org/10.2307/3612854.
  20. [22]Alan L. Selman. P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. Mathematical Systems Theory 13:55–65, 1979.DOI
  21. [23]Marius Zimand. On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs. arXiv:1210.4408, 2012. https://arxiv.org/abs/1210.4408.

Paper details

vlnc:W_tkmk9569
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude, Codex

View statement
Looking for related papers…
Contents