Answer: Exact recovery uses \(O(m\tau\log(M+1))\) oracle queries and bit running time polynomial in \(m,\tau,L,\log(M+1)\).
Theorem 6.1 — class: hardness
Given \(n\), \(M\), \(\tau\), \(L\), and an unknown probability measure \(\mu\) on at most \(\tau\) integral unit-demand types \(b\in\{0,\ldots,M\}^n\), with binary-rational masses summing to \(1\), an exact oracle returns \(x_\mu(p)=\sum_b\mu_b e^{i_b(p)}\) at tie-avoiding prices \(p\), where \(i_b(p)\in\arg\max_{i\in[n]_0}(b_i-p_i)\) and \(b_0=p_0=0\). Recover every supported pair \((b,\mu_b)\), minimizing the number of oracle queries.
Let \(m=n\geq1\) be the number of goods and \(M\geq1\) an integer supplied in binary.
A society is represented by its support: the list of its \(\tau\) distinct types with positive binary-rational masses; \(\tau\) is the support size, not the number of possible types. Here this list is hidden, and only \(n,M,\tau,L\) and oracle access are supplied; \(L\) bounds the total bit length of the hidden list.
Each type is \(b\in\{0,\ldots,M\}^n\), with mass \(\mu_b>0\), and \(\sum_b\mu_b=1\). Set \(b_0=p_0=0\), and let \(e^0=0\in\mathbb R^n\).
An adaptive query specifies binary-rational prices \(p\in\mathbb Q^n\), allowing negative prices, such that every supported type has a unique utility maximizer \(i_b(p)\in\operatorname*{arg\,max}_{0\leq i\leq n}(b_i-p_i)\).
The oracle returns the exact rational vector \(x_\mu(p)=\sum_b\mu_b e^{i_b(p)}\). Recover every supported pair \((b,\mu_b)\) exactly using a deterministic algorithm; measure worst-case queries and bit running time in \(m,\tau,L,\log(M+1)\).
Is the worst-case number of oracle queries needed for exact recovery polynomial in \(m,\tau,L,\log(M+1)\), or necessarily superpolynomial in these parameters?
For discrete positive integer-weight bid lists with \(B\) distinct bid vectors, an \(O(nB\log M)\) query upper bound and an \(\Omega(B\log M)\) query lower bound are reported; the latter is a query lower bound, not an NP-hardness result. [Source](https://arxiv.org/pdf/2005.01496)
No result explicitly addressing the normalized binary-rational mass formulation above was located.
1. Proven result
Exact recovery is possible with at most
\(\displaystyle \tau\bigl(m\lceil\log_2(M+1)\rceil+1\bigr)\)
oracle queries and bit running time polynomial in \(m,\tau,L,\log(M+1)\).
The proof uses the known total mass to obtain cumulative mass queries, then recovers one supported type at a time. It applies directly to positive rational masses.
2. Obtaining cumulative mass from an admissible query
Write \(S\subseteq\{0,\ldots,M\}^n\) for the hidden support. For an integer vector \(q\), define
\(\displaystyle F(q)=\sum_{\substack{b\in S\\b_i\le q_i\ \text{for every }i}}\mu_b.\)
Choose a power of two \(D>n\), with \(D\le 2(n+1)\), and query prices
\(\displaystyle p_i=q_i+\frac{i}{D},\qquad 1\le i\le n.\)
These are binary-rational prices. This query has a unique maximizer for every integer type, regardless of the hidden support:
\(\displaystyle (b_i-q_i)-(b_j-q_j)=\frac{i-j}{D}\).
The left side is integral, whereas the right side is nonzero and has absolute value less than one.
Moreover, the outside option is chosen exactly when every good’s utility is negative. Integrality gives
\(\displaystyle b_i-p_i<0\quad\Longleftrightarrow\quad b_i\le q_i.\)
Consequently, one oracle query computes
\(\displaystyle F(q)=1-\sum_{i=1}^n x_{\mu,i}(p).\)
Thus the oracle supplies the exact mass in any integer lower orthant, using prices guaranteed to be admissible.
3. Recovering one remaining supported type
Suppose a set \(T\subseteq S\) of types and their exact masses has already been recovered. Define the residual cumulative mass
\(\displaystyle F_T(q)=F(q)-\sum_{\substack{b\in T\\b_i\le q_i\ \text{for every }i}}\mu_b =\sum_{\substack{b\in S\setminus T\\b_i\le q_i\ \text{for every }i}}\mu_b.\)
A single original oracle query therefore evaluates \(F_T(q)\), followed by explicit subtraction of known masses.
Because all remaining masses are positive,
\(\displaystyle F_T(q)>0\quad\Longleftrightarrow\quad \text{some }b\in S\setminus T\text{ satisfies }b_i\le q_i\text{ for every }i.\)
Assume \(R=S\setminus T\) is nonempty. We determine coordinates \(a_1,\ldots,a_n\) successively.
Before determining coordinate \(j\), maintain the invariant
\(\displaystyle A_{j-1} =\{b\in R:b_i\le a_i\text{ for }i<j\} =\{b\in R:b_i=a_i\text{ for }i<j\} \ne\varnothing.\)
For \(j=1\), both sets equal \(R\), so the invariant holds.
For an integer \(t\), let
\(\displaystyle q^{(j)}(t)=(a_1,\ldots,a_{j-1},t,M,\ldots,M).\)
Since all supported coordinates are at most \(M\),
\(\displaystyle F_T(q^{(j)}(t))>0 \quad\Longleftrightarrow\quad \text{some }b\in A_{j-1}\text{ has }b_j\le t.\)
This predicate is monotone in \(t\). It is false at \(t=-1\), by nonnegativity of the coordinates, and true at \(t=M\), by nonemptiness of \(A_{j-1}\). Binary search therefore finds its smallest true integer \(a_j\), using at most \(\lceil\log_2(M+1)\rceil\) evaluations.
Equivalently,
\(\displaystyle a_j=\min_{b\in A_{j-1}}b_j.\)
Hence the set
\(\displaystyle A_j=\{b\in A_{j-1}:b_j\le a_j\}\)
is nonempty, and every member satisfies \(b_j=a_j\). Together with the preceding invariant, this proves the invariant for the next coordinate.
After all coordinates have been determined,
\(\displaystyle \varnothing\ne A_n=\{b\in R:b=a\},\qquad a=(a_1,\ldots,a_n).\)
Since the support contains distinct types, \(A_n=\{a\}\). In particular, \(a\) is a remaining supported type, and one additional cumulative mass query gives its exact mass:
\(\displaystyle F_T(a)=\mu_a.\)
This completes the recovery of one pair.
4. Complete algorithm and query bound
Start with \(T=\varnothing\). Repeat the preceding procedure exactly \(\tau\) times, adding the recovered pair to \(T\) after each iteration.
Inductively, every recovered type belongs to the original support and has its correct mass. Each iteration selects a type outside \(T\), so all recovered types are distinct. Before iteration \(k\le\tau\), precisely \(\tau-k+1\) types remain; thus the nonemptiness assumption always holds. After the final iteration, every supported pair has been recovered.
Each iteration uses at most \(n\lceil\log_2(M+1)\rceil\) queries to find the coordinates and one query to obtain the mass. With \(m=n\), the total is therefore
\(\displaystyle \tau\bigl(m\lceil\log_2(M+1)\rceil+1\bigr) =O(m\tau\log(M+1)).\)
5. Polynomial bit running time
The exact arithmetic does not require a number of operations proportional to the reciprocal of a small mass.
To bound its cost, write each hidden mass in reduced form as \(\mu_b=u_b/v_b\), and let
\(\displaystyle Q=\prod_{b\in S}v_b.\)
The total encoding-length bound implies \(\log_2 Q=O(L)\). Every subset sum of hidden masses has denominator dividing \(Q\). Since every such sum lies between zero and one, its reduced numerator and denominator have \(O(L)\) bits.
In particular:
When partial sums and differences are reduced after each operation, their bit lengths also remain \(O(L)\). Exact positivity tests therefore take polynomial time in \(L\).
Every queried coordinate \(q_i\) lies between zero and \(M\). The price \(p_i=q_i+i/D\) has bit length \(O(\log(M+1)+\log(n+1))\).
For each cumulative mass evaluation, the algorithm sums the \(n\) response coordinates, checks coordinatewise domination for at most \(\tau\) recovered types, and subtracts their relevant masses. This requires \(O(n\tau+n+\tau)\) comparisons and arithmetic operations on numbers of polynomially bounded bit length. Combined with the proved polynomial query bound, this establishes polynomial bit running time in the required parameters.
6. Relation to the cited result
Section 4 of the [cited paper](https://arxiv.org/pdf/2005.01496) gives the positive integer-weight bid-list upper bound. The argument here directly proves the normalized positive rational-mass bound, without converting masses into integer multiplicities. Its decisive ingredients are known total mass, integral type coordinates, positive masses, and exact oracle responses.
Thus the stated recovery problem has polynomial worst-case query complexity and polynomial bit running time.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The recovery argument is correct, all oracle queries are admissible, and both the stated query bound and polynomial bit running time are justified. No substantive or minor gaps were found.
The proof uses exactly the promised information: the integer coordinate bound \(M\), the support size \(\tau\), known total mass \(1\), and exact oracle responses. It does not assume access to the hidden support or a lower bound on positive masses.
The support size counts distinct types throughout. No step replaces rational masses by integer multiplicities.
The choice of a power of two \(D>n\), with \(D\le 2(n+1)\), is possible for every \(n\ge1\). Since \(D\) is a power of two, all proposed prices are binary-rational.
For each good, \(0<i/D<1\), so its utility
\(b_i-q_i-i/D\) cannot equal the outside utility \(0\). For distinct goods, equality would require an integer to equal the nonzero number \((i-j)/D\), whose absolute value is less than \(1\). Thus all utilities are pairwise distinct, and the maximizer is unique for every integer type.
The equivalence
\(b_i-p_i<0\Longleftrightarrow b_i\le q_i\)
is correct. Consequently, the outside option is selected exactly by types counted in \(F(q)\). Every other type contributes its mass to exactly one response coordinate, establishing
\(F(q)=1-\sum_{i=1}^n x_{\mu,i}(p)\).
This includes types with zero coordinates and the all-zero type.
Subtracting the masses of recovered types dominated by \(q\) gives exactly the cumulative mass of the remaining support.
Because all remaining masses are strictly positive, a residual cumulative mass is positive if and only if the queried orthant contains a remaining type. There is no cancellation and no numerical tolerance assumption: positivity is tested using exact rational arithmetic.
The initial invariant holds because no coordinate restrictions have yet been imposed and the remaining support is nonempty.
At coordinate \(j\), the trailing thresholds \(M\) impose no additional restriction. The predicate therefore tests precisely whether a member of \(A_{j-1}\) has coordinate \(b_j\le t\).
The predicate is monotone, false at \(t=-1\), and true at \(t=M\). These endpoint values follow from the stated promises and require no oracle queries. There are \(M+1\) possible minimum coordinates, so balanced binary search requires at most \(\lceil\log_2(M+1)\rceil\) evaluations.
Choosing the smallest true threshold gives the minimum \(j\)-th coordinate among members of \(A_{j-1}\). Hence restricting to \(b_j\le a_j\) is equivalent to restricting to \(b_j=a_j\), and the restricted set remains nonempty. Together with the preceding invariant, this establishes the next invariant.
After all coordinates are determined, the remaining types dominated by \(a\) are exactly those equal to \(a\). Distinctness of support types makes this set a singleton. Therefore the additional query returns \(F_T(a)=\mu_a\), rather than a sum containing other remaining masses.
Each iteration recovers one previously unrecovered supported type and its correct mass. Since the promised support size is \(\tau\), the remaining support is nonempty before each of the \(\tau\) iterations, and all supported pairs have been recovered afterward.
The stated count follows directly: at most \(n\lceil\log_2(M+1)\rceil\) coordinate queries and one mass query per iteration. Thus the total is at most
\(\tau\bigl(m\lceil\log_2(M+1)\rceil+1\bigr)\).
The bound also covers \(M=1\), \(n=1\), and \(\tau=1\).
The denominator-product argument is valid. Under the promised total encoding-length bound, the reduced denominators satisfy \(\log_2 Q=O(L)\). Every subset sum has denominator dividing \(Q\) and value between \(0\) and \(1\), so its reduced numerator and denominator have \(O(L)\) bits.
The relevant intermediate sums and differences also remain bounded in magnitude: response coordinates sum to at most \(1\), recovered masses sum to at most \(1\), and residual masses lie between \(0\) and \(1\). Reduction after each operation therefore keeps stored rational values within the claimed bit bound. Temporary arithmetic operands and results have polynomially bounded length as well.
The binary searches query only thresholds between \(0\) and \(M\); the threshold \(-1\) is a known false endpoint. The resulting prices have bit length \(O(\log(M+1)+\log(n+1))\).
The stated number of comparisons and arithmetic operations per cumulative evaluation is sufficient. Standard exact integer arithmetic and fraction reduction take polynomial time at these bit lengths. Together with the query count, this proves the claimed polynomial bit running time in the oracle model.
The contextual claim about Section 4 is supported: it gives an \(O(nB\log M)\) query upper bound for positive-weight bid lists. [Cited paper, Section 4](https://arxiv.org/pdf/2005.01496)
The recovery proof does not invoke that result as a theorem needed for correctness, so no extension of its hypotheses to rational masses is assumed.
No additional clarification or repair is required. The polynomial upper bound settles the requested polynomial-versus-superpolynomial alternative; a matching lower bound was not required.
⟨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.