Strategy Proof Mechanisms for Facility Location with Capacity Limits

Every numbered result is an axiomatic characterization, construction, or impossibility theorem; none asserts a complexity classification, algorithm, or approximation guarantee. The proposed population models are plausible research extensions, but they do not supply a qualifying computational anchor and alter the paper's deterministic unilateral-strategy-proofness semantics. Since bit (a) fails, the correct grade is red.

The objection that survived

The proposed instance-level output \(M(\mu)\) confuses evaluating a mechanism with synthesizing a globally represented mechanism, while positive-mass coalition strategy-proofness and fractional allocations change the paper's semantics.

What the mirror covers

The proposed mirrors concern Theorems 1, 3, and 4; Theorem 2 and the auxiliary minimality examples are left untouched, and none of the covered results is computational.

Open questions for a prover

The case FOR (proponent)

Strictly, this paper has no qualifying computational-complexity anchor. Theorem 1, Theorem 2, Theorem 3, and Theorem 4 are all proved here, but they are characterization and impossibility theorems about axiomatic mechanism design. None asserts NP-hardness, membership in \( \mathrm{P} \), fixed-parameter tractability, or any other complexity classification. Thus this paper cannot support a genuine ChoCo Class A/B/C verdict without importing a new result.

The strongest honest positive case is nevertheless that its central model has a very natural population mirror.

My lead would be a continuous version of Theorem 3, “Unequal-Capacity Continuous Mechanism Existence.” Fix two capacities \(a<b\) with \(a+b=1\), and a finite set of location types \(T=\{x_1,\ldots,x_\tau\}\subseteq[0,1]\). An instance is a mass vector \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of the population at location \(x_t\). A mechanism must return facility locations \(y_a,y_b\in[0,1]\) and a mass allocation \(z_{t,j}\ge0\) satisfying

\[ \sum_j z_{t,j}=\mu_t, \qquad \sum_t z_{t,j}\le c_j, \]

where \(c_a=a\) and \(c_b=b\). It must be anonymous, Pareto optimal with respect to distance \( |x_t-y_j| \), and, to make strategy-proofness non-vacuous in a continuum, immune to profitable positive-mass coalition misreports. The question is whether such a mechanism exists for every \(\mu\), and, if so, to output one.

This is recognisably the authors’ problem: locations, capacity limits, assignments, distance preferences, anonymity, Pareto optimality, and strategy-proofness are unchanged. Only the empirical counts become population masses. The regime is plausible for millions of residents distributed across a modest number of census locations, municipalities, or neighbourhood types, so \(n\gg\tau\).

Theorem 3’s proof transfers particularly cleanly. For any \(0<\varepsilon<b-a\), consider

\[ \mu(0)=a+\varepsilon, \qquad \mu(1)=b-\varepsilon. \]

This is the normalized analogue of the paper’s profile with \(k+1\) agents at \(0\) and \(k+d-1\) at \(1\). The same anonymity/Pareto argument rules out a mechanism. In the discrete theorem, the exceptional case \(d=1\) exists because there is a smallest positive mass, one agent. In the continuous version, every positive capacity gap permits such an \(\varepsilon\), so the exception disappears. The expected result is therefore an axiomatic impossibility, not a Class A/B/C complexity result.

A second, independent mirror uses Theorem 4, also proved here. For \(m\ge3\) equal-capacity facilities, set each capacity to \(1/m\), and use

\[ \mu(0)=\mu(1/2)=\frac{3}{2m}, \qquad \mu(1)=\frac{m-3}{m}. \]

The first two locations each require two facilities, while the remaining mass exactly fills \(m-3\) facilities at \(1\). Anonymity forces the facilities serving each location to coincide, and then all three relevant facilities must be co-located, contradicting Pareto optimality. This is an especially convincing high-multiplicity mirror because the proof is fundamentally about mass and capacity, not named individuals.

The constructive side is suggested by Theorem 1. With two facilities of capacity \(1/2\), the continuous INNERPOINT candidate takes the lower and upper median quantiles,

\[ q^-=\inf\{x:F_\mu(x)\ge 1/2\}, \qquad q^+=\inf\{x:F_\mu(x)>1/2\}, \]

and assigns half the mass to each facility, splitting a type if necessary. Evaluating this rule requires only sorting the \(\tau\) types and scanning cumulative masses. This is a plausible tractable continuous analogue of INNERPOINT, although Theorem 1 itself does not state a complexity result.

The weakest point is decisive: literal individual strategy-proofness becomes vacuous for an atomless population, since one individual has zero effect on \(\mu\). Positive-mass coalition strategy-proofness repairs that, but it is a strengthened notion absent from the paper. More importantly, the paper does not ask a computational question at all. I would therefore present it as a strong demonstration that the paper’s facility-location model admits a natural, technically illuminating population mirror—not as evidence that the paper itself fills ChoCo’s computational-complexity gap.

The case AGAINST (opponent, writing after the proponent)

The paper should not be green under ChoCo. The proponent’s opening concession is decisive: none of the paper’s four numbered theorems is a computational-complexity result. Theorem 1 is a characterization, Theorem 2 a construction, and Theorems 3 and 4 impossibility results about axioms. There is no computational input/output problem, complexity classification, approximation guarantee, or algorithmic bottleneck to continuize. A continuous mechanism-design paper might be worthwhile, but that is outside the programme’s stated question.

Theorem 3 is not rescued by its attractive high-multiplicity formulation. A population of residents at a finite set of locations is perfectly sensible; the problem is what is being computed. A mechanism is a function over every report distribution, not an outcome for one given \(\mu\). “Given \(\mu\), output a mechanism” is therefore not well-defined: outputting \(M(\mu)\) evaluates a mechanism, while strategy-proofness and Pareto optimality are global properties of \(M\). Producing \(M\) itself requires a representation and a mechanism-synthesis problem that the paper neither defines nor motivates. Any finite representation of that synthesis task would be a new problem, not a computational mirror of Theorem 3.

There is also a substantive mismatch in the proposed mass model. The paper’s anonymity says that agents with the same location must receive the same facility location under every permutation. The proposed flow \(z_{t,j}\) permits one location type to be split between facilities at different locations. That is a fractional or randomized assignment model, not the paper’s deterministic anonymous assignment model. If splitting is allowed, the key inference in Theorem 3—that an over-capacity location forces both facilities to coincide—no longer follows. If splitting is forbidden, the model retains an indivisibility condition that is not natural for the proposed continuous mass flow. A symmetric lottery could repair this, but then Pareto optimality and strategy-proofness become stochastic notions absent from the paper.

The coalition repair has the same problem. Individual strategy-proofness disappears in a continuum because one agent has measure zero and cannot change the distribution. Requiring immunity to positive-mass coalitions is a legitimate new research direction, but it is group strategy-proofness, not a faithful limit of the paper’s unilateral incentive condition. Theorem 3 supplies no result about it.

Theorem 4 depends on exactly the same lost premise. Its contradiction uses “two facilities serve the agents at \(0\), therefore anonymity forces those facilities to be co-located.” Under the proposed fractional mass allocation, the \(0\)-type can receive a common allocation lottery or flow across several differently located facilities, so that implication disappears. Enforcing identical facility locations for every member of a type restores the proof only by choosing the indivisible deterministic semantics in advance. Either choice produces a different axiomatic model, and neither produces a computational question.

Theorem 1 is the strongest positive case, but it still does not qualify. The weighted median/quantile rule is a natural high-multiplicity restatement of INNERPOINT, and its evaluation requires only sorting the \(\tau\) locations and scanning cumulative mass. That is an implementation of an explicit order-statistic formula, not a computational result established or sought by the paper. Asking for a mechanism representation, or asking whether the quantile rule is immune to positive-mass coalitions, again creates a new synthesis or incentive problem.

The high-multiplicity interpretation is therefore plausible, and a broader project on continuous facility-location optimization could certainly be worthwhile. But it would need to add a new objective—social-cost minimization, manipulation, control, or similar—and would no longer mirror any result in this paper. The honest negative conclusion is strong within ChoCo’s scope: the paper offers a natural population model, but no qualifying computational anchor.

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.