| paper | d4-conf-aaai-2026-1043 |
| 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: an exact optimal equilibrium-stable pair, or a certificate that none exists, can be found in time polynomial in \(\tau\) and \(L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given tau\ locations \(x_t\in[0,1]\) with positive rational masses \(mu_t\) summing to \(1\), and rational capacities \(q_1ge q_2>0\) with \(Q=q_1+q_2<1\), choose percentile parameters \(p_1,p_2\in[0,1]\) satisfying \(p_2-p_1ge Q\), placing facilities at \(y_j=F_mu^{-1}(p_j)\). Define FCFS service and equilibrium stability when a cutoff divides a location’s mass, then determine the complexity, in \(tau\), input bit length, and approximation tolerance delta, of finding a stable pair with welfare at least \(mathrm{OPT}_mu-delta\), where \(mathrm{SW}_mu=Q-sum_{j=1}^2int_{B_{mu,q_j}(y_j)}|x-y_j|\,dmu(x)\) and boundary mass may be split fractionally.
A town has tau\ residential locations \(x_t\), each containing a cohort of interchangeable residents with population share mu_t\). Each resident’s utility from service at \(y\) is \(1-|x_t-y|\); facilities have per-capita capacities \(q_1,q_2\). Percentile parameters select facility locations, and the objective is total served mass minus distance cost, subject to a tie-aware definition of equilibrium-stable FCFS service.
The paper’s equilibrium-stability characterization may not survive positive mass ties: fractional service at a cutoff alone does not establish which FCFS equilibria exist or whether they have the same welfare. The proponent acknowledges this tie-aware modeling work but does not settle it.
fatal: False
The mirror covers the two-facility equilibrium-stable percentile optimization underlying Theorem 10. It leaves the one-facility characterizations, other distribution classes, convergence results, experiments, and extensions to more facilities aside.
The strongest case is for the paper’s two-facility optimization problem, with the population represented by masses of location types. There is no numbered result here saying a problem is NP-hard, in P, or in another complexity class. The closest computational anchor is Theorem 10, proved in this paper: for a probability measure \(\mu\), capacities \(q_1,q_2\), and tolerance \(\delta>0\), Algorithm 1 returns a pair of facility positions whose objective \(W\) is within \(\delta\) of the minimum \(W\) over pairs satisfying the equilibrium-stability constraint
\[
|F_\mu(y_2)-F_\mu(y_1)|\ge q_1+q_2.
\]
The paper says the routine compares \(O(\delta^{-2})\) candidates; since asymptotic social welfare is total capacity minus \(W\), this gives welfare within \(\delta\) of the best equilibrium-stable percentile mechanism. This is an approximation result, not a theorem that the problem is in P.
A concrete mirror is High-Multiplicity ES Two-Facility Placement. Take a finite set of locations \(x_1<\cdots<x_\tau\) on a road. Type \(t\) consists of residents at location \(x_t\), with rational mass \(\mu_t>0\) and \(\sum_t\mu_t=1\). A type’s location completely determines its utility: if served by a facility at \(y\), each unit of its mass gets \(1-|x_t-y|\); otherwise it gets zero. Facilities have rational per-capita capacities \(q_1\ge q_2\), with \(Q=q_1+q_2<1\). A percentile pair \((p_1,p_2)\) places facility \(j\) at \(y_j=F_\mu^{-1}(p_j)\), where \(F_\mu\) is the society’s cumulative mass. Require \(p_2-p_1\ge Q\), the continuous equilibrium-stability constraint. At a service cutoff that divides a type’s mass, split that mass fractionally; those residents are interchangeable, so this does not change their utility.
The question is: given \((x_t,\mu_t)_{t=1}^\tau\), \(q_1,q_2\), and \(\delta>0\), find a feasible percentile pair with asymptotic social welfare within \(\delta\) of the maximum over feasible pairs. Using the paper’s welfare objective, write it as
\[
\operatorname{SW}_\mu(p_1,p_2)
=Q-\sum_{j=1}^2\int_{B_{\mu,q_j}(y_j)} |x-y_j|\,d\mu(x),
\]
where \(B_{\mu,q_j}(y_j)\) is the mass \(q_j\) closest to \(y_j\), with fractional splitting at a boundary tie. The output is the pair \((p_1,p_2)\), its facility locations, and the guarantee \(\operatorname{SW}_\mu(p_1,p_2)\ge \operatorname{OPT}_\mu-\delta\). The type-mass version needs a tie-aware definition of the paper’s FCFS and stability conditions; the displayed objective is its natural extension to co-located mass.
A convincing regime is a large town with many residents in a modest number of residential blocks or campuses: \(n\) is in the hundreds of thousands or millions, while \(\tau\) counts the distinct locations and is much smaller. Residents at one location share the preferences and service options the model uses, and capacity is naturally stated as a fraction of the population. The authors should recognize the mirror: it asks for the same facility placements, under the same FCFS and percentile-mechanism logic, to maximize the same welfare objective. Its expected direction is Class A. With finite \(\tau\), percentile placements fall at supported locations; enumerating location pairs and evaluating their fractional service costs gives a natural exact algorithm polynomial in \(\tau\) and the input bit length. Theorem 10 supplies the broader optimization structure and an approximation routine for distributions not given as a finite list of sites.
The mirror covers only the two-facility, equilibrium-stable percentile optimization behind Theorem 10. Further questions include how the result changes when stability is dropped, how the model extends to more facilities, and how the finite-type answer relates to the paper’s smooth-density asymptotics.
The weakest point is that the paper already studies a population distribution and its large-\(n\) limit. This is not a new reason to continuize facility location. The positive case is narrower: its theorem does not classify complexity in the number of types and their encoding length, and the co-located, high-multiplicity instance regime requires a tie-aware extension of the paper’s smooth-density model. That leaves a computational question worth asking, while making clear that the paper has already done much of the analytic continuization.
Theorem 10 is the strongest anchor, and it also makes the negative case strongest: the paper already studies the continuous population problem that the proposed mirror would pose. Its measure \(\mu\) is not merely noise added to a finite electorate. As \(n\) grows, the authors pass from sampled residents to a mass distribution, give facilities per-capita capacities, and optimize aggregate welfare against that distribution. In the two-facility case, their objective \(W\) and equilibrium-stability constraint are already stated over mass cutoffs. Theorem 10 then gives a search routine whose welfare is within \(\delta\) of the best feasible percentile mechanism.
The proposed finite-location version is sensible, but it does not identify a new continuization. It specializes the paper’s measure-based placement problem to rational masses at finitely many locations and asks for complexity in the support size and bit length. The paper does not give that input-sensitive complexity analysis, but its existing result already supplies the continuous optimization objective and a \(\delta\)-approximation routine. Pursuing the finite-support formulation would sharpen the computational representation of this problem; it would not make the population continuous for the first time or reveal a new computational question arising from that move.
There is a real modeling detail around atoms. Fractionally splitting residents at a service cutoff gives a natural welfare definition because residents at the same location have the same distance to a facility. But for two facilities, that convention alone does not establish that the resulting allocation is an FCFS equilibrium or that the paper’s equilibrium-stability characterization still applies when positive mass is tied. An atom-aware version could define those details. If it preserves the paper’s mass objective and stability constraint, it returns to the optimization problem Theorem 10 already treats; if tie equilibria change which welfare values are feasible, it has become a distinct mechanism game.
I would not argue that high multiplicity is implausible here: a large town with many residents concentrated in a modest number of locations is a credible regime, and grouping identical residents is appropriate. The residual case for a mirror is specifically an exact, bit-complexity analysis for finite-support inputs, together with a rigorous tie-aware game definition. That is a legitimate refinement, but on the text provided it looks too narrow to count as a worthwhile new continuous mirror. The negative case is strongest against novelty of the continuization itself; it is weaker if ChoCo treats input-sensitive complexity refinements of an already continuous optimization model as a programme contribution.
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.