Answer: The optimal deterministic worst-case query count is \(0\) when \(m=\tau=1\), and \(\tau(2^m-1)\) otherwise. A deterministic mass-allocation counterpart \(B\) of MPAR attains this bound and satisfies the stated no-uniform-improvement guarantee.
Theorem 15 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateNo admissible, admissibly equipped and de- terministic algorithm that calls the valuation function for feasible combinations only will require fewer calls than the MPAR algorithm. The worst case for the MPAR algorithm will occur if all feasible allocations that distribute all goods to the con- sumers are Pareto-optimal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goods \(C\), a finite support \(T\) of valuation types with rational masses \(\mu_t\), rational per-capita supplies \(q_j\), and oracle access to each type’s utility \(u_t(S)\), characterize the deterministic worst-case number of distinct type-bundle queries needed to return a welfare-maximizing feasible mass allocation \(x_{t,S}\), when queries are allowed only for type-bundle pairs used by some feasible allocation. Does a fractional analogue of MPAR attain a matching no-uniform-improvement guarantee?
Let \(C\) contain \(m\geq1\) goods. A society is given by its support: the list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Supplies \(q_j\geq0\) are binary rationals.
Each type has an unknown utility \(u_t:2^C\to\mathbb Q_{\geq0}\), with \(u_t(\varnothing)=0\); monotonicity is not assumed. Free ordinal access reveals bundles successively in a fixed total order of nonincreasing utility, with arbitrary fixed tie-breaking. Exact value queries reveal \(u_t(S)\).
A feasible mass allocation has rational coordinates \(x_{t,S}\geq0\), satisfies \(\sum_{S\subseteq C}x_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni j}x_{t,S}\leq q_j\), and has welfare \(\sum_{t,S}x_{t,S}u_t(S)\). Goods may remain unallocated.
A value query \((t,S)\) is permitted only if some feasible allocation has \(x_{t,S}>0\). Count distinct queried pairs; the empty-bundle value is already known. Algorithms must return an exact welfare maximizer for every permitted utility profile; other computation is unrestricted.
Let \(Q_A(I)\) be this count for deterministic algorithm \(A\) on instance \(I\). State query bounds and any running times in \(m,\tau,L\), where \(L\) is the binary length of the explicit input plus the maximum binary length of an oracle value.
What is the optimal deterministic worst-case number of permitted type-bundle value queries needed to return a welfare-maximizing feasible mass allocation?
Can a deterministic mass-allocation counterpart \(B\) of MPAR attain that bound and the no-uniform-improvement guarantee that no correct deterministic \(A\) satisfies \(Q_A(I)<Q_B(I)\) for every instance \(I\)?
In the discrete setting, MPAR enumerates feasible allocations undominated in the fixed bundle rankings and selects one of maximum welfare. A known theorem gives it a no-uniform-improvement guarantee among deterministic algorithms using the prescribed rank-lattice access and querying aggregate values only of feasible allocations. [Conen–Sandholm](https://www.cs.cmu.edu/~sandholm/AAAI02-cosa-mechanism.pdf)
No result settling this precise mass-allocation query model was located.
The optimal deterministic worst-case query count, over all instances with given \(m\) and \(\tau\), is
\(\displaystyle D(m,\tau)= \begin{cases} 0,&m=\tau=1,\\ \tau(2^m-1),&\text{otherwise}. \end{cases}\)
A deterministic mass-allocation counterpart \(B\) of MPAR attains this bound and satisfies the requested no-uniform-improvement guarantee. In every nonexceptional parameter regime, a single instance forces every correct deterministic algorithm to query all nonempty type–bundle pairs.
The guarantee with strict improvement on every instance is already obstructed by zero-supply instances. The proof below establishes it on instances with strictly positive supplies and strictly ranked utilities.
The cited discrete theorem concerns rank-lattice access and aggregate valuation queries. Its hypotheses differ from this problem, so the argument below is independent of that theorem. [Conen–Sandholm, Definitions 9–10 and Theorem 15](https://www.cs.cmu.edu/~sandholm/AAAI02-cosa-mechanism.pdf)
Define \(C_+=\{j\in C:q_j>0\}\) and \(k=|C_+|\).
Lemma 1. A nonempty pair \((t,S)\) is permitted exactly when \(S\subseteq C_+\).
Proof. If \(j\in S\) and \(q_j=0\), feasibility implies
\(\displaystyle 0\leq x_{t,S}\leq\sum_{s}\sum_{T\ni j}x_{s,T}\leq q_j=0.\)
Conversely, suppose \(S\subseteq C_+\). Choose the positive rational number
\(\displaystyle \delta=\frac12\min\bigl(\{\mu_t\}\cup\{q_j:j\in S\}\bigr).\)
Allocate mass \(\delta\) of type \(t\) to \(S\), its remaining mass to the empty bundle, and every other type entirely to the empty bundle. This allocation is feasible. \(\square\)
Thus there are exactly \(\tau(2^k-1)\) permitted nonempty pairs. Querying all of them and solving the resulting rational linear program gives an exact optimizer. In particular,
\(\displaystyle D(m,\tau)\leq\tau(2^m-1).\)
If \(k=0\), no queries are needed. If \(k=\tau=1\), allocating mass \(\min\{1,q_j\}\) to the sole permitted nonempty bundle is optimal because its utility is nonnegative. This proves the exceptional bound \(D(1,1)=0\).
These are bounds for each instance; the matching worst-case lower bound follows next.
Assume either \(m\geq2\), or \(m=1\) and \(\tau\geq2\). Label the goods \(1,\ldots,m\).
Choose positive dyadic masses summing to one. For example, with \(h=\lceil\log_2\tau\rceil\), take
\(\displaystyle \mu_t=2^{-h}\quad(t<\tau),\qquad \mu_\tau=1-(\tau-1)2^{-h}.\)
Set \(q_j=\frac12\) for every good, and define the baseline utilities
\(\displaystyle u_t^0(S)=\sum_{j\in S}2^{j-1}\qquad\text{for every }t,S.\)
These utilities satisfy all stated assumptions. Distinct bundles have distinct integer values, so every type’s ranking is strict. The assumptions do not require different listed types to have different utility functions.
Let \(P\) be the feasible allocation polytope, allowing real coordinates temporarily, and define
\(\displaystyle F=\left\{x\in P: \sum_t\sum_{S\ni j}x_{t,S}=\frac12\text{ for every }j\right\}.\)
For every feasible \(x\), its baseline welfare is
\(\displaystyle W^0(x)= \sum_{j=1}^m2^{j-1}\left(\sum_t\sum_{S\ni j}x_{t,S}\right) \leq\frac12\sum_{j=1}^m2^{j-1}.\)
The rational allocation \(x^0_{t,S}=\mu_t/2^m\) attains this upper bound. Since every coefficient \(2^{j-1}\) is positive, an allocation is baseline-optimal exactly when it belongs to \(F\).
Lemma 2. For every nonempty pair \((t,S)\), the coordinate \(x_{t,S}\) is nonconstant on the rational allocations in \(F\).
Proof for \(m\geq2\). Choose distinct goods \(a,b\), and put \(R=S\setminus\{a,b\}\). At type \(t\), define a direction \(d\) by
\(\displaystyle d_{t,R}=d_{t,R\cup\{a,b\}}=1,\qquad d_{t,R\cup\{a\}}=d_{t,R\cup\{b\}}=-1,\)
with every other coordinate zero.
The four bundles are distinct, and \(S\) is one of them. The direction preserves type \(t\)’s total mass because its entries sum to zero. It preserves consumption of \(a\) and \(b\) because each has one positive and one negative contribution. Every good in \(R\) has total contribution zero; all other goods have no contribution.
Consequently, for a sufficiently small positive rational \(\eta\), both \(x^0+\eta d\) and \(x^0-\eta d\) belong to \(F\). Their \((t,S)\) coordinates differ.
Proof for \(m=1,\ \tau\geq2\). Choose another type \(s\neq t\). Increase the singleton coordinate of type \(t\) and the empty coordinate of type \(s\), while decreasing the empty coordinate of type \(t\) and the singleton coordinate of type \(s\), by the same amount. This preserves both type masses and total good consumption. Small rational perturbations of either sign from \(x^0\) remain feasible and change \(x_{t,\{1\}}\). \(\square\)
Theorem 3. On the baseline instance above, every correct deterministic algorithm queries every nonempty pair.
Proof. Run a correct deterministic algorithm \(A\) on the baseline instance. Suppose it terminates without querying some nonempty pair \((t,S)\), and returns \(x\).
Correctness implies \(x\in F\). By Lemma 2, there is a rational \(y\in F\) with \(y_{t,S}\neq x_{t,S}\). Choose \(\sigma\in\{-1,1\}\) so that
\(\displaystyle \sigma(y_{t,S}-x_{t,S})>0.\)
Modify only the unqueried value, setting
\(\displaystyle u_t^\sigma(S)=u_t^0(S)+\frac{\sigma}{4}.\)
All other values remain unchanged. The modified value is nonnegative. Moreover, distinct baseline bundle values differ by at least one, so this perturbation preserves every complete bundle ranking.
Every value query made in the baseline run receives the same answer on the modified profile. Every ordinal response is also unchanged. Determinism therefore implies, inductively through the transcript, that \(A\) makes the same queries and returns the same \(x\).
But \(x\) and \(y\) have equal baseline welfare, whereas their modified welfare difference is
\(\displaystyle W^\sigma(y)-W^\sigma(x) =\frac{\sigma}{4}(y_{t,S}-x_{t,S})>0.\)
Thus \(x\) is not optimal for the modified profile, contradicting correctness. \(\square\)
All \(\tau(2^m-1)\) nonempty pairs are permitted because every supply is positive. Together with Section 2, this proves the asserted exact worst-case bound. The masses, supplies, baseline values, and perturbed values all have binary descriptions of length polynomial in \(m\) and \(\tau\).
A mass allocation gives each type a distribution over bundles. The appropriate ordinal dominance relation compares cumulative mass in successive ranking prefixes.
Restrict attention to the permitted bundles \(2^{C_+}\). Write each type’s filtered ranking as
\(\displaystyle S_{t,1},\ldots,S_{t,n},\qquad n=2^k.\)
Let \(P\) now denote the feasible polytope using these bundles. It is nonempty, bounded, and rational: assigning every type to the empty bundle is feasible, and \(0\leq x_{t,S}\leq\mu_t\).
For \(1\leq r<n\), define
\(\displaystyle F_{t,r}(x)=\sum_{\ell=1}^{r}x_{t,S_{t,\ell}}.\)
Say that \(y\) rank-dominates \(x\) if \(F_{t,r}(y)\geq F_{t,r}(x)\) for all \(t,r\), with at least one strict inequality. Define also
\(\displaystyle H(x)=\sum_t\sum_{r=1}^{n-1}F_{t,r}(x).\)
Put \(v_{t,r}=u_t(S_{t,r})\). The rankings guarantee \(v_{t,r}\geq v_{t,r+1}\), including when ties occur. Summation by parts gives
\(\displaystyle \sum_{r=1}^n x_{t,S_{t,r}}v_{t,r} = \mu_t v_{t,n} +\sum_{r=1}^{n-1}(v_{t,r}-v_{t,r+1})F_{t,r}(x). \)
Therefore, rank-dominance implies weakly greater welfare. Strict rank-dominance also implies strictly greater \(H\), regardless of utility ties.
Lemma 4. For every permitted utility profile, some welfare-maximizing vertex of \(P\) is rank-undominated.
Proof. Let \(P_W\) be the face maximizing welfare over \(P\). Maximize \(H\) over \(P_W\), and choose a vertex \(v\) of the resulting nonempty face. A vertex of a face of a polytope is a vertex of the original polytope.
If some \(y\in P\) rank-dominated \(v\), the summation-by-parts identity would give \(W(y)\geq W(v)\). Since \(v\) already maximizes welfare, \(y\in P_W\). But strict dominance gives \(H(y)>H(v)\), contradicting the choice of \(v\). \(\square\)
Let \(E\) be the finite set of vertices of \(P\) that are rank-undominated by any allocation in \(P\). Testing only dominance by individual vertices would not suffice.
Fix deterministic orders for enumeration, queries, and final tie-breaking.
Every query in step 4 is permitted, witnessed by the corresponding feasible vertex. All returned allocations are rational because \(P\) is rational. Lemma 4 proves correctness, including with arbitrary fixed tie-breaking.
This is a mass counterpart of MPAR: enumerate ordinally undominated feasible candidates and select a welfare maximizer. Its candidate set is finite because undominated vertices suffice.
Its query bound is
\(\displaystyle Q_B(I)\leq\tau(2^k-1)\leq\tau(2^m-1).\)
When \(k=\tau=1\), the feasible polytope is an interval, and its better-ranked endpoint is its unique undominated vertex. Thus \(B\) makes zero queries in the exceptional case.
Set \(N=\tau2^k\). Introduce one slack variable for each of the \(k\) supply inequalities. The resulting standard-form system has \(N+k\) variables and \(\tau+k\) independent equality constraints.
Enumerating all column bases therefore generates every vertex, with at most
\(\displaystyle R=\binom{N+k}{\tau+k}\)
bases to examine. Each basis can be checked using exact rational linear algebra. The coefficient matrix has entries in \(\{0,1\}\), and determinant bounds imply that generated vertex coordinates have binary length polynomial in \(m,\tau,L\).
For each vertex \(v\), test dominance by solving the rational linear program
\(\displaystyle \max H(y) \quad\text{subject to}\quad y\in P,\qquad F_{t,r}(y)\geq F_{t,r}(v)\ \text{for all }t,r. \)
The vertex is dominated exactly when this optimum exceeds \(H(v)\): every prefix difference is constrained to be nonnegative, and their sum is strictly positive precisely when at least one is positive.
The program is feasible, bounded, and has rational data of polynomial binary length, so the standard polynomial-time theorem for exact rational linear programming applies. Thus the complete procedure takes time polynomial in \(R,N,m,\tau,L\), plus time \(O(\tau m2^m)\) to read and filter the full rankings. A coarser bound is
\(\displaystyle O(\tau m2^m) +(\tau2^k+k)^{O(\tau+k)}\operatorname{poly}(m,\tau,L). \)
The direct algorithm that queries every permitted nonempty pair and solves the welfare linear program runs in \(\operatorname{poly}(\tau2^k,m,\tau,L)\) time. Vertex enumeration supplies the MPAR counterpart, rather than an improved running-time bound.
Fix nonexceptional \(m,\tau\), and let \(I^*\) be the baseline instance of Section 3. Theorem 3 implies that every correct deterministic \(A\) satisfies
\(\displaystyle Q_A(I^*)=\tau(2^m-1).\)
Since \(B\) is correct and obeys the same upper bound,
\(\displaystyle Q_B(I^*)=\tau(2^m-1).\)
Consequently, no correct deterministic \(A\) can satisfy \(Q_A(I)<Q_B(I)\) for every instance \(I\). In the exceptional case, \(B\) uses zero queries, which also precludes strict improvement.
This proves exactly the requested guarantee; it does not assert that \(B\) minimizes queries separately on every instance.
⟨structured verdict parsed — rendered above⟩
The claimed query bound and the construction of \(B\) are sound. I found no false central step or missing mathematical argument. There is one minor omission in the statement of the theorem supporting the running-time claims.
The optimal deterministic worst-case query count established by the output is
\[
D(m,\tau)=
\begin{cases}
0,&m=\tau=1,\\
\tau(2^m-1),&\text{otherwise}.
\end{cases}
\]
The proposed \(B\) attains this bound and satisfies the requested no-uniform-improvement guarantee.
Lemma 1 is correct in both directions.
Thus the permitted nonempty pairs are exactly those counted by \(\tau(2^k-1)\). Querying these values determines the entire relevant welfare objective. The feasible polytope is nonempty, bounded, and rational, so an exact rational maximizing allocation exists.
The zero-query cases are also correct. When \(k=0\), only the empty bundle can receive mass. When \(k=\tau=1\), nonnegativity of singleton utility makes allocating the maximum feasible singleton mass optimal, including when its utility is zero.
The masses in Section 3 are positive dyadic rationals and sum to one, including when \(\tau=1\). Supplies are positive binary rationals.
The additive baseline utilities assign distinct integer values to distinct bundles. Consequently, the claimed strict rankings and minimum utility separation of one are correct.
The welfare computation is correct. Every supply constraint contributes a nonnegative slack multiplied by a strictly positive coefficient. Therefore, attaining the displayed upper bound is equivalent to saturating every supply constraint.
The allocation \(x^0_{t,S}=\mu_t/2^m\) has the required type masses and consumes exactly one-half unit of each good. It is rational and strictly positive in every coordinate. Hence \(F\) is nonempty and is exactly the baseline optimal set.
Using identical utility functions for different listed type labels does not violate an explicit assumption of USER_TASK.
Lemma 2 is correct.
For \(m\geq2\), the four specified bundles are distinct, and \(S\) is one of them regardless of which of \(a,b\) it contains. The direction preserves the type-mass equality and every good’s consumption. Since all coordinates of \(x^0\) are strictly positive, sufficiently small rational perturbations of either sign remain feasible.
For \(m=1,\tau\geq2\), the direction involving two types preserves both type masses and total consumption. Positivity of the baseline coordinates again permits perturbations of either sign.
These arguments establish nonconstancy on rational allocations, as required. They do not merely establish variation among real allocations.
Theorem 3 is valid.
Correctness on the baseline forces the returned allocation \(x\) into \(F\). Nonconstancy of the unqueried coordinate supplies a rational \(y\in F\) with a different coordinate value.
The perturbation by \(\sigma/4\):
Query permission depends only on masses and supplies, which remain unchanged. Thus there is no permission-related difference between the two executions.
Determinism gives the same transcript and returned allocation. The displayed welfare difference is strictly positive, proving that this returned allocation fails on the modified profile.
The argument forces every nonempty pair on one baseline instance. It therefore establishes the claimed simultaneous lower bound, rather than only separate lower bounds using different instances.
The summation-by-parts identity is correct. Its coefficients \(v_{t,r}-v_{t,r+1}\) are nonnegative, so rank-dominance implies weakly greater welfare even with utility ties.
Strict rank-dominance increases \(H\), because all prefix differences are nonnegative and at least one is positive.
Lemma 4 is also correct:
The statement that dominance must be tested against all allocations, rather than only individual vertices, is appropriate. The proposed LP performs that test.
No strict-utility assumption is needed here.
The set \(E\) is finite and nonempty by Lemma 4. If it has one member, that member is welfare-optimal. Otherwise, every unknown value contributing to any candidate’s welfare is queried.
Each queried pair has a feasible witnessing vertex with positive mass, satisfying the permission rule. The empty-bundle contribution is already known. Therefore, the final welfare comparisons use fully determined objectives.
Rationality of the returned vertices follows from rationality of the polytope.
For \(k=\tau=1\), the ranking chooses a unique undominated endpoint whenever the interval is nondegenerate. This remains correct when utilities tie: either endpoint selected by the fixed ranking is welfare-optimal. When the interval degenerates, its sole point is the unique candidate.
Thus \(B\) is correct and satisfies the asserted query bounds.
The standard-form system has the claimed dimensions. Its equality rows are independent: empty-bundle columns isolate the type rows, and slack columns isolate the supply rows.
Enumerating column bases covers every vertex, including degenerate vertices. Singular bases can be rejected. Determinant bounds apply to matrices of order \(\tau+k\), so the claimed polynomial coordinate bit lengths are consistent with the stated parameters.
The dominance LP is feasible because it contains \(v\), and bounded because its feasible region lies in \(P\). Its objective exceeds \(H(v)\) exactly when some prefix inequality is strict.
The enumeration and LP counts support the stated running-time bounds. The full-ranking reading cost is explicitly included for \(B\); the direct all-values algorithm can operate without reading rankings.
Minor issue — Section 5, exact rational linear programming theorem. The output invokes a “standard polynomial-time theorem” without stating its precise guarantee or encoding measure. The application’s hypotheses are verified, so this is an expositional omission rather than a mathematical obstruction.
Minimum clarification: State the exact rational LP theorem being used, including exact optimizer recovery and polynomial dependence on total binary encoding length, and identify a reference. No additional mathematical argument is needed.
Section 6 correctly establishes the requested quantifiers. For every correct deterministic \(A\), the same nonexceptional baseline instance forces equality with \(B\)’s query count. In the exceptional regime, \(B\)’s zero count precludes strict improvement.
The proof does not claim instance-by-instance query optimality, and that stronger property is unnecessary.
The cited discrete theorem is not used as a premise. The description of its distinct access restrictions agrees with [Definitions 9–10 and Theorem 15](https://www.cs.cmu.edu/~sandholm/AAAI02-cosa-mechanism.pdf).
The output resolves exact query complexity and supplies running-time bounds. It does not establish a conventional polynomial-time or complexity-class hardness classification, so the requested continuous-complexity field is marked unresolved.
⟨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.