Equitable Mechanism Design for Facility Location

The proposed high-multiplicity welfare formulations are mathematically plausible and largely faithful to the paper. However, neither cited theorem is a qualifying named computational result: both are approximation guarantees for fixed mechanisms, rather than complexity or algorithmic theorems about an input problem. The programme's computational gate therefore fails even though worthwhile continuous extensions remain possible.

The objection that survived

Theorem 11 is a mechanism-performance theorem, not a qualifying computational result, and the finite-lift incentive semantics additionally introduce a new population-scale convention.

What the mirror covers

The proposed mirrors cover the one-facility Nash-welfare guarantee in Theorem 11 and the two-facility complemented-Gini guarantee in Theorem 7, while leaving the paper's other mechanism bounds, impossibility results, and randomized analyses outside the mirror.

Open questions for a prover

The case FOR (proponent)

This paper admits a strong, fairly direct mirror, although not because it contains an NP-hardness or polynomial-time theorem. Its named anchors are approximation results proved in the paper: chiefly Theorem 11 and Theorem 7.

The natural regime is a large public-service district. There are \(N\) residents but only \(\tau\ll N\) residential types, where type \(t\) is a location \(x_t\in[0,1]\). All residents of a type have the same preferences and utility function; \(\mu_t\) is the fraction of residents at \(x_t\). Thus a rational \(\mu\) is exactly a high-multiplicity electorate after clearing denominators. This could represent many households in a small number of neighbourhoods along a corridor, with one or two clinics, distribution centres, or other facilities to locate.

The facilities remain indivisible point locations, as in the paper. The continuity is in the population, not in the outcome space. For one facility, utility is \(u_t(y)=1-|x_t-y|\); for two facilities, it is \(u_t(y_1,y_2)=1-\min\{|x_t-y_1|,|x_t-y_2|\}\).

There is one strategic subtlety. Literal atomlessness makes unilateral manipulation vacuous: one individual has zero effect on \(\mu\). I would therefore define strategyproofness by finite-lift semantics. If \(\mu\) is realised by \(N\) clones and an agent of type \(a\) reports \(b\), the mechanism is evaluated on \(\mu+(e_b-e_a)/N\), and the true agent must not obtain smaller distance. This is exactly the paper’s individual strategyproofness after aggregation; it is not a replacement by coalition strategyproofness.

The strongest anchor is Theorem 11, proved in this paper. It says that LEFTMOST and MEDIAN have unbounded approximation ratio for Nash welfare, while MIDORNEAREST gives a \(2\)-approximation.

The corresponding problem is:

\(\textsf{Continuous-One-Facility-Nash}\). An instance consists of a finite rational type set \(T=\{x_1,\ldots,x_\tau\}\subseteq[0,1]\), rational masses \(\mu_t\), and one of the paper’s mechanisms. Define continuous Nash welfare by \(W_\mu(y)=\prod_t u_t(y)^{\mu_t}=\exp(\sum_t\mu_t\log u_t(y))\), with value \(0\) whenever a positive-mass type receives utility \(0\). The task is to output the mechanism’s location \(F(\mu)\), compute \(W_\mu^*=\max_{y\in[0,1]}W_\mu(y)\) to accuracy \(2^{-q}\), and return a certified approximation ratio \(W_\mu^*/W_\mu(F(\mu))\). The decision version asks whether this ratio is at most a supplied rational \(\rho\).

For MIDORNEAREST, the continuous rule is \(r(\mu)\) if all support lies left of \(1/2\), \(1/2\) if the support straddles \(1/2\), and \(\ell(\mu)\) if all support lies right of \(1/2\), where \(\ell(\mu)\) and \(r(\mu)\) are the extreme occupied locations. A solution is therefore a facility location, an approximate optimum, and a certified ratio.

This is an exact high-multiplicity translation. If \(\mu_t=n_t/N\), then \(W_\mu(y)\) is precisely the discrete \(N\)th root of the product of the \(N\) agents’ utilities. The mechanism output is also identical. Hence Theorem 11 transfers without changing its semantics. MIDORNEAREST always gives every type utility at least \(1/2\), so \(W_\mu(F(\mu))\ge 1/2\) and the ratio is at most \(2\). The bound remains tight: for \(\mu_\varepsilon=(1-\varepsilon)\delta_0+\varepsilon\delta_{1/2}\), the mechanism chooses \(1/2\), while the optimum approaches \(0\), giving ratio \(2^{1-2\varepsilon}\to2\). LEFTMOST and MEDIAN remain unbounded on \(\tfrac12\delta_0+\tfrac12\delta_1\).

I expect this continuous problem to be Class A. After sorting the types, \(\log W_\mu(y)\) is concave on each interval between consecutive locations, so the optimum can be found by scanning \(\tau+1\) one-dimensional pieces and solving their derivative conditions to the requested precision. The further design question is whether some other clone-strategyproof rule beats the \(2\) bound, and how the answer changes with restricted phantom measures or randomized mechanisms.

The second anchor is Theorem 7, also proved in this paper. It states that ENDPOINT\(_\gamma\) is strategyproof and gives an approximation ratio between \(15/14\) and \(35/29\) for the optimal complemented Gini index, with the best parameter \(\gamma=1/4\) yielding \(15/14\).

Define \(E_\mu(y_1,y_2)=1-G_\mu(y_1,y_2)\), where \(G_\mu(y_1,y_2)=\frac{\sum_{s,t}\mu_s\mu_t|u_s-u_t|}{2\sum_t\mu_tu_t}\). The problem is:

\(\textsf{Continuous-Two-Facility-Complemented-Gini}\). An instance consists of rational \(T\), rational \(\mu\), \(\gamma\in[0,1/2]\), and a precision parameter. Let \(\ell\) and \(r\) be the extreme occupied locations and define \(F_\gamma(\mu)\) by \(y_L=\min(\max(\ell,\gamma),r)\) and \(y_R=\max(\ell,\min(1-\gamma,r))\). The task is to output these two facility locations, compute \(E_\mu^*=\max_{y_1,y_2}E_\mu(y_1,y_2)\), and certify the ratio \(E_\mu^*/E_\mu(F_\gamma(\mu))\). The associated design question is to determine the best worst-case \(\alpha_\infty(\gamma)\) over all finite-support societies.

Again, clearing denominators recovers exactly the paper’s finite electorate: the weighted Gini expression is the discrete Gini expression, and ENDPOINT\(_\gamma\) returns the same facilities. Therefore the \(15/14\) guarantee at \(\gamma=1/4\) transfers directly to rational continuous societies, as do the paper’s finite lower-bound examples. Theorem 8’s \(30/29\) impossibility lower bound for deterministic strategyproof mechanisms would likewise transfer as a follow-up question, leaving the same small gap between the known upper and lower bounds.

For fixed two-facility instances, I expect the computational evaluation problem to be Class A. The mechanism is computable from the two extremes, the Gini value takes \(O(\tau^2)\) pairwise terms, and the optimal benchmark can plausibly be found by enumerating the polynomial-size arrangement of facility-assignment and utility-order regions; within each region the objective is a linear-fractional function. If the number of facilities becomes part of the input, assignment combinatorics may introduce a different, potentially harder problem.

The weakest point is undeniably incentive semantics. Without the finite-lift definition, the continuum makes strategyproofness empty. A referee could reasonably say that the clone-SP requirement is an additional modelling convention. The answer is that it is precisely the rational-clone bridge: every rational society has a finite realisation, and the mechanism must remain strategyproof on every such realisation. The other weakness is regime-specificity: a committee of seven uniquely located agents is not a sensible limit object. The mirror is persuasive only for large populations clustered into repeated location types.

My positive verdict is therefore narrow but strong: Theorems 11 and 7 have faithful high-multiplicity mirrors, with the same mechanisms, utilities, strategic deviations, and approximation benchmarks. Their continuous versions are computationally meaningful Class A questions, while the best strategyproof mechanism and the two-facility Gini gap generate genuine further problems. I would not claim that the whole paper continuizes, nor that the paper itself already contains the resulting complexity classification.

The case AGAINST (opponent, writing after the proponent)

The strongest objection is prior to continuization: neither cited anchor is a qualifying computational result under ChoCo’s stated gate. Theorem 11 and Theorem 7 are performance guarantees for explicitly given closed-form mechanisms. They do not assert the complexity of an input optimization problem, nor give an exact, approximation, or parameterized algorithm for one. Defining a new task that computes \(W_\mu^*\) or \(E_\mu^*\), then thresholding its ratio, is precisely wrapping a newly proposed optimization problem around a theorem about mechanism performance. It does not make that theorem a computational anchor.

Theorem 11 is the better of the two, but the proposed mirror also quietly separates the welfare statement from the strategic statement that makes the paper’s result meaningful. The weighted Nash welfare
\[ W_\mu(y)=\prod_t u_t(y)^{\mu_t} \]
is indeed a legitimate high-multiplicity functional: clearing denominators recovers the discrete product up to the \(N\)-th-root normalization. I would not object to that part. A large district with repeated location types is a sensible regime.

What does not survive is the claim that strategyproofness has been preserved “exactly.” In an actual atomless society, one resident’s report leaves \(\mu\) unchanged, so every aggregate mechanism is trivially strategyproof. The proposed finite-lift repairs this by reintroducing an \(N\)-dependent perturbation \((e_b-e_a)/N\). That is a coherent extension, but it is not a property of \(F(\mu)\) alone: it is a family of finite economies indexed by a hidden population scale. Replacing it with a positive-mass deviation gives coalition strategyproofness, which is a different incentive notion. Thus the continuous welfare calculation is faithful, while the paper’s central strategic quantifier is either vacuous or changed.

Theorem 11’s actual claim is also a worst-case statement over all finite profiles. The proponent’s task computes a per-instance ratio. A closer continuous problem would optimize
\[ \sup_{\mu}\frac{W_\mu^*}{W_\mu(F(\mu))} \]
or search for the best clone-compatible strategyproof mechanism over the whole mass simplex. That could be a legitimate new project, but it is not the named result in the paper. For the finite-support, one-facility version, the benchmark is a small one-dimensional concave optimization, so the proposed formulation supplies no new complexity question beyond a weighted restatement.

Theorem 7 has the same source problem. The weighted expression
\[ G_\mu(y_1,y_2) =\frac{\sum_{s,t}\mu_s\mu_t|u_s-u_t|} {2\sum_t\mu_tu_t} \]
does reproduce the finite Gini index under replication, and ENDPOINT\(_\gamma\) is computable from the extreme occupied types. That makes it a valid high-multiplicity welfare extension, but not a computational theorem from the paper. The claimed transfer of Theorem 8 is weaker still: its lower bound depends on one named agent moving from \(3/4\) to \(1\). In the continuum that move has zero aggregate effect; under finite-lift semantics it is an \(N\)-scale deviation; under positive-mass semantics it is a coordinated bloc deviation. The impossibility proof therefore does not transfer without a new strategic theorem.

One could repair the proposal by explicitly studying clone-stable mechanisms, or by asking for the worst-case ratio over all rational mass vectors, arbitrary numbers of facilities, or oracle-described location distributions. Those may be worthwhile ChoCo problems. But they are new mechanism-design and representation questions, not mirrors of Theorems 7 or 11. If the population is kept finite-type and the number of facilities fixed, the remaining optimization is a routine weighted facility-location calculation; if the model is made richer, its difficulty comes from the added facility or distribution representation rather than from the paper’s population structure.

The honest limitation of this negative case is that the welfare portions are not nonsensical. Repeated-location districts make high multiplicity plausible, and the weighted Nash and Gini objectives are mathematically faithful. Consequently, I cannot honestly prove the universal claim that no worthwhile extension exists. My red verdict is narrower but decisive under the programme’s screening rule: the proponent has not supplied a qualifying named computational anchor, and the only way to retain the paper’s strategyproofness is to add a new clone-scale or coalition semantics. If ChoCo admits mechanism-approximation theorems as anchors anyway, Theorem 11 survives as a modest Class-A extension, so the claimed universal negative would be too strong.

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.