| paper | d4-conf-atal-2018-0254 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. The core is always nonempty, and maximum total payment is \(dD_{R_c}(s,t)\). An exact polynomial-size extended linear description exists, but payment-only linear descriptions can require exponentially many inequalities. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a directed network \(G=(V,E)\), source and sink, rational demand \(d\), and a distribution \(\mu\) over supplier types \(r=(e,c_r)\), each with unit capacity, let \(x^\star\) be an efficient flow with \(0\le x_r^\star\le\mu_r\). What exact core constraints characterize payments to the winning supplier mass, and does a polynomial-size analogue of the paper’s vertex-pair collection suffice to compute maximum total core payments or report that the core is empty?
A capacity-scaled path procurement model with finitely many supplier types, rational masses \(\mu_r\), and unit service decisions for each provider. The efficient allocation is a demand-\(d\) flow \(x^\star\); core coalitions combine available supplier mass across routes, and the objective is to maximize total payments \(P_r=x_r^\star p_r\) under individual rationality and the coalition constraints.
The mirror covers Theorem 3.1’s equivalent core descriptions and Section 5’s maximum-payment computation in a capacity-scaled setting. It leaves aside Theorem 4.3’s worst-case constraint lower bound, incentive compatibility, false-name-proofness, and the empirical runtime results.
The strongest mirror is the core computation for path procurement. The paper’s natural high-multiplicity regime is a large network operator buying capacity from many small providers. Providers have the same type when they serve the same directed link and share the same unit cost, capacity, eligibility, and contract terms. A network with standardized tariff classes could have millions of providers but comparatively few supported types. This is a property of that procurement regime, not of path auctions in general.
My anchor is Theorem 3.1, proved in this paper. It says the two stated constraint collections describe the same core. Collection (C1) has a constraint for each nonempty subset \(x\) of the edges \(E'\) on the selected shortest path: \(\sum_{e\in x}p_e \le d(s,t,G-x)-(d(s,t,G)-\sum_{e\in x}c_e)\). Collection (C2) instead has a constraint for each ordered pair \(a,b\) of vertices on that path, with \(b\) after \(a\): \(\sum_{e\in E(a,b)}p_e \le d(a,b,G-E(a,b))\), omitting pairs for which that bypass does not exist. Both are used with individual-rationality constraints \(p_e\ge c_e\). Thus an exponential family of coalition constraints can be replaced exactly by \(O(n^2)\) constraints. This is a structural formulation result, not a named P-versus-NP classification; the paper’s Section 5 computes maximum core payment using the reduced collection.
Lead mirror — High-Multiplicity Core Pricing for Path Procurement. An instance is a directed network with source \(s\), sink \(t\), rational demand \(d\), and a finite support \(T\) of supplier types. A type \(r\) has a directed link \(e(r)\), unit cost \(c_r\), and rational population mass \(\mu_r\), with \(\sum_r\mu_r=1\). Each unit of mass supplies one unit of link capacity. Demand and capacity are normalized by population size, so in the underlying large society total demand scales with the number of providers. The instance also specifies a chosen efficient \(s\)-\(t\) flow \(x^\star\), where \(0\le x^\star_r\le\mu_r\); fixing it mirrors the paper’s payment computation after selecting the efficient path.
The action is a payment total \(P_r\) to the winning mass of each type, which receives that payment uniformly. The objective is to maximize \(\sum_r P_r\) over core outcomes. For any coalition, let \(y_r\le x^\star_r\) be its winning mass and \(z_r\le\mu_r-x^\star_r\) its losing mass. Its available capacity on type \(r\)’s link is \(y_r+z_r\). If it can route demand \(d\), let \(K(y+z)\) be the minimum cost of doing so with those capacities. The core condition for a coalition including the auctioneer is
\[
-\sum_r P_r+\sum_{r:x^\star_r>0}y_r\left(\frac{P_r}{x^\star_r}-c_r\right)\ge -K(y+z).
\]
Payments must also satisfy individual rationality, \(P_r\ge c_r x^\star_r\). Supplier-only coalitions then have nonnegative utility, and the efficient grand coalition has welfare \(-\sum_r c_r x^\star_r\). The requested solution is the exact maximum total payment and a payment vector attaining it, or a report that the core is empty. Assume nonwinning capacity can support an alternative \(s\)-\(t\) flow, so the maximum-payment objective is bounded.
I expect this problem to be tractable, Class A, though that is a hypothesis for the mirror, not a result of the paper. Given a candidate payment vector, a violated coalition can be found by minimizing its utility plus its best procurement cost. This is an LP: choose \(y,z\), and a value-\(d\) flow \(f\), subject to \(0\le y_r\le x^\star_r\), \(0\le z_r\le\mu_r-x^\star_r\), and \(0\le f_r\le y_r+z_r\). Its size is polynomial in \(|V|\) and \(\tau=|T|\), and the input is rational. That gives a separation route for optimizing payments with the full coalition constraints. A central follow-up is whether the paper’s pair-of-vertices inequalities also yield an exact compact description here, or whether flow-based separation is the right analogue. Further questions include the minimum size of a continuous core description and how closely the continuous optimum approximates large finite instances.
The mirror covers the paper’s computational core-selection problem and its maximum-payment objective. It does not claim to cover incentive compatibility, false-name-proofness, or the experiments. It continuizes the supplier population; the aggregate flow can be fractional because it summarizes capacity supplied by many providers, while each provider’s allocation remains an integral serve-or-not decision.
The weakest point is the model change: the paper has one owner per edge and selects one path, while this mirror has many providers per link type and allows aggregate flow across routes. That is a natural capacity-procurement extension of the transport-routing problem the paper itself names, but Theorem 3.1’s proof uses a single shortest path. The theorem therefore motivates the question; it does not establish that its \(O(n^2)\) constraint system carries over.
Theorem 3.1 is a structural equivalence for a particular allocation: one winning owner per edge on one selected shortest path. Its \(O(n^2)\) constraints are intervals along that path. They have no population-mass parameter, and distinct edges cannot be pooled into one type because their positions in the network matter. So the theorem’s main insight does not itself yield a continuous-population question.
The closest faithful mirror is to put many interchangeable suppliers at each edge while still buying one unit per edge. But with \(N\) suppliers, the winning mass at each edge is only \(1/N\), which vanishes as the population grows. The core payments then depend on which supplier types are available and their costs, not on a nontrivial allocation of mass. To avoid that collapse, the model must scale demand and supplier capacity so positive mass is procured.
That repair is plausible, but it changes the computational object. The allocation becomes a capacitated flow, and coalitions can combine fractions of suppliers across routes. The paper’s interval constraints and their proof no longer describe the core. The proposed \(y,z,f\) separation LP may give a polynomial algorithm for this new model, but that is a flow-based multi-unit procurement result; Theorem 3.1 only motivates it. The more distinctive question—whether a compact constraint system like (C2) survives—remains open.
This is a solid objection to treating Theorem 3.1 itself as the continuous mirror. It is not a solid case that no worthwhile mirror exists: the repaired capacity-procurement problem is a credible path-auction extension, and the programme permits precisely this kind of co-modification. The honest negative case is therefore weak on the universal claim.
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.