Answer: —
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn unknown target valuation v in any atomic language L can be learned with at most sizeL(v)·(m+1)+1 demand queries and at most sizeL(v) value queries. This algorithm is efficient for atomic languages and pro- vides the first polynomial query learning algorithm for the OR language. OR can be more concise than XOR although it is not always expressive [Nisan, 2000]. We do not know of a learning algorithm for OR with membership and equivalence queries alone, so this result suggests the power of demand queries.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) indivisible goods, a known support \(T\) of \(\tau\) valuation types with rational masses \(\mu_t>0\) summing to \(1\), and an unknown normalized, free-disposal valuation \(v_t\) in an atomic language \(L\) for each type, with value and demand queries available to a representative of each type, recover every \(v_t\) and thus the exact weighted measure \(\nu=\sum_{t\in T}\mu_t\delta_{v_t}\). If \(q_t=\mathrm{size}_L(v_t)\), can this be done with at most \(\sum_t(q_t(m+1)+1)\) demand queries and \(\sum_t q_t\) value queries?
Let \(G\) contain \(m\geq1\) indivisible goods. A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Fix a known atomic language \(\mathcal L\). A representation is \((B,w)\), where \(B\subseteq2^G\) and \(w:B\to\mathbb Q_{\geq0}\); its semantics are \(v(S)=\phi_{\mathcal L}(S;B,w)\). The empty representation denotes zero. For valid representations, the evaluator agrees with atomic weights, depends only on contained atoms, and is monotone under compatible addition of atoms: \(\phi_{\mathcal L}(A;B,w)=w(A)\) for \(A\in B\), \(\phi_{\mathcal L}(S;B,w)=\phi_{\mathcal L}(S;B|_S,w|_{B|_S})\), and \(\phi_{\mathcal L}(S;B\cup B',w')\geq\phi_{\mathcal L}(S;B,w)\) when \(w'|_B=w\), where \(B|_S=\{A\in B:A\subseteq S\}\).
Each unknown \(v_t:2^G\to\mathbb Q_{\geq0}\) is normalized, satisfies free disposal, has an \(\mathcal L\)-representation, and satisfies \(v_t(S)<K\) for a known positive binary rational \(K\). Let \(q_t\) be its minimum number of atoms and \(Q=\sum_tq_t\).
A representative of each type answers truthful queries. \(\operatorname{VALUE}_t(S)\) returns \(v_t(S)\). \(\operatorname{DEMAND}_t(S,p)\) returns YES exactly when \(S\) maximizes \(v_t(R)-p(R)\); otherwise it returns any \(R\) with strictly greater utility. Ties require YES, and the empty bundle is permitted.
Prices are nonnegative functions on bundles, with succinct symbolic descriptions using \(\mathcal L\)-representations, rational constants, and piecewise bundle-containment tests. Oracle calls have unit cost; writing queries, reading answers, and other computation count toward running time. Let \(L\) include the encoded support and bound and a bound on the bit length of exact valuation answers. Recovery means producing an \(\mathcal L\)-representation of each \(v_t\), specifying \(\nu=\sum_t\mu_t\delta_{v_t}\).
Is exact recovery polynomial-time solvable in this oracle model, with running time polynomial in \(m,\tau,L,Q\) and at most \(\sum_t(q_t(m+1)+1)\) demand queries and \(Q\) value queries, or is it NP-hard even with these oracles?
For one discrete agent, exact learning in an atomic language is known to require at most \(q(m+1)+1\) demand queries and \(q\) value queries; this is a query-complexity guarantee. [Lahaie, Constantin and Parkes](https://www.ijcai.org/Proceedings/05/Papers/1481.pdf)
No separate result for the specified distribution-input problem was identified in the literature search.
I establish three partial results:
NOTES can require exponentially many atom additions under the stated semantic axioms.These results do not settle polynomial-time recovery or oracle-relative NP-hardness for every language allowed by USER_TASK. In particular, the counterexample concerns the proposed implementation; it does not rule out another learner satisfying the supplied single-agent query-complexity guarantee.
For every finite goods set $G$, define
$$
c_B(S)=\bigl|\{A\in B:A\subseteq S,\ |A|=1\}\bigr|
$$
and
$$
\phi_{\mathcal L}(S;B,w)
=
\max\left(
\{0,c_B(S)-1\}
\cup
\{w(A):A\in B,\ A\subseteq S\}
\right).
$$
Declare $(B,w)$ valid precisely when, for every $A\in B$,
$$
w(A)\geq \max\{0,c_B(A)-1\}
$$
and
$$
w(A)\geq w(C)
\qquad
\text{for every }C\in B\text{ with }C\subseteq A.
$$
This is one fixed language: the same rule applies for every number of goods.
It satisfies the required semantic properties:
Moreover, every subrepresentation of a valid representation is valid. Deletion can only decrease singleton counts and remove inequalities involving deleted atoms.
Every represented function satisfies free disposal: if $S\subseteq R$, then the singleton count cannot decrease and every weight term available at $S$ remains available at $R$.
Let $m\geq3$, and define
$$
v(S)=\max\{0,|S|-1\}.
$$
The representation consisting of all singleton atoms, each with weight zero, represents $v$. It is valid because each singleton contains exactly one singleton atom. Thus its minimum representation size satisfies $q\leq m$.
For the reverse inequality, consider any valid representation of $v$. By atomic agreement, every singleton atom has weight zero; an empty atom, if present, also has weight zero.
Let $k$ be the number of singleton atoms. Consider a two-element bundle $P$ that does not have both of its singletons among those atoms. Then
$$
c_B(P)\leq1.
$$
If $P$ itself were absent from $B$, its contained atoms could only be singleton atoms and an empty atom, all of weight zero. Consequently,
$$
\phi_{\mathcal L}(P;B,w)=0,
$$
contrary to $v(P)=1$.
Therefore every pair except possibly those entirely among the $k$ singleton atoms must itself be an atom. Hence
$$
|B|
\geq
k+\binom m2-\binom k2.
$$
For $0\leq k\leq m$ and $m\geq3$,
$$
k+\binom m2-\binom k2-m
=
\frac{(m-k)(m+k-3)}2
\geq0.
$$
It follows that $|B|\geq m$, proving
$$
q=m.
$$
The target is normalized and rational. Taking $K=m$ gives
$$
v(S)\leq m-1<K.
$$
One type of mass $1$ therefore gives an admissible society.
Consider precisely the learner in NOTES. Its manifest starts empty. An outer demand query uses manifest prices $h$. A returned discrepancy bundle $S$ is then tested using
$$
p_{H,S}(R)=
\begin{cases}
h(R),&R\subsetneq S,\\
K,&\text{otherwise}.
\end{cases}
$$
If this demand query returns YES, the learner adds $(S,v(S))$.
Order all bundles of size at least two by nondecreasing cardinality, breaking ties arbitrarily. The outer demand oracle can return them in this order.
To verify this assertion, suppose the next bundle is $S$, of cardinality $r\geq2$. All previously added atoms have weight $|A|-1$, and none is a singleton. The manifest therefore evaluates as
$$
h(R)=
\max\left(
\{0\}\cup
\{|A|-1:A\text{ was previously added},\ A\subseteq R\}
\right).
$$
Every previously added atom contained in $S$ is a proper subset of $S$. Consequently,
$$
h(S)\leq r-2<r-1=v(S).
$$
The empty bundle has utility zero, so $S$ is a permitted strict improvement in the outer demand query.
On the other hand, every proper subset $R\subsetneq S$ satisfies
$$
h(R)=v(R).
$$
Indeed, this is immediate for $|R|\leq1$. If $|R|\geq2$, then $R$ was already added, so its own atom contributes $|R|-1$; every other contained atom contributes at most that value.
For the shrinking query, every proper subset of $S$ consequently has utility zero. Every other bundle has utility
$$
v(R)-K<0.
$$
Thus the empty bundle maximizes utility, and the oracle must return YES. The learner adds $S$ immediately.
Every intermediate representation is valid: it contains no singleton atoms, and weights $|A|-1$ increase under containment.
After all bundles of size at least two have been added, the manifest equals $v$ everywhere, so the next outer query returns YES.
The resulting counts are therefore
$$
N_V=2^m-m-1
$$
and
$$
N_D=2(2^m-m-1)+1.
$$
Already at $m=3$, the value-query count is $4>q=3$. At $m=4$, both requested bounds fail:
$$
N_V=11>4,
\qquad
N_D=23>4(4+1)+1=21.
$$
Thus the proposed implementation can have exponentially many rounds even though $q=m$.
Agreement on every proper subset of a discrepancy bundle does not imply that the bundle belongs to a fixed minimum representation. Undiscovered zero-weight atoms can affect larger bundles without creating discrepancies on their own bundles.
The cited paper’s proof uses this atom-identification inference when establishing its learning bound. The displayed semantic axioms do not justify that inference. See [Lahaie, Constantin and Parkes, Section 3.1](https://www.ijcai.org/Proceedings/05/Papers/1481.pdf).
This does not prove a lower bound against all possible learners.
Consider a language satisfying the stated axioms and these additional properties:
$$
\phi_{\mathcal L}(A;B\setminus\{A\},w)=w(A),
$$
then
$$
\phi_{\mathcal L}(S;B\setminus\{A\},w)
=
\phi_{\mathcal L}(S;B,w)
\qquad\text{for every }S\subseteq G.
$$
Restrictions of $w$ are implicit where atoms have been deleted.
Under these additional hypotheses, the proposed learner is correct and achieves the requested bounds.
Fix a minimum representation $(B_*,w_*)$ of the target $v$.
For every $A\in B_*$, monotonicity under addition and atomic agreement give
$$
\phi_{\mathcal L}(A;B_*\setminus\{A\},w_*)
\leq
w_*(A).
$$
Equality would, by the second additional property, allow deletion of $A$ without changing $v$. This would contradict minimum cardinality. Therefore
$$
\phi_{\mathcal L}(A;B_*\setminus\{A\},w_*)
<
w_*(A).
$$
Suppose the current manifest uses some $C\subseteq B_*$ with the target weights:
$$
h(S)=\phi_{\mathcal L}(S;C,w_*).
$$
For every missing atom $A\in B_*\setminus C$, monotonicity gives
$$
h(A)
\leq
\phi_{\mathcal L}(A;B_*\setminus\{A\},w_*)
<
w_*(A)
=
v(A).
$$
Thus every missing atom is a strict discrepancy on its own bundle. This is the property absent from the counterexample.
Initially $C=\varnothing$. Inductively suppose $C\subseteq B_*$ and its weights are correct. Validity and monotonicity give
$$
0\leq h(S)\leq v(S)
\qquad\text{for every }S\subseteq G.
$$
Normalization then implies $h(\varnothing)=0$.
For the outer query $\operatorname{DEMAND}(\varnothing,h)$:
Apply the shrinking price displayed in Section 1.3. The empty bundle has utility zero. Any returned strict improvement must satisfy
$$
R\subsetneq S,
\qquad
v(R)>h(R),
$$
because bundles outside the proper subsets have strictly negative utility.
Eventually a shrinking query returns YES. At that point,
$$
v(R)=h(R)
\qquad\text{for every }R\subsetneq S,
$$
while the current bundle still satisfies $v(S)>h(S)$.
By dependence on contained atoms, this strict discrepancy implies that some missing target atom $A\in B_*\setminus C$ satisfies $A\subseteq S$. Otherwise the target and manifest would have identical contained representations at $S$.
Section 2.1 gives $v(A)>h(A)$. Since all proper subsets of $S$ agree, $A$ cannot be a proper subset. Therefore
$$
A=S.
$$
A value query on $S$ returns $w_*(S)$, so adding that atom preserves the induction invariant.
Each successful round adds a distinct atom of $B_*$. Hence there are at most $q$ rounds.
Each successful round uses one outer demand query. Its shrinking phase uses at most $m$ demand queries: each non-YES response strictly decreases the cardinality of a nonempty discrepancy bundle, and a singleton’s shrinking query must return YES.
Including the terminating outer query gives
$$
N_D\leq q(m+1)+1,
\qquad
N_V\leq q.
$$
The learner submits prices symbolically. It never needs to evaluate $h$ locally. A stored atom consists of an $m$-bit bundle and a queried rational weight with bit length bounded by $L$. Thus the manifest encoding has size
$$
O\bigl(q(m+L)\bigr).
$$
A shrinking price additionally contains $S$, $K$, and the proper-containment test. Proper containment is expressible through the permitted tests:
$$
R\subsetneq S
\quad\Longleftrightarrow\quad
R\subseteq S\ \text{and}\ S\not\subseteq R.
$$
Writing queries, reading answers, and updating representations therefore take polynomial time in $m,L,q$. No local optimization or semantic evaluation is required.
For $q=0$, the target is zero, and the initial outer query terminates immediately.
Define XOR evaluation by
$$
\phi_{\mathrm{XOR}}(S;B,w)
=
\max\left(\{0\}\cup\{w(A):A\in B,\ A\subseteq S\}\right).
$$
Use representations satisfying atomic agreement.
Subrepresentations remain valid: at a retained atom $A$, deletion cannot increase the evaluation above its original value $w(A)$, while $A$ itself still supplies $w(A)$.
Suppose deletion of $A$ leaves its own value equal to $w(A)$. Write $h$ for the evaluation after deletion. XOR evaluations satisfy free disposal, so for every $S\supseteq A$,
$$
h(S)\geq h(A)=w(A).
$$
Restoring $A$ therefore does not change the maximum at $S$. For $S$ not containing $A$, restoring $A$ has no effect by containment.
This proves local redundancy implies global redundancy. Consequently Section 2 establishes the requested polynomial-time recovery guarantee for XOR.
Define OR evaluation by
$$
\phi_{\mathrm{OR}}(S;B,w)
=
\max
\left\{
\sum_{A\in D}w(A):
D\subseteq B,\
A\subseteq S\text{ for every }A\in D,\
D\text{ is pairwise disjoint}
\right\}.
$$
The empty packing is permitted. Again, use representations satisfying atomic agreement.
For normalized targets, an empty atom has weight zero and can be omitted without changing evaluation. We may therefore work with nonempty atoms.
Subrepresentations remain valid. At a retained atom $A$, the one-atom packing achieves $w(A)$; deleting other atoms cannot increase the original evaluation above $w(A)$.
Now suppose deleting $A$ leaves its own value equal to $w(A)$. Since there are finitely many packings, some packing $D$ of remaining atoms contained in $A$ attains
$$
\sum_{C\in D}w(C)=w(A).
$$
Consider any feasible packing $E$ for any bundle $S$ in the original representation.
If $A\notin E$, the packing remains available after deletion. If $A\in E$, replace $A$ by $D$. Every member of $D$ is contained in $A$, so it is disjoint from every member of $E\setminus\{A\}$. The replacement is feasible and preserves total weight.
Every original packing value is therefore achievable after deletion. Conversely, deletion cannot increase the optimum. The evaluations agree for every $S$.
Thus OR also satisfies the sufficient condition, and Section 2 establishes the requested polynomial-time recovery guarantee for OR.
This reduction does not require either additional structural condition.
Suppose a single-type learner for the fixed language runs in polynomial time in $m,L,q$ and uses at most
$$
q(m+1)+1
$$
demand queries and $q$ value queries.
Run it separately for each listed type $t$. Since
$$
q_t\leq Q
\qquad\text{and}\qquad
\sum_tq_t=Q,
$$
the sum of its running times is polynomial in $m,\tau,L,Q$. The total query counts are
$$
N_D\leq Q(m+1)+\tau
=
\sum_t\bigl(q_t(m+1)+1\bigr)
$$
and
$$
N_V\leq Q.
$$
Output the original masses together with the recovered representations. This specifies exactly
$$
\nu=\sum_t\mu_t\delta_{v_t}.
$$
Repeated valuations may retain separate entries; this specifies the same measure without requiring representation-equivalence testing.
Conversely, any recovery algorithm for the support-input problem applies to the single-type case by taking $\tau=1$ and mass $1$.
Thus explicit support and masses introduce no additional obstruction. The unresolved issue is the single-type computational guarantee for the full class of languages in the question.
The stated axioms do not supply the deletion property used in Section 2. Indeed, in Section 1, deleting a zero-weight singleton preserves its own value but changes larger-bundle values.
Accordingly, the repaired proof resolves XOR, OR, and languages satisfying the additional conditions, but it does not resolve arbitrary $\mathcal L$ under the original assumptions. A complete answer still requires either a different polynomial-time learner with the specified bounds or a hardness argument that remains valid in the presence of the permitted symbolic-price demand oracle.
⟨structured verdict parsed — rendered above⟩
Classification: partial. The counterexample, conditional recovery theorem, XOR and OR applications, and explicit-support reduction are sound in substance. They do not settle the requested complexity classification for an arbitrary language satisfying only the original axioms. The prover expressly acknowledges that limitation.
There is no demonstrated false central mathematical step. Two minor presentation issues need clarification.
The proposed evaluator satisfies atomic agreement on valid representations: at an atom $A$, the validity inequalities bound both the singleton-count contribution and every contained atomic weight by $w(A)$, while $A$ itself contributes $w(A)$.
Dependence on contained atoms holds because both components of the evaluator use only atoms contained in the evaluated bundle. Compatible addition cannot decrease either component. The empty representation evaluates to zero.
Deletion preserves validity: singleton counts decrease, and every inequality involving retained atoms was already satisfied. Free disposal also follows directly from the formula, since enlarging a bundle preserves all available weight contributions and cannot decrease its singleton count.
Assessment: correct.
The all-singleton representation with zero weights represents
$$
v(S)=\max\{0,|S|-1\}.
$$
For an arbitrary representation of this target, atomic agreement forces every singleton atom and any empty atom to have weight zero. If a pair lacks at least one of its singleton atoms and is not itself an atom, every available contribution to its value is zero. Thus that pair must be an atom.
The resulting lower bound
$$
|B|\geq k+\binom m2-\binom k2
$$
is valid. The calculation
$$
k+\binom m2-\binom k2-m
=
\frac{(m-k)(m+k-3)}2
$$
is correct and nonnegative throughout the stated range $m\geq3$ and $0\leq k\leq m$. Therefore $q=m$.
Normalization, rationality, free disposal, and the strict bound with $K=m$ all hold.
Assessment: correct, including the boundary case $m=3$.
Under the intended queries
$$
\operatorname{DEMAND}(\varnothing,h)
\quad\text{and}\quad
\operatorname{DEMAND}(\varnothing,p_{H,S}),
$$
the proposed adversarial execution is valid.
Before adding a bundle $S$ of size $r$, every previously added atom contained in $S$ is a proper subset, so
$$
h(S)\leq r-2<v(S).
$$
Consequently $S$ is an allowed outer response: the oracle need only return a strict improvement, not a maximizing bundle.
Every proper subset of $S$ already agrees with the target. Under the shrinking prices, proper subsets therefore have utility zero, while all remaining bundles have strictly negative utility because $v(R)<K$. The reference empty bundle maximizes utility, so the oracle must answer YES.
Intermediate representations satisfy the declared validity conditions. After all bundles of size at least two have been added, the manifest equals the target.
The counts
$$
N_V=2^m-m-1,
\qquad
N_D=2(2^m-m-1)+1
$$
and the numerical comparisons at $m=3$ and $m=4$ are correct.
Minor issue: NOTES is not supplied, and Section 1.3 does not explicitly identify the reference bundle in its shrinking demand query. The execution is verifiable under the empty-reference interpretation above, which is also consistent with the cited algorithm. The write-up should state both complete query tuples and identify the learner directly instead of relying on an unavailable document.
The claim about the cited paper is supported: its Section 3.1, Lemma 1, infers discovery of proper-subset atoms from agreement, minimality, and containment dependence. The displayed counterexample shows that inference is not justified by the semantic assumptions stated in USER_TASK. This is a criticism of that inference under those assumptions, not a lower bound against every learner. [Lahaie, Constantin and Parkes, Section 3.1](https://www.ijcai.org/Proceedings/05/Papers/1481.pdf)
The two additional conditions are stated with adequate quantifiers. Their uses are justified:
The manifest invariant is maintained correctly. Since the manifest is a valid subrepresentation of the target,
$$
0\leq h(S)\leq v(S).
$$
The lower bound also follows by compatible addition from the empty representation. Normalization then gives $h(\varnothing)=0$.
The outer query correctly detects equality or supplies a nonempty discrepancy. In the shrinking phase, every strict-improvement response is a proper-subset discrepancy. Strict cardinality descent ensures termination. A terminal YES establishes agreement on every proper subset.
Containment dependence then guarantees a missing target atom inside the current discrepancy bundle. The previously established strict discrepancy at every missing atom excludes proper containment, so the discovered bundle is itself a missing target atom. The value query supplies its correct atomic weight.
Assessment: correct under the additional conditions, with the empty reference bundle made explicit.
A shrinking phase starts at a nonempty bundle of size at most $m$. Each non-YES response decreases its cardinality, and the singleton query terminates. Thus at most $m$ shrinking queries occur per successful round.
The stated bounds follow:
$$
N_D\leq q(m+1)+1,
\qquad
N_V\leq q.
$$
The polynomial-time claim is justified in the specified symbolic-price model. The learner stores only queried weights and bundles, performs containment operations, and writes polynomial-size queries. It does not need to evaluate or optimize the manifest locally. The case $q=0$ is handled correctly.
These are upper bounds; the proof does not assert equality of query counts.
For XOR, retained atoms continue to supply their own weights after deletion, and deletion cannot increase the maximum. The local-to-global redundancy argument correctly uses containment and monotonicity of the remaining maximum.
For OR, deletion likewise preserves atomic agreement. The finite packing maximum at $A$ supplies the asserted replacement packing. With nonempty atoms, replacing $A$ by that packing preserves feasibility: its members lie within $A$ and are disjoint from every other member of the original packing. Total weight is unchanged.
Omitting a zero-weight empty atom is legitimate for normalized targets. No omitted edge case breaks either application.
Assessment: both applications establish the claimed polynomial recovery guarantees in the stated oracle model.
Running the assumed single-type learner independently for each listed type preserves the query bounds:
$$
N_D\leq Q(m+1)+\tau,
\qquad
N_V\leq Q.
$$
A uniform polynomial bound for the single-type learner sums to a polynomial in $m,\tau,L,Q$. Keeping duplicate valuations as separate weighted entries specifies the same measure, so equivalence testing is unnecessary. The converse specialization to $\tau=1$ is valid.
Assessment: correct conditional reduction. It does not establish the missing single-type guarantee for arbitrary languages.
Major scope limitation: the original arbitrary-language question remains unresolved. Neither the counterexample to one implementation nor the conditional theorem establishes universal polynomial recovery or oracle-relative NP-hardness. This is an acknowledged limitation, not a concealed inference error. Settling the target requires one of the two results identified in the prover’s own final paragraph.
Minor terminology error: Section 5 says the axioms do not supply “the deletion property” and then cites the singleton example. That example preserves validity under deletion; it violates local redundancy implies global redundancy. The write-up should name the second property explicitly. The example does not demonstrate failure of deletion-preserved validity.
The established results warrant another round, but the additional conditions cannot be treated as consequences of USER_TASK.
⟨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.