| paper | d4-conf-sagt-2021-0002 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even for \(N=1\), values in \(\{0,1\}\), and equal positive dyadic activation costs. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite seller set \(J\), buyer types \(T\) with rational masses \(\mu_t\geq 0\) summing to \(1\), per-type values \(v_{tj}\), fixed activation costs \(\kappa_j\), and cohort size \(N\), choose assigned masses \(x_{tj}\geq 0\) and activation variables \(y_j\in\{0,1\}\), with \(\sum_j x_{tj}\leq\mu_t\) and \(x_{tj}\leq\mu_ty_j\), to maximize \(N\sum_{t,j}v_{tj}x_{tj}-\sum_j\kappa_jy_j\).
A continuous buyer population represented by type masses \(\mu_t\), assigned to a finite set of sellers; the decision variables are assigned masses \(x_{tj}\) and binary seller activations \(y_j\), and the objective is total gains from trade \(N\sum_{t,j}v_{tj}x_{tj}-\sum_j\kappa_jy_j\).
In the proponent's normalized formulation, setup costs are \(1/N\) and vanish as \(N\) grows; including \(N\) in aggregate welfare repairs this scaling.
fatal: False
It covers the gains-from-trade assignment hardness in Proposition 1 for constant nonempty-set seller costs; it leaves the incentive, budget-balance, core, and approximation results unmirrored.
My lead is a buyer-heavy mirror of Proposition 1, proved in this paper in Appendix A.1. The proposition says that with multiple sellers whose costs are constant over every nonempty subset of buyers, finding an assignment that maximizes gains from trade is NP-hard. The authors prove it by reducing Set Cover: buyers represent universe elements, sellers represent sets, a buyer values a seller at one exactly when that seller’s set contains the buyer’s element, and each seller pays cost one if it serves anyone. The maximum gains from trade encode the minimum set-cover size.
A plausible high-multiplicity regime is a platform serving a very large batch of riders through a finite menu of providers. Riders fall into a modest number of complete value types—for example, the same origin, destination, time window, and urgency, with the same values for each provider. A provider has a one-time setup cost if it serves any riders in the batch. This is asymmetric: the rider population is continuous, while the providers remain scarce, finite agents. That preserves the paper’s fixed-cost seller semantics.
Here is the problem I would hand to a prover: Continuous Buyer-Mass Gains-from-Trade Maximization with Fixed-Cost Sellers. The input is a finite seller set \(J\), a support \(T\) of buyer value types with rational masses \(\mu_t\geq 0\) summing to one, value vectors \(v_{tj}\), and seller setup costs \(\kappa_j\). Serving any positive mass costs seller \(j\) exactly \(\kappa_j\), regardless of the amount served. Choose assigned masses \(x_{tj}\geq 0\) and activation variables \(y_j\in\{0,1\}\), subject to
\[
\sum_{j\in J}x_{tj}\leq\mu_t,\qquad x_{tj}\leq\mu_t y_j.
\]
Maximize
\[
\sum_{t\in T}\sum_{j\in J}v_{tj}x_{tj}
-\sum_{j\in J}\kappa_j y_j.
\]
The solution is an assignment of buyer mass to providers and a set of activated providers. This is the paper’s gains-from-trade assignment problem with a distribution over buyer types; fractional \(x_{tj}\) reflects that the population itself is mass-valued.
The hardness transfers. Given a Set Cover instance with \(q\) elements, make each element a buyer type of mass \(1/q\), and each set a seller. Set \(v_{tj}=1\) when the element belongs to the set, and zero otherwise. To make the population genuinely high-multiplicity, repeat every type \(K\) times, so there are \(Kq\) buyers but only \(q\) buyer types; use setup cost \(1/(Kq)\), the original unit cost expressed per capita. Any uncovered type can be covered by activating a set that contains it: the added mass value is at least \(1/q\), exceeding the setup cost when \(K>1\). Thus an optimum covers every type, and among full covers it chooses a minimum-size set cover. The optimum is \(1-\mathrm{OPT}/(Kq)\). The expected classification is therefore Class B: hardness transfers. The combinatorics live in the provider choices and the incidence pattern across types, not in having many separately named buyers.
The mirror covers the assignment optimization underlying the paper’s efficient-mechanism results, and specifically the hardness claim in Proposition 1. It does not claim to continuize the paper’s DSIC, budget-balance, or core guarantees. Further questions include whether the problem has useful algorithms parameterized by the number of providers or by support size, and which changes to fixed setup costs make the welfare problem tractable.
The weakest point is the finite seller side. Making sellers atomless too, while retaining a cost charged whenever any positive amount is served, risks making activation costs degenerate: an arbitrarily small seller mass could serve a large buyer mass. Keeping providers finite is a deliberate boundary of this mirror, and its acceptability depends on the authors recognizing a large buyer cohort facing a finite provider menu as a meaningful regime of their assignment problem.
The strongest objection is to the reduction’s claimed high-multiplicity scaling, not to its anchor. Repeating each type \(K\) times leaves its mass at \(1/q\); \(K\) appears only through setup costs \(1/(Kq)\). As \(K\) grows, those costs vanish relative to normalized welfare, so the limiting optimization makes activation effectively free. That does not establish that multiplicity itself creates a useful continuous model.
But a better mirror repairs this. Keep the same type masses and unit setup costs, and write aggregate welfare as
\[
N\sum_{t,j} v_{tj}x_{tj}-\sum_j y_j,
\]
where \(N=Kq\). Then the model preserves the paper’s fixed-cost semantics: covering a type gains \(K\), so for \(K>1\) an optimum covers every type and uses a minimum set cover. This is a coherent large buyer cohort facing a finite provider menu, and the authors could reasonably recognize it as their assignment problem. The finite seller side is a limitation of the regime, but not a decisive objection. Existing work also treats non-atomic agents in two-sided markets, though its segmentation and facility-location questions differ from this fixed-cost assignment problem ([Segmenting Two-Sided Markets](https://users.cs.duke.edu/~kamesh/TS.pdf), [Two-sided Facility Location](https://arxiv.org/abs/1711.11392)).
The repaired mirror retains a finite activation decision, and its type masses can be assigned without any useful fractional splitting. That makes the mirror less revealing of continuous optimization than the proponent suggests. Still, the programme explicitly allows a mirror whose answer is that hardness persists. Since the population regime is sensible and the question is computational, this concern does not defeat the anchor. Proposition 1 survives; I cannot honestly make the requested universal negative case against 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.