| paper | Strategic Facility Location with Clients That Minimize Total Waiting Time |
| authors | — |
| venue | AAAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 8
statement extracted from the paper’s text layer
Given a finite host graph, \(k\) facilities, rational masses \(d_t\) of customer types with reachability ranges \(R_t\), and \(\varepsilon > 0\), output a facility placement \(s\) such that every facility's uniformly captured mass is within factor \(1+\varepsilon\) of its best unilateral deviation.
Uniform-2-FLG with finitely many customer types, each carrying demand mass \(d_t\) and a reachability range; facilities choose sites, customer mass splits uniformly, and payoffs are captured demand.
The Uniform-2-FLG already aggregates each range class into a single weighted demand, so introducing population masses adds no new strategic or computational degrees of freedom.
fatal: False
Covers Theorems 8 and 9 for Uniform-2-FLG; leaves the Min-2-FLG results, including Theorems 1–7, outside the mirror.
There is a credible continuous mirror here, although I would anchor it on the paper’s Uniform-2-FLG results rather than claim that the whole Min-2-FLG immediately continuizes.
The natural high-multiplicity setting is a city, campus, or service network with many recurring customers and finitely many candidate facility sites. A customer type \(t\) consists of its shopping range \(R_t\subseteq V\), its purchasing-power level \(q_t\), and the common rule that it distributes demand uniformly among reachable facilities. The population is given by rational masses \(\mu_t\), with aggregate demand \(d_t=\mu_tq_t\). There may be millions of customers but only a few hundred catchment-and-demand types. Facilities remain named strategic agents: each of the \(k\) facilities chooses a site in the finite set \(V\).
For a facility placement \(s=(s_1,\ldots,s_k)\), define
\[ A_t(s)=\{j:s_j\in R_t\}. \]
If \(A_t(s)\neq\varnothing\), type \(t\) sends \(d_t/|A_t(s)|\) to every facility in \(A_t(s)\). Thus facility \(j\)'s payoff is its received purchasing-power mass,
\[ \ell_j(s)=\sum_{t:j\in A_t(s)}\frac{d_t}{|A_t(s)|}. \]
This is genuinely population continuization: the graph and facility actions remain discrete, while the customer population is represented by mass over indistinguishable reachability types. The fact that customers already split purchasing power fractionally in the paper is not itself the continuization; the new object is the mass distribution \((\mu_t)\).
My lead anchor is Theorem 8, proved in this paper: “There is a FPTAS to compute a \((1+\epsilon)\)-approximate equilibrium in the Uniform-2-FLG.”
The corresponding continuous problem is:
Continuous Uniform Approximate Equilibrium. Given \(V\), \(k\), the type ranges \(R_t\), rational masses \(d_t\), and \(\epsilon>0\), output a facility placement \(s\) such that, for every facility \(j\) and every alternative site \(v\in V\),
\[ \ell_j(s)\geq \frac{1}{1+\epsilon}\ell_j(v,s_{-j}). \]
The induced uniform customer allocation is part of the solution. Equivalently, no facility can improve its captured mass by a factor greater than \(1+\epsilon\).
I expect this problem to be in Class A. The proof mechanism in the paper survives the replacement of individual weighted clients by type masses. The potential becomes
\[ \Phi_\mu(s)=\sum_t d_t H_{|A_t(s)|}, \]
where \(H_r\) is the \(r\)-th harmonic number. A unilateral facility move changes this potential by exactly the facility’s payoff change. The paper’s approximate-best-response dynamics therefore work with \(\tau\) types rather than with an explicitly listed population, and run in time polynomial in \(|V|,k,\tau\), the encoding length of the masses, and \(1/\epsilon\).
This is a mirror the authors should recognise: it is their Uniform-2-FLG, with the client population compressed into repeated reachability types. A realistic realization is a large recurring demand market in which a platform or routing policy sends each customer class uniformly to all eligible outlets. The number of customer instances can be much larger than the number of catchment types, so the high-multiplicity interpretation is substantive rather than cosmetic.
A second, complementary anchor is Theorem 9, also proved here: “Computing an exact equilibrium in the Uniform-2-FLG is PLS-complete.”
The exact continuous problem is:
Continuous Uniform Exact Equilibrium. On the same mass-and-range instance, output a placement \(s\) satisfying
\[ \ell_j(s)\geq \ell_j(v,s_{-j}) \]
for every facility \(j\) and every site \(v\in V\).
I expect this to be Class B: hardness transfers from the discrete problem. Given the paper’s LOCALMAXCUT reduction, assign one continuous type to each constructed client vertex, with mass proportional to its weight. Normalising all masses by their total does not change any best-response comparison. The reduction therefore produces a continuous instance with an exact equilibrium precisely when the LOCALMAXCUT instance has the required local optimum.
The high-multiplicity interpretation can be made literal: replace each weighted type by \(R\) indistinguishable customer copies, each with \(1/R\) of the type’s purchasing power. The aggregate loads and all facility incentives remain unchanged, while the number of agents becomes arbitrarily larger than the number of types. The strategic difficulty lives in the facility/site and reachability structure, not in individual customer identities. Thus the continuum does not erase the paper’s PLS-hardness; it exposes the expected Class A/Class B boundary between approximation and exact equilibrium.
This case deliberately covers Theorems 8 and 9, not the entire paper. I would not yet claim an equally clean mirror for the central Min-2-FLG results. In the original model, a client is an atomic splittable player whose own allocation affects facility loads. If many identical clients are replaced by an atomless population, the limiting equilibrium becomes Wardrop-like: positive mass uses only facilities of minimum load. That is a related problem, but not literally the same atomic congestion game. A natural further question is therefore to define the continuous Min-2-FLG formally, solve its fixed-placement client equilibrium by convex or variational methods, and determine whether the paper’s \(3+2\epsilon\) approximation argument survives.
That atomicity issue is the weakest point of the mirror. The strongest part nevertheless survives: the Uniform-2-FLG is an explicit model studied in the paper, its customers are already defined by reachability and purchasing power, and both its approximation algorithm and its exact-equilibrium hardness extend naturally to distributions over repeated customer types.
The strongest negative case is that the proposed Uniform-2-FLG mirror has no genuine population limit to take. In that version, clients do not strategize at all: a client matters only through its shopping range and purchasing power. For a type \(t\), the only quantity entering any facility payoff is
\[ d_t=\mu_t q_t. \]
Replacing the whole type by one weighted client with weight \(d_t\) produces exactly the same load for every facility placement, the same deviations, and the same potential. Splitting that weight among a million identical customers changes nothing. This is not merely a case where “continuity does not help”; the paper has already quotiented out client identity and formulated the game at the aggregate-weight level.
That defeats Theorem 8 as a genuinely new continuous anchor. The proposed potential,
\[ \Phi_\mu(s)=\sum_t d_t H_{|A_t(s)|}, \]
is simply the paper’s existing potential after collecting equal-range clients and adding their weights. The FPTAS therefore does extend to the notation of masses, but it is already an algorithm for the same weighted-demand game. Calling the weights fractions of a recurring population supplies a plausible story, not a new computational object. Even granting the proponent’s better formulation with separate customer types and facility sites, it remains a weighted coverage game whose sufficient statistic is the finite vector \((d_t)\).
Theorem 9 fails for the same reason. The LOCALMAXCUT reduction can certainly be written with type masses, and normalizing all weights preserves every best-response comparison. But that shows only that the weighted facility-placement game is PLS-hard. It does not show that a continuous population creates a new problem. The reduction uses customer weights as numerical coefficients; it never uses customer multiplicity, identity, or an atomless population. The proposed “replace each type by \(R\) copies” construction is especially revealing: it is an exact replication with no change in the instance’s strategic content. The continuum is decorative.
A possible rescue would be to move from Uniform-2-FLG to the paper’s Min-2-FLG and let many atomic clients converge to an atomless population. That does create a more substantial modelling change, but it removes the paper’s defining client game. The atomic equilibrium condition depends on a client internalizing the effect of her own allocation on facility load, as in Lemma 1’s terms \(\ell_j+\sigma_{ij}\). Under a fixed-total-demand atomless limit, each individual’s effect vanishes and the model becomes a Wardrop assignment problem. Keeping each client’s atom non-negligible prevents the high-multiplicity limit; shrinking it produces a different game. A Wardrop facility-location game could be worthwhile in its own right, but it would be a new model motivated by congestion theory, not a continuous mirror of Theorems 1–7.
The honest limitation is that this is not an airtight universal objection. Recurring customer classes with common catchment patterns are perfectly plausible, and the programme explicitly permits weighted high-multiplicity interpretations. If that interpretation alone counts as a worthwhile mirror, then the proponent has supplied a legitimate one. The negative case is narrower but substantial: for the two anchors actually offered, the population has already been aggregated in the paper’s formulation. Their “continuous versions” are valid re-descriptions of the existing weighted game, not new continuization questions for ChoCo.
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.