Answer: \(\text{Polynomial-time solvable}\)
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism M4 is constant-approximate, constant-strategyproof, and constant-Lipschitz.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\), sorted rational locations \(x_1<\cdots<x_\tau\), and rational masses \(\mu_j>0\) summing to \(1\) with \(n\mu_j\in\mathbb Z\), can one compute from the support a deterministic two-facility mechanism in time \(\mathrm{poly}(\tau,L)\) that preserves constant approximation, one-person strategyproofness, and the paper’s \(n\)-scaled Lipschitz guarantee?
A society is given by its support: \(P=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}\), with sorted rational locations \(x_1<\cdots<x_\tau\), positive binary rational masses summing to \(1\), and a binary integer \(n\ge2\) satisfying \(n\mu_j\in\mathbb Z\). Here \(\tau\) is the support size, \(L\) is the total input bit length, and the number of facilities is fixed at \(m=2\).
An anonymous deterministic mechanism \(M_n\) returns a lexicographically ordered pair \(T=(p_1,p_2)\) of facilities in \(\mathbb R^2\), allowing coincident facilities. Define \(d(x,T)=\min_{\ell\in\{1,2\}}\|(x,0)-p_\ell\|_1\), with service ties assigned to the first facility, \(C(P,T)=\sum_j\mu_jd(x_j,T)\), and \(\operatorname{OPT}(P)=\min_T C(P,T)\).
Require absolute constants \(A,B,K\ge1\), independent of all inputs, such that \(C(P,M_n(P))\le A\operatorname{OPT}(P)\), including when the optimum is zero.
One-person constant-strategyproofness means \(d(x_j,M_n(P))\le B\,d(x_j,M_n(P-n^{-1}\delta_{x_j}+n^{-1}\delta_y))\) for every supported location \(x_j\) and every report \(y\in\mathbb R\); only mass \(1/n\) moves.
For any two societies \(P,Q\) with the same \(n\), require \(\sum_{\ell=1}^2\|M_n(P)_\ell-M_n(Q)_\ell\|_1\le KnW_1(P,Q)\), where \(W_1\) uses absolute distance on the line. These guarantees apply also to real locations; computation is required on rational inputs, with exact rational facility coordinates as output.
Can such a mechanism be evaluated from the support in time \(\operatorname{poly}(m,\tau,L)\), or is this computation NP-hard?
For explicitly listed agents, a deterministic mechanism with constant approximation, constant-strategyproofness, and constant Lipschitz continuity in the sorted-profile \(\ell_1\) distance is known ([Fullerton, Hu, and Plaxton](https://arxiv.org/html/2507.04485v3)).
No result settling the computation with binary multiplicities and support-based running time was located.
The intended existence question is resolved positively. The mechanism \(M_4\) of Fullerton, Hu, and Plaxton can be evaluated exactly from the support in time \(\operatorname{poly}(\tau,L)\). Binary multiplicities need not be expanded.
We prove this by giving a compressed evaluation algorithm and verifying that its output is exactly the published mechanism.
Write \(c=\operatorname{OPT}(P)\) and \(b=\sum_j\mu_jx_j\). Define \(h_1,h_2\) by
\(h_1\ge x_1,\qquad \sum_j\mu_j\max(0,h_1-x_j)=c,\)
\(h_2\le x_\tau,\qquad \sum_j\mu_j\max(0,x_j-h_2)=c.\)
Put \(f_1=\min(h_1,b)\), \(f_2=\max(h_2,b)\), and \(\Delta=f_2-f_1\). If \(\Delta=0\), set \(\xi_1=\xi_2=0\). Otherwise define
\(u_j=\dfrac{\max(0,\min(f_2,x_j)-f_1)}{\Delta},\qquad v_2=\sum_j\mu_ju_j,\qquad v_1=1-v_2,\)
\(\xi_\ell=\min(\Delta,2c/v_\ell).\)
The mechanism returns
\(M_n(P)=\bigl((f_1,\max(8c,\xi_1)),(f_2,\max(8c,\xi_2))\bigr).\)
These are the normalized formulas for \(M_4\). The published result gives approximation factor \(15\) and absolute constants \(B_0,\kappa\) for strategyproofness and Lipschitz continuity on every real sorted agent profile. Its conventions for facility ordering, distance, and service ties agree with those in the question. [Fullerton–Hu–Plaxton, Sections 3.2 and 4.2, Theorem 4.2](https://arxiv.org/html/2507.04485v3#S4.SS2).
The remainder proves the computational claim and verifies the transfer of that theorem to the present input representation.
We first establish
\(c=\min_{1\le r\le s\le\tau}\sum_{j=1}^{\tau}\mu_j\min(|x_j-x_r|,|x_j-x_s|).\)
Proof. Take any facility pair in the plane. Projecting both facilities onto the horizontal axis weakly decreases every service distance.
For the resulting pair, assign each support point to a nearest facility, using the prescribed tie rule. For each nonempty assigned group, replace its facility by a weighted median of that group. Such a median can be chosen at a support location and minimizes the group's sum of weighted absolute distances: between consecutive group locations, the slope of that sum is the weight strictly to the left minus the weight strictly to the right. At a weighted median, these slopes change from nonpositive to nonnegative.
If a group is empty, place its facility at any support location. The replacements do not increase the cost of the fixed assignment. Allowing agents to choose their nearest replacement facility can only decrease it further.
Consequently, every facility pair has cost at least that of some pair of support locations. Conversely, every support pair is an admissible facility pair. Taking the minimum over the finite collection proves the formula. \(\square\)
There are \(O(\tau^2)\) candidate pairs, each evaluated using \(O(\tau)\) arithmetic operations. Thus this step uses \(O(\tau^3)\) operations, independently of the magnitude of \(n\).
The function
\(G_1(t)=\sum_j\mu_j\max(0,t-x_j)\)
is continuous, satisfies \(G_1(x_1)=0\), and tends to infinity as \(t\) tends to infinity. It is strictly increasing on \([x_1,\infty)\): for \(t'>t\ge x_1\), the first summand alone increases by \(\mu_1(t'-t)>0\). Hence the equation defining \(h_1\) has exactly one solution.
Similarly,
\(G_2(t)=\sum_j\mu_j\max(0,x_j-t)\)
is continuous and strictly decreasing on \((-\infty,x_\tau]\), ranges from infinity to zero, and therefore uniquely defines \(h_2\).
These roots require only linear equations. For \(1\le k\le\tau\), let
\(A_k=\sum_{j\le k}\mu_j,\qquad Z_k=\sum_{j\le k}\mu_jx_j.\)
On \([x_k,x_{k+1}]\), with the final interval extending to infinity, we have \(G_1(t)=A_kt-Z_k\). Therefore the root candidate is
\(h_1=\dfrac{c+Z_k}{A_k}.\)
Scan the intervals and select a candidate that belongs to its interval. Uniqueness guarantees that all accepted candidates agree, including when the root is a breakpoint.
For \(h_2\), use suffix sums
\(A^k=\sum_{j\ge k}\mu_j,\qquad Z^k=\sum_{j\ge k}\mu_jx_j.\)
On \([x_{k-1},x_k]\), with the first interval extending to negative infinity, the candidate is
\(h_2=\dfrac{Z^k-c}{A^k}.\)
Both scans use \(O(\tau)\) arithmetic operations after computing prefix and suffix sums.
All subsequent quantities are obtained by rational arithmetic and comparisons. We must also check that their denominators are nonzero. Since placing both facilities at \(x_\tau\) is feasible,
\(c\le G_1(x_\tau),\)
so \(h_1\le x_\tau\). Similarly, \(h_2\ge x_1\). Together with the mean bounds, this gives
\(x_1\le f_1\le b\le f_2\le x_\tau.\)
When \(\Delta>0\), we have \(u_1=0\) and \(u_\tau=1\). Consequently,
\(v_1\ge\mu_1>0,\qquad v_2\ge\mu_\tau>0.\)
Thus every division in the mechanism is valid. When \(\Delta=0\), that branch performs no division by \(\Delta\) or by either \(v_\ell\).
The facilities are lexicographically ordered: if \(\Delta>0\), their first coordinates are strictly ordered; otherwise their first coordinates coincide and their heights both equal \(8c\).
A polynomial number of arithmetic operations is insufficient without controlling operand sizes. Here those sizes are polynomial as well.
Set \(a_j=n\mu_j\), which is a positive integer by hypothesis. Compute these integers directly from the binary input; no agent expansion is required.
Write \(x_j=p_j/q_j\), with positive integer denominators, and choose
\(D=\prod_{j=1}^{\tau}q_j,\qquad z_j=Dx_j\in\mathbb Z.\)
The integers \(D,z_j,a_j\) have \(O(L)\) bits. Compute the integer
\(H=\min_{r\le s}\sum_j a_j\min(|z_j-z_r|,|z_j-z_s|).\)
Then \(c=H/(nD)\). Every candidate sum has \(O(L)\) bits because it is bounded by \(n(z_\tau-z_1)\).
The scaled roots satisfy
\(Dh_1=\dfrac{H+\sum_{j\le k}a_jz_j}{\sum_{j\le k}a_j},\qquad Dh_2=\dfrac{\sum_{j\ge k}a_jz_j-H}{\sum_{j\ge k}a_j}.\)
The scaled mean is \(Db=\sum_ja_jz_j/n\). Each numerator has \(O(L)\) bits, and each denominator is a positive integer at most \(n\). Hence the selected scaled coordinates \(s_1=Df_1\) and \(s_2=Df_2\) also have \(O(L)\)-bit rational representations.
For completeness, consider the heights when \(s_2>s_1\). Choose a common denominator \(q\) for \(s_1,s_2\) by multiplying their denominators. Write
\(s_1=\alpha/q,\qquad s_2=\beta/q,\qquad d=\beta-\alpha>0.\)
All these integers have \(O(L)\) bits. Define
\(t_j=\max(0,\min(d,qz_j-\alpha)),\)
\(N_2=\sum_ja_jt_j,\qquad N_1=nd-N_2.\)
Then \(u_j=t_j/d\), and
\(v_\ell=\dfrac{N_\ell}{nd},\qquad \dfrac{2c}{v_\ell}=\dfrac{2Hd}{DN_\ell},\qquad \Delta=\dfrac{d}{qD}.\)
The positivity proved above gives \(N_1,N_2>0\). Moreover, \(N_\ell\le nd\), so these integers and all height numerators and denominators have \(O(L)\) bits.
Thus the complete evaluation uses \(O(\tau^3)\) exact arithmetic operations on polynomial-size operands. Standard integer arithmetic implements it in \(\operatorname{poly}(\tau,L)\) bit time, with exact rational output.
Let \(\pi(P)\) be the sorted profile containing \(a_j\) copies of \(x_j\). This profile is used only in the proof.
Its unnormalized optimal cost is \(nc\), and its mean is \(b\). In the published defining equations, replacing sums over agents by multiplicity-weighted sums and dividing by \(n\) gives exactly the equations for \(h_1,h_2\) above.
Likewise, the published fractional counts are \(nv_\ell\). Its vertical terms therefore become
\(\dfrac{8(nc)}{n}=8c,\qquad \dfrac{2(nc)}{nv_\ell}=\dfrac{2c}{v_\ell}.\)
It follows that
\(M_n(P)=M_4(\pi(P)).\)
This identity holds for real locations as well as rational locations.
The expanded profile has exactly \(n\ge2\) agents, so the published theorem applies. Dividing its social-cost inequality by \(n\) gives
\(C(P,M_n(P))\le15\operatorname{OPT}(P).\)
Moving mass \(1/n\) from a supported location to any real report \(y\) changes exactly one agent report in the expanded profile. Thus its strategyproofness inequality gives precisely the required inequality, with \(B=\max(1,B_0)\).
Zero optimum is included. Indeed, positive masses imply \(c=0\) exactly when \(\tau\le2\). For one support point, the mechanism places both facilities there. For two support points, it places one at each, with both heights zero.
For two societies with the same \(n\), write their expanded sorted profiles as \(\pi,\rho\). We claim
\(\|\pi-\rho\|_1=nW_1(P,Q).\)
To justify this, let \(F_P,F_Q\) be their cumulative distribution functions. The identity
\(|u-v|=\int_{\mathbb R}|\mathbf1_{\{u\le t\}}-\mathbf1_{\{v\le t\}}|\,dt\)
shows that every coupling has cost at least \(\int_{\mathbb R}|F_P(t)-F_Q(t)|\,dt\), by the inequality between the absolute value of an expectation and the expectation of an absolute value.
The coupling pairing the \(i\)-th sorted agent with the \(i\)-th sorted agent attains this bound. For every \(t\), the indices satisfying \(\pi_i\le t\) and those satisfying \(\rho_i\le t\) are initial segments. Their symmetric difference therefore has size equal to the difference of their sizes. Integrating yields the claimed identity.
Applying the published Lipschitz bound now gives
\(\sum_{\ell=1}^2\|M_n(P)_\ell-M_n(Q)_\ell\|_1 \le\kappa\|\pi-\rho\|_1 =\kappa nW_1(P,Q).\)
Choose \(K=\max(1,\kappa)\).
There exists an anonymous deterministic mechanism satisfying every stated guarantee, with absolute constants \(A=15\), \(B\), and \(K\), whose exact rational evaluation takes \(\operatorname{poly}(\tau,L)\) time. This settles the support-based existence question for fixed \(m=2\).
⟨structured verdict parsed — rendered above⟩
The argument resolves the intended existence question. It gives an exact polynomial-time evaluation of a particular anonymous mechanism satisfying all three guarantees. I found no major or minor mathematical issues.
This establishes the existence of an efficiently evaluable mechanism; it does not claim that every mechanism satisfying the guarantees is efficiently evaluable.
The cited definitions match the prover’s formulas. The paper defines the horizontal coordinates using the same optimal-cost equations and mean truncation. Its fractional counts and vertical offsets become exactly the displayed normalized quantities after division by \(n\).
The cited result applies to arbitrary real, nondecreasing profiles with at least two agents, including repeated locations. Its definitions use Manhattan service distance, lexicographically ordered facilities, first-facility service ties, arbitrary real unilateral reports followed by sorting, and the sum of coordinate distances between ordered outputs. Thus the hypotheses and conventions needed for the transfer are satisfied.
The approximation factor \(15\) is explicitly supplied by Lemma 4.5; constant strategyproofness and the global Lipschitz inequality are supplied by Lemmas 4.7 and 4.10 and collected in Theorem 4.2. No extra hypothesis is omitted in the application. [Fullerton–Hu–Plaxton, Sections 2, 3.2, and 4.2](https://arxiv.org/html/2507.04485v3#S4.SS2).
Assessment: Correct invocation of the published result.
Each step of the support-pair reduction is valid:
Consequently, every admissible pair is weakly dominated in cost by a support pair. Conversely, support pairs are admissible. The finite minimum therefore equals the planar optimum.
Allowing \(r=s\) covers coincident facilities and the single-support case. The stated enumeration requires \(O(\tau^3)\) arithmetic operations.
Assessment: Correct, including attainment and degenerate cases.
The root arguments are sound. For \(t'>t\ge x_1\), the first summand of \(G_1\) increases by exactly \(\mu_1(t'-t)>0\). The analogous last summand gives strict decrease for \(G_2\) on its specified domain. Continuity, endpoint values, and unbounded ranges establish existence and uniqueness, including when \(c=0\).
The prefix and suffix formulas are correct on their stated intervals. At a breakpoint, including a zero-contribution endpoint term does not change the equation. Positive prefix and suffix masses ensure valid denominators.
The feasible single-location comparisons establish
\[
x_1\le f_1\le b\le f_2\le x_\tau.
\]
When \(\Delta>0\), these bounds imply \(u_1=0\) and \(u_\tau=1\). Hence \(v_1\ge\mu_1>0\) and \(v_2\ge\mu_\tau>0\). The coincident-coordinate branch avoids all potentially undefined divisions and gives equal heights.
Assessment: The formulas are well-defined and produce lexicographically ordered rational facilities.
The integer scaling argument correctly controls operand sizes.
The input assumptions give positive integers \(a_j=n\mu_j\) with total \(n\). The product \(D\) has bit length bounded by the sum of input denominator lengths, and each scaled integer location \(z_j\) has \(O(L)\) bits.
Each candidate defining \(H\) is nonnegative and bounded by \(n(z_\tau-z_1)\), so its bit length is \(O(L)\), including the zero-range case. The root and mean numerators also have \(O(L)\) bits: their absolute magnitudes are bounded using \(n\max_j|z_j|\) and \(H\). Negative locations cause no difficulty.
The height calculation is algebraically correct:
\[
v_\ell=\frac{N_\ell}{nd},
\qquad
\frac{2c}{v_\ell}=\frac{2Hd}{DN_\ell}.
\]
Multiplying the two coordinate denominators preserves \(O(L)\) bit length. The bounds \(0<N_\ell\le nd\) control the remaining operands. The zero-\(\Delta\) branch uses only the already bounded coordinates and \(8c\).
Thus the claimed arithmetic-operation bound yields polynomial bit time and polynomial-size exact output. No dependence polynomial in the numerical value of \(n\) is introduced.
Assessment: Correct support-based bit-complexity analysis.
Replacing sums over agents by multiplicity-weighted sums gives precisely the stated defining equations. The expanded optimum is \(nc\), its mean is \(b\), and its fractional counts are \(nv_\ell\). Both vertical normalizations are correct. The identity with the published mechanism also holds in the zero-\(\Delta\) branch.
The expanded profile is used for justification only; the evaluation algorithm never constructs it.
Dividing the published social-cost inequality by \(n\) gives the required normalized approximation bound.
Every supported location contains at least one agent because \(a_j\ge1\). Moving mass \(1/n\) therefore corresponds to one unilateral report change. Sorting afterward is already part of the published strategyproofness definition, so reports crossing other agents’ locations are covered.
The zero-optimum discussion is correct. Positive masses make zero cost possible exactly when at most two distinct locations require service. The displayed mechanism serves those locations at zero height and zero distance.
The coupling argument correctly proves
\[
\|\pi-\rho\|_1=nW_1(P,Q).
\]
The lower bound follows from the indicator identity and the absolute-value inequality. The sorted pairing attains it because, at each threshold, both indicator sets are initial segments. Finite support ensures the relevant integrals are finite.
The published output metric is exactly the required ordered-facility metric. Its Lipschitz bound therefore transfers with \(K=\max(1,\kappa)\).
Assessment: All three guarantees transfer with absolute constants.
The conclusion follows as written. No missing lemma, incorrect calculation, unverified theorem application, or quantifier failure was found. No additional clarification is needed to make the argument verifiable.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.