| paper | d4-conf-sigecom-2001-0028 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.6
statement extracted from the paper’s text layer
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\)?
Use a distributed chain of markets whose types specify role and unit cost or value, with rational type masses and one common population scale. Each individual still supplies, converts, or receives an integral unit; the aggregate allocation records fractional mass by type. The computation returns traded mass, type allocations, and Pivot Protocol payments derived from marginal quantiles.
The proponent’s stated polynomial-time bound is centralized, and Theorem 5.6’s \(O(\log n)\)-message guarantee does not itself specify communication for rational mass inputs; that distributed complexity still needs to be established.
fatal: False
The mirror covers distributed computation of the Pivot Protocol’s Trade Reduction outcome and marginal payments. It does not establish that the finite mechanism’s incentive, individual-rationality, or budget-balance guarantees survive the mass limit, and it leaves the other auction-rule results and simulations aside.
The strongest honest positive case is narrow: mirror the paper’s distributed computation of a supply-chain auction outcome, not all of its incentive and budget-balance results.
My anchor is Theorem 5.6, proved in this paper. It says that if a normalized double-auction rule is incentive compatible and non-discriminating, its trade size depends only on the optimal trade size \(l\), and its payments can be determined from \(O(1)\) prices once \(l\) is known, then the Pivot Protocol can be implemented with \(O(\log n)\) messages sent and received by each market, each message containing one price. Trade Reduction is one qualifying rule: it trades \(l-1\) units and uses prices determined by the marginal bids. This is a communication-complexity result, rather than a hardness result; I would use it as my only anchor.
A plausible regime is a large commodity chain with many one-unit suppliers, processors, and customers: for example, repeated production or conversion contracts and many buyers in the final market. Agents in a type share their market role and per-unit cost or value. Each market has a common population scale \(N\), with \(N\) much larger than the number \(\tau\) of distinct types. The input records each type’s rational mass as a fraction of that market’s population. Agents still receive or provide integral units; only the allocation reported for a type can be fractional. Here a type is exactly the complete role-and-cost/value description the paper’s mechanism uses.
I would hand a prover Mass Pivot Trade-Reduction Outcome Computation. There are \(h+1\) supply-side roles—an initial supplier and \(h\) converter markets—and a final buyer market. For each supply role \(j\), the input gives a finite-support rational distribution \(\mu_j\) over nonnegative unit costs; the buyer input gives \(\mu_B\) over nonnegative unit values. Each distribution has total mass one. Let \(c_j(z)\) be the cost of the \(z\)-th cheapest unit of mass in role \(j\), and \(b(z)\) the value of the \(z\)-th highest-value buyer mass. Set \(C(z)=\sum_{j=0}^{h}c_j(z)\), and let \(q^\star\) be the largest mass for which \(b(z)\ge C(z)\), using a stated one-sided quantile convention at jumps.
The task is to compute the continuous Pivot Protocol outcome for the mass version of Trade Reduction: the common traded mass \(q^\star\); for each role, the mass \(x_{j,a}\) allocated from every type \(a\), choosing the cheapest \(q^\star\) mass; the \(q^\star\) mass of highest-value buyers; and the per-unit payments produced by the Pivot Protocol’s marginal-price rule, with order-statistic bids replaced by the specified one-sided quantiles. A solution is this exact allocation-and-payment tuple. Equivalently, \(q^\star\) maximizes \(W(q)=\int_0^q[b(z)-C(z)]\,dz\), with the largest maximizer chosen in a tie. The \(l-1\) trades of finite Trade Reduction, divided by \(N\), converge to the same mass as \(N\) grows; the single-unit reduction disappears at population scale.
I expect this problem to be Class A. Each input curve is a step function with at most \(\tau\) support breakpoints. Merging the breakpoints across roles, finding the last interval where demand covers aggregate supply, and evaluating the protocol’s marginal prices takes time polynomial in \(h,\tau,L\), where \(L\) is the binary input length. In the distributed version, markets can pass their support breakpoints and costs along the chain, and the Pivot Protocol can propagate the resulting prices back. This is a type-sensitive bound independent of \(N\), though it does not claim the paper’s \(O(\log n)\) message bound carries over unchanged. Further questions include tight message complexity as a function of \(\tau\) and \(L\), and which incentive and budget properties survive this mass formulation.
The mirror is plausible because the underlying computation still takes role-indexed bids, constructs supply and demand curves, chooses a common trade quantity, and coordinates prices along a chain. The authors’ protocol already works on these curves; grouping repeated bids into type masses is a natural high-multiplicity input regime. The mirror covers Theorem 5.6’s outcome-computation problem, not the paper’s entire mechanism-design contribution.
Its weakest point is the anchor’s measure: Theorem 5.6 bounds messages in \(n\), while the proposed problem asks for a bound in support size and bit length. Also, a continuous mass allocation can erase the finite mechanism’s one-unit trade reduction, so this does not establish that its incentive or budget guarantees survive. That limits the claim, but leaves a concrete computational question about the same supply-chain auction and its distributed evaluation.
The only anchor is Theorem 5.6, and the strongest objection is that the proposed mass problem does not preserve what the theorem measures. The theorem counts price messages between market servers. The proposed “Mass Pivot Trade-Reduction Outcome Computation” instead gives the support distributions as input and asks for an allocation and payment tuple, with a centralized running-time bound. That bound does not mirror the theorem’s communication result. The suggestion that markets could pass breakpoints is a separate problem: it needs to specify what each market initially knows, what messages are allowed, how their bit lengths count, and who must produce the output.
There is a coherent repair: give each market its own rational type masses, require a distributed protocol to compute the exact mass traded and prices, and measure communication in \(h,\tau,L\). But this is also where the negative case weakens. If all masses have a common denominator \(N\), replicate each type \(N\mu_t\) times. Since the input masses are binary rationals, \(\log N=O(L)\). The finite instance then has \(N\) agents per market, and Theorem 5.6’s rank search applies. Trade Reduction’s traded mass differs from the optimal mass by \(1/N\), which vanishes in the limit; its marginal prices correspond to the stated one-sided quantiles. So the repaired mirror appears to be a weighted-quantile extension and limit of the paper’s result, rather than a new complexity phenomenon.
That supports a narrow negative claim: the proponent has not shown that Theorem 5.6’s communication bound itself becomes a new continuous computational question. It does not support the requested universal claim. Repeated role-and-cost types in large supply chains are plausible, and the weighted-quantile version is well-posed. The theorem is also plainly a named computational result. Under the programme’s rules, a direct or low-yield answer is not enough to reject a sensible mirror. The honest negative case is therefore weak: it can challenge the proposed anchor’s formulation, but it cannot defeat the strongest repaired mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.