{"id":"f09eb404-7bf7-4380-ab3b-1fc1cc727caa","arxiv_id":"2412.00563","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For one scarce facility, the asymptotically optimal truthful mechanism is the quantile that minimizes a Wasserstein-type transport cost; for two facilities, a grid search finds the best equilibrium-stable percentile mechanism.","lead":"This paper designs truthful mechanisms for placing capacity-limited facilities when agents' locations follow a known probability distribution, connecting the problem to optimal transport. It characterizes the asymptotically optimal percentile mechanism for one facility and near-optimal equilibrium-stable mechanisms for two facilities.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's derivative identity (7) is false: for uniform μ, q=0.5, y=0.1 it predicts W'=−1.1, while direct differentiation gives W'=−0.3; the root-finding routine for asymmetric distributions is therefore unreliable.","rationale":"Agree with the CONDITIONAL verdict, but for a reason the reader did not emphasize. The reader's OT-definition concern attacks the proof of Theorem 3; the limit statement is nevertheless true by an order-statistics argument, so that issue is fixable without changing the results. The false derivative identity is an internal mathematical error that is checkable immediately and affects the algorithmic contribution: the bisection/root-finding procedure for finding optimal percentile mechanisms for asymmetric SP and SD distributions is built on it, and the numerical tables are the only evidence for those cases. I do not claim the final classification theorems are false—Theorem 6's conclusion can be recovered by direct monotonicity of −Δ—but as written the proof and the numerical routine are unsupported. Because the paper's central existence result appears salvageable and the error is localized, no stronger verdict than CONDITIONAL is warranted; the reader's conditional acceptance already demands such repair.","tokens_in":32767,"tokens_out":36724,"duration_ms":339123,"concrete_test":"Evaluate both sides of Eq. (7) for μ=Uniform[0,1], q=0.5, y=0.1. Directly, W(y)=∫_0^{0.5}|x−y|dx, so W'(0.1)=−0.3. From Theorem 1, R=0.4, R'=−1, and Δ=F(0.5)+F(−0.1)−2F(0.1)=0.3, so the right-hand side of (7) is 2(0.4)(−1)−0.3=−1.1. This disparity settles that (7) is false. Then recompute an asymmetric Beta entry, e.g., B(6,2) with q=0.5 in Table 2, by minimizing W via direct numerical integration over a fine grid instead of zeroing (7); if the percentiles shift, the published numerical mechanism is not the claimed optimal.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2's computational story stands on identity (7), but (7) is not correct. Differentiating W(y)=∫_{y−R}^{y+R}|x−y|dμ directly and using F(y+R)−F(y−R)=q gives W'(y)=−Δ(y) for interior y, where Δ=F(y+R)+F(y−R)−2F(y); the endpoint terms cancel because differentiating the constant-mass identity forces f(y+R)(1+R')=f(y−R)(1−R'). In the boundary regime y<F^{-1}(q/2), W(y)=∫_0^{F^{-1}(q)}|x−y|dμ, so W'(y)=2F(y)−q. Neither formula agrees with (7). Concrete check: for uniform μ on [0,1], q=0.5, y=0.1, we have R=0.4, R'=−1, Δ=0.3, so (7) gives W'=−1.1, but direct differentiation of W(y)=∫_0^{0.5}|x−y|dx gives W'(0.1)=−0.3. Since Section 3.2.2 instructs the reader to find zeros of W' with a root finder, and Tables 1–2 report the resulting optimal percentiles, a wrong derivative can displace the computed optima for asymmetric SP and SD distributions. The existence theorem for Problem (5) may still be true, but the claimed 'routine to numerically compute' the optimal mechanism is not justified as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":32976,"tokens_out":10023,"duration_ms":98857,"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":[{"comment":"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":"Section 2, Eq. (2), and Theorem 3"},{"comment":"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":"Section 3.2, Theorem 5 (Eq. (7))"},{"comment":"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":"Section 3.1, Lemma 1 and Theorems 6–8"},{"comment":"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.","section":"Section 3.3, Theorem 9"}],"minor_comments":[{"comment":"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).","section":"Theorem 1"},{"comment":"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.","section":"Table 1 and Section 5.1"},{"comment":"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.","section":"Figure 2 caption"},{"comment":"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.","section":"Proof of Theorem 7"},{"comment":"There are numerous spelling errors (e.g., \"desgin,\" \"mechainism,\" \"Equibrlium\") that should be corrected before publication.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one-line take: the OT bridge is a good idea, but the paper as posted has a false derivative identity in Theorem 5, and that invalidates the numerical routine and part of the proof machinery. It should go to review, but with a clear expectation of major revision.\n\nWhat's genuinely new: the Bayesian treatment of the capacitated facility location problem with scarce resources, the radius-function reformulation, the existence theorem (Theorem 4), and the closed-form characterizations for monotone, single-peaked, and single-dipped distributions. The motivating example (median vs decile) is effective. The two-facility impossibility result q1+q2 >= 2/3 is a real addition. If the main theorems survive, this is a useful paper for the mechanism design community.\n\nThe soft spots, in order of severity.\n\n1. Theorem 5 is simply wrong. For uniform mu on [0,1], q=0.5, y=0.1, R=0.4, R'=-1, Delta=0.3. Formula (7) gives W'=-1.1. Direct differentiation of W(y)=∫_0^{0.5}|x-y|dx gives -0.3. The correct interior derivative is W'=-Delta, with a different boundary form, not (7). Since Section 3.2.2 tells readers to find zeros of W' and Tables 1-2 report the resulting percentiles, the computational results are not trustworthy as written. The main characterizations may still be true — the sign arguments in Lemma 1 and Theorem 6 can be repaired — but the current proof text and the numerical method both rest on a false equality.\n\n2. The OT foundation is shaky. Equation (2) defines W1 with a 'stochastically dominates' constraint, which is not the standard Wasserstein distance. Theorems 2 and 3 use plans of total mass q and invoke the triangle inequality without proving it for this unbalanced object. This is patchable by using partial optimal transport properly, but as posted the derivation of the limit SW is not rigorous.\n\n3. Theorem 9 has a dimensionally wrong statement: q(1-W1) instead of q-W1. The following text uses the right object, so it looks like a typo, but it should be fixed.\n\n4. The experiments are described without code, seeds, or confidence intervals. The claim that the Bayesian approximation ratio is below 1.02 is not independently checkable.\n\nWho gets value: readers in algorithmic mechanism design who want to see how OT can give distribution-tuned mechanisms for capacitated problems. The paper deserves a serious referee, but it is not close to being accepted in its current form. I would require a corrected derivative, a proper treatment of unbalanced transport, the Theorem 9 fix, and a release of code.","headline":"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.","tokens_in":33613,"tokens_out":6749,"would_cite":false,"duration_ms":67049,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B03","90B80","49Q22","91B14"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["facility location","capacitated facility","Bayesian mechanism design","percentile mechanisms","optimal transport","Wasserstein distance","social welfare","truthfulness"],"falsifier":"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.","tokens_in":32454,"feed_emoji":"📍","tokens_out":12624,"duration_ms":104561,"temperature":0.7,"pith_summary":"The paper asks where to place a facility that can serve only a fraction $q$ of a population, when agents truthfully report their positions and then compete first-come-first-served for limited space. It shows that, as the number of agents grows, the expected social welfare of a location $y$ is $q$ minus the Wasserstein transport cost between the population distribution and a point mass of total mass $q$ at $y$. Maximizing welfare is therefore equivalent to minimizing that transport cost, and the minimizer $\\bar{y}$ yields an optimal truthful mechanism: place the facility at the $F_\\mu(\\bar{y})$-quantile. This gives a distribution-tuned alternative to worst-case mechanisms such as the median, and the same transport formulation handles two facilities and non-identically distributed agents. The paper also provides a search routine that, when no exactly optimal stable mechanism exists, finds one whose asymptotic welfare is within any prescribed tolerance.","feed_headline":"Optimal facility placement is a Wasserstein transport problem","feed_subtitle":"Best truthful one-facility rule is the quantile of a transport-cost minimizer, not the median.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Introduces the FLPSR single-facility setting, the first-come-first-served competition, the median mechanism baseline, and the fact that every truthful one-facility mechanism is a percentile mechanism.","marker":"[Aziz et al.(2020a)]"},{"why":"Defines the FCFS game for multiple facilities and the equilibrium-stable percentile condition (1), which the two-facility results rely on.","marker":"[Auricchio et al.(2024b)]"},{"why":"Provides the convergence $W_1(\\mu, \\mu_{\\vec{x}}) \\to 0$ of empirical measures used to pass from finite samples to the asymptotic formula in Theorem 3.","marker":"[Bobkov and Ledoux(2019)]"},{"why":"Supplies Bahadur's representation of sample quantiles, which links the minimizer $\\bar{y}$ to the optimal percentile $p=F_\\mu(\\bar{y})$.","marker":"[De Haan and Taconis-Haantjes(1979)]"},{"why":"Defines the transportation plan set with stochastic dominance that underlies equation (2), the unbalanced Wasserstein distance used throughout.","marker":"[Pele and Werman(2009)]"},{"why":"Shows the asymptotic convergence of expected social welfare for extended ranking mechanisms, invoked in the proof of the two-facility optimality condition.","marker":"[Auricchio et al.(2024d)]"}],"fun_headline_variants":["Scarce facility placement is an optimal transport problem","Optimal facility siting reduces to Wasserstein distance","Large-population facility location solved via optimal transport","High capacity blocks simple optimal rule for two facilities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Scarce facility placement is an optimal transport problem","Optimal facility siting reduces to Wasserstein distance","Large-population facility location solved via optimal transport","High capacity blocks simple optimal rule for two facilities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001106,"raw_usage":{"total_tokens":4698,"prompt_tokens":1118,"completion_tokens":3580,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":734,"completion_tokens_details":{"reasoning_tokens":3519}},"tokens_in":734,"tokens_out":3580,"duration_ms":28510,"temperature":1.0,"reasoning_tokens":3519,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:14:02.883407+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}