Answer: \(F\) is false-name-proof on the stated rational-mass domain, and \(R(M)=M/2\) for every rational \(M\ge 2\); the supremum is attained.
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe left-right-middle mechanism is false- name-proof and has an approximation ratio of n/2 for social cost.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For a finite-support rational mass measure \(\rho\) on \(\mathbb R\), with total mass \(M\ge2\) and every positive type mass at least \(1\), apply the left-right-middle lottery to the support endpoints and their midpoint with probabilities \(1/4,1/4,1/2\). Against deviations in which one resident replaces their truthful unit report by any finite set of unit identity reports, is this mechanism false-name-proof, and is its exact worst-case ratio of expected social cost to the optimum weighted social cost \(M/2\)?
A society is given by its support: \(\rho=\sum_{j=1}^{\tau}w_j\delta_{x_j}\), with distinct locations \(x_j\in\mathbb R\), positive binary-rational masses \(w_j\ge1\), and total mass \(M=\sum_jw_j\ge2\), without normalization. Here \(\tau\) is the support size, not the number of possible types.
For computational claims, locations are also encoded as binary rationals; state running times in \(\tau\), total input bit length \(L\), and any additional parameters. There is no candidate-count parameter \(m\).
For every nonzero finite positive report measure \(\mu\), let \(F(\mu)\) select its support minimum, support maximum, and their midpoint with probabilities \(1/4,1/4,1/2\), respectively; coincident outcomes have their probabilities combined.
A resident at \(x\in\operatorname{supp}\rho\) may replace one truthful unit report by a nonempty finite multiset of unit reports at arbitrary real locations \(z_1,\ldots,z_k\), producing \(\rho'=\rho-\delta_x+\sum_{\ell=1}^{k}\delta_{z_\ell}\). Reports need not include \(x\); the remaining report measure stays fixed, and \(\rho'\) need not satisfy the truthful mass restrictions.
False-name-proofness means \(\mathbb E_{Y\sim F(\rho)}|x-Y|\le\mathbb E_{Y\sim F(\rho')}|x-Y|\) for every such deviation. Define \(C_\rho(y)=\sum_jw_j|x_j-y|\), \(\operatorname{OPT}(\rho)=\min_{y\in\mathbb R}C_\rho(y)\), and \(R(M)=\sup_{\rho:\,\rho(\mathbb R)=M,\,\operatorname{OPT}(\rho)>0}\mathbb E_{Y\sim F(\rho)}C_\rho(Y)/\operatorname{OPT}(\rho)\), over the specified truthful domain.
Is \(F\) false-name-proof on this mass domain, and is \(R(M)=M/2\) for every rational \(M\ge2\)?
For finite societies of \(n\ge2\) unit agents, left-right-middle is false-name-proof and has exact worst-case social-cost ratio \(n/2\); every randomized false-name-proof mechanism has social-cost ratio \(\Omega(n)\). [Source](https://www.ifaamas.org/Proceedings/aamas2011/papers/B5_G62.pdf)
No result settling this precise rational-mass model was located in the literature search.
Both statements hold: \(F\) is false-name-proof, and \(R(M)=M/2\) for every rational \(M\ge 2\). The supremum is attained.
Here “binary-rational” means a rational represented by binary-encoded numerator and denominator, consistently with the question’s quantifier over every rational total mass. If it instead means a dyadic rational, the result holds for every admissible dyadic total mass; other total masses have no admissible societies.
The unit-agent analogue is Theorem 6 of [Todo, Iwasaki, and Yokoo](https://aamas.csc.liv.ac.uk/Proceedings/aamas2011/papers/B5_G62.pdf). We prove the stated mass version directly.
For real numbers \(u\le v\), define the expected distance of a resident at \(x\) under the endpoint-and-midpoint lottery by
\(H_x(u,v)=\frac14|x-u|+\frac14|x-v|+\frac12\left|x-\frac{u+v}{2}\right|=\frac{|x-u|+|x-v|+|2x-u-v|}{4}.\)
This formula remains valid when \(u=v\), since coincident outcomes have their probabilities combined.
The reverse triangle inequality gives
\(|2x-u-v|=|(x-u)+(x-v)|\ge \bigl||x-u|-|x-v|\bigr|.\)
Consequently,
\(H_x(u,v)\ge \frac{|x-u|+|x-v|+\bigl||x-u|-|x-v|\bigr|}{4}=\frac12\max\{|x-u|,|x-v|\}.\)
If \(x\in[u,v]\), the two quantities \(x-u\) and \(x-v\) have opposite signs, so this inequality is an equality:
\(H_x(u,v)=\frac12\max\{x-u,v-x\}.\)
Furthermore, for every \(t\in[u,v]\),
\(|x-t|\le \max\{|x-u|,|x-v|\}.\)
Indeed, when \(u<v\), write \(t=(1-\lambda)u+\lambda v\), where \(\lambda\in[0,1]\), and apply the triangle inequality. When \(u=v\), the assertion is immediate. Thus we have proved
\(H_x(u,v)\ge \frac12|x-t|\qquad\text{for every }t\in[u,v].\)
Fix an admissible society \(\rho\) and a resident location \(x\in\operatorname{supp}\rho\). Since the mass at \(x\) is at least one, \(\rho-\delta_x\) is a nonnegative measure. Every allowed deviation produces a nonzero measure with finite support.
If the truthful support has only one location, the resident’s truthful expected distance is zero. No deviation can improve upon zero.
Now suppose the truthful support has at least two locations. Let
\(a=\min\operatorname{supp}\rho,\qquad b=\max\operatorname{supp}\rho.\)
Choose \(t\in\{a,b\}\) satisfying
\(|x-t|=\max\{x-a,b-x\}.\)
Because \(a<b\), this maximum is positive, so \(t\ne x\). Removing one unit at \(x\) therefore leaves the entire positive mass at \(t\) unchanged.
Consider any allowed deviation
\(\rho'=\rho-\delta_x+\sum_{\ell=1}^{k}\delta_{z_\ell},\qquad k\ge 1,\)
and denote its support endpoints by \(A\le B\). The unchanged mass at \(t\) implies \(t\in[A,B]\). Applying the lemma to the deviating lottery, and its equality formula to the truthful lottery, gives
\(\mathbb E_{Y\sim F(\rho')}|x-Y|=H_x(A,B)\ge \frac12|x-t|=H_x(a,b)=\mathbb E_{Y\sim F(\rho)}|x-Y|.\)
This applies to every finite collection of real reports, including deviations that omit \(x\). Hence \(F\) is false-name-proof on the stated domain.
Fix an admissible society with \(\operatorname{OPT}(\rho)>0\). Its support has at least two locations. Write
\(a=\min\operatorname{supp}\rho,\qquad b=\max\operatorname{supp}\rho,\qquad D=b-a>0,\qquad c=\frac{a+b}{2}.\)
An optimum exists: projection onto \([a,b]\) weakly decreases every distance to a support location, and \(C_\rho\) is continuous on this compact interval.
For every support location \(x_j\in[a,b]\),
\(|x_j-a|+|x_j-b|=D,\qquad |x_j-c|\le D/2.\)
Multiplying by the masses and summing yields
\(C_\rho(a)+C_\rho(b)=MD,\qquad C_\rho(c)\le MD/2.\)
Therefore,
\(\mathbb E_{Y\sim F(\rho)}C_\rho(Y)=\frac14\bigl(C_\rho(a)+C_\rho(b)\bigr)+\frac12C_\rho(c)\le MD/2.\)
Let \(w_a,w_b\) denote the masses at the two endpoints. The truthful-domain restriction gives \(w_a,w_b\ge 1\). For every real \(y\),
\(C_\rho(y)\ge w_a|a-y|+w_b|b-y|\ge |a-y|+|b-y|\ge D,\)
where the final inequality is the triangle inequality. Taking the minimum gives \(\operatorname{OPT}(\rho)\ge D\). Thus
\(\frac{\mathbb E_{Y\sim F(\rho)}C_\rho(Y)}{\operatorname{OPT}(\rho)}\le \frac{MD/2}{D}=M/2.\)
For any rational \(M\ge 2\), consider
\(\rho_M=(M-1)\delta_0+\delta_1.\)
Both masses are rational and at least one, and the total mass is \(M\). The endpoint lower bound just proved gives \(\operatorname{OPT}(\rho_M)\ge 1\), while \(C_{\rho_M}(0)=1\). Hence \(\operatorname{OPT}(\rho_M)=1\).
The three outcome costs are
\(C_{\rho_M}(0)=1,\qquad C_{\rho_M}(1)=M-1,\qquad C_{\rho_M}(1/2)=M/2.\)
Consequently,
\(\mathbb E_{Y\sim F(\rho_M)}C_{\rho_M}(Y)=\frac14+\frac{M-1}{4}+\frac12\frac M2=M/2.\)
This admissible two-location society attains the upper bound. Therefore \(R(M)=M/2\) for every rational \(M\ge 2\).
For a truthful input of support size \(\tau\) and total bit length \(L\), computing \(F(\rho)\) requires scanning the locations for their minimum and maximum, then computing their midpoint. This uses \(O(\tau)\) rational comparisons and \(O(\tau L^2)\) bit operations with schoolbook arithmetic.
Given a binary-encoded rational \(M\) of bit length \(B\), both \(R(M)=M/2\) and the attaining society \((M-1)\delta_0+\delta_1\) can be constructed in \(O(B^2)\) bit operations, with output length \(O(B)\). No population expansion is required.
⟨structured verdict parsed — rendered above⟩
The prover’s two claims are proved under its explicitly stated encoding convention. The argument covers every allowed deviation and every rational total mass \(M\ge2\). No major or minor mathematical issues were found.
Interpreting “binary-rational” as a rational with binary-encoded numerator and denominator is explicit and consistent with the task’s quantifier over every rational \(M\). The alternative dyadic interpretation is correctly distinguished: a finite sum of dyadic masses cannot have a nondyadic total mass.
Every truthful society and every allowed deviating report measure has finite, nonempty support, so the endpoints used throughout the proof exist.
The identity
\(H_x(u,v)=(|x-u|+|x-v|+|2x-u-v|)/4\)
correctly incorporates the midpoint’s probability.
The reverse triangle inequality applies to \(x-u\) and \(x-v\). The subsequent identity uses the valid formula
\(p+q+|p-q|=2\max\{p,q\}\)
for nonnegative \(p,q\). Thus the asserted lower bound is correct for every real \(x\) and every \(u\le v\).
When \(x\in[u,v]\), the two differences have opposite signs or one is zero. Consequently, equality in the stated reverse-triangle bound holds, including endpoint and coincident-endpoint cases.
The convex-combination argument correctly bounds \(|x-t|\) for every \(t\in[u,v]\). The separate treatment of \(u=v\) avoids division by zero. The lemma is fully established.
The restriction \(w_x\ge1\) ensures that subtracting \(\delta_x\) leaves a nonnegative measure. Adding a nonempty multiset gives a nonzero measure with finite support.
For singleton truthful support, truthful expected distance is zero, and every deviating expected distance is nonnegative.
For nonsingleton support, a farthest truthful endpoint \(t\) exists. Its distance from \(x\) is positive, so \(t\ne x\). Removing a unit at \(x\) therefore leaves the mass at \(t\) unchanged; adding positive reports cannot remove it. Hence \(t\in[A,B]\), regardless of whether the deviation retains a report at \(x\).
Both uses of the lemma satisfy their hypotheses: \(t\in[A,B]\) gives the deviating lower bound, while \(x\in[a,b]\) gives the truthful equality. The resulting inequality has exactly the direction required by false-name-proofness. It applies to arbitrary real report locations, repeated reports, and every finite \(k\ge1\).
Positive optimal cost excludes singleton support, so \(D=b-a>0\).
Projection onto \([a,b]\) weakly decreases each distance to a truthful support location. Continuity on that compact interval therefore establishes existence of an optimum.
The endpoint-distance identity and midpoint-distance bound hold pointwise on \([a,b]\). Multiplication by positive masses and summation correctly give
\(C_\rho(a)+C_\rho(b)=MD\)
and
\(C_\rho(c)\le MD/2\).
The lottery probabilities then yield expected cost at most \(MD/2\).
The optimum lower bound correctly retains the contributions of two distinct endpoints. Their masses are at least one, and the triangle inequality gives
\(C_\rho(y)\ge D\)
for every real \(y\). Dividing by the positive optimum proves the claimed ratio bound \(M/2\). No normalization or integrality assumption is used.
For every rational \(M\ge2\), the proposed society has distinct rational locations, admissible rational masses \(M-1\ge1\) and \(1\), and total mass \(M\).
The previously established lower bound gives optimum at least one, and the cost at zero is exactly one. All three displayed outcome costs are correct. Their weighted sum is \(M/2\), so this society attains the upper bound.
The case \(M=2\) is included: both masses equal one, and the attained ratio is one. Thus the argument establishes a maximum, not merely an approached supremum.
Scanning for the two endpoints requires \(O(\tau)\) rational comparisons. Cross multiplication compares binary-encoded rationals in \(O(L^2)\) bit operations using schoolbook arithmetic; midpoint computation involves integers of \(O(L)\) bits. The stated \(O(\tau L^2)\) bound is valid, though coarse.
Subtracting one from \(M\) and dividing \(M\) by two produce representations of \(O(B)\) bits within the claimed \(O(B^2)\) time. No population expansion or candidate-count parameter is needed.
The historical attribution is accurate: [Theorem 6 of the cited paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2011/papers/B5_G62.pdf) states the unit-agent analogue. The rational-mass argument is proved directly and does not depend on transferring that theorem to fractional masses.
Repair feedback: None is required. The polynomial classification below concerns the explicitly proved computations of \(F(\rho)\), \(R(M)\), and an attaining society.
⟨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.