REVIEW 4 major objections 5 minor 3 references
Designing Optimal Mechanisms to Locate Facilities with Insufficient Capacity for Bayesian Agents
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Optimal facility placement for capacity-constrained agents is a Wasserstein transport problem, and the best truthful mechanism is the quantile of the transport-cost minimizer.
desk verdict The OT connection is promising, but the paper's Theorem 5 derivative identity is false, so the numerical routine and several proofs are not reliable as posted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the pair consisting of the radius function $R_{\mu,q}(y)$, the unique radius for which the interval $[y-R, y+R]$ has $\mu$-measure $q$, and the Wasserstein distance $W_1(\mu, q\delta_y)$ between a probability measure and a measure of total mass $q$. The radius function identifies which agents are served in the limit, and the transport distance turns the served-set identity into a cost-minimization problem. The bridge identity $\mathrm{SW} = q - W_1(\mu_{\vec{x}}, q\delta_y)$ connects the discrete game to optimal transport, and the derivative formula $W'(y) = 2R_{\mu,q}(y)R'_{\mu,q}(y) - \Delta_\mu(y)$ reduces the optimal mechanism to a one-dimensional root-finding problem for a wide class of distributions.
What would settle it
Simulate $n=10^5$ agents from an asymmetric distribution such as $\text{Beta}(6,2)$, compute the expected social welfare of the percentile mechanism $p=F_\mu(\bar{y})$ for a few capacities $q$, and compare it with $q - W_1(\mu, q\delta_{\bar{y}})$ computed directly from equation (2); if the gap does not shrink to numerical precision, Theorem 3 and the optimality claim fail.
Extended reading notes
Core claim
The central discovery is that the capacitated facility location problem with scarce resources, in the Bayesian large-population limit, is an optimal transport problem. For a single facility of capacity $q$, the paper proves the identity $\mathrm{SW} = q - W_1(\mu_{\vec{x}}, q\delta_y)$ for finite samples and the limit $\lim_{n\to\infty} \mathbb{E}[\mathrm{SW}] = q - W_1(\mu, q\delta_y)$, where $W_1$ is computed with transportation plans whose second marginal stochastically dominates the target. The radius function $R_{\mu,q}(y)$ marks the served interval, so the optimization reduces to minimizing $W(y) = \int_{y-R(y)}^{y+R(y)} |x-y|\,d\mu$. Theorem 4 establishes that this minimization always has a solution $\bar{y}$ and that the percentile mechanism with $p = F_\mu(\bar{y})$ is optimal as $n\to\infty$; the same argument provides a derivative formula that turns the search into root-finding. For two facilities, the paper gives a necessary and sufficient condition for an equilibrium-stable optimal percentile mechanism to exist, shows that no such mechanism exists when total capacity is at least $2/3$ for monotone or single-peaked distributions, and supplies a $\delta$-accurate search routine otherwise.
Load-bearing premise
The proof relies on treating the transport cost $W_1(\mu, q\delta_y)$ between a probability measure and a measure of total mass $q$ as an ordinary distance, specifically using the triangle inequality, even though the paper does not prove that this unbalanced transport cost satisfies the metric axioms.
Editorial extensions
If this is right
- For any absolutely continuous distribution and any capacity $q<1$, a truthful percentile mechanism achieves the optimal expected social welfare in the $n\to\infty$ limit, so designers can tailor facility placement to the known population distribution rather than rely on worst-case rules.
- For monotone densities the optimal percentile is $q/2$, for symmetric single-peaked distributions it is the median, and for symmetric or asymmetric single-dipped distributions it is $q/2$ or $(1-q)/2$, giving closed-form or immediate root-finding solutions.
- When two facilities are placed, optimality and equilibrium stability conflict once the total capacity reaches $2/3$: no equilibrium-stable percentile mechanism can be optimal, and the conflict also rules out all monotone and single-peaked distributions.
- In the remaining two-facility cases, the proposed search routine returns a mechanism whose asymptotic social welfare is within $\delta$ of the best equilibrium-stable mechanism, for any specified tolerance $\delta$.
- The same transport-based percentile recipes apply when agents are not identically distributed, by replacing each agent's law with the mixture distribution $\bar{\mu} = \int_\Theta \mu(\cdot|\theta)\,d\eta$.
Reading between the lines
- Beyond the paper, the optimal one-facility percentile can be read as a quantile-spacing condition: it is the $y$ where the capacity-$q$ interval is balanced against the local density, which for asymmetric distributions is computable directly from the quantile function.
- The two-facility threshold $q_1+q_2 \ge 2/3$ suggests a capacity phase transition for stability versus optimality that may generalize to more facilities, a direction the paper does not explore.
- The unbalanced transport formulation could extend to concave utility decay or tiered capacities, but the served-set geometry would no longer be an interval, so the radius-function argument would need a different basis.
- One could test whether the mechanism remains near-optimal for small $n$ on distributions outside the beta family, such as truncated log-normals; the paper's experiments do not cover this.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a Bayesian version of the capacitated facility location problem with scarce resources (FLPSR) on the line. Agents' types are independent and identically distributed (or conditionally so) draws from a known distribution; after facilities are placed, agents compete in a first-come-first-served game. The paper's central claim is that, for one facility, any absolutely continuous distribution μ and capacity q, the limiting expected social welfare equals q minus W1(μ, qδ_y), and the optimal percentile mechanism is obtained by minimizing W(y)=∫_{y−R(y)}^{y+R(y)} |x−y| dμ, with existence asserted in Theorem 4. The paper then characterizes the optimum for monotone, symmetric/asymmetric single-peaked, and single-dipped distributions, and extends the approach to two facilities under an equilibrium-stability constraint. Numerical experiments with Beta distributions and non-identically distributed agents are reported.
Significance. The proposed optimal-transport connection is natural and potentially useful: it turns a mechanism-design problem into a deterministic optimization over facility positions and yields parameter-free, distribution-tuned mechanisms. The one-facility existence result and the monotone and symmetric single-dipped characterizations are clean and, if repaired, would constitute a genuine contribution to Bayesian facility location. The paper also provides extensive finite-n experiments showing approximation ratios close to 1 and O(1/sqrt(n)) convergence. However, the current version contains two load-bearing mathematical errors (the definition and metric use of W1 for measures of unequal total mass, and the derivative identity in Theorem 5) and an incorrect non-i.i.d. limit formula, so the published claims are not yet supported.
major comments (4)
- [Section 2, Eq. (2), and Theorem 3] Equation (2) defines W1(μ,ν) using plans whose second marginal "stochastically dominates ν," but this is not the standard definition of a transportation plan, and it does not make W1(μ, qδ_y) a metric on measures of unequal total mass. The proof of Theorem 3 in Appendix A applies the triangle inequality W1(μ, qδ_y) ≤ W1(μ, μ_x) + W1(μ_x, qδ_y) and cites [Bobkov and Ledoux] for E[W1(μ, μ_x)] → 0; both steps presuppose an unbalanced Wasserstein distance with a proven triangle inequality. As written, the derivation of the asymptotic formula (4) is incomplete.
- [Section 3.2, Theorem 5 (Eq. (7))] The derivative formula (7) is false. For μ = Uniform[0,1], q = 0.5, y = 0.1, one has R = 0.4, R' = -1, and Δ = 0.3, so (7) gives W' = -1.1, whereas direct differentiation of W(y) = ∫_0^{0.5} |x−y| dx gives W'(0.1) = -0.3. The endpoint terms cancel because differentiating F(y+R) − F(y−R) = q yields f(y+R)(1+R') = f(y−R)(1−R'), so the correct interior identity is W'(y) = −Δ(y), not 2RR' − Δ. Since Section 3.2.2 instructs the reader to locate zeros of W' by root finding and Tables 1–2 report the resulting percentiles for asymmetric single-peaked and single-dipped distributions, the numerical routine and the reported optima are not justified as written.
- [Section 3.1, Lemma 1 and Theorems 6–8] The proofs of Lemma 1, Theorem 6, and Theorem 8 use the sign of W' obtained from Eq. (7), for instance "W' is negative since Δ<0, R'=-1, and R≥0" in the proof of Lemma 1. Since Eq. (7) is false, those sign arguments are not valid; the stated characterizations may still be true, but they need proofs that avoid the erroneous derivative identity.
- [Section 3.3, Theorem 9] The claimed limit in Theorem 9, lim E[SW] = q(1 − W1(μbar, qδ_y)), is inconsistent with Theorem 3 and with the preceding display in Section 3.3, which writes E[SW] = ∫|x−y| dμbar and omits both the capacity q and the utility offset 1. The same transportation argument that gives (4) yields q − W1(μbar, qδ_y) as the limit, not q(1 − W1(μbar, qδ_y)). The non-identically-distributed extension is therefore stated incorrectly, although the idea of replacing the average empirical distribution by μbar is a reasonable route to repair it.
minor comments (5)
- [Theorem 1] In the displayed derivative formula for R_{μ,q}, the denominator in the "otherwise" case prints fμ(y+R)+fμ(y+R); it should be fμ(y+R)+fμ(y−R).
- [Table 1 and Section 5.1] For m = 2, the reported vectors are called "optimal percentile vectors," but Corollary 2 states that no ES mechanism is optimal for single-peaked distributions; the text should clarify that the table reports best ES mechanisms rather than unconstrained optima.
- [Figure 2 caption] The caption labels the central panel as the Beta distribution B(6,6), while the surrounding text describes it as B(6,2); the caption and the text should be harmonized.
- [Proof of Theorem 7] The proof of Theorem 7 is not complete: after the overlap case, the argument jumps to an inequality involving absolute values that is not shown to contradict the assumed minimality of R_{μ,q}, and the asserted uniqueness of the minimum at the median is not fully proved.
- [Throughout] There are numerous spelling errors (e.g., "desgin," "mechainism," "Equibrlium") that should be corrected before publication.
Circularity Check
No significant circularity: the optimal mechanism is the minimizer of an in-paper functional, not a fitted or self-cited output.
full rationale
The derivation chain is self-contained in the relevant sense. W(y) is defined from the radius function in (3), the asymptotic SW identity (4) is obtained from the q-nearest-agent characterization of the FCFS equilibrium (Theorem 2), and the optimal percentile p=F_mu(bar y) is a reparametrization of the minimizer of W, so no parameter is fitted to data it later predicts. Self-citations to Auricchio et al. (2024b,d) and Auricchio and Zhang (2024) supply prior published background facts (truthfulness/ES conditions and a derivative technique); those facts are not the output of the present derivation and Theorem 4 does not reduce to them. The proof of Theorem 5 also delegates the A-term to Auricchio and Zhang (2024), an omitted in-paper proof, but the cited argument is an independent, checkable mathematical step rather than an assumption of the target result. The non-standard W1 definition in (2) and the likely incorrect derivative identity (7) are mathematical correctness risks, not circularity: they do not make the conclusion equivalent to the input by construction. No fitted input is renamed as a prediction and no uniqueness theorem is imported from the authors' prior work, so no circular step is exhibited.
Assumptions & free parameters
assumptions (5)
- domain assumption Agents' distribution μ is absolutely continuous with continuous density on [0,1]
- domain assumption The FCFS game for one facility accommodates the tqn agents closest to y, and for m≥2 every agent commits to a facility and a pure Nash equilibrium exists
- standard math Empirical measures converge in W1: lim E[W1(μ,μ_X)]=0
- standard math Every truthful mechanism for m=1 is a percentile mechanism, and percentile mechanisms are truthful
- domain assumption In the non-i.d. extension, agent parameters θ_i are i.i.d. draws from η
Cite this review
Pith. "Pith review of Designing Optimal Mechanisms to Locate Facilities with Insufficient Capacity for Bayesian Agents." pith.science (2026). https://pith.science/paper/MPSJKTWN
@misc{pith2026241200563,
author = {Pith},
title = {Pith review of: Designing Optimal Mechanisms to Locate Facilities with Insufficient Capacity for Bayesian Agents},
year = {2026},
howpublished = {\url{https://pith.science/paper/MPSJKTWN}},
note = {Machine review of arXiv:2412.00563}
}
read the original abstract
In this paper, we study the Facility Location Problem with Scarce Resources (FLPSR) under the assumption that agents' type follow a probability distribution. In the FLPSR, the objective is to identify the optimal locations for one or more capacitated facilities to maximize Social Welfare (SW), defined as the sum of the utilities of all agents. The total capacity of the facilities, however, is not enough to accommodate all the agents, who thus compete in a First-Come-First-Served game to determine whether they get accommodated and what their utility is. The main contribution of this paper ties Optimal Transport theory to the problem of determining the best truthful mechanism for the FLPSR tailored to the agents' type distributions. Owing to this connection, we identify the mechanism that maximizes the expected SW as the number of agents goes to infinity. For the case of a single facility, we show that an optimal mechanism always exists. We examine three classes of probability distributions and characterize the optimal mechanism either analytically represent the optimal mechanism or provide a routine to numerically compute it. We then extend our results to the case in which we have two capacitated facilities to place. While we initially assume that agents are independent and identically distributed, we show that our techniques are applicable to scenarios where agents are not identically distributed. Finally, we validate our findings through several numerical experiments, including: (i) deriving optimal mechanisms for the class of beta distributions, (ii) assessing the Bayesian approximation ratio of these mechanisms for small numbers of agents, and (iii) assessing how quickly the expected SW attained by the mechanism converges to its limit.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[2]
Let ⃗ ypoutq be the output of Algorithm 1. Thus, we infer Wp⃗ yq“ ż BRpy1qpy1q |x´ y1|dµ` ż BRpy2qpy2q |x´ y2|dµ ď ż BRptqptq |x´ y1|dµ` ż BRpsqpsq |x´ y2|dµ ď ż BRptqptq p|x´ t|` δ 2qdµ` ż BRpsqpsq p|x´ s|` δ 2qdµ ď Wpt, sq` δ. By the same argument, we infer that Wpt, sqď Wp⃗ yq` δ, hence|Wpt, sq´ Wp⃗ yq|ď δ. To conclude the thesis, we notice that, by co...
-
[3]
From our hypothesis, we have thatp2´ p1ą 2 3 thus we either have thatp1ď q1 2 or p2ď 1´ q2 2
Without loss of generality, let us assume thaty1ď y2, so that the facility with capacityq1 is located to the left of the facility with capacity q2. From our hypothesis, we have thatp2´ p1ą 2 3 thus we either have thatp1ď q1 2 or p2ď 1´ q2 2 . Let us assume thatp1 ď q1 2 . First notice that, sincefµ is non-null almost everywhere on r0, 1s, there exists anϵ...
-
[2010]
[Auricchio et al.(2019)]Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, and Marco Veneroni
Strategyproof Approximation of the Minimax on Networks.Mathematics of Operations Research 35, 3 (2010), 513–526. [Auricchio et al.(2019)]Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, and Marco Veneroni. 2019. Computing Wasserstein Barycenters via linear programming. InInternational Conference on Integration of Constraint Programming, Artificial ...
arXiv 2010
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.