Answer: No finite uniform query bound exists. The guarantee is impossible for algorithms deterministic conditional on their samples.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet n ≥9, ϵ < 1/50, δ < 1/200 and ∆< 4/5. Then any deterministic algorithm that for all games (N, v) on n players, and all distributions D on N, computes a pay- off allocation in the (ϵ, δ)-probably approximate nucleolus with probability at least 1 −∆requires access to the values of Ω(2n/3) coalitions sampled from D.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Let \(T\) be a finite set of complete record types with rational masses \(\mu_t\ge 0\) summing to \(1\), and let \(V:[0,\mu]\to[0,1]\) be a coalition-value oracle with \(V(0)=0\). For every integer \(r\) such that each \(r\mu_t\) is integral, form a game with \(r\mu_t\) players of type \(t\), where a coalition \(S\) has value \(V(y(S))\) and \(y_t(S)=|S\cap T_t|/r\). Promise that the scaled per-player payoffs in these games’ nucleoli converge to a rate vector \(p^\star\). Given samples \(Y\sim D\) and oracle values \(V(Y)\), what is the query complexity of outputting an efficient rate vector \(p\), with \(\sum_t\mu_t p_t=V(\mu)\), such that \(\Pr_{Y\sim D}[|p\cdot Y-p^\star\cdot Y|\le\epsilon]\ge 1-\delta\), with success probability at least \(1-\Delta\)?
A society is given by its support: a list \(T\) of \(\tau\ge1\) complete record types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(m\) is the maximum record encoding length and \(L\) is the total binary input length.
Let \(B=\prod_{t\in T}[0,\mu_t]\) and let \(V:B\to[0,1]\) be a Borel-measurable value oracle with \(V(0)=0\); no monotonicity or continuity is assumed.
For every positive integer \(r\) with all \(r\mu_t\) integral, form a game with \(r\mu_t\) players of type \(t\) and coalition value \(v_r(S)=V(y(S))\), where \(y_t(S)=|S\cap T_t|/r\).
Use the nucleolus convention that lexicographically minimizes the descending list of all coalition deficits over efficient real allocations, without individual-rationality constraints. Write \(a_t^{(r)}\) for its common per-player payoff within type \(t\); promise that \(p_t^\star=\lim_{r\to\infty}r a_t^{(r)}\) exists and is finite along all admissible \(r\).
The algorithm knows \(V(\mu)\) and receives independent labeled samples \((Y,V(Y))\), with \(Y\sim D\) for an arbitrary unknown Borel probability distribution on \(B\); it has no other value-query access. Each labeled sample counts as one query; oracle data are exact, and running time uses an exact-real arithmetic model with unit-cost oracle operations and parameters \(m,\tau,L,\epsilon,\delta,\Delta\).
For rational \(0<\epsilon<1/50\), \(0<\delta<1/200\), and \(0<\Delta<4/5\), the output is \(p\in\mathbb R^\tau\) satisfying \(\sum_t\mu_t p_t=V(\mu)\) and, with probability at least \(1-\Delta\) over sampling, \(\Pr_{Y\sim D}[|p\cdot Y-p^\star\cdot Y|\le\epsilon]\ge1-\delta\).
What is the worst-case query complexity of this approximation problem for algorithms deterministic conditional on their samples: is it polynomial in \(m,\tau,L,1/\epsilon,1/\delta,\log(1/\Delta)\), or does it require superpolynomially many queries, possibly with no finite uniform bound?
For finite games with \(n\ge9\), the same approximation guarantee requires \(\Omega(2^{n/3})\) labeled coalition samples in the worst case for algorithms deterministic conditional on sampling, under the stated accuracy and confidence ranges. [Yan–Procaccia](https://procaccia.info/wp-content/uploads/2020/12/core.pdf)
No query-complexity result for this exact promised replica-limit problem was located.
There is no finite uniform query bound. Under the stated assumptions, no algorithm deterministic conditional on its samples can satisfy the guarantee on every promised instance.
The proof uses two types, binary-rational masses, monotone Borel value functions, and a rational sampling point. Both replica limits are computed explicitly. Although the simplest sampling distribution is a point mass, the construction also rules out a finite uniform bound for distributions with full support.
We first justify the symmetry property used below.
For a finite game, write \(e_S(x)=v(S)-\sum_{i\in S}x_i\), and let \(\theta(x)\) be the descending list of these deficits. The lexicographic minimizer over efficient real allocations exists and is unique.
For existence, choose any efficient allocation and let \(M\) be its maximum deficit. The efficient allocations whose maximum deficit is at most \(M\) form a nonempty compact set: singleton constraints imply \(x_i\ge v(\{i\})-M\), and efficiency then bounds every coordinate above. Each coordinate of the sorted deficit list is continuous. Successively minimizing its finitely many coordinates over nested compact sets therefore produces a lexicographic minimizer.
For uniqueness, suppose distinct allocations \(x,z\) have the same optimal sorted list. Their coalition-indexed deficit vectors must differ, since singleton deficits determine allocations. Let \(\lambda\) be the largest deficit value occurring in a coordinate where those vectors differ. Above \(\lambda\), the indexed deficits agree. The sets of coordinates attaining \(\lambda\) have the same cardinality but differ. Because deficits are affine, the midpoint \((x+z)/2\) preserves all deficits above \(\lambda\) and attains \(\lambda\) exactly on the intersection of those two sets. Its sorted list is consequently lexicographically smaller, a contradiction.
A player permutation preserving coalition values permutes the deficit list and preserves efficiency. Uniqueness therefore implies that the nucleolus is invariant under every such permutation. In particular, players in the same symmetry orbit receive equal payoffs.
Take two distinct record types with masses \(\mu_1=\mu_2=1/2\). Thus \(B=[0,1/2]^2\), and the admissible replica sizes are precisely \(r=2k\), where \(k\) is a positive integer.
Define
\[
\]
\(V_A(y_1,y_2)=\begin{cases}1,&y_1>0\text{ and }y_2>0,\\0,&\text{otherwise},\end{cases}\)
and
\[
\]
\(V_B(y_1,y_2)=\begin{cases}1,&y_1=1/2\text{ and }y_2>0,\\0,&\text{otherwise}.\end{cases}\)
Both functions are Borel measurable, take values in \([0,1]\), and satisfy \(V_A(0)=V_B(0)=0\). Both are also coordinatewise monotone on \(B\). Their known grand-coalition values coincide:
\(V_A(\mu)=V_B(\mu)=1.\)
In a replica of size \(r=2k\), a coalition wins exactly when it contains at least one player of each type.
Permutations within either type preserve the game. A permutation exchanging the two equally sized type groups also preserves it. These symmetries act transitively on all players, so every player receives the same nucleolus payoff. Efficiency forces that payoff to be \(1/r\).
Consequently, for every admissible \(r\),
\(r a_1^{(r)}=r a_2^{(r)}=1,\)
and hence \(p_A^\star=(1,1)\).
A coalition wins exactly when it contains every type-\(1\) player and at least one type-\(2\) player.
Consider \(k\ge2\). The allocation paying \(1/k\) to every type-\(1\) player and zero to every type-\(2\) player is efficient and has every deficit at most zero: winning coalitions receive payoff \(1\), and losing coalitions receive nonnegative payoff.
The empty coalition always has deficit zero. Thus the minimum possible maximum deficit is zero, and the nucleolus belongs to the core, meaning that all its coalition deficits are nonpositive.
Let \(x\) be any core allocation. Every singleton loses, so singleton constraints give \(x_i\ge0\). For each type-\(2\) player \(b\), the coalition containing all type-\(1\) players and \(b\) wins. Efficiency and its core constraint imply
\(\sum_{j\text{ of type }2,\ j\ne b}x_j\le0.\)
Every summand is nonnegative. Since there are at least two type-\(2\) players, every such player occurs in one of these sums. Therefore all type-\(2\) payoffs are zero.
Symmetry within type \(1\), together with efficiency, now gives the nucleolus payoff \(1/k\) to each type-\(1\) player. Hence, for every admissible \(r\ge4\),
\(r a_1^{(r)}=2,\qquad r a_2^{(r)}=0.\)
The exceptional replica \(r=2\) does not affect the limit. Thus \(p_B^\star=(2,0)\).
Both societies satisfy the promised existence and finiteness of the replica limit along all admissible sizes.
Set \(y_0=(1/2,0)\), and let \(D\) be the point mass at \(y_0\). Both oracles return the same label there:
\(V_A(y_0)=V_B(y_0)=0.\)
The support records, masses, known grand-coalition value, distribution, and every labeled sample are identical between the two instances. Every sample is exactly \((y_0,0)\).
An algorithm deterministic conditional on its samples therefore has the same behavior and output on both instances, regardless of how many samples it requests. If it does not output on this sample sequence, it already fails the required task.
Because \(D\) is a point mass and \(\delta<1\), the distributional accuracy condition is equivalent to accuracy at \(y_0\). However,
\(p_A^\star\cdot y_0=1/2,\qquad p_B^\star\cdot y_0=1.\)
A common output \(p\) could meet both accuracy conditions only if
\(\left|p\cdot y_0-1/2\right|\le\epsilon \quad\text{and}\quad \left|p\cdot y_0-1\right|\le\epsilon.\)
The triangle inequality would then imply \(1/2\le2\epsilon\), contradicting \(\epsilon<1/50\).
Thus the algorithm fails the accuracy condition on at least one of the two promised instances. On that instance its success probability is zero, because its entire sample sequence is deterministic. This contradicts the required positive success probability \(1-\Delta\).
The argument applies even if efficiency is imposed on the output; restricting the available outputs cannot remove the contradiction.
The preceding distribution is degenerate. Nevertheless, requiring full support on \(B\) would still leave no finite uniform query bound.
Fix a proposed bound of \(N\ge1\) samples. Let \(U\) be normalized two-dimensional Lebesgue measure on \(B\), and define
\(D_q=(1-q)\,\operatorname{Dirac}_{y_0}+qU,\)
where \(q>0\) is chosen sufficiently small that
\(1-q>\delta,\qquad (1-q)^N>\Delta.\)
Such a choice exists because both left-hand sides tend to \(1\) as \(q\) tends to zero. The distribution \(D_q\) has full support.
With probability \((1-q)^N\), the first \(N\) samples are all \((y_0,0)\). On this event the algorithm has the same deterministic output on both societies. By the preceding separation argument, that output is inaccurate at \(y_0\) for at least one fixed society.
For that society, inaccuracy at \(y_0\) puts probability mass at least \(1-q>\delta\) outside the permitted error interval. Its output therefore fails the distributional guarantee throughout this event. Its failure probability exceeds \(\Delta\).
Since this construction works for every finite \(N\), full support alone does not provide a finite uniform sample bound either.
The exact promised replica-limit problem is not merely subject to a superpolynomial lower bound. Under its stated sampling model, the target is unidentifiable on some valid instances, so the requested universal guarantee is impossible. No transfer of the finite-game lower bound is needed.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The two societies satisfy every promise, have identical observations under the chosen sampling distribution, and require incompatible predictions. Consequently, the requested universal guarantee is impossible, regardless of the number of samples.
No major or minor mathematical issues were found.
The existence argument is valid for the allocation domain specified in the task: efficient real allocations without individual-rationality constraints.
For a fixed upper bound \(M\) on the maximum deficit, singleton constraints give lower bounds on every allocation coordinate. Efficiency then gives upper bounds. The resulting feasible set is nonempty, closed, and bounded, hence compact. The sorted deficit coordinates are continuous because there are finitely many coalitions. Successive minimization over nested compact sets therefore produces a lexicographic minimizer. Restricting to this initial set loses no possible improvement, since allocations outside it have a larger first deficit coordinate.
The uniqueness argument is also valid. Singleton deficits distinguish distinct allocations. At the largest differing deficit value \(\lambda\), the two indexed deficit vectors agree at every coordinate with a value above \(\lambda\). Their sets of coordinates attaining \(\lambda\) have equal cardinality, because their sorted lists coincide, but those sets differ. At the midpoint, precisely their intersection retains value \(\lambda\); every coordinate in their symmetric difference becomes strictly smaller. Thus the midpoint preserves the larger entries and strictly improves the sorted list at the first affected position, contradicting optimality.
The claimed symmetry follows: a value-preserving player permutation preserves efficiency and the sorted deficit list, so uniqueness forces invariance.
No external theorem is invoked without justification.
The masses \(\mu_1=\mu_2=1/2\) are positive binary rationals summing to one. The admissible replica sizes are exactly the positive even integers.
Both functions are Borel measurable: their winning regions are defined by coordinate equalities and inequalities. Both take values in \([0,1]\), vanish at the origin, and have grand-coalition value one. Their coordinatewise monotonicity is correctly asserted, although the task does not require it.
The use of two distinct record types is compatible with the support encoding. Both instances can use exactly the same records and masses.
For \(r=2k\), a coalition wins exactly when it contains at least one player of each type.
Permutations within each type and a permutation exchanging the equally sized type groups preserve coalition values. These symmetries act transitively on all players. The symmetry result therefore gives a common payoff, and efficiency makes it \(1/r\).
Hence \(r a_t^{(r)}=1\) for both types at every admissible size, establishing the promised finite limit \(p_A^\star=(1,1)\).
For \(k\ge2\), winning requires all type-\(1\) players and at least one type-\(2\) player.
The displayed allocation is efficient. Winning coalitions receive one, and losing coalitions receive nonnegative payoff, so every deficit is nonpositive. The empty coalition has deficit zero at every allocation. Consequently, the optimal maximum deficit is exactly zero, and the nucleolus satisfies all core inequalities.
Every singleton loses, giving nonnegative coordinates for any core allocation. For each type-\(2\) player \(b\), efficiency and the winning-coalition inequality give
\[
\sum_{\substack{j\text{ of type }2\\j\ne b}}x_j\le0.
\]
Together with nonnegativity, this forces each included summand to vanish. Since \(k\ge2\), each type-\(2\) player is included in such a sum for some different \(b\). Thus all type-\(2\) payoffs vanish.
Within-type symmetry and efficiency then force each type-\(1\) payoff to equal \(1/k\). Since \(r=2k\), the scaled payoffs are \((2,0)\). Excluding the single replica size \(r=2\) does not affect convergence.
The second promised limit \(p_B^\star=(2,0)\) is therefore established. Both limits also satisfy the required efficiency identity.
At \(y_0=(1/2,0)\), both oracle labels are zero. Under the point-mass distribution, all samples and all known input data coincide between the instances.
Conditional determinism therefore forces the same behavior and output. Nontermination cannot satisfy the output requirement.
Because \(\delta<1\), accuracy under this distribution requires accuracy at its sole point. The target predictions there are correctly computed as \(1/2\) and \(1\). A common prediction accurate for both would imply
\[
1/2\le2\epsilon,
\]
which contradicts the stated range of \(\epsilon\).
At least one fixed instance therefore has success probability zero. Since \(\Delta<1\), this violates the required confidence. Imposing output efficiency cannot remedy the incompatible predictions.
This proves the main claim more strongly than a finite-sample lower bound: additional samples supply no distinguishing information on these instances.
The mixture with normalized Lebesgue measure has full support on the box. For every finite sample cap \(N\), a sufficiently small positive \(q\) satisfies both stated strict inequalities.
The event that the first \(N\) samples equal the common atom has probability \((1-q)^N\). For an algorithm using at most \(N\) samples, its observed sequence and output on this event are fixed and identical between societies, including if it stops earlier.
The incompatible predictions identify at least one fixed society whose output is inaccurate at the atom throughout this event. That atom has mass \(1-q>\delta\), so the distributional guarantee fails. The event probability exceeds \(\Delta\).
The extension correctly rules out any finite uniform sample cap even under full support. It does not claim that every individual full-support distribution makes identification impossible.
No additional lemma, calculation, or clarification is needed to verify the conclusion. The finite-game lower bound is unnecessary for this construction.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.