Strategic Facility Location via Predictions

Theorem 4.3 satisfies the computational bit through an algorithmic performance guarantee. However, an individual in the continuum has zero influence on the mass lottery, so the paper's strategic equilibrium notion collapses. Treating each type as a coordinated deviating bloc creates a different weighted-player game, so no valid continuous analogue of the anchored theorem survives.

The objection that survived

The proposed mass-PNE replaces individual agents with coordinated type cohorts, whereas the literal continuum makes unilateral deviations payoff-equivalent.

What the mirror covers

The attempted mirror covers only Theorem 4.3's strict-convexity robustness guarantee \(O(1+1/c^2)\); it does not establish valid mirrors for the general-metric bound, the \(\mathrm{Harmonic}(0)\) theorem, or the structural equilibrium claims.

Open questions for a prover

The case FOR (proponent)

The strongest honest positive case is a narrow one built around Theorem 4.3, proved in this paper. It is not a hardness or polynomial-time theorem—the paper contains no named complexity classification—so this would be a performance-oriented continuization rather than a full ChoCo complexity result.

Theorem 4.3 states that, in a strictly convex normed metric space, the Harmonic mechanism is \(O(1+1/c^2)\)-robust when \(\Delta=(c/n)\operatorname{SC}(\hat o,\ell)\). More explicitly, Harmonic selects reported location \(\tilde\ell_i\) with probability proportional to \(1/(d(\tilde\ell_i,\hat o)+\Delta)\); for every true profile, every prediction \(\hat o\), and every pure Nash equilibrium of the induced reporting game, the expected social cost is at most \(O(1+1/c^2)\) times the optimum. The result is proved here; it is not merely cited. Lemma 4.1, the \(2\)-approximation guarantee for random dictatorship, is cited from Alon et al. and is only a supporting ingredient.

A natural continuous-population setting is municipal facility planning. Suppose a city has \(N\) residents, but residents fall into only \(\tau\) location types: for example, \(N\gg\tau\) residents live in \(\tau\) repeated origin clusters and have identical facility preferences within each cluster. Let type \(t\) have preferred location \(p_t\) and population mass \(\mu_t\), where \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\). The city has a predicted facility location \(\hat o\). A type is complete here because all agents of that type have the same preferred location, metric costs, and reporting protocol.

The continuous problem I would hand to a prover is Continuous Harmonic Mass-Equilibrium. Its input is a strictly convex normed metric space \((M,d)\), finitely many location types \(p_1,\ldots,p_\tau\), rational masses \(\mu_1,\ldots,\mu_\tau\), a prediction \(\hat o\), a constant \(c>0\), and a public parameter \(\Delta=c\sum_t\mu_t d(p_t,\hat o)\). The optimum is \(\operatorname{OPT}_\mu=\min_{x\in M}\sum_t\mu_t d(p_t,x)\).

Each type chooses one reported location \(r_t\in M\). The continuous Harmonic mechanism samples a facility from the mass-weighted distribution \(\pi_r\) defined by

\(\pi_r=\frac{1}{Z_r}\sum_{t=1}^{\tau}\frac{\mu_t}{d(r_t,\hat o)+\Delta}\delta_{r_t}\),

where \(Z_r=\sum_t\frac{\mu_t}{d(r_t,\hat o)+\Delta}\). Thus the facility remains a single point; only the population supplying the lottery is continuous. Type \(t\)'s cost is \(u_t(r)=\mathbb{E}_{F\sim\pi_r}[d(p_t,F)]\), and the population social cost is \(\operatorname{SC}_\mu(r)=\sum_t\mu_t u_t(r)\).

The strategic equilibrium notion must be stated explicitly. A mass-PNE is a report vector \(r\) such that no type-cohort can replace its entire mass by a different report \(z\) and reduce its per-capita cost: \(u_t(r)\le u_t(r_{-t},z)\) for every type \(t\) and every \(z\in M\). A solution consists of such an \(r\), the induced distribution \(\pi_r\), and either the exact social cost or an approximation to it. Equivalently, with a threshold \(B\), one can ask whether there exists a mass-PNE satisfying \(\operatorname{SC}_\mu(r)\le B\operatorname{OPT}_\mu\).

This is a genuine population continuization. For rational masses \(\mu_t=n_t/N\), the mechanism and normalized social cost are exactly those of \(N\) repeated agents when all members of a type report identically. The facility is not fractional, the metric is not replaced by a probability space, and the outcome is not relaxed beyond the paper’s existing lottery. What changes is that the population is represented by masses rather than named individuals.

The connection to Theorem 4.3 is strong because its proof uses aggregate sums over agents, the shortest-path restriction on reports, and metric inequalities. Those sums become weighted sums over types. The analogue of Claim 3.3 should restrict each \(r_t\) to a shortest path from \(p_t\) to \(\hat o\), reducing the strategic variables to \(\tau\) path parameters. The strict-convexity inequality used in Theorem 4.3 is pointwise, so its weighted version should survive unchanged. I would therefore expect this mirror to be tractable in a qualified Class A sense for finitely supported populations: approximate equilibrium computation and PoA certification should reduce to finite-dimensional continuous optimization, with complexity governed by \(\tau\), the metric dimension, and the encoding length of the masses—not by \(N\). Exact equilibrium selection remains an open computational question because the paper’s Kakutani argument is existential rather than algorithmic.

The main weakness is also the decisive modelling choice. In a literal nonatomic population, one individual has zero influence on \(\pi_r\), so unilateral deviations become vacuous and arbitrary report distributions can be equilibria. The proposed mass-PNE avoids that collapse by treating identical populations as coordinated reporting cohorts. That is plausible for districts, neighbourhood associations, or institutional representatives, but it is not the literal individual-agent equilibrium concept of the paper. If the authors reject cohort coordination, this mirror fails. A second limitation is that Theorem 4.3 supplies an approximation guarantee, not a complexity result; this case cannot claim that a discrete hardness barrier disappears. Its positive claim is more modest: the paper’s strategic facility-location analysis has a coherent high-multiplicity formulation whose aggregate geometry and \(O(1+1/c^2)\) robustness guarantee should persist.

The obvious follow-up is the paper’s general-metric robustness theorem, with the weaker \(O(1+1/c^3)\) bound, using the same mass model without strict convexity. Further questions concern type splitting, misspecified \(\Delta\), polynomial-time exact equilibrium computation, and finite-\(N\) approximation errors.

The case AGAINST (opponent, writing after the proponent)

The proponent has identified a legitimate high-multiplicity encoding of the aggregate facility-location objective, but not a nondegenerate continuization of the paper’s strategic result.

For rational masses \(\mu_t=n_t/N\), the proposed lottery is indeed exactly the lottery obtained when \(n_t\) identical agents report the same location. That establishes that repeated location types are sensible. It does not, however, preserve the equilibrium notion. In the paper, a unilateral agent controls one positive-probability term \(1/(d_i+\Delta)\). In a nonatomic population, one individual has measure zero and changing their report does not change the induced distribution \(\pi_r\). Every report is therefore payoff-equivalent: the pure-equilibrium condition becomes vacuous, and arbitrary aggregate report profiles can be equilibria. The shortest-path dominance in Claim 3.3 disappears as a strategic statement, and the PNE theorem becomes degenerate rather than informative.

The proposed “mass-PNE” repairs this only by changing the players. A type is now a coordinated bloc that can move its entire mass at once. That is a finite weighted-player game with \(\tau\) strategic actors, not the high-multiplicity limit of the paper’s \(N\) individual agents. In the replicated finite election, one member of a type may deviate alone; the whole cohort cannot be assumed to coordinate. Conversely, if districts or neighbourhood associations are made the strategic actors, the residents are merely data behind those actors. This can be a reasonable new model, but it is not a population continuization of the paper’s agent-level game.

The strongest possible repair does not help much. One could define deviations by positive-measure coalitions, or explicitly make each type a representative bloc. But then one must choose a new coalition-equilibrium concept and specify whose objective determines a deviation. The paper’s Claim 3.3, Kakutani argument, and Theorem 4.3 do not answer those questions. Their proofs may well extend algebraically after replacing sums by weighted sums, but that would establish a new weighted coalition game, not preserve the strategic object being mirrored.

There is also no computational anchor here. Theorem 4.3 is a performance bound, not a complexity theorem, algorithm, separation problem, or optimization classification. Claim 3.3 and the PNE-existence theorem are likewise structural and existential. The proposed “approximate equilibrium computation” is not defined in the paper, and finite-dimensionality does not imply an algorithm: Kakutani supplies existence, not a procedure, while the metric-space input and encoding model are unspecified. The continuous facility location space was already present in the paper; adding finitely many explicit masses introduces no new mass-transfer, high-multiplicity, or column-generation problem.

The general-metric robustness theorem has the same defect. Replacing the \(O(1+1/c^2)\) bound by \(O(1+1/c^3)\) changes the geometric inequality, not the population or computational structure. Lemma 4.1 is only a cited supporting approximation bound and cannot serve as an independent anchor.

So the positive case shows that a weighted, cohort-controlled variant can be formulated and perhaps reanalysed. It does not show a worthwhile ChoCo mirror of this paper: the literal continuum has vacuous individual incentives, while the nonvacuous repair is a different finite weighted game with no named computational question. The honest weakness in this negative case is that a programme willing to study coordinated population blocs could still find that variant useful; what fails is its claim to be the continuous-population continuation of the paper’s strategic facility-location results.

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.