Extended Ranking Mechanisms for the m -Capacitated Facility Location Problem in Bayesian Mechanism Design

Bit (a) fails: none of the cited theorems asserts complexity or an algorithm for a named computational problem as required. The proposed finite-type quantile and mass-flow formulations are recognizable and potentially worthwhile extensions, but they cannot repair the missing computational anchor. Theorem 5.3 is close, since its formula is algorithmically usable, so the margin is narrow rather than clear.

The objection that survived

The decisive objection is that no named result meets bit (a), even though a finite-type population version of the facility-location problem is plausible.

What the mirror covers

The proposed extension covers ERM feasibility and truthfulness, the quantile/Wasserstein limit, and the special \(m=2\), \(U[0,1]\) optimum; it leaves the general optimal-ERM problem, EEM comparisons, experiments, and other mechanisms untouched.

Open questions for a prover

The case FOR (proponent)

The strongest honest case is a narrow Class-A mirror for the ERM design problem. One qualification matters first: the paper contains no named theorem stating NP-hardness, membership in \(P\), W[1]-hardness, or FPT. Thus, under a strictly complexity-labelled anchor rule, it fails the formal gate. Under the broader reading that an exact algorithmic characterization counts, there is a credible positive case.

The population mirror is a capacitated location market with many interchangeable residents. A type \(t\) is a complete location-cost type: all agents of type \(t\) have the same position \(a_t\in\mathbb Q\) and incur cost \(|a_t-y|\) at facility location \(y\). Its mass \(\mu_t\) is the fraction of the population of that type. Facilities have capacity fractions \(q_j\), so capacities scale with the population size. An aggregate assignment is a flow \(z_{tj}\) satisfying \(\sum_jz_{tj}=\mu_t\) and \(\sum_tz_{tj}\le q_j\). This is not fractionalizing residents: for rational masses, clearing denominators produces an ordinary clone population in which every resident is assigned integrally.

For a mass distribution \(\mu\), let \(Q_\mu(p)\) be its quantile function. An ERM with parameters \((\pi,\mathbf p)\) places facility \(j\) at \(Q_\mu(p_j)\), gives it capacity \(q_{\pi(j)}\), and assigns population mass to its nearest facility. Its objective is normalized social cost, or equivalently the one-dimensional Wasserstein transport cost. This is exactly the limit suggested by the paper’s order-statistic mechanism and by Lemma 4.1 and Theorem 4.2, both proved in the paper. The latter identifies the limiting Bayesian approximation ratio with a ratio of Wasserstein objectives rather than merely motivating an analogy.

My strongest direct anchor is the paired result Theorem 3.1 and Theorem 3.2, both proved here. They give an exact feasibility characterization and show that every feasible ERM is truthful.

The corresponding problem is Feasible-Truthful-ERM\(_\infty\). An instance consists of rational \(m\), capacity fractions \(\mathbf q\), and strictly increasing rational quantiles \(0<p_1<\cdots<p_m<1\). Define \(r_1=p_2\), \(r_2=p_3-p_1\), through \(r_{m-1}=p_m-p_{m-2}\), and \(r_m=1-p_{m-1}\). The question is whether there is a permutation \(\pi\) such that the quantile ERM is feasible for every finite type-mass society, and, if so, to output such a \(\pi\). A solution must satisfy \(q_{\pi(j)}\ge r_j\) for every \(j\); Theorem 3.2 then certifies truthfulness. The problem is expected to be in \(P\): it is a threshold matching problem, solvable by sorting or bipartite matching, and the resulting mechanism acts on a society by computing weighted quantiles and a nearest-facility mass assignment.

This is recognisably their problem, not a softened replacement. Their mechanism is already parameterized by rank fractions \(p_j\), percentage capacities \(q_j\), and nearest-facility assignment. The mirror only replaces order statistics by population quantiles and individual counts by mass. The natural regime is a large recurring population of residents from a bounded collection of repeated neighbourhood or service-location types; \(N\) grows while \(\tau\), the number of distinct location-cost types, remains small.

The second anchor is Theorem 5.3, proved here. It gives an explicit optimum for two facilities and a uniform population. The corresponding problem is Optimal-Uniform-2-ERM\(_\infty\). Its input is rational \(q_1\ge q_2\), with \(q_1+q_2\ge1\), and the society \(\mu=U[0,1]\). The output is a feasible \((\pi,\mathbf p)\) minimizing the limiting Bayesian approximation ratio. With \(\pi=I_d\), feasibility gives \(p_2\le q_1\) and \(1-p_1\le q_2\), and the mechanism cost is

\(W(p_1,p_2)=\frac{p_1^2}{2}+\frac{(1-p_2)^2}{2}+\frac{(p_2-p_1)^2}{4}\).

Theorem 5.3 gives the exact solution:

\( \mathbf p=(0.25,0.75) \) if \(q_2\ge0.75\);

\( \mathbf p=(1-q_2,q_1) \) if \(3q_2-2-q_1\le0\);

\( \mathbf p=(1-q_2,1-\frac{q_2}{3})\) otherwise.

Thus this mirror is also expected to be in \(P\): the answer is obtained by a constant number of rational comparisons and arithmetic operations. The scenario is a large stream of residents distributed along a corridor, with two public facilities whose capacities are fixed fractions of the population. The uniform density is the paper’s own scenario, so author recognition is especially strong, although this particular anchor is better described as a continuous-density extension than as a finite-\(\tau\) clone limit.

The expected classification is therefore Class A for both stated problems. The general problem suggested by Theorem 4.2 and Theorem 5.1—optimizing \((\pi,\mathbf p)\) for arbitrary \(m\), capacity vector, and succinctly represented \(\mu\)—is an open follow-up. It may remain tractable through one-dimensional transport and dynamic programming, or it may develop continuum-specific difficulty through the capacity permutation and quantile constraints. I would not claim either result without a separate analysis.

The weakest point is that the paper’s formal Bayesian model samples individually named agents from an absolutely continuous distribution, whereas the ChoCo mirror wants a society with repeated complete types. Theorem 4.2 also assumes a regular density, so an exact finite-atomic extension requires care with quantile ties and medians. Finally, individual truthfulness becomes vacuous in a genuinely atomless population; the meaningful extension must use rational clone semantics or positive-mass coalition deviations. These are real extension obligations.

They do not destroy the case because the direct feasibility anchor has exact rational-clone semantics, and the paper itself supplies the limiting quantile/Wasserstein dictionary. The proposed mirror should cover only Theorems 3.1–3.2 and 5.3, with Theorem 4.2 as the bridge—not the paper’s experiments, the general existence statement in Theorem 5.1, or unrelated mechanism comparisons.

The case AGAINST (opponent, writing after the proponent)

The negative case starts at the source gate: this paper has no named computational result. Theorem 3.1 is a feasibility characterization for a mechanism family, and Theorem 3.2 derives truthfulness from it. Neither states the complexity of a computational problem, nor gives an algorithmic result in the ChoCo sense. The proponent’s Feasible-Truthful-ERM\(_\infty\) is manufactured by wrapping the displayed inequalities in a decision problem. Once \(\mathbf p\) and \(\mathbf q\) are given, the society \(\mu\) is irrelevant: feasibility is decided by checking whether capacities can be matched to the fixed thresholds
\[ p_2,\ p_3-p_1,\ \ldots,\ p_m-p_{m-2},\ 1-p_{m-1}. \]
That is a sorting or matching implementation of the theorem itself, not a population-continuized computational question.

The proposed mass assignment does not repair this. For rational masses, clearing denominators simply produces a finite clone electorate to which the paper’s finite-\(n\) mechanism applies. No computational difficulty has moved from individual agents into a distribution; the distribution is absent from the predicate. If instead one asks for the best \((\pi,\mathbf p)\) for a given mass distribution, that is a new optimization problem closer to Theorem 5.1, not a mirror of Theorems 3.1–3.2.

There is also a semantic mismatch around truthfulness. In an atomless population, one individual has zero mass and cannot alter any quantile or facility location. Truthfulness therefore loses the pivotal order-statistic effect that drives the finite theorem. Retaining finite rational clones gives a family of discrete instances, while allowing positive-mass deviations replaces individual strategyproofness by a coalition notion. Both are legitimate research directions, but neither is the paper’s stated Bayesian incentive problem.

Theorem 5.3 does not rescue the case. It is an explicit constant-dimensional calculation for \(m=2\) and the fixed distribution \(U[0,1]\), not a computational complexity or algorithmic result. Its formula is already the paper’s own population-limit analysis rewritten as a continuous optimization problem. There is no encoded society, growing type multiplicity, or nontrivial input dimension for ChoCo to analyze.

The stronger finite-type version also breaks the claimed anchor. The paper’s \(U[0,1]\) model is atomless: under its i.i.d. absolutely continuous law, distinct agents have distinct locations with probability \(1\). Thus the paper’s large-\(n\) regime is not high multiplicity in the ChoCo sense. Replacing it by finitely many location types produces an atomic distribution, outside the hypotheses used for Theorem 4.2 and the derivation of Theorem 5.3. Restoring a density requires infinitely many location types; retaining finite types requires a new theorem. There is no type-space choice that preserves both the paper’s exact result and a nontrivial fixed-type high-multiplicity interpretation.

Theorem 4.2 is only an analytic bridge. It proves convergence of empirical measures and order statistics to quantiles and Wasserstein objectives. It does not formulate or solve a computational problem, and for the paper’s continuous laws it describes exchangeable sampling rather than repeated complete types. Wasserstein notation does not itself supply an algorithmic anchor.

A broader project—optimizing ERM parameters for arbitrary rational finite-support societies—could be sensible. But it would be an extension or re-modelling, requiring new incentive semantics, new treatment of atomic quantiles and ties, and new complexity results. The paper does not provide the named computational anchor needed to justify it. Under the programme’s rules, neither proposed anchor survives.

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.