| paper | d4-conf-sagt-2025-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(\text{Polynomial-time solvable}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(n\), sorted rational locations \(x_1<\cdots<x_\tau\), and rational masses \(\mu_j>0\) summing to \(1\) with \(n\mu_j\in\mathbb Z\), can one compute from the support a deterministic two-facility mechanism in time \(\mathrm{poly}(\tau,L)\) that preserves constant approximation, one-person strategyproofness, and the paper’s \(n\)-scaled Lipschitz guarantee?
Types are resident locations \(x_j\), each carrying mass \(\mu_j\). The mechanism outputs an ordered pair of facility points in \(\mathbb R^2\), with average service cost \(\sum_j\mu_j\min_{\ell\in\{1,2\}}(|x_j-p_{\ell,1}|+|p_{\ell,2}|)\) and benchmark \(c^*(\mu)=\min_{a\le b}\sum_j\mu_j\min(|x_j-a|,|x_j-b|)\). A resident’s report changes the distribution by replacing mass \(1/n\) at their location with mass \(1/n\) at the reported location; for societies with the same \(n\), stability is measured by \(D_n(\mu,\nu)=nW_1(\mu,\nu)\).
Covers Theorem 2’s \(M4\) approximation, incentive, and stability guarantees; it leaves the separate analyses of \(M1\), \(M2\), and \(M3\), and broader metric generalizations, untouched.
The best anchor is Theorem 2, proved in this paper. There is no named NP-hardness, \(P\), W[1]-hardness, or FPT result here. Theorem 2 is a constructive mechanism result instead: \(M4\) is constant-approximate, constant-strategyproof, and constant-Lipschitz. More fully, its social cost is at most \(15\) times optimum (Lemma 4.5); a unilateral misreport can improve an agent’s service distance by at most a universal constant factor; and changing the profile changes the facility locations by at most a universal constant times the profile’s \(\ell_1\) change. The paper proves all three claims. It does not state a runtime bound or classify a computational problem into a complexity class.
A plausible high-multiplicity regime is two service hubs for residents along a long corridor, where facilities can also be placed in a surrounding strip. The type is a resident’s exact coordinate along the corridor: people at the same coordinate have identical costs to every possible facility location. A city might have hundreds of thousands of residents but only dozens or hundreds of heavily occupied apartment blocks or service sites, so \(n\) is much larger than the support size \(\tau\). The mass at a site is its fraction of the population. This keeps the paper’s two-facility decision and service costs intact while making the population the continuous object.
I would pose the lead mirror as Compressed Distributional Two-Facility Mechanism. An instance is \(n\), together with sorted rational locations \(x_1<\cdots<x_\tau\) and rational masses \(\mu_j>0\) summing to \(1\), where \(n\mu_j\) is an integer for each \(j\). The masses are binary-encoded, so the input can describe a large population without listing its members. A solution is a single deterministic rule \(F\) that, on each instance, outputs two ordered facility points \(p_1,p_2\in\mathbb R^2\). For a location \(x\), service distance is \(d(x,p)=|x-p_1|+|p_2|\), and the rule’s average social cost is \(\sum_j\mu_j\min_\ell d(x_j,p_\ell)\). Its benchmark is \(c^*(\mu)=\min_{a\le b}\sum_j\mu_j\min(|x_j-a|,|x_j-b|)\).
Require universal constants \(A,\lambda,K\), independent of \(n\) and \(\tau\), such that the rule has average cost at most \(A c^*(\mu)\); for every resident at \(x\) and every report \(y\in\mathbb R\), \(d(x,F(\mu))\le\lambda d(x,F(\mu-\frac1n\delta_x+\frac1n\delta_y))\); and its facility locations obey the paper’s stability bound. For that last condition, on two societies with the same \(n\), use \(D_n(\mu,\nu)=n\int_0^1|Q_\mu(u)-Q_\nu(u)|\,du\), where \(Q\) is the quantile function. This equals the \(\ell_1\) distance between their sorted \(n\)-person profiles, so the requested bound is \(\|F(\mu)-F(\nu)\|_1\le K D_n(\mu,\nu)\).
The natural candidate solution is precisely weighted \(M4\): evaluate the paper’s quantities using masses instead of repeated agents. Its two horizontal coordinates are the weighted \(M2\) coordinates \(f_1,f_2\); if \(\Delta=f_2-f_1>0\), the fractional assignment weights are \(w_2(x)=\max(0,\min(f_2,x)-f_1)/\Delta\) and \(w_1(x)=1-w_2(x)\), averaged over \(\mu\). The vertical coordinates are \(\phi_\ell=\max\{8c^*(\mu),\xi_\ell\}\), where \(\xi_\ell=0\) if \(\Delta=0\), and otherwise \(\xi_\ell=\min\{\Delta,2c^*(\mu)/w_\ell\}\). The roots defining \(f_1,f_2\), the weighted two-median cost, and the assignment averages can all be computed from the \(\tau\) support values with rational arithmetic. So I expect this mirror to be tractable in \(\mathrm{poly}(\tau,L)\) time; that compressed runtime is a claim to establish for the mirror, not a complexity result stated by the paper.
The scope is \(M4\)’s two-facility guarantee for line-location agents and plane facilities, including its approximation, incentive, and stability properties. It does not attempt to mirror the paper’s other settings or claim that its facilities can be restricted to the line. Its plausibility comes from changing the roster into a weighted histogram while retaining the agents’ types, objective, facility choices, and unilateral-report question. Each rational histogram expands to a finite roster, so the paper’s theorem supports this regime rather than colliding with it. This is a high-multiplicity formulation; the additional computational question is whether its guarantees can be delivered directly from the compressed input.
The weak point is that the incentive guarantee needs the \(1/n\)-mass deviation. In a strictly atomless population, a single person has zero mass and cannot change \(\mu\), making unilateral strategyproofness vacuous. Keeping \(n\) and the one-person mass preserves the paper’s incentive question, but means this is an exact high-multiplicity compression, not a pure atomless limit. The stability claim also uses \(D_n=nW_1\), matching the paper’s roster-scale profile distance; the theorem does not by itself give a constant bound in normalized \(W_1\). Whether that stronger population-scale stability bound holds is a useful next question.
Theorem 2 is the wrong kind of result for ChoCo’s complexity programme. It proves that the explicit mechanism \(M4\) has approximation, incentive, and stability guarantees; it does not classify the complexity of a computational problem. The proposed mirror changes the question to whether \(M4\)’s output can be computed from a compressed histogram. That may be a representation or implementation question, but it is not a complexity question supplied by the paper’s theorem. The theorem already gives the rule on full profiles, and the paper claims no computational barrier to evaluating it.
The corridor example is credible, and repeated residents at the same coordinate are a legitimate high-multiplicity type. That is evidence for the regime, not an objection. But with \(n\mu_j\) integral, the histogram is a lossless encoding of a finite profile: expanding it recovers exactly the input to \(M4\). The proposed mirror therefore adds a compressed input format, not a new continuous computational object.
There is also a limit problem for the incentive anchor. In an atomless population, one resident’s report does not change \(\mu\), so unilateral strategyproofness becomes vacuous. Keeping the deviation \(\mu-\frac1n\delta_x+\frac1n\delta_y\) preserves the paper’s incentive question, but also preserves a finite individual mass and \(n\). A positive-mass deviation could avoid that degeneracy, but it would ask about coalition manipulation, which is a different incentive question. This is a genuine tension in the continuous mirror, though the exact high-multiplicity formulation remains sensible under ChoCo’s stated bridge.
A stronger alternative would ask for the best trade-off among approximation, incentive, and Lipschitz guarantees over all distributional mechanisms. But that is a global mechanism-synthesis problem over functions on a real-valued domain, not a computational problem on a society input. Making it algorithmic would require extra restrictions on the mechanism class that this paper’s result does not motivate.
So the negative case rests on scope: the paper offers a theorem about properties of a mechanism, not a computational result whose complexity changes when the population is continuized. It is not airtight. If ChoCo expands to include the representation complexity of evaluating mechanisms, the compressed \(M4\) question could be worth studying. Under the programme’s current focus, I would not count it as a worthwhile continuous 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.