Answer: Let \(B\) be the maximum revealed welfare among queried partitions. The smallest certifiable factor is \(Cm/B\) if \(B>0\), and \(+\infty\) if \(B=0\). It is computable in polynomial time in the full input length. No finite \(q\) guarantees a finite certificate uniformly over \(\mathcal V_C\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo other search algorithm (than the one that searches the bottom two levels) can establish a bound k while searching only n = 2a−1 nodes or fewer.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T\), mass vector \(\mu\), and an oracle-accessible class \(\mathcal V_L\) of nonnegative typed coalition-value functions \(v:D_\mu\to\mathbb R_{\ge0}\), where \(D_\mu=\{x\in\mathbb R_{\ge0}^{\tau}:x\le\mu\}\), \(v(0)=0\), and \(v(x)\le L\lVert x\rVert_1\), a query is a finite partition \(X=(x^1,\ldots,x^r)\) with \(\sum_jx^j=\mu\) revealing \(v(x^j)\). After \(q\) queries, determine the smallest \(K\) for which an output \(\widehat X\) can certify \(\max_Y V_{v'}(Y)\le K V_{v'}(\widehat X)\) for every \(v'\in\mathcal V_L\) consistent with the transcript.
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\). Here \(\tau\) is the support size, not the number of possible types; let \(m=\sum_t\mu_t\), without requiring \(m=1\).
Fix a known positive binary rational \(C\). Let \(D_\mu=\{x\in\mathbb R_{\ge0}^{\tau}:x\le\mu\}\), with componentwise inequalities. Let \(\mathcal V_C\) contain all functions \(v:D_\mu\to\mathbb R_{\ge0}\) satisfying \(v(0)=0\) and \(v(x)\le C\lVert x\rVert_1\), with rational values at rational arguments. No continuity, monotonicity, or superadditivity is assumed.
A mass partition is a finite sequence \(X=(x^1,\ldots,x^r)\) of nonzero vectors summing to \(\mu\); identical vectors may occur repeatedly. Its welfare is \(V_v(X)=\sum_jv(x^j)\), and \(\operatorname{OPT}(v)=\sup_Y V_v(Y)\), over all finite mass partitions with real coordinates.
A query specifies a mass partition with binary-rational coordinates and reveals every constituent value exactly. The input is a feasible transcript of \(q\ge1\) queries; consistency means agreement with every revealed value. The output \(\widehat X\) must be one of the queried partitions.
A finite factor \(K\ge1\) is certified when \(\operatorname{OPT}(v')\le K V_{v'}(\widehat X)\) for every consistent \(v'\in\mathcal V_C\). The optimal certificate is \(+\infty\) if no finite factor is possible; the inequality also governs zero-welfare cases.
Let \(L\) be the total binary input length and \(N\) the total number of listed coalition vectors. State running times in \(m,\tau,L,C,q,N\), counting the full query descriptions.
What is the smallest certifiable approximation factor for a given transcript, and can any finite \(q\) guarantee a finite factor uniformly over \(\mathcal V_C\), or is that impossible?
For unrestricted nonnegative coalition values on \(a\ge3\) discrete agents, establishing any uniform finite approximation factor requires \(2^{a-1}\) partition queries; the unique minimum query set consists of all partitions into one or two coalitions and gives the tight factor \(a\). [Sandholm et al.](https://www.cs.cmu.edu/~sandholm/www/coalstruct.aij.pdf)
Later discrete work characterizes minimum search sets for prescribed approximation factors. [Rahwan, Michalak, and Jennings](https://www.cs.cmu.edu/~sandholm/cs15-892F11/minimum%20coalition%20structure%20search.ijcai11.pdf)
No result settling this precise mass-partition oracle problem was identified in the literature search.
Let the queried partitions be \(X^{(1)},\ldots,X^{(q)}\). Write \(W_i\) for the revealed welfare of \(X^{(i)}\), counting repeated coalition vectors with their multiplicities, and let \(B=\max_{1\le i\le q}W_i\).
The smallest certifiable factor is \(Cm/B\) when \(B>0\), and \(+\infty\) when \(B=0\). When \(B>0\), any queried partition attaining \(B\) is an optimal output. The factor can be computed exactly in polynomial time in the full transcript length.
No finite number of queries guarantees a finite certificate uniformly over \(\mathcal V_C\). This holds already for \(\tau=1\), including adaptive query strategies.
For every \(v\in\mathcal V_C\) and every finite mass partition \(Y=(y^1,\ldots,y^r)\), the defining bound gives
\(V_v(Y)=\sum_{j=1}^r v(y^j)\le C\sum_{j=1}^r\lVert y^j\rVert_1=C\sum_{t=1}^{\tau}\sum_{j=1}^r y_t^j=C\sum_{t=1}^{\tau}\mu_t=Cm.\)
The equalities use nonnegative coordinates and \(\sum_j y^j=\mu\). Taking the supremum over all permitted partitions yields \(\operatorname{OPT}(v)\le Cm\).
In particular, feasibility of the transcript implies \(0\le W_i\le Cm\) for every \(i\). Since \(C>0\) and every \(\mu_t>0\), we have \(Cm>0\).
Let \(S\) be the set of distinct coalition vectors occurring anywhere in the transcript, and put \(n=|S|\le N\).
Lemma. There is a binary-rational \(\alpha\in(0,1)\) such that both \(\alpha\mu\) and \((1-\alpha)\mu\) lie outside \(S\).
Proof. Choose a power of two \(D\ge 2n+2\), and consider the \(2n+1\) distinct candidates \(\alpha_k=k/D\), where \(1\le k\le 2n+1\). Every candidate lies strictly between zero and one.
For each fixed \(s\in S\), the equation \(\alpha\mu=s\) excludes at most one candidate: its first coordinate requires \(\alpha=s_1/\mu_1\), and \(\mu_1>0\). Likewise, \((1-\alpha)\mu=s\) excludes at most one candidate.
Thus all vectors in \(S\) together exclude at most \(2n\) candidates. At least one candidate remains. Its two coalition vectors are binary-rational, nonzero, componentwise bounded by \(\mu\), and sum to \(\mu\). This proves the lemma. \(\square\)
The two vectors may coincide; the definition explicitly permits repeated vectors.
For \(s\in S\), let \(a(s)\) be its revealed value. Feasibility ensures that repeated occurrences have the same value and that \(0\le a(s)\le C\lVert s\rVert_1\).
Define a completion \(v^+\) on \(D_\mu\) by assigning:
This function is nonnegative, satisfies the required upper bound, and agrees with every revealed value. At rational arguments its values are rational: the observed values are rational by the premises, and \(C\lVert x\rVert_1\) is rational whenever \(x\) is rational. Consequently, \(v^+\in\mathcal V_C\).
Apply the lemma and let \(Y=(\alpha\mu,(1-\alpha)\mu)\). Neither constituent belongs to \(S\), so
\(V_{v^+}(Y)=C\lVert\alpha\mu\rVert_1+C\lVert(1-\alpha)\mu\rVert_1=C\alpha m+C(1-\alpha)m=Cm.\)
Together with Section 1, this proves \(\operatorname{OPT}(v^+)=Cm\). Hence
\(\max\{\operatorname{OPT}(v'):v'\in\mathcal V_C\text{ consistent with the transcript}\}=Cm.\)
The maximum is attained, and the attaining completion has an optimal partition consisting of two binary-rational coalitions. Thus this sharpness argument does not depend on using irrational coordinates.
Fix a queried output \(X^{(i)}\). Its welfare is \(W_i\) under every consistent completion.
If \(W_i>0\), Section 1 shows that \(K=Cm/W_i\) is certified. This factor satisfies \(K\ge1\), since \(W_i\le Cm\). Conversely, the completion \(v^+\) from Section 3 forces every certified factor to satisfy \(Cm\le K W_i\). Therefore the smallest factor for this output is exactly \(Cm/W_i\).
If \(W_i=0\), that same completion has positive optimum \(Cm\), whereas \(K W_i=0\) for every finite \(K\). No finite factor is certified.
Minimizing over the permitted outputs therefore gives:
In particular, an all-zero transcript cannot certify finite approximation even if the actual function happens to be identically zero: the certificate must also cover the consistent completion \(v^+\).
Here is a single counterexample function, independent of the query strategy. Define \(v_0(x)=0\) when \(x\in\mathbb Q^\tau\), and \(v_0(x)=C\lVert x\rVert_1\) otherwise.
This function belongs to \(\mathcal V_C\): it satisfies the required bounds, vanishes at zero, and has rational values at rational arguments. Every permitted query consists of rational vectors, so every answer is zero.
Nevertheless, choose an irrational \(\alpha\in(0,1)\). Because each \(\mu_t\) is positive and rational, both \(\alpha\mu\) and \((1-\alpha)\mu\) have irrational coordinates. Their partition has welfare \(Cm\), and Section 1 therefore gives \(\operatorname{OPT}(v_0)=Cm>0\).
Thus every permitted queried output has zero welfare while the optimum is positive. No finite factor is possible. This applies to every finite query count and survives adaptivity or randomization because the same fixed function answers every permitted query with zero.
The obstruction is also stronger than a zero-welfare example. For any rational \(0<\varepsilon\le C\), define \(v_\varepsilon(x)=\varepsilon\lVert x\rVert_1\) at rational vectors and \(v_\varepsilon(x)=C\lVert x\rVert_1\) elsewhere. This again belongs to \(\mathcal V_C\).
Every queried partition then has welfare \(\varepsilon m>0\), while the irrational split above attains \(Cm\). Every finite transcript consequently has exact optimal certificate \(C/\varepsilon\). Given any prescribed finite \(K\), choosing rational \(0<\varepsilon<C/K\) makes this certificate exceed \(K\), although every revealed constituent value is strictly positive.
On the promised feasible input, the algorithm:
There are \(O(N+\tau+q)\) rational arithmetic operations. Using standard binary numerator-denominator encodings, the intermediate numbers have \(O(L)\) bits: denominators in a sum can be represented by their product, whose bit length is bounded by the total input bit length. The numerators also have \(O(L)\) bits. Schoolbook arithmetic therefore gives the conservative bit-time bound \(O\!\left(L+(N+\tau+q)L^2\right)\), which is \(O(L^3)\), with \(O(L)\) space.
This bound counts the full query descriptions. It has no dependence on the numerical magnitudes of \(m\) or \(C\) beyond their binary encoding lengths already included in \(L\).
The cited discrete results study partitions of a finite agent set and their search guarantees. [Sandholm et al.](https://www.cs.cmu.edu/~sandholm/www/coalstruct.aij.pdf), [Rahwan, Michalak, and Jennings](https://www.cs.cmu.edu/~sandholm/cs15-892F11/minimum%20coalition%20structure%20search.ijcai11.pdf). Here, Section 2 proves that every finite transcript leaves an entirely unqueried two-coalition mass partition, which establishes the precise continuous certificate above.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The exact certificate, the impossibility of a uniform finite guarantee, and the polynomial running-time bound are justified. I found no major or minor issues.
For every permitted partition, the inequality
\(v(y^j)\le C\lVert y^j\rVert_1\)
applies to each constituent. Nonnegative coordinates and the partition identity imply
\(\sum_j\lVert y^j\rVert_1=m\).
Consequently, every partition has welfare at most \(Cm\), and taking a supremum preserves that bound.
This argument applies to arbitrary real-coordinate partitions, as required. It does not assume that an optimum is attained.
Feasibility gives \(0\le W_i\le Cm\). The assumptions \(C>0\), \(\tau\ge1\), and \(\mu_t>0\) also ensure \(Cm>0\).
Assessment: Correct.
The transcript contains only finitely many distinct vectors, so \(n=|S|\le N\).
The candidate construction is valid:
Thus at most \(2n\) candidates are excluded, leaving at least one of the \(2n+1\) candidates available.
Both resulting vectors are nonzero, lie in \(D_\mu\), have binary-rational coordinates, and sum to \(\mu\). If they coincide, their repetition is explicitly allowed by the task.
Assessment: Correct, including the counting constants and domain restrictions.
Feasibility ensures that the revealed assignment \(a(s)\) is well-defined across repeated occurrences and satisfies the required value bound. Queried constituents are nonzero, so the separate assignment at zero does not conflict with any assignment on \(S\).
The proposed completion \(v^+\):
No regularity condition in the task prohibits this piecewise definition.
The two constituents supplied by Section 2 lie outside \(S\), so each receives its full upper-bound value. Their total welfare is exactly \(Cm\). Together with Section 1, this proves \(\operatorname{OPT}(v^+)=Cm\).
Accordingly, the asserted maximum over consistent completions is justified: it is bounded above universally and attained by the exhibited completion.
Assessment: Correct.
For a fixed queried output, consistency fixes its welfare at \(W_i\).
When \(W_i>0\), the universal upper bound certifies \(Cm/W_i\). Feasibility ensures this factor is at least one. The completion \(v^+\) forces every certified factor to satisfy \(Cm\le KW_i\), proving necessity as well as sufficiency.
When \(W_i=0\), that completion has strictly positive optimum, so no finite factor satisfies the required inequality.
Minimizing over queried outputs therefore gives exactly \(Cm/B\) when \(B>0\), and \(+\infty\) when \(B=0\). Repeated constituent vectors are correctly counted through their multiplicities.
Assessment: Correct, including zero-welfare cases.
The function \(v_0\) satisfies all requirements of \(\mathcal V_C\). Every permitted query uses rational coordinates and therefore receives only zero values.
For irrational \(\alpha\in(0,1)\), multiplication by each positive rational \(\mu_t\) leaves both \(\alpha\mu_t\) and \((1-\alpha)\mu_t\) irrational. Hence both constituents receive their full upper-bound values, giving welfare \(Cm>0\).
Thus every queried output has zero welfare despite a positive optimum. Because the same function works independently of the query strategy, the argument also covers adaptive and randomized strategies and already applies when \(\tau=1\).
The positive-value variant \(v_\varepsilon\) is also valid. Every queried partition has welfare \(\varepsilon m\), while the irrational split attains \(Cm\). Its certificate is therefore exactly \(C/\varepsilon\). Choosing a sufficiently small positive rational \(\varepsilon\) establishes the stated lack of a uniform bounded factor even with strictly positive revealed constituent values.
Assessment: Correct.
The algorithm computes only sums, comparisons, one product, and one quotient. It requires neither a representation of an unknown function nor optimization over real-coordinate partitions.
The count \(O(N+\tau+q)\) of rational arithmetic operations is appropriate; reading all coordinates is separately covered by the \(O(L)\) input-reading term.
Under the stated binary numerator-denominator encoding, products of denominators used in sums have bit length bounded by the aggregate input length. Numerators, comparisons, and the final ratio likewise require \(O(L)\) bits. Schoolbook arithmetic therefore supports the conservative bound
\(O(L+(N+\tau+q)L^2)=O(L^3)\).
The computation can retain the input and current sums within \(O(L)\) space.
There is no additional dependence on the numerical magnitudes of \(m\) or \(C\) beyond their encoding lengths. The cited discrete literature is background; no step of the proof depends on an unverified application of those results.
Assessment: Correct.
No additional clarification or repair is needed.
⟨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.