| paper | The Capacity Constrained Facility Location Problem |
| authors | H. Aziz, Hau Chan, Barton E. Lee, D. Parkes |
| venue | WINE 2019 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: For \(m=1\), the decision problem is in \(\mathrm{P}\). The exact optimum and an optimal support location are computable in \(O(\tau^2L^2)\) bit operations. The exact worst-case ratio is \(R(\kappa)=\min\{2,1/\kappa\}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
Given finitely supported rational location types \( x_t\in[0,1]\) with masses \(\mu_t\) summing to one and capacity fraction \(\kappa\in(0,1]\), compute the maximum welfare from placing a facility at \(s\in[0,1]\) and serving the \(\kappa\)-closest mass, allowing a partial endpoint type, and determine the worst-case approximation ratio of the weighted-median mechanism relative to this optimum over all such \(\mu\).
A high-multiplicity facility-location welfare model with complete location types \(t\), masses \(\mu_t\), capacity fraction \(\kappa\), facility location \(s\), served subdistribution \(\nu_t\le\mu_t\), and objective \(\sum_t\nu_t(1-|s-x_t|)\), where \(\nu\) is the \(\kappa\)-closest mass to \(s\).
The proponent does not explicitly state the continuous median-mechanism guarantee corresponding to Theorem 4, so the exact \((n,k)\)-dependent bound and its \(\kappa\)-limit still need to be formulated.
fatal: False
The mirror covers the high-multiplicity welfare problem and the median mechanism's approximation guarantee, while leaving the GMM characterization, finite DIC lower bound, and allocation-anonymous impossibility without surviving mirrors.
The strongest honest case is a narrow one: the paper supports a continuous mirror of its capacity-constrained welfare problem, and probably of its strategyproofness/approximation results, but it does not contain a qualifying complexity anchor in the strict sense requested.
No numbered theorem, lemma, proposition, or corollary in the manuscript proves NP-hardness, membership in \(P\), parameterized tractability, or a comparable complexity statement. The closest result is unnumbered Remark 2, proved by the authors’ argument: after sorting agents, an optimal solution serves a contiguous block of \(k\) agents, places the facility at the median of that block, and can therefore be found in polynomial time by checking the at most \(n\) contiguous blocks. Theorem 1 gives the GMM characterization, Theorem 2 characterizes when the optimum is strategyproof, and Theorems 3 and 4 give approximation bounds, but none is a complexity-class result. Thus, strictly speaking, there is no compliant computational anchor.
That said, I would still put forward the following lead mirror, anchored transparently to Remark 2.
Call it Continuous Capacity-Constrained Facility Welfare.
An instance consists of \(\tau\) voter or resident types \(t\), each with ideal location \(x_t\in[0,1]\), rational mass \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and a rational capacity fraction \(\kappa\in(0,1]\). A type is complete: its members have the same ideal location, utility function, and all other features relevant to service. A facility is placed at \(s\in[0,1]\). The facility serves mass \(\kappa\), chosen from the types closest to \(s\); if the capacity boundary cuts through a type, only the required fraction of that type is served. Every served individual obtains utility \(1-\lvert s-x_t\rvert\), and every unserved individual obtains zero.
The problem is to output a facility location \(s\) and a served subdistribution \(\nu\), with \(0\le\nu_t\le\mu_t\) and \(\sum_t\nu_t\le\kappa\), maximizing
\[ W_\kappa(s,\nu) = \sum_{t=1}^{\tau}\nu_t\bigl(1-\lvert s-x_t\rvert\bigr), \]
subject to \(\nu\) consisting of the \(\kappa\)-closest mass to \(s\). Equivalently, the task is to compute
\[ W_\kappa^*(\mu) = \max_{s\in[0,1]} W_\kappa(s,\nu^{s,\kappa}). \]
This is a genuine population continuization. The many agents could be residents seeking a scarce hospital service, with types representing a modest number of severity or neighbourhood cohorts. Millions of residents may share a few types, so \(\tau\ll N\) is credible. Capacity scales honestly with the population: a hospital serving \(k\) of \(n\) people becomes a capacity fraction \(\kappa=k/n\). The individual allocation remains integral; only the fraction served within a type is fractional.
The bridge back to the paper is exact. If \(\mu_t=n_t/n\) and \(\kappa=k/n\), multiplying the continuous welfare by \(n\) gives the paper’s finite social welfare. The authors’ contiguous-block observation becomes: an optimum serves an interval of the ordered population mass, possibly cutting the two endpoint types, and places the facility at an appropriate weighted median. With finite support, this suggests a polynomial-time algorithm in \(\tau\) and the input bit length. I would expect this mirror to be Class A: tractable by weighted-median and breakpoint enumeration. It is not merely making outcomes fractional; it makes the population distribution itself the input object.
A more ambitious mirror can be anchored by the paper’s named Theorem 1, although it is a structural rather than complexity-class anchor. Theorem 1, proved in the paper, states that for a finite-agent mechanism \(M\), the following are equivalent: \(M\) is a Generalized Median Mechanism; \(M\) is strategyproof for some \(k<n\); and \(M\) is strategyproof for every \(k\le n\).
The continuous question would be:
Given ideal-location types \(x_1,\ldots,x_\tau\), capacity fraction \(\kappa\), and a deterministic rule \(M:\Delta_\tau\to[0,1]\), characterize exactly those rules that are population-strategyproof. Here population-strategyproofness must be made non-vacuous: for every true distribution \(\mu\), type \(t\), alternative report \(r\), and mass \(\delta\le\mu_t\), moving mass \(\delta\) from \(t\) to \(r\) must not increase the utility of that true type under the resulting facility location. The continuous analogue of the theorem asks whether this is equivalent to an uncompromising, weighted generalized-median rule, and whether strategyproofness for one nontrivial \(\kappa<1\) implies strategyproofness for every capacity fraction.
I would expect a positive answer, at least for finite-support distributions: the paper’s proof is driven by one-dimensional uncompromisingness rather than by the number of agents. This would be a meaningful continuization of the paper’s main theorem, probably Class A as a characterization and representation problem.
Theorem 3 supplies a second, optional approximation anchor. Proved in the paper, it states that for \(n\ge2\), every strategyproof mechanism has approximation ratio at least
\[ 2\frac{k}{k+1} \quad\text{when }1\le k\le\left\lceil\frac{n-1}{2}\right\rceil, \]
and at least
\[ \max\left\{\frac{n-1}{k+1},1\right\} \]
otherwise. Its continuous counterpart would ask for the optimal worst-case ratio among population-strategyproof rules as a function of \(\kappa\), with the ratio taken over all finite-support distributions \(\mu\). The finite lower-bound constructions suggest limiting lower bounds of \(2\) for \(\kappa\le1/2\) and \(1/\kappa\) for \(\kappa>1/2\), though that transfer needs proof with only finitely many repeated types. This is a plausible Class A/structural optimization problem, not an evident hardness-transfer result.
My weakest point is the strategic one. In a genuinely nonatomic population, a single individual has zero mass and cannot change \(M(\mu)\), so ordinary individual strategyproofness becomes vacuous. The proposed mass-deviation definition is therefore a deliberate co-modification, not a literal limit of the paper’s incentive constraint. The welfare mirror avoids that problem and is the strongest case: it is precise, high-multiplicity, faithful to the paper’s underlying facility-location problem, and plausibly polynomial-time solvable. The DIC mirrors are credible research questions, but they require the authors to accept population-level incentive compatibility as the correct continuum counterpart.
The negative case is strongest at the source gate: this paper has no qualifying computational anchor. Its numbered results are a mechanism characterization, an incentive-compatibility impossibility, and distortion/approximation bounds. Remark 2 is only an informal polynomial-time observation about the unconstrained welfare optimum; it is not a theorem, lemma, or corollary establishing a complexity classification, exact algorithmic result, or parameterized result. Thus any continuous computational problem proposed here would be a new study inspired by the paper, not a continuization of one of its computational results.
The welfare mirror is mathematically coherent, but it is too thin to rescue the paper. With rational masses \(\mu_t=n_t/n\) and capacity \(\kappa=k/n\), clearing denominators produces exactly the finite instance obtained by cloning each type \(n_t\) times. The authors’ own algorithm—sort locations, scan contiguous blocks, and use a median—becomes a weighted scan over cumulative masses. The mass is active in the selection of the served subdistribution, but no new pricing problem, integrality phenomenon, or complexity obstruction appears. This is a useful weighted reformulation of Remark 2, not a continuous counterpart of the paper’s mechanism-design contribution. A hospital-cohort story makes the high-multiplicity regime plausible, but it does not supply the missing computational anchor.
The proposed strategyproofness mirror fails more fundamentally. Theorem 1 characterizes mechanisms on labelled finite profiles. A GMM is represented using constants \(a_S\) indexed by subsets \(S\subseteq N\), and the paper explicitly permits identity-sensitive mechanisms such as dictatorships and identity-based tie-breaking. A distribution \(\mu\) over location types erases exactly that information. If labels are retained as part of the type, then the number of types grows with the number of agents and the high-multiplicity regime disappears. If labels are discarded, one has restricted the theorem to anonymous mechanisms and is no longer characterizing the mechanisms in the paper.
Nor does ordinary DIC survive the atomless limit. A single agent changing their report does not change \(\mu\), so a rule \(M(\mu)\) cannot react to that deviation. Individual strategyproofness therefore becomes vacuous at the population level. The proposed repair—moving a positive mass \(\delta\) from one type to another—is a coalition or cohort deviation, not the paper’s unilateral deviation. It may define an interesting new model, but it is a substantive re-modelling of the strategic actor. The paper’s proof of Theorem 1 depends precisely on one labelled agent changing the facility outcome and, in some arguments, being selected by an identity-level tie-break. That event has no faithful nonatomic counterpart.
Theorem 3 does not repair the case. It is a finite distortion bound, not a computational complexity result, and its construction uses \(n\)- and \(k\)-dependent profiles with finely separated individual locations. With fixed \(\tau\), those profiles collapse into a few masses; with \(\tau\) growing to preserve all distinct locations, the claimed high-multiplicity compression disappears. Taking \(k/n\to\kappa\) is a legitimate per-capita extension, but it changes the resource regime; keeping \(k\) fixed instead sends \(\kappa\) to zero and makes the served population vanish. The suggested limiting ratios are therefore conjectural properties of a newly chosen population game, not continuous versions of the stated theorem.
The honest concession is that the weighted welfare problem is not nonsensical. It could be studied as a modest high-multiplicity facility-location exercise. But the best versions divide exhaustively into a thin weighted restatement, a vacuous individual-strategy model, an identity-preserving model with no multiplicity, or a positive-mass coalition model that changes the problem. None yields a worthwhile ChoCo mirror of a named computational result in this paper.
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.