Answer: Yes. An explicit rule computable in time polynomial in \(\tau\) and \(L\), independently of \(n\), satisfies every clone strategy-proofness constraint and guarantees \(\operatorname{SC}_\nu(P_\nu)\leq6\operatorname{OPT}_\nu\), including when \(\operatorname{OPT}_\nu=0\).
Theorem 4.4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism 3 is randomized, strategy-proof, and 6-approximation for the social cost objective.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite rational type set \(T=\{x_1,\ldots,x_\tau\}\subset\mathbb{Q}\), rational masses \(\mu\in\Delta_\tau\), and public facility \(0\), design an explicit rule \(M\) mapping reported mass vectors to finite-support distributions \(P_\mu\) over zero-cost shortcut edges \(e=(a,b)\), strategy-proof on every denominator-clearing clone expansion, such that \(\operatorname{SC}_\mu(P_\mu)\le 6\operatorname{OPT}_\mu\), where \(d_e(x)=\min\{|x|,|x-a|+|b|,|x-b|+|a|\}\), \(\operatorname{SC}_\mu(P)=\mathbb{E}_{e\sim P}[\sum_t\mu_t d_e(x_t)]\), and \(\operatorname{OPT}_\mu=\min_e\sum_t\mu_t d_e(x_t)\).
A society is given by its support: distinct locations \(T=\{x_1,\ldots,x_\tau\}\subset\mathbb Q\), each with a positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is no separate parameter \(m\).
The public facility is at \(0\). One may add an undirected zero-cost edge \(e=(a,b)\in\mathbb R^2\), allowing coincident endpoints. Define \(d_e(x)=\min\{|x|,|x-a|+|b|,|x-b|+|a|\}\), \(c(P,x)=\mathbb E_{e\sim P}d_e(x)\), \(\operatorname{SC}_\nu(P)=\sum_t\mu_t c(P,x_t)\), and \(\operatorname{OPT}_\nu=\min_{e\in\mathbb R^2}\sum_t\mu_t d_e(x_t)\), where \(\nu=\sum_t\mu_t\delta_{x_t}\).
A single rule \(M\), defined on all finitely supported rational societies, returns a finite distribution \(P_\nu\) encoded by rational endpoints and rational probabilities. Reports may introduce locations outside the original support; masses are conserved, and there are no payments.
Strategy-proofness on every denominator-clearing clone expansion means: for every positive integer \(n\) with \(n\mu_t\in\mathbb Z\) for all \(t\), every supported \(x\), and every report \(y\in\mathbb Q\), \(c(P_\nu,x)\le c(P_{\nu+(\delta_y-\delta_x)/n},x)\). Zero-mass locations are removed and repeated locations merged.
Can such an explicit rule \(M\) be computed in time polynomial in \(\tau\) and \(L\), independently of the clone count \(n\), while guaranteeing \(\operatorname{SC}_\nu(P_\nu)\le6\operatorname{OPT}_\nu\) for every society, including those with \(\operatorname{OPT}_\nu=0\)?
For finite agent lists, a randomized strategy-proof mechanism achieves social-cost approximation factor \(6\), and the same source states a randomized lower bound of \(1.02\). [Source](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p2116.pdf)
No result explicitly treating the rational-mass input and clone condition above was located in the literature search.
Yes. Define \(S_\nu=\sum_{t=1}^{\tau}\mu_t|x_t|\).
If \(S_\nu=0\), return the edge \((0,0)\) with probability \(1\). Otherwise, return \((0,x_t)\) with probability
\[ p_t=\frac{\mu_t|x_t|}{S_\nu}, \]
omitting locations with \(x_t=0\).
This is the mass-weighted form of Mechanism 3 in [Chan and Wang’s paper](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p2116.pdf). Below, we prove directly that this single rule satisfies every required clone strategy-proofness inequality, has polynomial computation and output size, and guarantees the requested approximation. The approximation argument actually yields a factor of \(5\).
Write \(g(x,z)=d_{(0,z)}(x)=\min\{|x|,|x-z|\}\).
Fix an admissible clone count \(n\), a supported true location \(x\), and any rational report \(y\). Put \(\varepsilon=1/n\). Since \(n\mu_x\) is a positive integer, \(\varepsilon\leq\mu_x\), so the residual measure \(\rho=\nu-\varepsilon\delta_x\) is nonnegative.
Define
\[ r=|x|,\qquad q=|y|,\qquad D=\sum_z\rho(\{z\})|z|,\qquad A=\sum_z\rho(\{z\})|z|g(x,z). \]
The sums range over the finite support of \(\rho\). Because \(0\leq g(x,z)\leq r\), we have \(0\leq A\leq rD\).
If \(r=0\), truthful cost is zero, and the desired inequality follows from nonnegativity of costs. If \(r>0\) and \(D=0\), all residual mass is at \(0\), so truthful reporting selects \((0,x)\) with probability \(1\), again giving zero cost.
It remains to consider \(r>0\) and \(D>0\). The truthful and deviating expected costs are respectively
\[ C_{\mathrm{true}}=\frac{A}{D+\varepsilon r}, \qquad C_{\mathrm{report}}= \frac{A+\varepsilon qg(x,y)}{D+\varepsilon q}. \]
These formulas remain valid when locations merge or disappear: their contributions simply add or vanish.
Both denominators are positive. Cross-multiplication gives
\[ C_{\mathrm{report}}-C_{\mathrm{true}} = \frac{\varepsilon\bigl((r-q)A+ qg(x,y)(D+\varepsilon r)\bigr)} {(D+\varepsilon q)(D+\varepsilon r)}. \]
If \(q\leq r\), both terms in the numerator are nonnegative.
Suppose \(q>r\). The reverse triangle inequality gives
\[ g(x,y)\geq\min\{r,q-r\}. \]
Moreover, \(q\min\{r,q-r\}\geq r(q-r)\): when \(q-r\leq r\), this follows from \(q\geq r\); when \(q-r>r\), it follows from \(q\geq q-r\). Consequently,
\[ qg(x,y)(D+\varepsilon r) \geq r(q-r)D \geq(q-r)A. \]
Thus the numerator is nonnegative in this case as well. We have proved
\[ c(P_\nu,x)\leq c\!\left(P_{\nu+(\delta_y-\delta_x)/n},x\right). \]
The argument applies to every permitted \(n\) and every rational \(y\), including reports outside the original support.
We first justify comparison with the unrestricted optimum.
Take any edge \((a,b)\), relabeling its endpoints so that \(|a|\leq|b|\). The triangle inequality implies
\[ |x-a|+|b|\geq |x-a|+|a|\geq|x|. \]
Hence
\[ d_{(a,b)}(x)=\min\{|x|,|x-b|+|a|\}. \]
Choose \(z\) on the segment from \(0\) to \(b\) such that \(|b-z|=|a|\); explicitly, \(z=\operatorname{sgn}(b)(|b|-|a|)\), with \(z=0\) when \(b=0\). Then
\[ |x-z|\leq|x-b|+|a|, \]
so \(d_{(0,z)}(x)\leq d_{(a,b)}(x)\) for every \(x\). Therefore restricting to edges \((0,z)\) does not change the optimal value.
For completeness, this restricted optimum is attained. Let \(R=\max_t|x_t|\). Clamping \(z\) to \([-R,R]\) weakly decreases \(|x_t-z|\) for every supported location, and hence weakly decreases every cost. The function
\[ C(z)=\sum_t\mu_t g(x_t,z) \]
is continuous, being a finite sum of minima of continuous functions. It therefore attains its minimum on the compact interval \([-R,R]\). In particular,
\[ \operatorname{OPT}_\nu=\min_{z\in\mathbb R}C(z). \]
If \(S_\nu=0\), positivity of the masses implies that every supported location is \(0\). Both the mechanism’s cost and the optimum are zero.
Assume \(D:=S_\nu>0\), and choose an optimal \(z\). Put
\[ \delta_t=g(x_t,z), \qquad \Gamma=C(z)=\operatorname{OPT}_\nu. \]
Since \(C(v)\leq D\) for every \(v\), an optimum at \(z=0\) immediately gives \(\operatorname{SC}_\nu(P_\nu)\leq D=\Gamma\).
Otherwise, reflection of all locations preserves distances, probabilities, and costs, so we may assume \(z>0\). Partition the support indices into
\[ A=\{t:x_t\leq z/2\},\qquad H=\{t:z/2<x_t\leq2z\},\qquad F=\{t:x_t>2z\}. \]
Let \(B=H\cup F\), let \(\beta=\sum_{t\in B}\mu_t\), and define \(\Gamma_U=\sum_{t\in U}\mu_t\delta_t\) for each part \(U\). Thus \(\Gamma=\Gamma_A+\Gamma_H+\Gamma_F\).
For \(t\in A\), \(\delta_t=|x_t|\). For \(t\in B\), \(x_t>0\) and \(\delta_t=|x_t-z|\). In particular,
\[ D\geq\frac{\beta z}{2}. \]
The mechanism’s expected social cost is
\[ \operatorname{SC}_\nu(P_\nu) =\sum_t\frac{\mu_t|x_t|}{D}C(x_t). \]
We bound the three contributions separately.
Contribution from \(A\). Using \(C(x_t)\leq D\),
\[ \sum_{t\in A}\frac{\mu_t|x_t|}{D}C(x_t) \leq\sum_{t\in A}\mu_t|x_t| =\Gamma_A. \]
Contribution from \(F\). Here \(\delta_t=x_t-z>x_t/2\). Therefore,
\[ \sum_{t\in F}\frac{\mu_t|x_t|}{D}C(x_t) \leq\sum_{t\in F}\mu_tx_t \leq2\Gamma_F. \]
Contribution from \(H\). Fix \(t\in H\). For \(j\in A\), the cost under \((0,x_t)\) is at most \(|x_j|=\delta_j\). For \(j\in B\), the triangle inequality gives
\[ g(x_j,x_t)\leq|x_j-x_t| \leq|x_j-z|+|z-x_t| =\delta_j+\delta_t. \]
Summing these bounds yields \(C(x_t)\leq\Gamma+\beta\delta_t\). Consequently,
\[ \sum_{t\in H}\frac{\mu_tx_t}{D}C(x_t) \leq \Gamma\sum_{t\in H}\frac{\mu_tx_t}{D} +\frac{\beta}{D}\sum_{t\in H}\mu_tx_t\delta_t. \]
The first sum of probabilities is at most \(1\). Also \(x_t\leq2z\) on \(H\), and \(D\geq\beta z/2\). Hence this contribution is at most
\[ \Gamma+\frac{2\beta z}{D}\Gamma_H \leq\Gamma+4\Gamma_H. \]
Combining the three parts gives
\[ \operatorname{SC}_\nu(P_\nu) \leq\Gamma+\Gamma_A+4\Gamma_H+2\Gamma_F \leq5\Gamma \leq6\operatorname{OPT}_\nu. \]
No step divides by \(\Gamma\). Thus the same proof establishes zero social cost whenever \(\operatorname{OPT}_\nu=0\).
More explicitly, zero optimum forces every supported location to belong to \(\{0,z\}\), because each positive-mass summand \(g(x_t,z)\) must vanish. If \(z\ne0\), the rule then selects \((0,z)\) with probability \(1\).
Write the input rationals as \(x_t=a_t/b_t\) and \(\mu_t=u_t/v_t\), with positive denominators. Form the integer
\[ Q=\prod_{t=1}^{\tau}b_tv_t. \]
Its bit length is \(O(L)\). Define integers
\[ W_t=u_t|a_t|\frac{Q}{b_tv_t}, \qquad W=\sum_tW_t. \]
Then \(W_t/Q=\mu_t|x_t|\). If \(W=0\), output the single edge \((0,0)\). Otherwise, output each edge \((0,x_t)\) with positive \(W_t\), assigning probability \(W_t/W\).
The integers involved have bit length \(O(L+\log\tau)\). Computing them requires polynomially many operations on integers of polynomial bit length. There are at most \(\tau\) output edges, and the total output length is polynomial in \(\tau\) and \(L\).
The algorithm never constructs a clone list or uses a clone count. It is one rule on rational societies, computed entirely from their support representation.
⟨structured verdict parsed — rendered above⟩
The output proves the requested result. The rule is well defined on every allowed society, satisfies every required clone strategy-proofness inequality, and has polynomial computation and output size independent of the clone count. The stronger approximation factor of \(5\) is also justified.
No major or minor mathematical issues were found. No additional clarification is needed.
When \(S_\nu>0\), all stated probabilities are nonnegative and sum to \(1\). Omitting locations at \(0\) removes only zero-probability outcomes. Every output endpoint and probability is rational.
When \(S_\nu=0\), positivity of the masses forces every supported location to be \(0\), so the specified deterministic output covers the otherwise undefined normalization.
The rule depends only on the rational society, rather than on a particular clone expansion. This addresses the requirement for a single rule defined across all input societies.
The attribution is accurate: Mechanism 3 selects an agent’s location with probability proportional to its distance from the facility. Combining probabilities for agents at the same location gives the stated mass-weighted formula. The proof here establishes the required properties directly rather than relying on the paper’s finite-list theorem. [Chan and Wang, Mechanism 3](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p2116.pdf)
Residual measure. For every admissible \(n\), the supported location \(x\) satisfies \(n\mu_x\geq1\). Thus \(\varepsilon=1/n\leq\mu_x\), and \(\rho\) is nonnegative. Replacing the removed mass by mass at any rational \(y\) produces another allowed society after merging and removing zero masses.
Bounds on the residual contribution. The inequality \(0\leq A\leq rD\) follows term by term from \(0\leq g(x,z)\leq r\).
Degenerate cases.
Both cases establish the desired inequality without requiring a formula for a potentially zero deviating denominator.
Expected-cost formulas. In the remaining case, \(D>0\). The truthful added mass contributes zero to the numerator because \(g(x,x)=0\). The reported mass contributes \(\varepsilon qg(x,y)\). Both displayed denominators are positive, including when \(y=0\). Merging locations does not alter these weighted sums.
Algebra. Rechecking the subtraction gives exactly the displayed numerator
\(\varepsilon((r-q)A+qg(x,y)(D+\varepsilon r))\).
For \(q\leq r\), its terms are nonnegative. For \(q>r\), the reverse triangle inequality and monotonicity of the minimum give the stated lower bound on \(g(x,y)\). Both subcases used to verify
\(q\min\{r,q-r\}\geq r(q-r)\)
are valid. Together with \(A\leq rD\), this proves that the numerator remains nonnegative.
Conclusion: The argument covers every admissible clone count, every supported true location, and every rational report, including reports outside the original support.
Relabeling endpoints by absolute value is permitted because the edge is undirected. The displayed triangle inequality correctly eliminates the route through \(a\), leaving
\(d_{(a,b)}(x)=\min\{|x|,|x-b|+|a|\}\).
The proposed \(z\) exists because \(|a|\leq|b|\), and satisfies \(|b-z|=|a|\), including when \(b=0\). Consequently, the triangle inequality establishes pointwise domination by \((0,z)\).
This proves that restricting the optimum does not worsen its value. Conversely, restricted edges are allowed unrestricted edges, so the optimal values agree.
The attainment argument is valid. Clamping to \([-R,R]\) decreases or preserves distance to every supported location. The objective is continuous on this nonempty compact interval, so the extreme value theorem applies. The argument also covers \(R=0\).
Conclusion: Comparison with the unrestricted real-endpoint optimum is fully justified.
Initial cases. The treatment of \(S_\nu=0\) is correct. If \(z=0\) is optimal, then \(\Gamma=C(0)=D\), while every selected edge has social cost at most \(D\). Reflection correctly reduces a negative optimal endpoint to the positive case.
Partition and boundary cases. The sets \(A,H,F\) are disjoint and exhaustive. The boundary \(x_t=z/2\) is correctly placed in \(A\), where the two relevant distances agree. The boundary \(x_t=2z\) is correctly placed in \(H\). The stated formulas for \(\delta_t\) hold throughout their respective parts, including negative locations in \(A\).
The bound \(D\geq\beta z/2\) follows from \(x_t>z/2\) on \(B\).
Contributions from \(A\) and \(F\). Both use the valid bound \(C(x_t)\leq D\). On \(F\), \(\delta_t=x_t-z>x_t/2\), giving the claimed contribution bound.
Contribution from \(H\). The individual bounds for \(j\in A\) and \(j\in B\) correctly imply
\(C(x_t)\leq\Gamma+\beta\delta_t\).
The first probability sum is at most \(1\). The remaining estimate uses \(x_t\leq2z\) and \(2\beta z/D\leq4\), with \(D>0\).
There is no division by \(\beta\); hence empty parts and \(\beta=0\) do not invalidate the calculation.
Final constant. The combined expression is
\(2\Gamma_A+5\Gamma_H+3\Gamma_F\).
All three components are nonnegative, so this is at most \(5\Gamma\). The claimed factor of \(5\), and therefore the requested factor of \(6\), follows.
The approximation argument never divides by \(\Gamma\), so it remains valid when the optimum is zero.
The explicit characterization is also correct: positivity of every mass and nonnegativity of every summand force each supported location to lie in \(\{0,z\}\). When \(z\neq0\) and \(D>0\), the rule selects \(z\) with probability \(1\), giving zero social cost.
Conclusion: Zero-optimum societies are covered without an unstated nondegeneracy assumption.
The product \(Q\) has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Each \(b_tv_t\) divides \(Q\), so every \(W_t\) is an integer and the identity \(W_t/Q=\mu_t|x_t|\) is exact.
The stated bit-length bounds for \(W_t\) and \(W\) are valid; summing at most \(\tau\) integers adds at most \(O(\log\tau)\) bits. Standard binary integer arithmetic therefore performs the construction in polynomial time.
There are at most \(\tau\) output edges. Their rational endpoints come from the input, and their probability numerators and denominators have polynomial bit length. Reducing fractions, if required by the encoding, also takes polynomial time.
The algorithm does not use \(n\) or construct clones.
Conclusion: The output establishes polynomial-time construction of the required rule. It does not claim a polynomial-time algorithm for computing the exact optimum.
None required. The mathematical argument resolves all requirements of USER_TASK.
⟨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.