| paper | Multi-Stage Facility Location Problems with Transient Agents |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given stages \(T\) and tolerance \(r\), a finite rational set of arrival-location types \((a,z)\) with rational masses summing to one, choose facility locations \(y_s\) for \(s=1,\ldots,T+r-1\) and service masses \(x_{a,z,s}\) summing to each type's mass, with \(a<a'\) implying every positive service stage for \((a,z)\) is no later than every positive service stage for \((a',z')\), to minimize the total weighted distance sum of \(x_{a,z,s}|y_s-z|\).
A finite high-multiplicity population of arrival-stage/location types carrying rational mass; decisions are facility locations and fractional service assignments within tolerance windows, optimized by weighted absolute-distance social cost.
Theorem 3's expanded-count dynamic program does not establish polynomial complexity in the number of types and the bit-length of rational masses; compressed cut-point states could conceal new hardness.
fatal: False
The mirror covers the NMC-FCFS social-cost and maximum-cost optimization results, Theorems 3 and 4, while leaving the non-FCFS algorithms, WMC results, and mechanism-design theorems unaddressed.
The strongest mirror is the FCFS version of the paper’s optimization problem, with the population—not time or facility location—made continuous.
A credible regime is municipal testing over \(T\) days. On each day, a large cohort of residents arrives from a small number of neighbourhoods or pickup points. Residents from the same arrival day and location are indistinguishable for the model: they have the same position, arrival time, tolerance \(r\), and travel-cost function. Thus there may be millions of residents but only \(qT\) distinct types, where a type is \((a,z)\): arrival stage \(a\) and location \(z\). The mass \(\mu_{a,z}\) is the fraction of the population of that type. FCFS is the natural fairness rule that every earlier-arriving cohort must be served no later than every later-arriving cohort.
My lead anchor is Theorem 3, proved in this paper: “\(\mathrm{OPT}^{\mathrm{NMC-WFCFS}}(T+r-1,T,0,0)\) computes the optimal social cost for the NMC-WFCFS model” in polynomial time.
The corresponding problem is:
Continuous FCFS Transient-Facility Social Cost. An instance consists of integers \(T,r\), a finite rational location set \(Z=\{z_1,\ldots,z_q\}\subseteq\mathbb Q\), and rational masses \(\mu_{a,j}\ge 0\), with \(\sum_{a,j}\mu_{a,j}=1\). A type \((a,j)\) arrives at stage \(a\), is located at \(z_j\), and must be served at some stage \(s\in\{a,\ldots,a+r-1\}\).
A solution chooses facility locations \(y_1,\ldots,y_{T+r-1}\) and nonnegative service masses \(x_{a,j,s}\), where \(x_{a,j,s}\) is the mass of type \((a,j)\) served at stage \(s\), satisfying
\[ \sum_{s=a}^{a+r-1}x_{a,j,s}=\mu_{a,j}. \]
The FCFS condition is that whenever \(a<a'\), positive service of type \((a,j)\) at stage \(s\) and positive service of type \((a',j')\) at stage \(s'\) must satisfy \(s\le s'\). The objective is
\[ \min \sum_{a,j,s}x_{a,j,s}\lvert y_s-z_j\rvert . \]
The solution is the facility sequence and service-mass assignment attaining the minimum.
This is not a diluted facility-location problem. It preserves the paper’s stages, deadlines, one facility per stage, arbitrary service assignment within tolerance windows, FCFS constraint, and social-cost objective. The only change is replacing a long list of duplicate agents by its weighted histogram. A rational discrete instance maps to \(\mu_{a,j}=n_{a,j}/n\), and a discrete service schedule maps to the \(x\)-variables. Conversely, rational mass solutions can be scaled into sufficiently large finite populations. The continuous objective is simply the normalized discrete objective.
I would expect this mirror to be Class A. The key structural observation behind Theorem 3 is that served agents form consecutive blocks in each ordered cohort, and FCFS restricts how those blocks interact across stages. In the continuous version, consecutive blocks become intervals of cumulative mass. The function \(g(W)\) becomes a weighted 1-median cost,
\[ g_\mu(W)=\min_y\int_W |z-y|\,d\mu, \]
which is piecewise-linear and attained at a weighted median. The paper’s dynamic-programming states should therefore become states indexed by a bounded number of support locations and rational mass cut-points, with each transition solved by a small linear or piecewise-linear optimization problem. The important question is whether this compressed weighted DP is polynomial in \(T,r,q\) and the encoding length of the masses, rather than polynomial in the expanded population size.
My second anchor is Theorem 4, also proved here: “Algorithm 2 computes the optimal maximum cost for the NMC-WFCFS model” in polynomial time.
The matching problem is:
Continuous FCFS Transient-Facility Bottleneck Cost. The instance and feasible solutions are exactly as above. Minimize \(M\) subject to
\[ x_{a,j,s}>0\quad\Longrightarrow\quad |y_s-z_j|\le M. \]
Equivalently, \(M\) is the largest travel distance incurred by any positive-mass agent under the chosen service assignment, and the task is to find the minimum possible \(M\).
This is especially convincing as a mirror because the paper’s serving-range formulation survives almost literally. A serving range of length \(\ell\) covers a mass of agents if it covers every location with positive mass. With finite support, the only relevant candidate lengths are pairwise distances between support locations, so there are only \(O(q^2)\) candidate values. The FCFS feasibility recursion can then track the last range covering each cohort exactly as Algorithm 2 does. I would expect this problem to be polynomial, probably more straightforwardly than the social-cost version. The masses matter semantically—an arbitrarily small positive mass still counts in a maximum-cost objective—but they do not create a new combinatorial population-size parameter.
The high-multiplicity scenario is plausible rather than artificial. A testing authority may know that 18% of a neighbourhood’s residents arrive on day \(a\), and that all residents represented by a pickup point have the same travel location in the model. It is entirely reasonable to optimize over those proportions instead of pretending that one-person granularity is operationally meaningful. The paper already treats \(X_t\) as ordered multisets and uses multiplicities through \(N_t\), so the authors should recognize this as a weighted, high-multiplicity form of their own model.
I would not use the paper’s mechanism-design theorems as anchors. Theorems 5–8 concern group strategy-proofness and approximation of strategic mechanisms; a nonatomic strategic model would require additional choices about reports, coalitions, and measurable deviations. The two optimization anchors already give a clean computational mirror. Likewise, the paper proves no NP-hardness result for the unrestricted models: its conclusion only conjectures that the no-FCFS optimization problems are NP-hard. That conjecture cannot serve as a hardness anchor.
The main weakness is that the paper’s algorithms are polynomial in the expanded number of agents, whereas the genuinely continuous question asks for polynomial dependence on the number of types and the bit-length of their masses. A weighted version might conceal a new succinct-encoding hardness, so Theorem 3 does not automatically imply the claimed compressed algorithm. This is a real technical gap, not something to hand-wave away. Still, the FCFS block structure, weighted-median objective, and finite-support serving ranges make the positive expectation credible. The natural follow-up is precisely to determine whether the compressed FCFS problems are Class A, and whether removing FCFS produces a continuum-specific hardness boundary.
The strongest negative case is that these are not yet demonstrated to be worthwhile continuous results; they are plausible weighted reformulations whose genuinely new complexity has not been established.
Theorem 3 is the better anchor, but it survives the criticism. The paper already represents agents as ordered location multisets, so the proposed model merely aggregates identical \((\text{arrival stage},\text{location})\) agents and permits their mass to split across service stages. That is exactly the high-multiplicity relaxation, not an artificial change of story. The proponent is right that weighted medians and cumulative-mass blocks are the natural replacements for the paper’s consecutive subsets.
The real objection is technical: Theorem 3’s polynomial algorithm is polynomial in the expanded counts \(n_{\max}\), not in the number of types and the bit-length of binary-encoded masses. “Replace counts by masses” does not prove a succinct algorithm. Fractional cut-points may be determined by combinations of masses, and the paper’s dynamic-programming state space might conceal a new compressed-encoding difficulty. Until a polynomial algorithm or hardness result is supplied, this is a research proposal rather than a result. But that is a gap in the proposed follow-up, not a fundamental reason the mirror is worthless. An atomless location distribution would make the model more natural still: consecutive blocks become cumulative-mass intervals and costs become quantile integrals.
Theorem 4 offers a stronger negative point. For maximum cost, the magnitudes of positive masses are irrelevant. If every listed type has positive mass, changing \(1\%\) of the population to \(90\%\) changes nothing: feasibility depends only on which support points must be covered. Passing to an atomless distribution likewise turns the objective into an essential-support or essential-supremum problem. A mass-sensitive percentile or tail objective would be more genuinely continuous, but that would no longer mirror the paper’s maximum-cost theorem. Thus this anchor risks degenerating into a finite-support coverage problem with population labels attached.
Still, even that objection does not defeat the mirror outright. The original maximum-cost objective itself ignores multiplicity, and a support-based high-multiplicity problem is still a legitimate computational question. Nor can one object that agents lack multiplicity, that identity is essential, or that the problem is already continuously solved: cohorts at common locations are a credible high-multiplicity regime, and both objectives are computational rather than axiomatic.
So the honest negative verdict is narrow: reject Theorem 4 as the strongest ChoCo target because its mass dependence collapses, and demand an actual compressed-complexity theorem before treating Theorem 3 as a contribution. A universal “no worthwhile mirror in any scenario” is not supportable. The FCFS social-cost problem is a faithful and potentially valuable continuous mirror; the negative case can downgrade it from established result to unresolved promise, but cannot eliminate 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.