Answer: Polynomial-time solvable
Theorem 5.6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet R be a normalized DA rule that is IC and non-discriminating. Assume that the trade size decided by this rule is a function of the Optimal Trade Size l only, and the payments can be decided using O(1) prices when knowing l. Then the Pivot Protocol can be implemented with only O(log(n)) messages sent and received by each market, where each message contains a single price.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For a supply chain with \(h\) converter markets, each market initially knows only its own finite-support rational distribution over unit costs or values, with total mass \(1\) and common population scale. Let \(c_j(u)\) be the \(u\)-quantile of costs in supply role \(j\), for \(j=0,\ldots,h\), and \(b(u)\) the \(u\)-quantile of buyer values in descending order. Define \(q^*=\max\{q\in[0,1]: b(q)\ge\sum_{j=0}^{h}c_j(q)\}\), using specified one-sided quantiles at jumps. With cutoff mass split proportionally among tied types, compute the exact traded mass, each role’s allocation by type, and the payments from the Pivot Protocol formulas using the corresponding one-sided quantiles. What are the worst-case message and bit complexities as functions of \(h\), total support size \(\tau\), and input bit length \(L\)?
There are \(m=h+1\) goods in a linear supply chain, with \(h\geq0\) one-to-one conversion roles, an initial supplier role, and a final buyer role. All unit costs and values are nonnegative binary rationals; each role has divisible population mass \(1\), and feasible allocations trade the same mass in every role.
A society is given by its support: the list of types with positive binary-rational masses. Write \(\tau\) for the total support size across roles, not the number of possible types, and \(L\) for the total input bit length, including costs, values, and masses.
For \(0<u\leq1\), let \(c_j(u)\), \(0\leq j\leq h\), be the first cost whose cumulative mass in increasing cost order reaches \(u\); define \(b(u)\) analogously in decreasing value order. Put \(C(u)=\sum_{j=0}^{h}c_j(u)\) and \(q^*=\max(\{0\}\cup\{q\in(0,1]:b(q)\geq C(q)\})\).
Trade mass \(q=q^*\), selecting lowest costs and highest values in each role; split any partially selected cutoff group proportionally to its type masses. For \(q>0\), write \(f^-=f(q)\) and \(f^+=\lim_{u\downarrow q,\,u>q}f(u)\); at \(q=1\), set \(c_j^+=+\infty\) and \(b^+=0\), with \(C^\pm=\sum_jc_j^\pm\).
Fix the quantile extension of the VCG-based Pivot payment rule: \(P_B=\max(C^-,b^+)\), \(P_S=\min(C^+,b^-)\), and each cost role receives per traded unit \(p_j=\min\{c_j^+,P_S-\sum_{k\ne j}c_k^-\}\). Buyers pay \(P_B\) per traded unit; each type’s total payment is its allocated mass times its role’s price. Unallocated mass pays zero; when \(q=0\), all allocations and payments are zero.
The \(h+2\) nonstrategic market servers form a bidirectional path in role order, with the buyer server as pivot. Initially each knows only its own support; the topology and input-size parameters are public. A deterministic protocol must leave each server with its role’s exact allocation and payments. Messages are nonempty finite binary strings between neighbors; count all transmissions and all transmitted bits, including requests and headers, with no information conveyed through timing.
Is this exact continuous allocation-and-payment problem solvable in polynomial time, or is it NP-hard? What worst-case message and bit bounds are achievable on the path, stated together with running times in \(m,h,\tau,L\)?
For discrete unit agents, the Pivot implementation uses \(O(\log n)\) single-price messages sent and received per market when trade size depends only on the optimal trade size and payments require constantly many prices once that size is known; the VCG rule satisfies these conditions ([Babaioff–Nisan](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/babaioff04a.pdf)). No result settling the exact continuous problem specified here was located in the literature search.
The specified allocation-and-payment problem is polynomial-time solvable. Exact rational outputs can be computed without expanding masses into discrete agents.
Let \(m=h+1\). The path has \(m+1=h+2\) servers and \(m\) edges. The following deterministic protocols achieve these bounds, counting every neighbor transmission and every transmitted bit:
| Protocol | Total transmissions | Total transmitted bits | Total bit-operation time |
|---|---:|---:|---:|
| Gather supports, return a summary | Exactly \(2m=2(h+1)\) | \(O(mL)\) | \(O(\tau L^2+mL)\) |
| Search using packets containing constantly many integers | \(O(mL)\) | \(O(mL^2)\) | \(O((\tau+m\log(\tau+1))L^2)\) |
These are achievable upper bounds. Running times include processing messages and writing all outputs, using elementary integer arithmetic. Rational outputs are represented by binary numerators and denominators.
In each cost role, group equal costs and order the groups by increasing cost. In the buyer role, group equal values and order them by decreasing value. Every group has positive mass.
Let \(\mathcal T\) be the union of all positive cumulative group masses across all roles. Write its distinct elements as
\[ 0=t_0<t_1<\cdots<t_K=1. \]
There are at most \(\tau\) groups altogether, so \(K\leq\tau\).
By the definition using the first cumulative mass that reaches the requested quantity, every quantile function is constant on each interval \((t_{\ell-1},t_\ell]\). In particular, its value at \(t_\ell\) is the value throughout that interval.
Define \(\Delta(u)=b(u)-C(u)\). Each \(c_j\) is nondecreasing, and \(b\) is nonincreasing. Consequently, \(\Delta\) is nonincreasing. Therefore the indices satisfying \(\Delta(t_\ell)\geq0\) form an initial segment.
It follows directly that:
Indeed, in the second case the feasible positive quantities are exactly \((0,t_r]\). This also proves that the maximum in the definition of \(q^*\) exists.
Thus an exact algorithm only needs to inspect support breakpoints.
Use the usual explicit binary encoding of rational numerators and denominators. Finite binary expansions can be converted to this representation with linear overhead.
Let \(D\) be the product of the denominators of all input costs, values, and masses. The sum of their denominator bit lengths is at most \(L\), so \(D\) has \(O(L)\) bits. Every input rational can therefore be represented as an integer divided by \(D\).
All cumulative masses have this form, with scaled numerators between \(0\) and \(D\). Scaled costs and values have \(O(L)\) bits. A sum of at most \(m\) scaled costs also has \(O(L)\) bits: summation adds at most \(O(\log m)\) bits, and \(m\leq\tau\leq O(L)\).
For \(q>0\), all payment prices are finite. In particular, \(P_S\leq b^-\), including when \(q=1\), where \(P_S=b^-\). Rewrite each cost-role price as
\[ p_j=\min\{c_j^+,P_S-C^-+c_j^-\}. \]
The second argument is finite. Moreover, \(C^+\geq C^-\) and \(b^-\geq C^-\), hence \(P_S\geq C^-\). Thus this second argument is nonnegative. At \(q=1\), the infinite first argument simply leaves the finite second argument.
Every finite price is an integer divided by \(D\), with numerator of \(O(L)\) bits.
Now consider a cutoff group of mass \(M\), preceded by total mass \(A\). For a type of mass \(\mu_i\) in that group, the required proportional allocation is
\[ x_i=\mu_i\frac{q-A}{M}. \]
The quantile definition guarantees \(A<q\leq A+M\), so this allocation is well-defined and lies between \(0\) and \(\mu_i\). Summing over the group gives exactly \(q-A\).
Writing \(q=Q/D\), \(A=a/D\), \(M=M'/D\), and \(\mu_i=M_i/D\), we obtain
\[ x_i=\frac{M_i(Q-a)}{DM'}. \]
If the role price is \(T/D\), its total payment is
\[ x_i\frac{T}{D}=\frac{M_i(Q-a)T}{D^2M'}. \]
Both numerator and denominator have \(O(L)\) bits. Fully allocated and unallocated types have equally small representations. Consequently, all exact outputs together require \(O(\tau L)\) bits.
After scaling inputs to denominator \(D\), perform the following operations:
At a breakpoint, evaluate the interval ending there before applying its changes. Apply all changes at the same breakpoint together. This implements precisely the endpoint convention in the question.
The first interval with negative \(\Delta\) determines \(q^*\) as its left endpoint. If none is negative, \(q^*=1\). The sweep also identifies the values needed for \(C^\pm\) and \(b^\pm\).
There are \(O(\tau)\) scaling operations, \(O(\tau\log(\tau+1))\) integer comparisons, and \(O(\tau)\) sweep updates. All operands have \(O(L)\) bits. Elementary multiplication and division take \(O(L^2)\) bit operations, while comparisons and additions take \(O(L)\). Computing the prices and outputs takes another \(O(\tau L^2)\).
The resulting bound is
\[ O\bigl(\tau L^2+\tau L\log(\tau+1)\bigr)=O(\tau L^2). \]
This uses support size, not a denominator-expanded population size.
Index the cost-role servers from \(0\) through \(m-1\), with the buyer server immediately after server \(m-1\).
Server \(0\) sends its support to server \(1\). Each subsequent cost server appends its own support and forwards the resulting packet toward the buyer. The buyer adds its locally known support and performs the central computation.
Each edge carries exactly one upstream packet: \(m\) transmissions.
Ordered role records, support counts, and self-delimiting binary integer encodings suffice to parse the packet. They have constant-factor encoding overhead, so every packet has \(O(L)\) bits, including headers.
If \(q=0\), the buyer sends a zero-trade flag down the path. Every server then outputs zero allocations and payments.
If \(q>0\), the buyer sends the common summary
\[ (D,Q,U,V),\qquad Q=Dq,\quad U=DC^-,\quad V=DP_S. \]
Each cost server forwards that summary and computes locally:
The buyer computes its own allocations and \(P_B=\max(C^-,b^+)\) locally.
Each edge carries exactly one downstream packet: another \(m\) transmissions. The summary has \(O(L)\) bits, including its framing.
Thus the protocol uses exactly \(2m\) transmissions and \(O(mL)\) transmitted bits. All information is explicitly encoded; execution is driven by message receipt, with no information conveyed through timing. Processing, copying packets, and producing outputs take \(O(\tau L^2+mL)\) bit operations altogether.
A second protocol avoids transmitting support lists.
First, aggregate denominator products upstream and broadcast their product \(D\) downstream. Each server then scales and sorts its own support locally. These setup passes use \(O(m)\) transmissions and \(O(mL)\) bits.
Every breakpoint lies on the grid \(\{k/D:1\leq k\leq D\}\). Define the monotone predicate
\[ F(k)\ \Longleftrightarrow\ b(k/D)\geq\sum_{j=0}^{m-1}c_j(k/D). \]
Although \(D\) can be exponentially large, its binary length is \(O(L)\). Binary search therefore finds the largest feasible grid index \(K\), or determines that none exists, in \(O(L)\) evaluations.
For each evaluation, the buyer sends the requested index \(k\) down the path. The supplier starts an upstream response with its scaled quantile cost; every other cost server adds its scaled quantile cost and forwards the sum. The buyer compares this sum with its locally computed scaled buyer value.
Each evaluation uses \(2m\) transmissions and \(O(mL)\) bits. Each packet contains only constantly many integers, including its request and framing fields.
Section 1 proves that the answer is exactly \(q=K/D\), with \(q=0\) when no index is feasible. Cache \(C^-\) from the evaluation of the final feasible index.
If \(0<K<D\), one additional evaluation at \((K+1)/D\) yields \(C^+\). There is no breakpoint strictly between \(K/D\) and \((K+1)/D\), so the endpoint convention gives
\[ c_j((K+1)/D)=c_j^+,\qquad b((K+1)/D)=b^+. \]
For \(K=D\), use the stipulated endpoint conventions. Finally, broadcast the allocation-and-payment summary from Section 4.
The total bounds are \(O(mL)\) transmissions and \(O(mL^2)\) bits. Local preprocessing and output generation cost \(O(\tau L^2)\). Each grid evaluation uses binary searches in the local supports, costing at most \(O(mL\log(\tau+1))\) bit operations altogether. Across \(O(L)\) evaluations, the running time is therefore
\[ O\bigl((\tau+m\log(\tau+1))L^2\bigr). \]
Babaioff–Nisan’s Theorem 5.6 counts messages containing a single price and searches an integer trade-size range. Its hypotheses and conclusion concern discrete agents. [Babaioff–Nisan, Section 5.3](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/babaioff04a.pdf)
Here, cumulative masses introduce rational breakpoints whose positions depend on their encoded masses. The proofs above establish the continuous result directly. The \(2m\)-transmission bound uses support-sized packets; the second protocol supplies a separate bound for packets containing constantly many integers.
The stipulated exact problem is consequently polynomial-time solvable. NP-hardness under polynomial-time reductions would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the specified problem. The breakpoint argument, exact arithmetic bounds, allocation and payment calculations, and both communication protocols are correct. I found no major or minor issues requiring repair.
The output addresses the explicit support representation in USER_TASK. It uses \(\tau\) as the total number of supported types and \(L\) as the total input bit length. It does not expand rational masses into unit agents.
The relation \(m=h+1\) gives \(m\) cost roles, one buyer role, and \(m\) path edges, exactly as used in the protocols. Every role has positive total mass, so its support is nonempty; consequently, the bounds \(m\leq\tau\) and \(\tau=O(L)\) are valid under the stated explicit encoding.
Grouping equal prices preserves each quantile function. Every cumulative group mass is positive, and each role’s last cumulative mass is \(1\). Thus the ordered union of breakpoints is well-defined, ends at \(1\), and has at most \(\tau\) elements.
The interval convention is correct: each quantile function is constant on \((t_{\ell-1},t_\ell]\), including the right endpoint. Cost quantiles are nondecreasing and the buyer quantile is nonincreasing, so \(\Delta=b-C\) is nonincreasing.
Therefore the feasible breakpoint indices form an initial segment. If the first interval is infeasible, no positive quantity is feasible. Otherwise the feasible positive quantities are exactly \((0,t_r]\), where \(r\) is the last feasible breakpoint index. This establishes the stated formula for \(q^*\), including attainment of the maximum. Equality is correctly treated as feasible.
The product \(D\) of all input denominators is a valid common denominator. Its bit length is bounded by the sum of the denominator bit lengths, hence is \(O(L)\). Scaling an input rational to denominator \(D\) yields an integer numerator with \(O(L)\) bits.
Cumulative mass numerators lie between \(0\) and \(D\). Summing at most \(m\) scaled costs increases the maximum numerator length by at most \(O(\log m)\), which remains within \(O(L)\). The argument correctly bounds bit lengths rather than numerical magnitudes; \(D\) may be exponentially large without invalidating polynomial running time.
For positive trade, feasibility gives \(b^-\geq C^-\). Monotonicity gives \(C^+\geq C^-\), including the stipulated infinite endpoint value. Consequently,
\[
C^-\leq P_S\leq b^-.
\]
The rewritten second argument \(P_S-C^-+c_j^-\) is finite and nonnegative. Thus every cost-role price is finite, including at \(q=1\), where the infinite first argument of the minimum is discarded. The buyer price is also finite.
The proportional allocation calculation is correct. For a cutoff group, the inequalities \(A<q\leq A+M\) ensure that the displayed allocation lies in \([0,\mu_i]\), and summing over its types gives exactly \(q-A\). Fully selected groups and unselected groups then give total allocated mass \(q\) in every role.
Substitution into the common-denominator representation correctly produces the stated allocation denominator \(DM'\) and payment denominator \(D^2M'\). The numerators and denominators have \(O(L)\) bits. Hence the total output-size bound \(O(\tau L)\) is valid. Reduced fractions are not required by the task.
The sweep respects the endpoint convention by evaluating an interval before applying changes at its right endpoint. Processing simultaneous changes together avoids dependence on an arbitrary ordering of coincident breakpoints.
The first negative interval has left endpoint \(q^*\); if no interval is negative, \(q^*=1\). The first-interval case therefore correctly produces zero trade. The sweep also supplies the left and right quantile values needed for the stipulated payments.
The operation counts are valid: \(O(\tau)\) scaling and sweep operations and \(O(\tau\log(\tau+1))\) comparisons. With \(O(L)\)-bit operands and elementary arithmetic, the stated bound
\[
O(\tau L^2+\tau L\log(\tau+1))=O(\tau L^2)
\]
follows from \(\tau=O(L)\). Price computation and writing the exact outputs fit within this bound.
Each of the \(m\) edges carries one upstream packet containing the accumulated supports. Ordered role records, counts, and self-delimiting integer encodings permit parsing with \(O(L)\) bits per packet.
For positive trade, the downstream summary \((D,Q,U,V)\) provides precisely the shared quantities needed by each cost server. Its own support supplies its cutoff group and local quantile values. The buyer already has the information required for its allocations and \(P_B\). For zero trade, the explicit flag suffices.
Exactly one downstream packet crosses each edge, including in the zero-trade case. The count of exactly \(2m\) transmissions is therefore correct, as are the bounds \(O(mL)\) transmitted bits and \(O(\tau L^2+mL)\) total bit-operation time. The protocol uses explicit messages and does not encode information through timing.
Denominator aggregation and broadcast give every server the same \(D\). Every breakpoint is an integer multiple of \(1/D\), and the predicate \(F(k)\) is monotone. Binary search over the finite range therefore takes \(O(L)\) evaluations.
Section 1 justifies that the last feasible grid index gives the exact continuous optimum. A positive final feasible index has been evaluated, so caching its aggregate cost is valid.
For \(0<K<D\), there is no breakpoint strictly between \(K/D\) and \((K+1)/D\). The right-closed quantile convention therefore makes evaluation at \((K+1)/D\) return the required right-limit values, even if that grid point itself is a breakpoint. The cases \(K=D\) and zero trade are handled by the stipulated endpoint conventions and zero-trade summary.
Each evaluation requires \(m\) downstream requests and \(m\) upstream responses. The packets contain constantly many \(O(L)\)-bit integers. Thus \(O(mL)\) transmissions and \(O(mL^2)\) transmitted bits are valid. The local search and arithmetic costs also support
\[
O\bigl((\tau+m\log(\tau+1))L^2\bigr).
\]
The cited Theorem 5.6 concerns normalized, incentive-compatible, non-discriminating discrete double-auction rules, with trade size determined by the optimal trade size and payments determined by constantly many prices once that size is known. Its conclusion is the stated logarithmic single-price message bound. The prover’s comparison is consistent with that theorem and does not use it to establish the continuous result. [Babaioff–Nisan, Section 5.3](https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume21/babaioff04a.pdf)
The continuous polynomial-time conclusion follows from the explicit algorithms above. The final qualification about NP-hardness implying \(\mathrm{P}=\mathrm{NP}\) is appropriate. No optimality claim for the communication bounds is made or needed.
No additional clarification is needed to verify the argument.
⟨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.