Answer: Deterministic polynomial-time solvable in \(\tau\) and \(L\).
Lemma 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateI-critical and II-critical prices are computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(T\) with rational masses \(\mu_t\ge 0\) summing to \(1\), public budgets \(b_t\), per-unit values \(v_t\), reserve price \(v_s>0\), and per-capita supply \(q>0\), define \(D_\mu(p)=\sum_{t\in T}\mu_t\,\mathbf{1}[p\le v_t]\left\lfloor b_t/p\right\rfloor\). Find the exact rational price \(p^\star\ge v_s\), if one exists, such that \(D_\mu(p^\star)>q\) and \(D_\mu(p^\star+\varepsilon)\le q\) for every \(\varepsilon>0\). Each unit of mass retains integral per-agent demand, while aggregate demand may be fractional.
A society is given by its support \(T\): the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a public budget \(b_t\) and a reported per-unit value \(v_t\), with \(0\le v_t\le b_t\). The reserve price \(v_s>0\) and per-capita supply \(q>0\) are inputs. All numerical inputs are binary rationals; \(L\) is their total encoding length together with the support list.
For real prices \(p\ge v_s\), define \(D_\mu(p)=\sum_{t\in T}\mu_t\mathbf{1}[p\le v_t]\lfloor b_t/p\rfloor\). Individual demand is integral and uncapped; aggregate demand may be fractional. Equality with a valuation permits demand.
The computational problem is to return an exact rational \(p^\star\ge v_s\) satisfying \(D_\mu(p^\star)>q\) and \(D_\mu(p^\star+\varepsilon)\le q\) for every real \(\varepsilon>0\), or report that none exists.
Is this exact critical-price computation solvable in time polynomial in \(\tau\) and \(L\), or is it NP-hard?
For a finite society of \(n\) buyers and \(m\) identical units, with individual demand capped at \(m\), computing both kinds of critical prices has a stated \(O(mn^2)\) algorithm, polynomial in the numerical supply \(m\) ([Xiao, Song, and Khoussainov](https://cdn.aaai.org/ojs/20458/20458-13-24471-1-2-20220628.pdf)).
No result settling this exact rational-mass, uncapped-demand problem was verified.
The exact critical-price computation is solvable in deterministic time polynomial in \(\tau\) and \(L\).
The algorithm uses exact bisection to isolate the critical breakpoint, then recovers its rational value directly. The key is that, although there may be exponentially many breakpoints, their denominators have polynomially many bits.
Use the standard binary encoding of a rational as a numerator and a positive denominator written in binary. Write each numerical input as \(a/d\), and let \(h\ge 1\) be the maximum bit length of any such numerator or denominator. Thus \(h\le L\), every nonnegative input is less than \(2^h\), and every positive input is at least \(2^{-h}\).
Set \(U=2^h\). Then \(U>v_s\), \(U>v_t\) for every type, and \(D_\mu(U)=0\).
On the price domain \(p\ge v_s\), every demand change occurs at a point in the finite set
\(\displaystyle \mathcal C=\{v_t:t\in T,\ v_t\ge v_s\}\ \cup\ \bigcup_{t\in T}\left\{\frac{b_t}{k}:k\in\mathbb Z,\ 1\le k\le\left\lfloor\frac{b_t}{v_s}\right\rfloor\right\}.\)
Indeed, the valuation indicator changes immediately after \(v_t\), and the floor changes immediately after a price \(b_t/k\). Including points at which valuation restrictions suppress a floor change only enlarges this set.
For any integer \(k\) appearing here,
\(\displaystyle k\le \frac{b_t}{v_s}\le 2^{2h}.\)
If \(b_t=a_t/d_t\), the breakpoint \(b_t/k\) has the representation \(a_t/(d_tk)\), whose denominator is at most \(2^{3h}\). Valuation breakpoints have denominators at most \(2^h\). Consequently, every member of \(\mathcal C\) has a rational representation with denominator at most \(H=2^{3h}\).
For distinct rational numbers \(a/d\) and \(a'/d'\) with positive denominators at most \(H\),
\(\displaystyle \left|\frac ad-\frac{a'}{d'}\right|=\frac{|ad'-a'd|}{dd'}\ge\frac1{H^2}=2^{-6h},\)
because the nonzero integer \(ad'-a'd\) has absolute value at least \(1\).
Thus distinct candidate breakpoints are separated by at least \(\delta=2^{-6h}\). The algorithm will use this bound without enumerating \(\mathcal C\).
Each summand of \(D_\mu(p)\) is nonincreasing for positive prices. Therefore \(D_\mu\) is nonincreasing.
If \(D_\mu(v_s)\le q\), then \(D_\mu(p)\le q\) for every \(p\ge v_s\), so no requested price exists.
Suppose instead that \(D_\mu(v_s)>q\), and define
\(\displaystyle S=\{p\ge v_s:D_\mu(p)>q\},\qquad r=\sup S.\)
This set is nonempty and bounded above by \(U\).
We claim that \(D_\mu(r)>q\). If \(r=v_s\), this follows from the assumption. If \(r>v_s\), each individual demand is constant on some interval immediately to the left of \(r\), including \(r\) itself:
Since the support is finite, \(D_\mu\) is constant on \((r-\eta,r]\) for some \(\eta>0\). The definition of the supremum provides a point of \(S\) in this interval, so \(D_\mu(r)>q\).
Every price greater than \(r\) has demand at most \(q\), by the definition of \(r\). Hence \(r\) satisfies the requested conditions. Monotonicity also gives
\(\displaystyle S=[v_s,r].\)
Moreover, \(r\in\mathcal C\): otherwise every individual demand would be constant on a common interval immediately to its right, contradicting the definition of \(r\).
Finally, the requested price is unique. If two such prices satisfied \(p_1<p_2\), the condition at \(p_1\), with \(\varepsilon=p_2-p_1\), would imply \(D_\mu(p_2)\le q\).
Write this unique price as \(p^\star=r\). We have proved that it exists exactly when \(D_\mu(v_s)>q\).
After the existence check, initialize \(\ell=v_s\) and \(u=U\). Maintain
\(\displaystyle D_\mu(\ell)>q,\qquad D_\mu(u)\le q.\)
At each iteration, evaluate demand exactly at \(z=(\ell+u)/2\). If \(D_\mu(z)>q\), replace \(\ell\) by \(z\); otherwise replace \(u\) by \(z\).
Since \(S=[v_s,p^\star]\), these invariants imply
\(\displaystyle \ell\le p^\star<u.\)
In particular, if a midpoint equals \(p^\star\), its demand is strictly greater than \(q\), so it becomes the lower endpoint.
Perform \(N=7h+1\) iterations. The resulting width satisfies
\(\displaystyle u-\ell=\frac{U-v_s}{2^N}<\frac{2^h}{2^{7h+1}}=2^{-6h-1}<\delta.\)
Therefore \([\ell,u)\) contains at most one distinct member of \(\mathcal C\), and that member is \(p^\star\).
Let \(A=\{t\in T:\ell\le v_t\}\) be the types active at \(\ell\). For each \(t\in A\), compute
\(\displaystyle k_t=\left\lfloor\frac{b_t}{\ell}\right\rfloor,\qquad c_t=\min\left\{v_t,\frac{b_t}{k_t}\right\}.\)
These divisions are well-defined: \(\ell\le v_t\le b_t\) implies \(k_t\ge 1\). Also \(A\) is nonempty because \(D_\mu(\ell)>q>0\).
Return
\(\displaystyle c=\min_{t\in A}c_t.\)
We now prove that \(c=p^\star\).
First, \(c_t\ge\ell\) for every active type, so \(c\ge\ell\). For each active type, the definition of \(c\) gives \(c\le v_t\) and \(c\le b_t/k_t\). Hence
\(\displaystyle k_t\le\frac{b_t}{c}\le\frac{b_t}{\ell}<k_t+1,\)
so its demand at \(c\) remains exactly \(k_t\). Every type inactive at \(\ell\) remains inactive at \(c\), because \(c\ge\ell>v_t\). Therefore
\(\displaystyle D_\mu(c)=D_\mu(\ell)>q.\)
It follows that \(c\le p^\star<u\).
Furthermore, \(c\in\mathcal C\). The minimum defining \(c\) is attained at a valuation or a budget breakpoint \(b_t/k_t\); in the latter case, \(b_t/k_t\ge\ell\ge v_s\), so its index is within the range defining \(\mathcal C\).
Thus \(c\) and \(p^\star\) both belong to \(\mathcal C\cap[\ell,u)\). The separation bound makes this intersection contain at most one distinct point. Consequently, \(c=p^\star\), completing the correctness proof.
It remains to show that exact arithmetic does not make the algorithm exponential.
Bisection prices. After \(j\) iterations, both endpoints lie on the grid
\(\displaystyle v_s+(U-v_s)\frac{r}{2^j},\qquad 0\le r\le 2^j.\)
Writing \(v_s=a_s/d_s\), a grid point has the representation
\(\displaystyle \frac{a_s2^j+(Ud_s-a_s)r}{d_s2^j}.\)
Its numerator and denominator have \(O(h+j)\) bits. Since \(j\le N=O(h)\), every evaluated price has \(O(L)\) bits. Maintaining these grid representations avoids denominator growth.
Individual demands. At any evaluated price \(p\ge v_s\),
\(\displaystyle \left\lfloor\frac{b_t}{p}\right\rfloor\le\frac{b_t}{v_s}\le 2^{2h}.\)
The quotient therefore has \(O(L)\) bits and can be computed by exact integer division on \(O(L)\)-bit operands.
Aggregate comparisons. Write \(\mu_t=a_{\mu,t}/d_{\mu,t}\) and \(q=a_q/d_q\). Precompute
\(\displaystyle Q=d_q\prod_{t\in T}d_{\mu,t},\qquad w_t=Q\mu_t,\qquad w_q=Qq.\)
All these quantities are integers. The bit length of \(Q\) is \(O(L)\), since the total encoding length includes all denominator lengths. Then demand exceeds supply exactly when
\(\displaystyle \sum_{t:\,p\le v_t}w_t\left\lfloor\frac{b_t}{p}\right\rfloor>w_q.\)
The sum also has \(O(L)\) bits: using \(\sum_t\mu_t=1\),
\(\displaystyle QD_\mu(p)\le Q\sum_t\mu_t\frac{b_t}{v_s}\le Q\,2^{2h}.\)
Each demand evaluation uses \(O(\tau)\) integer operations on \(O(L)\)-bit operands. There are \(O(L)\) evaluations, followed by one pass over the support to recover \(c\). Standard integer arithmetic therefore gives a polynomial running time in \(\tau\) and \(L\).
The output itself has \(O(L)\) bits, since it is either an input valuation or \(b_t/k_t\) with \(k_t\le 2^{2h}\).
The cited paper computes critical prices by enumerating individual change-points under the finite supply cap and states an \(O(mn^2)\) running time. [Xiao, Song, and Khoussainov, “Multi-Unit Auction in Social Networks with Budgets,” Lemma 2](https://cdn.aaai.org/ojs/20458/20458-13-24471-1-2-20220628.pdf).
The proof above establishes the requested result independently. It neither expands rational masses into buyers nor enumerates uncapped demand levels. Polynomial bit bounds, breakpoint separation, and exact monotonic bisection suffice.
⟨structured verdict parsed — rendered above⟩
The prover’s polynomial-time claim is correct. The argument resolves the exact problem in USER_TASK, including rational masses, uncapped individual demand, equality at valuations, and the possibility that no critical price exists. No major or minor mathematical issues were found.
The encoding assumptions are valid. With \(h\) defined as the maximum numerator or denominator bit length, every nonnegative input is less than \(2^h\), and every positive input is at least \(2^{-h}\). Consequently, \(U=2^h\) exceeds every valuation and the reserve, and \(D_\mu(U)=0\).
The candidate set \(\mathcal C\) contains every possible demand-change point on the required domain:
The index bound \(k\le b_t/v_s\le 2^{2h}\) is correct. The representation \(b_t/k=a_t/(d_tk)\) therefore has denominator at most \(2^{3h}\). Reduction to lowest terms is unnecessary for this upper bound.
The separation calculation is also correct: distinct rationals with positive denominators bounded by \(H\) differ by at least \(H^{-2}\), because their cross-product difference is a nonzero integer. Thus \(\delta=2^{-6h}\) is a valid uniform separation bound.
Every individual demand is nonnegative and nonincreasing for positive prices. Its product form causes no monotonicity problem: while eligible, demand decreases with price; after eligibility ends, demand becomes zero. Positive masses preserve monotonicity under aggregation.
Therefore, \(D_\mu(v_s)\le q\) correctly implies nonexistence.
When \(D_\mu(v_s)>q\), the set \(S\) is nonempty and bounded. The proof that its supremum \(r\) belongs to \(S\) is valid:
For \(r>v_s\), the supremum property supplies an element of \(S\) in this interval. For \(r=v_s\), the initial strict inequality supplies the conclusion directly. Hence \(D_\mu(r)>q\).
Every price above \(r\) lies outside \(S\), establishing the condition for every positive real increment. Monotonicity then justifies \(S=[v_s,r]\).
Membership \(r\in\mathcal C\) follows from local constancy to the right at any point outside \(\mathcal C\). The uniqueness argument correctly applies the first price’s condition with increment equal to the difference between two proposed prices.
The endpoint invariants are initialized correctly and preserved by each exact comparison.
Since demand remains strictly above supply at the critical price itself, the resulting enclosure is correctly written as \(\ell\le p^\star<u\). In particular, a midpoint equal to \(p^\star\) becomes the lower endpoint.
The iteration count and width calculation are correct:
\(u-\ell=(U-v_s)/2^{7h+1}<2^{-6h-1}<\delta\).
Thus \([\ell,u)\) contains the critical price and at most one distinct candidate breakpoint. Coincident breakpoints from multiple types do not affect this conclusion.
The active set is nonempty because \(D_\mu(\ell)>q>0\). For every active type, \(\ell\le v_t\le b_t\), so \(k_t\ge1\); all recovery divisions are defined.
Each \(c_t\) is at least \(\ell\). Because \(c\) is their minimum, every active type satisfies \(c\le v_t\) and \(c\le b_t/k_t\). Together with \(c\ge\ell\), these inequalities establish precisely the displayed floor bounds and preserve demand \(k_t\) at \(c\).
Inactive types remain inactive, since their valuations are strictly below \(\ell\). Hence \(D_\mu(c)=D_\mu(\ell)>q\), implying \(c\le p^\star<u\).
The attained minimum is a valuation breakpoint or a budget breakpoint with an admissible index. Therefore \(c\in\mathcal C\cap[\ell,u)\). The already-proved separation bound correctly forces \(c=p^\star\).
The complexity analysis accounts for numerical magnitudes rather than treating exact arithmetic as constant time.
The bisection grid representation is algebraically correct and has numerator and denominator bit lengths \(O(h+j)\). With \(j=O(h)\), evaluated prices have \(O(L)\) bits. The stated representation prevents uncontrolled denominator growth.
Individual quotients are bounded by \(2^{2h}\), and their computation uses integer operands of \(O(L)\) bits.
The common denominator \(Q=d_q\prod_t d_{\mu,t}\) has \(O(L)\) bits because denominator lengths are included in the total input length. The weights and supply threshold are integers with \(O(L)\) bits. The aggregate bound using \(\sum_t\mu_t=1\) correctly gives \(QD_\mu(p)\le Q2^{2h}\). Exact comparisons therefore remain polynomial in bit complexity.
There are \(O(L)\) demand evaluations, each requiring \(O(\tau)\) integer operations on polynomial-size operands, followed by polynomial-time recovery. The returned rational also has \(O(L)\) bits. This establishes the claimed polynomial running time.
The description of the earlier algorithm is accurate: Lemma 2 enumerates capped individual change-points and states an \(O(mn^2)\) running time. [Xiao, Song, and Khoussainov, Lemma 2](https://cdn.aaai.org/ojs/20458/20458-13-24471-1-2-20220628.pdf).
The present correctness and complexity argument does not invoke that lemma. It directly handles the support representation and rational aggregate demand required by USER_TASK.
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.