Answer: Yes. The prescribed lower-weighted-median rule is deterministic, clone strategyproof, and achieves a \(k\)-approximation in \(O((m\tau+\tau\log(\tau+1))L^2)\) bit operations.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism 6 is strategyproof, and has an ap- proximation ratio of k for the social cost. Mechanism 6 has a parameterized approximation ratio re- lated to the number of facilities. Since k is publicly known and constant in real life scenarios, Mechanism 6 achieves a constant approximation ratio in most cases.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\), finitely many rational locations \(x\), and rational masses \(\mu_{x,A}\) over complete types \((x,A)\) with \(\varnothing\ne A\subseteq[k]\) and \(\sum_{x,A}\mu_{x,A}=1\), compute a deterministic rule returning facility locations \(y\in\mathbb{R}^k\) that is strategyproof under denominator-cleared clone deviations in the reported sets \(A\), places each facility \(j\) at a fixed weighted median of \(\nu_j(x)=\sum_{A\ni j}\mu_{x,A}\), and satisfies \(\operatorname{SC}^{\max}_\mu(y)\le k\min_{z\in\mathbb{R}^k}\operatorname{SC}^{\max}_\mu(z)\), where \(\operatorname{SC}^{\max}_\mu(y)=\sum_{x,A}\mu_{x,A}\max_{j\in A}|y_j-x|\).
Let \(k\ge3\) labeled facilities lie on \(\mathbb R\); write \(m=k\). Locations are public, acceptable sets private, and facilities may coincide.
A society is given by its support: the list of \(\tau\) types \((x,A)\) with positive binary rational masses \(\mu_{x,A}\), where \(x\in\mathbb Q\), \(\varnothing\ne A\subseteq[k]\), and \(\sum_{x,A}\mu_{x,A}=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
For \(y\in\mathbb R^k\), define \(c_{x,A}(y)=\max_{j\in A}|y_j-x|\) and \(\operatorname{SC}^{\max}_\mu(y)=\sum_{x,A}\mu_{x,A}c_{x,A}(y)\).
Require \(M_j(\mu)\) to be the lower weighted median of \(\nu_j(x)=\sum_{A\ni j}\mu_{x,A}\): the smallest supported location whose cumulative mass is at least half the total. If that total is zero, set \(M_j(\mu)=0\).
Clone strategyproofness means that for every positive integer \(D\) with all \(D\mu_{x,A}\) integral, every supported \((x,A)\), and every nonempty report \(B\subseteq[k]\), setting \(\mu'=\mu-D^{-1}\delta_{(x,A)}+D^{-1}\delta_{(x,B)}\) gives \(c_{x,A}(M(\mu))\le c_{x,A}(M(\mu'))\); \(\delta_{(x,A)}\) denotes unit mass at that type.
Does there exist a deterministic rule computable in time polynomial in \(m,\tau,L\) that satisfies these median and clone strategyproofness requirements and guarantees \(\operatorname{SC}^{\max}_\mu(M(\mu))\le k\min_{z\in\mathbb R^k}\operatorname{SC}^{\max}_\mu(z)\) for every society, or is this approximation guarantee unattainable under these requirements?
For finite unweighted societies, placing each facility at the median of its approving agents is strategyproof and achieves social-cost approximation ratio \(k\), with a tight example for that mechanism ([source](https://ojs.aaai.org/index.php/AAAI/article/download/33542/35697)).
No result addressing exactly the rational-mass, support-encoded problem with the clone deviations above was located.
The answer is affirmative. The prescribed lower-weighted-median rule is deterministic, clone strategyproof, and achieves the required approximation. It can be computed in
\(O\!\left((m\tau+\tau\log(\tau+1))L^2\right)\)
bit operations using elementary integer arithmetic.
The proof below establishes the support-encoded rational-mass result directly, extending the finite Max-variant guarantee in the [cited paper](https://ojs.aaai.org/index.php/AAAI/article/view/33542).
For a nonzero finitely supported measure \(\nu\) on \(\mathbb R\), let \(\operatorname{med}^{-}(\nu)\) denote its lower weighted median. For the zero measure, define \(\operatorname{med}^{-}(0)=0\).
Lemma. Suppose \(\varepsilon>0\) and \(\nu(\{x\})\ge\varepsilon\). Set \(\widehat\nu=\nu-\varepsilon\delta_x\), \(q=\operatorname{med}^{-}(\nu)\), and \(r=\operatorname{med}^{-}(\widehat\nu)\). Then
\(\lvert q-x\rvert\le\lvert r-x\rvert.\)
Proof. Write \(W=\nu(\mathbb R)\) and \(F(t)=\nu((-\infty,t])\).
If \(\widehat\nu=0\), then \(\nu\) is concentrated at \(x\), so \(q=x\) and the inequality holds. Assume henceforth that \(\widehat\nu\ne0\).
If \(q=x\), the inequality also holds immediately.
If \(q<x\), removal at \(x\) leaves both the mass at \(q\) and the cumulative mass through \(q\) unchanged. Consequently,
\(\widehat\nu((-\infty,q])=F(q)\ge W/2\ge(W-\varepsilon)/2.\)
Since \(q\) remains supported, the new lower median satisfies \(r\le q<x\). Thus \(\lvert r-x\rvert\ge\lvert q-x\rvert\).
Finally, suppose \(q>x\). By the definition of the lower median, \(F(t)<W/2\) for every \(t<q\). For such a \(t\), there are two cases.
\(\widehat\nu((-\infty,t])=F(t)-\varepsilon<W/2-\varepsilon<(W-\varepsilon)/2.\)
\(F(t)\le F(x)-\nu(\{x\})\le F(x)-\varepsilon<W/2-\varepsilon.\)
No mass is removed below \(t\), so again
\(\widehat\nu((-\infty,t])<(W-\varepsilon)/2.\)
Thus no supported location below \(q\) reaches half the new total mass. Therefore \(r\ge q>x\), which proves the inequality. \(\square\)
Clone strategyproofness. Fix any allowed \(D\), supported type \((x,A)\), and nonempty report \(B\). Put \(\varepsilon=D^{-1}\). Since \(D\mu_{x,A}\) is a positive integer, \(\varepsilon\le\mu_{x,A}\), so the deviation produces a valid society.
For each truly acceptable facility \(j\in A\), its approval marginal after the deviation is
\(\nu'_j=\nu_j\) if \(j\in B\), and \(\nu'_j=\nu_j-\varepsilon\delta_x\) if \(j\notin B\).
In the first case its position is unchanged. In the second case the lemma applies, because \(\nu_j(\{x\})\ge\mu_{x,A}\ge\varepsilon\). Hence, for every \(j\in A\),
\(\lvert M_j(\mu)-x\rvert\le\lvert M_j(\mu')-x\rvert.\)
Taking the maximum over \(A\) gives exactly
\(c_{x,A}(M(\mu))\le c_{x,A}(M(\mu')).\)
This proves clone strategyproofness for every admissible \(D\).
We first verify weighted-median optimality, including the specified tie convention.
Lemma. For every finitely supported nonnegative measure \(\nu\), its prescribed lower median minimizes
\(f(t)=\sum_s\nu(\{s\})\lvert t-s\rvert.\)
Proof. If \(\nu=0\), then \(f\) is identically zero. Otherwise let \(q=\operatorname{med}^{-}(\nu)\) and \(W=\nu(\mathbb R)\). The median definition gives
\(\nu((-\infty,q))<W/2,\qquad \nu((-\infty,q])\ge W/2.\)
For \(t>q\), every \(s\le q\) contributes a distance increase of \(t-q\), while every \(s>q\) contributes an increase at least \(-(t-q)\), by the triangle inequality. Thus
\(f(t)-f(q)\ge(t-q)\bigl(\nu((-\infty,q])-\nu((q,\infty))\bigr)\ge0.\)
For \(t<q\), every \(s\ge q\) contributes an increase of \(q-t\), and every \(s<q\) contributes an increase at least \(-(q-t)\). Consequently,
\(f(t)-f(q)\ge(q-t)\bigl(\nu([q,\infty))-\nu((-\infty,q))\bigr)\ge0.\)
The case \(t=q\) is immediate. \(\square\)
Define the auxiliary objective
\(S_\mu(y)=\sum_{(x,A)}\mu_{x,A}\sum_{j\in A}\lvert y_j-x\rvert.\)
Rearranging the finite sums yields
\(S_\mu(y)=\sum_{j=1}^{k}\sum_x\nu_j(x)\lvert y_j-x\rvert.\)
By the lemma, each coordinate \(M_j(\mu)\) minimizes its corresponding summand, including when \(\nu_j=0\). Therefore
\(S_\mu(M(\mu))\le S_\mu(z)\qquad\text{for every }z\in\mathbb R^k.\)
For each nonempty acceptable set \(A\), nonnegativity gives
\(\max_{j\in A}\lvert y_j-x\rvert\le\sum_{j\in A}\lvert y_j-x\rvert\le |A|\max_{j\in A}\lvert y_j-x\rvert.\)
Multiplying by the masses and summing, with \(|A|\le k\), gives
\(\operatorname{SC}^{\max}_\mu(y)\le S_\mu(y)\le k\operatorname{SC}^{\max}_\mu(y).\)
Combining these inequalities, for every \(z\),
\(\operatorname{SC}^{\max}_\mu(M(\mu))\le S_\mu(M(\mu))\le S_\mu(z)\le k\operatorname{SC}^{\max}_\mu(z).\)
For completeness, the minimum in the question exists. Let \(a\) and \(b\) be the smallest and largest supported agent locations. Clipping any facility coordinate to \([a,b]\) weakly decreases its distance to every supported location, and hence weakly decreases every agent’s cost. The social-cost function is continuous, so it attains its minimum on the compact set \([a,b]^k\). Applying the preceding inequality to a minimizer proves the required guarantee.
Index the supported types by \(i\in\{1,\ldots,\tau\}\), and write their masses as \(\mu_i=a_i/b_i\), with positive binary integers \(a_i,b_i\). Define
\(Q=\prod_{i=1}^{\tau}b_i,\qquad w_i=a_i(Q/b_i).\)
These are exact integer weights, and \(\sum_iw_i=Q\). The bit length of \(Q\) is \(O(L)\), because the total denominator encoding length is at most \(L\). Every weight and every partial sum is also an \(O(L)\)-bit integer.
The algorithm is:
Types at the same location may appear in any order: the first threshold crossing still outputs that location. Thus the algorithm implements precisely the required lower weighted median.
Using schoolbook arithmetic, scaling the masses costs \(O(\tau L^2)\) bit operations. Sorting uses \(O(\tau\log(\tau+1))\) rational comparisons, each costing \(O(L^2)\) by cross multiplication. Constructing facility memberships and performing the scans costs \(O(m\tau L+L)\). The resulting bound is
\(O\!\left((m\tau+\tau\log(\tau+1))L^2\right).\)
All outputs are supported input locations or zero. No enumeration of possible types or expansion into individual clones is required.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task. The prescribed rule is deterministic, clone strategyproof, computable in polynomial time in \(m,\tau,L\), and satisfies the required \(k\)-approximation guarantee. No major or minor issues were found.
The removal lemma is valid in every case.
\[
F(t)\le F(x)-\nu(\{x\})\le F(x)-\varepsilon<W/2-\varepsilon
\]
is valid because \(x<q\). Hence no remaining supported location below \(q\) reaches the new threshold, so \(r\ge q>x\).
Both ordering conclusions give the required distance inequality. The proof handles threshold ties and disappearance of all approval mass.
The quantifiers match the task: the proof fixes an arbitrary admissible \(D\), supported type, and nonempty report.
Because \(D\mu_{x,A}\) is a positive integer, \(\varepsilon=D^{-1}\le\mu_{x,A}\). The deviation therefore preserves nonnegative masses and total mass one. Types whose mass becomes zero can simply be omitted from the support.
For each \(j\in A\), the marginal either remains unchanged or loses exactly \(\varepsilon\delta_x\). The removal lemma applies in the latter case because \(\nu_j(\{x\})\ge\mu_{x,A}\). Thus every truly acceptable facility’s distance weakly increases. Taking the maximum preserves the inequality.
Facilities newly approved outside \(A\) do not enter the deviator’s true cost. No case is missing.
The optimality lemma is proved directly and correctly.
For a nonzero measure, the specified lower median satisfies both
\(\nu((-\infty,q))<W/2\) and \(\nu((-\infty,q])\ge W/2\). These give the required signs in the two displayed bounds for \(f(t)-f(q)\). The distance bounds used for points on the opposite side follow from the triangle inequality.
The zero measure is explicitly covered. Consequently, each prescribed coordinate minimizes its corresponding absolute-distance objective, including unapproved facilities.
The rearrangement defining the separable objective \(S_\mu\) is valid because all sums are finite. Coordinatewise optimality therefore establishes \(S_\mu(M(\mu))\le S_\mu(z)\) for every real vector \(z\).
For every nonempty \(A\), the maximum–sum inequalities are correct. Multiplication by nonnegative masses and \(|A|\le k\) give the claimed comparison between \(S_\mu\) and social cost. The resulting chain proves the bound against every \(z\).
The minimum-existence argument also checks out:
Thus the minimum is attained, and applying the bound to a minimizer is justified. Zero optimal cost and coincident facility positions cause no exception.
The integer scaling is exact: each denominator divides \(Q\), and normalization gives \(\sum_i w_i=Q\). The product’s bit length is bounded by the total denominator encoding length, hence is \(O(L)\). Positivity and normalization also bound every weight and partial sum by \(Q\).
Sorting by rational cross multiplication is exact and costs \(O(L^2)\) per comparison with schoolbook arithmetic. Computing the product, exact quotients, and weights fits the stated \(O(\tau L^2)\) bound.
The sorted scans implement the lower weighted median. Repeated locations do not change the returned location, even if the threshold is crossed partway through their entries. Zero approval mass receives the required output zero.
The membership processing, scans, and output fit the stated overall bound
\(O((m\tau+\tau\log(\tau+1))L^2)\). The procedure depends on the supplied support and does not expand rational masses into clones.
The cited paper is background only; no external theorem from it is needed for the proof.
None. The write-up establishes all assigned requirements without an unresolved step.
⟨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.