Answer: Both properties hold in the stated mass-splitting model. The exact worst-case approximation ratio is \(1/3\). For \(m=1\), the specified exact algorithm uses \(O(\tau)\) arithmetic operations, \(O(L^2)\) bit operations, and \(O(L)\) working space under standard binary rational encoding.
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe approximation ratio for the social util- ity of Mechanism 2 is 1 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(l>0\) and a finite-support rational society \(\mu\) over types \(t=(x,p)\in[0,l]\times\{0,1\}\), set \(z_t=x\) when \(p=0\), \(z_t=l-x\) when \(p=1\), and \(a=\sum_{t:z_t<l/2}\mu_t\). Let \(F(\mu)=0\) if \(a\le 1/2\), and \(F(\mu)=l\) otherwise, extending this rule to reported finite-support real-mass distributions so deviations are defined. Prove or refute that \(F\) is group-strategyproof against every positive-mass coalition whose members may reassign their reports and that \(U(F(\mu);\mu)\ge \frac13\max_{y\in[0,l]}U(y;\mu)\) for every rational input; give the exact algorithm and its bit complexity.
Let \(l>0\) be a binary rational. A society is given by its support: the list of \(\tau\) types \(t=(x,p)\in[0,l]\times\{0,1\}\) with positive binary-rational masses \(\mu_t\), summing to \(1\); locations are binary rational. Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is one facility, so \(m=1\).
For \(y\in[0,l]\), define \(u((x,0),y)=|x-y|\), \(u((x,1),y)=l-|x-y|\), and \(U(y;\mu)=\sum_t\mu_tu(t,y)\). Both location and preference may be misreported.
Set \(z_{(x,0)}=x\), \(z_{(x,1)}=l-x\), and \(a=\sum_{t:z_t<l/2}\mu_t\). Define \(F(\mu)=0\) when \(a\le1/2\), and \(F(\mu)=l\) otherwise; use the same rule for finite-support distributions with real locations and real masses.
A coalition is a submass \(0\le\gamma_t\le\mu_t\) with \(\sum_t\gamma_t>0\). It may split its mass among arbitrary finitely many reports in \([0,l]\times\{0,1\}\), preserving total mass; the resulting distribution is \(\mu'=\mu-\gamma+\nu\). Group strategyproofness means that no such deviation satisfies \(u(t,F(\mu'))>u(t,F(\mu))\) for every \(t\) with \(\gamma_t>0\).
Does \(F\) remain group strategyproof and satisfy \(U(F(\mu);\mu)\ge\frac13\max_{y\in[0,l]}U(y;\mu)\) for every rational society, or does either property fail?
What exact algorithm computes \(F\), and what is its bit complexity in \(m=1\), \(\tau\), and \(L\)?
For finite lists of agents, this endpoint rule is group strategyproof and guarantees a social-utility approximation ratio of \(1/3\). [Zou and Li](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p615.pdf)
No result for exactly the mass-splitting model above was located in the search.
Both properties hold: \(F\) is group strategyproof in the stated mass-splitting model, and its worst-case social-utility approximation ratio is exactly \(1/3\).
For \(m=1\), an exact implementation uses \(O(\tau)\) arithmetic operations and, with schoolbook integer arithmetic, \(O(L^2)\) bit operations and \(O(L)\) working space.
The finite-agent counterpart is Mechanism 2 in [Zou and Li, Theorems 3 and 6](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p615.pdf). The proofs below establish the claims directly for the stated model, including deviations with real masses and real report locations.
For every type \(t=(x,p)\), the definition of \(z_t\) gives
\(\displaystyle u(t,0)=z_t,\qquad u(t,l)=l-z_t.\)
Consequently,
\(\displaystyle u(t,l)>u(t,0)\iff z_t<l/2,\)
\(\displaystyle u(t,0)>u(t,l)\iff z_t>l/2.\)
Types with \(z_t=l/2\) are indifferent between the endpoints.
Let \(A\) be the set of all report types satisfying \(z_t<l/2\). For any finite-support mass distribution \(\rho\), write \(\rho(A)\) for its total mass on \(A\). Thus \(a=\mu(A)\).
Consider any admissible coalition \(\gamma\) and report distribution \(\nu\). Set
\(\displaystyle c=\sum_t\gamma_t>0.\)
Mass preservation means \(\nu\) has total mass \(c\). For the resulting society \(\mu'=\mu-\gamma+\nu\),
\(\displaystyle a'=\mu'(A)=a-\gamma(A)+\nu(A),\qquad 0\le \nu(A)\le c.\)
If \(F(\mu')=F(\mu)\), no coalition member strictly improves. It therefore suffices to exclude a change of endpoint that strictly benefits every participating type.
Case \(F(\mu)=0\). Here \(a\le 1/2\). If every participating type strictly benefited from switching to \(l\), Section 1 would imply that every such type lies in \(A\). Hence \(\gamma(A)=c\), and
\(\displaystyle a'=a-c+\nu(A)\le a\le 1/2.\)
The rule therefore still outputs \(0\), a contradiction.
Case \(F(\mu)=l\). Here \(a>1/2\). If every participating type strictly benefited from switching to \(0\), each would satisfy \(z_t>l/2\). Thus \(\gamma(A)=0\), and
\(\displaystyle a'=a+\nu(A)\ge a>1/2.\)
The rule therefore still outputs \(l\), again a contradiction.
These cases exhaust all possible changes of output. The argument uses only nonnegativity and mass preservation, so it applies to arbitrary finite splitting among real reports with real masses. This proves group strategyproofness under the definition in the question.
We first prove an endpoint estimate valid for either preference.
Fix an endpoint \(e\in\{0,l\}\), a location \(y\in[0,l]\), and a type \(t\). Define
\(\displaystyle c_t=u(t,e),\qquad d=|y-e|.\)
Then
\[\displaystyle u(t,y)\le c_t+d,\qquad u(t,y)\le 2l-c_t-d. \tag{1}\]
To verify both inequalities, first take \(e=0\), so \(d=y\).
For \(p=0\), we have \(c_t=x\). The first inequality follows from \(|x-y|\le x+y\). For the second,
\(\displaystyle |x-y|+x+y=2\max\{x,y\}\le 2l.\)
For \(p=1\), we have \(c_t=l-x\). Using respectively \(|x-y|\ge x-y\) and \(|x-y|\ge y-x\) gives
\(\displaystyle l-|x-y|\le l-x+y=c_t+d,\)
\(\displaystyle l-|x-y|\le l+x-y=2l-c_t-d.\)
For \(e=l\), reflect both \(x\) and \(y\) about \(l/2\). This preserves their distance and either preference’s utility, and converts the chosen endpoint to \(0\). Thus the same inequalities hold.
Now take \(e=F(\mu)\), and put
\(\displaystyle S=U(e;\mu),\qquad H=\{t:c_t\ge l/2\},\qquad b=\sum_{t\in H}\mu_t.\)
The mechanism guarantees \(b\ge 1/2\):
Since all utilities are nonnegative,
\[\displaystyle S\ge b\,l/2. \tag{2}\]
For types outside \(H\), the first inequality in (1) gives
\(\displaystyle u(t,y)\le c_t+d.\)
For types in \(H\), the second inequality in (1), together with \(2c_t\ge l\), gives
\(\displaystyle u(t,y)\le 2l-c_t-d\le c_t+l-d.\)
Multiplying these inequalities by the masses and summing yields
\(\displaystyle U(y;\mu)\le S+(1-b)d+b(l-d)=S+bl+(1-2b)d.\)
Because \(b\ge 1/2\) and \(d\ge 0\), the last term is nonpositive. Equation (2) gives \(bl\le 2S\). Therefore, for every \(y\in[0,l]\),
\(\displaystyle U(y;\mu)\le S+bl\le 3S.\)
The function \(U\) is continuous, being a finite sum of continuous utilities, so it attains its maximum on \([0,l]\). Consequently,
\(\displaystyle U(F(\mu);\mu)\ge \frac13\max_{y\in[0,l]}U(y;\mu).\)
This proof also applies to finite-support societies with real locations and masses.
Give each of the two types \((0,0)\) and \((l/2,0)\) mass \(1/2\). These are admissible rational data whenever \(l\) is rational.
Only the first type belongs to \(A\), so \(a=1/2\) and \(F(\mu)=0\). The resulting utility is
\(\displaystyle U(0;\mu)=\frac12\cdot 0+\frac12\cdot\frac l2=\frac l4.\)
For an arbitrary facility location,
\(\displaystyle U(y;\mu)=\frac12y+\frac12|l/2-y|.\)
This equals \(l/4\) when \(y\le l/2\), and equals \(y-l/4\) when \(y\ge l/2\). Its maximum is therefore \(3l/4\), attained at \(y=l\). Hence
\(\displaystyle \frac{U(F(\mu);\mu)}{\max_y U(y;\mu)}=\frac13.\)
Thus \(1/3\) is the exact worst-case ratio of this rule.
Use the standard binary encoding of rationals by a binary numerator and positive binary denominator. Write
\(\displaystyle l=r/s,\qquad x_t=c_t/d_t,\qquad \mu_t=h_t/k_t.\)
Here the symbols \(c_t\) are location numerators, independently of their use in Section 3.
Scan the support once. Membership in \(A\) can be determined without computing transformed locations:
\(\displaystyle t\in A\iff \begin{cases} 2c_ts<rd_t,&p_t=0,\\ 2c_ts>rd_t,&p_t=1. \end{cases}\)
Equality is excluded in both cases, as required by the strict midpoint test.
Maintain an unreduced rational accumulator \(N/D\), initially \(0/1\). For each type belonging to \(A\), update simultaneously
\(\displaystyle (N,D)\leftarrow (Nk_t+h_tD,\;Dk_t).\)
This preserves the invariant that \(N/D\) is the total mass of the selected types processed so far. At termination, output \(0\) if \(2N\le D\), and output \(l\) otherwise. The invariant proves that this algorithm computes \(F\) exactly, including the tie case.
There are \(O(\tau)\) arithmetic operations. Their bit complexity is polynomial despite the unreduced fractions:
Location comparisons. Let \(b_l\) be the encoding length of \(l\), and \(b_{x_t}\) that of \(x_t\). Schoolbook multiplication and integer comparison cost \(O(b_l b_{x_t})\) per type, including linear overhead. Summing over the support gives
\(\displaystyle O\!\left(b_l\sum_t b_{x_t}\right)=O(L^2).\)
Mass accumulation. The denominator is a product of processed mass denominators, so its bit length is \(O(L)\). Every partial selected mass lies in \([0,1]\); hence \(0\le N\le D\), and the numerator also has \(O(L)\) bits.
More precisely, if the selected mass encodings have lengths \(b_1,\ldots,b_q\), an update costs
\(\displaystyle O\!\left(\left(1+\sum_{j<i}b_j\right)b_i\right).\)
Summing these costs gives \(O(L^2)\), since \(\sum_i b_i\le L\). The final comparison costs \(O(L)\).
Thus, for \(m=1\), the specified exact algorithm takes \(O(\tau)\) arithmetic operations, \(O(L^2)\) bit operations, and \(O(L)\) working space. It operates on support masses directly; expanding rational masses into individual agents is unnecessary.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. Both substantive proofs are rigorous, the tight example is valid, and the exact algorithm has the claimed bit complexity. No major or minor mathematical issues were found.
The identities \(u(t,0)=z_t\) and \(u(t,l)=l-z_t\) follow directly from both utility definitions. Their difference is \(l-2z_t\), so the strict endpoint-preference conditions are correct.
The midpoint case \(z_t=l/2\) is explicitly handled: such types are indifferent and therefore cannot participate in a deviation that strictly benefits every participating type by changing endpoints. The definition of \(A\) correctly excludes these types.
For every admissible deviation, the identity
\[
a'=a-\gamma(A)+\nu(A)
\]
is valid by additivity of mass. The bound \(0\le\nu(A)\le c\) follows from nonnegativity and preservation of the coalition’s total mass.
If the output remains unchanged, all participating types retain exactly the same utility. Thus restricting attention to changes of endpoint is exhaustive.
When the original output is \(0\), strict improvement by every participating type requires all coalition mass to come from \(A\). Hence \(\gamma(A)=c\), and the displayed bound \(a'\le a\le1/2\) prevents the output from changing to \(l\). The equality case is handled correctly by the mechanism’s tie rule.
When the original output is \(l\), strict improvement by every participating type requires \(z_t>l/2\), so \(\gamma(A)=0\). Consequently \(a'\ge a>1/2\), preventing a change to \(0\).
These arguments cover arbitrary admissible submasses and arbitrary finite splitting. They impose no rationality requirement on deviating reports or their masses. The conclusion matches the task’s definition, which requires strict improvement for every participating type.
Both inequalities in equation (1) are valid throughout the stated domains.
For \(e=0\) and \(p=0\), the triangle inequality establishes the first bound. The identity
\[
|x-y|+x+y=2\max\{x,y\}
\]
establishes the second because \(x,y\in[0,l]\).
For \(e=0\) and \(p=1\), the two lower bounds on \(|x-y|\) give exactly the two displayed upper bounds. The signs and constants are correct.
The reflection argument for \(e=l\) is legitimate: reflecting the type’s location and the facility location preserves their distance, keeps the preference unchanged, and maps the selected endpoint to \(0\). It also preserves the quantities used in the inequalities.
The mass bound \(b\ge1/2\) is correct in both output cases. For output \(0\), \(H\) is precisely the complement of \(A\). For output \(l\), \(H\) includes \(A\) and all midpoint types. Thus midpoint mass is treated consistently.
Nonnegative utilities imply \(S\ge bl/2\). For types in \(H\), the comparison
\[
2l-c_t-d\le c_t+l-d
\]
is equivalent to \(2c_t\ge l\), which holds by definition of \(H\).
Summing the two bounds over \(H\) and its complement correctly produces
\[
U(y;\mu)\le S+bl+(1-2b)d.
\]
Here the complement has mass \(1-b\) because the society has total mass \(1\). Since \(b\ge1/2\) and \(d\ge0\), dropping the last term preserves the upper bound. The earlier estimate gives \(bl\le2S\), establishing \(U(y;\mu)\le3S\) for every feasible \(y\).
The maximum exists: the utility is continuous, and \([0,l]\) is compact and nonempty. All hypotheses for this standard maximum-attainment fact are present. Moreover, \(S\ge l/4>0\), so the approximation ratio has no zero-denominator issue.
The proposed society has two distinct valid support types, positive masses summing to \(1\), and binary-rational data whenever \(l\) is binary rational. In particular, \(l/2\) remains binary rational.
Exactly one type belongs to \(A\), giving \(a=1/2\) and output \(0\). The stated utility \(l/4\) is correct. The two expressions for \(U(y;\mu)\) agree at \(y=l/2\), and its maximum is \(3l/4\) at \(y=l\). The ratio is therefore exactly \(1/3\). Combined with the universal bound, this establishes the claimed worst-case ratio.
With positive denominators, the cross-multiplication tests are equivalent to the strict midpoint conditions. The reversed inequality for preference \(1\) is correct. Equality is excluded as required.
The simultaneous accumulator update computes
\[
\frac{Nk_t+h_tD}{Dk_t}=\frac ND+\frac{h_t}{k_t}.
\]
Its invariant and final comparison therefore implement the mechanism exactly, including the tie case.
The arithmetic-operation count is \(O(\tau)\). The schoolbook location-comparison bounds sum to \(O(L^2)\), including repeated use of the encoding of \(l\).
The unreduced denominator has bit length bounded by the sum of processed denominator lengths. Every partial selected mass is at most \(1\), so its numerator satisfies \(0\le N\le D\). Both accumulator integers consequently have \(O(L)\) bits.
The stated per-update multiplication and addition bound is valid. Summing it gives \(O(L^2)\), and the final comparison and output fit within that bound. Standard schoolbook arithmetic can perform these operations with \(O(L)\) working space. Thus all three complexity claims hold under the explicitly stated numerator–denominator encoding.
The attribution is accurate: Mechanism 2 uses the same transformed-location test and tie rule, while Theorems 3 and 6 state its finite-agent group strategyproofness and approximation ratio. [Zou and Li](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p615.pdf)
The prover does not use those finite-agent theorems to infer the mass-splitting result; it supplies direct proofs for the assigned model. No unverified transfer between models remains.
No additional mathematical clarification or repair is needed.
⟨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.