| paper | d4-conf-wine-2023-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: For explicit terminal-table output, computation is NP-hard under polynomial-time metric reductions and cannot run in polynomial time because the table can be exponentially large. Even deciding whether terminal revenue is below a rational threshold is NP-hard under polynomial-time many-one reductions. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), and type-specific values \(v_t\), budgets \(B_t\), and integral caps \(K_t\), together with a rational monotone submodular rank oracle \(F_\mu:2^T\to\mathbb{Q}_+\) whose capacities scale with population mass, compute the terminal mass table \(\pi_{t,k,p}\) produced by an ascending-price clinching auction. Here \(\pi_{t,k,p}\) is the mass of type-\(t\) people receiving \(k\in\{0,\ldots,K_t\}\) indivisible goods and paying \(p\); cohort splits preserve the aggregate polymatroid constraints. Is this outcome computable in time polynomial in \(|T|\), \(\sum_t K_t\), the rational input bit length, and the number of value-oracle calls?
An atomless population over complete buyer types, with rational mass per type and a type-level polymatroid whose capacities scale with mass. The computation tracks mass across cohorts indexed by type, integral bundle, and payment, applying mass-splitting clinches while respecting aggregate feasibility and individual budgets.
The paper’s analysis does not bound how many state cohorts mass splits may create, leaving polynomiality in support size and per-person caps speculative.
fatal: False
The mirror covers Theorem 3.3’s computation of the auction outcome. It leaves the paper’s Pareto optimality and welfare guarantees, including Theorems 5.1, 5.4, and 5.6, unclaimed.
The paper’s usable computational anchor is Theorem 3.3, proved here: the authors’ polyhedral clinching auction for indivisible goods can be implemented in polynomial time. Each iteration takes polynomial time given a value oracle for the integer polymatroid \(f\), including computing clinches by submodular minimization. The number of iterations is at most \(\sum_i f(i)+n\le n(f(N)+1)\). The authors count the number of goods as part of the input size; with binary encoded supply, that bound can be pseudo-polynomial. The paper gives no named hardness result, so this is the sole anchor.
My lead mirror is Mass Clinching Outcome Computation. Its input is a finite support \(T\) of buyer types, rational masses \(\mu_t>0\) summing to \(1\), and, for each type \(t\), a per-unit value \(v_t\), public budget \(B_t\), and integral per-person cap \(K_t\). Type includes every feature that affects feasible allocations. The environment is a rational, monotone submodular rank function \(F_\mu:2^T\to\mathbb Q_+\), with capacities scaled to the population mass; aggregate allocations \(q\) must satisfy \(q(S)\le F_\mu(S)\) for every \(S\subseteq T\), and \(q_t\le K_t\mu_t\).
The society is atomless, with mass \(\mu_t\) of type \(t\). Each person still receives an integer number \(k\le K_t\) of indivisible goods and pays \(p\le B_t\). The output is a finite table \(\pi_{t,k,p}\) giving the mass of type \(t\) receiving \(k\) goods and paying \(p\). Thus type-level averages can be fractional, while each person’s bundle remains integral.
The procedure to compute is the mass version of Algorithms 1–2: use the same ascending price clock, value and budget demand updates, and maximal-clinch rule. When a cohort splits because some of its mass receives a different number of goods or pays differently, track the resulting state cohorts separately. A clinch is a feasible integral bundle increment to some mass of a cohort that leaves the projected feasible future allocations of all other cohorts unchanged. A solution is the terminal table produced by these updates, with all mass accounted for, feasible aggregate allocation, and individual budget and utility constraints satisfied. The complexity question is whether this table can be computed in time polynomial in \(|T|\), \(\sum_t K_t\), the input bit length \(L\), and the number of value-oracle calls to \(F_\mu\).
A plausible regime is a large advertising market in which many campaigns share a small number of value, budget, and eligible-inventory classes. Then the number of advertisers is much larger than the number of types, while inventory and eligibility constraints scale with the market. The paper’s public budgets, indivisible allocations, and polymatroid constraints all have direct counterparts in this model. Allowing masses of people to receive different integral bundles preserves the indivisibility that matters to the auction.
I would expect this question to be Class A, conditional on the type-level polymatroid representation being explicit and the per-person caps counted as input size. The finite support and submodular structure make a polynomial type-level implementation plausible. Further questions include whether the output agrees with a limit of finite replicated markets, and whether the continuous mechanism retains the paper’s IC, IR, PO, and welfare guarantees.
The mirror covers Theorem 3.3’s computation of the auction outcome. It does not claim continuous versions of the PO or welfare theorems as additional anchors.
The weak point is substantial: Theorem 3.3’s running time is polynomial in the number of buyers and goods, not in the number of types, and does not establish a support-sized algorithm. Moreover, a type must include all allocation-relevant constraints; doing so could make \(|T|\) as large as the population. Tracking the mass splits created by integer clinches may also make the state space grow. Those are open parts of the proposed mirror, rather than consequences of the paper. The case for it is that it asks a recognizable high-multiplicity question about the authors’ actual auction procedure while retaining integral individual allocations.
The only computational anchor is Theorem 3.3: the authors prove that their auction can be implemented in polynomial time. The strongest case against its mirror is that this is a runtime bound for a particular finite-buyer procedure, whose input includes an arbitrary polymatroid on named buyers. The theorem gives no type-level representation or compression. In general, buyers with the same value and budget may still play different roles in the polymatroid constraints. Capturing those differences in their types could make the support as large as the population.
That objection applies to the paper’s general model, but it does not defeat the better mirror. A large advertising market with a small number of value, budget, and eligibility classes is plausible, and the paper itself points to ad-slot auctions. One can define a type-level polymatroid whose capacities scale with class mass, then ask for the mass distribution of buyers over integral bundles and payments. This is a computational question about a continuous population. The necessary type-level environment is a genuine modeling choice, but the programme permits such co-modification when the authors would recognize the resulting question as theirs.
The proposed oracle model also needs care: a polynomial bound in oracle calls is not a bit-complexity bound unless the oracle and rational data are specified. But that is fixable, and it does not make the mirror unworthy. Nor does the divisible-goods literature settle it: those papers continuize outcomes or study finite-buyer markets, rather than the computational problem for a continuous population. High-multiplicity work would support the regime rather than count against it.
So the negative case is weak. The theorem supplies a real computational anchor, and I cannot honestly rule out a worthwhile mirror in the restricted, type-symmetric market. The open questions are whether the mass version is well-defined for a chosen family of polymatroids and whether its outcome can be computed from support-sized input. Those are the substance of the mirror, not reasons to reject it.
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.