| paper | FLIGHT: Facility Location Integrating Generalized, Holistic Theory of Welfare |
| authors | — |
| venue | AAMAS 2025 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed population mirror is direct, recognizable, and likely tractable, but the paper contains no numbered computational result satisfying the source gate. Theorem 9 supplies a distributional identity and Theorem 1 supplies structure; the polynomial placement algorithm is new analysis by the proponent. Therefore bit (a) fails even though the continuous question itself is worthwhile.
fails bit a — no named computational result to mirror
The mirror directly covers Theorem 9's expected-welfare identity and uses Theorem 1's concavity; it leaves the paper's other structural, approximation, estimation, and asymptotic results without computational mirrors.
The strongest honest positive case is narrow: a Class-A population mirror of the paper’s Section 6, led by Theorem 9, which is proved in this paper (with the full proof deferred to [30]). Theorem 9 states that, for i.i.d. locations drawn from \(P\), expected welfare is \(n\) times the convolution \([\alpha\ast P](y)\). Theorem 1, also proved here, supplies the key structural fact that the welfare function is concave in the facility location.
A natural regime is a city or service corridor with millions of residents but only \(\tau\) relevant location types: for example, residents of the same transport zone, sharing the same effective location and utility response. The type is the complete welfare-relevant description, here a location \(a_t\in[0,1]\); the mass \(\mu_t\) is the fraction of residents of that type. We have \(n\gg\tau\), and rational masses \(\mu_t=n_t/n\) recover a finite electorate of repeated resident clones exactly.
My lead problem would be:
Population-FLIGHT Placement\(_\infty\). An instance consists of rational locations \(a_1,\ldots,a_\tau\in[0,1]\), rational masses \(\mu_1,\ldots,\mu_\tau\) with \(\sum_t\mu_t=1\), and a concave utility function \(\alpha:[-1,1]\to\mathbb Q\), represented for example as a rational piecewise-linear function whose maximum is attained at \(0\). Define
\[ \mathcal W_\alpha(y;\mu)=\sum_{t=1}^{\tau}\mu_t\alpha(y-a_t). \]
The task is to output a facility location \(y^\star\in[0,1]\) maximizing \(\mathcal W_\alpha(y;\mu)\), or an \(\epsilon\)-optimal location satisfying \(\mathcal W_\alpha(y^\star;\mu)\ge \max_y\mathcal W_\alpha(y;\mu)-\epsilon\).
This is exactly the population version of the paper’s welfare objective, not a fractional facility-location problem: the facility remains one indivisible point \(y\), while only the population is represented by mass. If \(\mu_t=n_t/n\), then \(n\mathcal W_\alpha(y;\mu)=W_\alpha(y,x)\), so the set of optimal facility locations is unchanged. The paper’s Theorem 9 becomes the identity \(\mathcal W_\alpha(y;\mu)=[\alpha\ast\mu](y)\).
For the stated piecewise-linear encoding, this problem should be in Class A. The sum is a concave piecewise-linear function. One can form the translated breakpoints of the \(\tau\) copies of \(\alpha\), sort them, and locate the interval where the aggregate slope changes sign. The running time is polynomial in \(\tau\), the number of pieces of \(\alpha\), and the encoding length \(L\), rather than in the potentially enormous population size \(n\). With a value-and-subgradient oracle for a more general concave \(\alpha\), one obtains the corresponding oracle-polynomial version.
The mirror is particularly recognizable to the authors because they themselves introduce an i.i.d. distribution \(P\), define expected welfare through convolution, and motivate it by settings in which the exact locations of a large population are unavailable. The continuous problem merely makes their distributional object the society itself. It also generates worthwhile computational questions: what happens when \(P\) is a succinct density rather than finite support; how does complexity depend on the representation of a learned \(\alpha\); can one compute multi-facility or capacitated variants; and what uniform finite-sample guarantees allow the empirical optimizer to replace the population optimizer?
The paper’s Theorem 10 and Theorem 11 provide supporting motivation rather than stronger anchors. Theorem 10 identifies expected welfare as the best \(F\)-distance estimator of empirical welfare, and Theorem 11 gives convergence of normalized empirical welfare to expected welfare in probability. These naturally motivate a second problem—compute or estimate the population welfare function from samples—but neither theorem states a complexity classification, so I would not pad the case by presenting them as independent computational anchors.
The serious weakness is the source gate. This paper contains no numbered theorem asserting membership in \(P\), NP-hardness, FPT, W[1]-hardness, or a comparable computational classification. Theorem 9 is a named, constructive distributional result, and the placement problem above is a genuine and likely tractable high-multiplicity mirror, but the runtime claim is new analysis rather than a result established by the paper. Thus, under a strict ChoCo rule requiring a named computational anchor, the paper fails that formal gate despite having an unusually natural population-continuous object. Under a more permissive rule accepting named algorithmically enabling results, this is a defensible, narrowly scoped Class-A mirror.
The negative case is decisive under ChoCo’s source gate. The paper has no numbered computational result to mirror. Theorem 9 is an expectation identity:
\[
\mathbb{E}\!\left[\sum_{i=1}^{n}\alpha(y-X_i)\right]
=n\int \alpha(y-x)\,dP(x).
\]
For \(P=\sum_t\mu_t\delta_{a_t}\), this is exactly
\[
n\sum_t\mu_t\alpha(y-a_t).
\]
Thus Population-FLIGHT is a recognizable high-multiplicity restatement of the paper’s objective, but the paper never proves a complexity classification, an algorithm, an approximation guarantee, or even a computational formulation for choosing \(y\). The proponent’s proposed polynomial algorithm is new work prompted by the theorem, not a computational result established by it. Under the stated rule, that is fatal.
Theorem 1 cannot rescue the case. Concavity of
\[
W_\alpha(y,x)=\sum_i\alpha(y-x_i)
\]
is a structural observation, not an algorithmic result. Passing to masses merely replaces the sum by a weighted sum:
\[
\mathcal W_\alpha(y;\mu)=\sum_t\mu_t\alpha(y-a_t),
\]
whose concavity follows immediately. The theorem supplies no complexity question beyond the newly invented task of optimizing a one-dimensional concave function.
The strongest possible re-modelling does not repair the missing anchor. One could use an atomless society and define
\[
\mathcal W_\alpha(y;\mu)=\int_{[0,1]}\alpha(y-x)\,d\mu(x).
\]
With finite rational support, this is just weighted finite facility location and the population size has disappeared by exact clone compression. With a density, learned welfare function, or value oracle, the computational problem depends on representation, integration access, regularity assumptions, and approximation conventions that the paper does not specify. Multi-facility and capacitated versions would be legitimate new facility-location research, but they are extensions invented beyond Theorem 9, not mirrors of a named result.
Theorem 10 and Theorem 11 do not help either: they concern mean-square estimation and a law-of-large-numbers limit, not computation. Moreover, convergence of normalized welfare does not by itself give convergence or efficient recovery of an optimizer; uniform convergence, uniqueness or stability of maximizers, and finite-sample guarantees would all have to be supplied separately.
So the proposed mirror is mathematically sensible, and this is the main weakness of the negative case: in a looser programme one could reasonably study it as a narrow Class-A population extension. But it is not a qualifying ChoCo mirror of this paper. The paper already contains the distributional population object, while contributing no computational result about it. Any worthwhile complexity theory would be imported by the analyst’s chosen encoding or by a new facility-location variant. I would therefore grade the paper red under the programme’s stated standard.
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.