Answer: For \(T=3\), \(\rho_T(\delta)=1/(2\delta)\) when \(0<\delta\le1/4\), and \(\rho_T(\delta)=1/\delta-2\) when \(1/4<\delta\le1/3\). For \(T\ge4\), the successive formulas are \(3/(4\delta)-1\) on \(0<\delta\le1/6\), \(1/\delta-5/2\) on \(1/6<\delta<1/5\), \(1/(2\delta)\) on \(1/5\le\delta\le1/4\), and \(1/\delta-2\) on \(1/4<\delta\le1/3\). The supremum is not attained exactly when \(T\ge4\) and \(0<\delta\le1/6\).
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMedianFurthest is 3 4n–approximate.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For feasible \(\tau\ge 3\) and rational \(\delta>0\), let \(S\subseteq\mathbb{Q}\) have \(3\le |S|\le\tau\), and let \(\mu\) be a rational distribution on \(S\) with \(\mu_x\ge\delta\) for every \(x\in S\). Let \(q_\mu\) be the lower weighted median, \(a=\min S\), and \(b=\max S\); define the mass version of MedianFurthest to return \(\{q_\mu,a\}\) when \(q_\mu-a>b-q_\mu\), and \(\{q_\mu,b\}\) otherwise. Determine the exact value of \(\rho_\tau(\delta)=\sup_\mu \frac{\sum_{x\in S}\mu_x\min_{f\in\mathrm{MF}(\mu)}|x-f|}{\min_{p,q\in\mathbb{R}}\sum_{x\in S}\mu_x\min\{|x-p|,|x-q|\}}\), and give rational distributions attaining or approaching the supremum.
A society is given by its support: a list of \(\tau\) distinct rational locations with positive masses encoded as binary rationals; \(\tau\) is the actual support size, not the number of possible types. Write \(T\) for the support-size cap. Fix an integer \(T\ge3\) and rational \(0<\delta\le1/3\); admissible societies satisfy \(3\le\tau\le T\), \(S\subseteq\mathbb Q\), \(\sum_{x\in S}\mu_x=1\), and \(\mu_x\ge\delta\).
There are \(m=2\) facilities on the real line. Let \(L\) be the total binary input length; state any running times in \(m,\tau,L,T\). Locations may have either sign.
Define \(q_\mu=\min\{x\in S:\sum_{y\in S,\,y\le x}\mu_y\ge1/2\}\), \(a=\min S\), and \(b=\max S\). MedianFurthest returns \(\mathrm{MF}(\mu)=\{q_\mu,a\}\) if \(q_\mu-a>b-q_\mu\), and \(\{q_\mu,b\}\) otherwise.
For a facility set \(F\), let \(C_\mu(F)=\sum_{x\in S}\mu_x\min_{f\in F}|x-f|\) and \(\mathrm{OPT}(\mu)=\min_{p,q\in\mathbb R}C_\mu(\{p,q\})\). Nearest-facility ties do not affect cost; the support restriction ensures \(\mathrm{OPT}(\mu)>0\).
What is the exact worst-case approximation ratio \(\rho_T(\delta)=\sup_{(S,\mu)\text{ admissible}}C_\mu(\mathrm{MF}(\mu))/\mathrm{OPT}(\mu)\), and which rational societies attain it or approach it when it is not attained?
For a finite list of \(n\) agents, MedianFurthest has a proved approximation guarantee of \(3n/4\), using the lower median and choosing the right endpoint on an endpoint-distance tie. [Source](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p68.pdf)
No result settling this exact mass-based worst-case ratio was located in the literature search.
The support cap matters only through whether three or four support points are allowed.
For \(T=3\), the supremum is always attained and equals:
| Mass floor | \(\rho_3(\delta)\) |
|---|---:|
| \(0<\delta\le1/4\) | \(1/(2\delta)\) |
| \(1/4<\delta\le1/3\) | \(1/\delta-2\) |
For every \(T\ge4\), the answer is:
| Mass floor | \(\rho_T(\delta)\) | Attainment |
|---|---:|---|
| \(0<\delta\le1/6\) | \(3/(4\delta)-1\) | Not attained |
| \(1/6<\delta<1/5\) | \(1/\delta-5/2\) | Attained |
| \(1/5\le\delta\le1/4\) | \(1/(2\delta)\) | Attained |
| \(1/4<\delta\le1/3\) | \(1/\delta-2\) | Attained |
All attaining examples and approaching sequences below have rational locations and masses. A characterization of all attaining societies is also given.
For context, the finite-agent \(3n/4\) guarantee quoted in the question appears as [Theorem 6 of Ferraioli–Serafino–Ventre](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p68.pdf). The following proof is self-contained.
Let \(q=q_\mu\), and let \(e\) be the endpoint selected by MedianFurthest. The endpoint \(e\) differs from \(q\), since the support contains at least three points.
Apply the rational affine transformation \(x\mapsto(x-q)/(e-q)\), keeping masses unchanged. Both costs scale by the same positive factor, so the approximation ratio is preserved.
In the transformed society:
Write
\(U=\sum_{x<0}\mu_x\), \(v=\mu_0\), \(V=\sum_{0<x<1}\mu_x\), and \(w=\mu_1\).
Then
\(U+v+V+w=1\), \(U\le1/2\), \(V+w\le1/2\), and \(v,w\ge\delta\).
Reflection can turn the lower median into the upper median, but the two weak mass inequalities remain valid. Moreover, the prescribed tie rules imply
\(\boxed{U<1/2\ \text{or}\ A<1.}\)
Indeed, if the original selected endpoint was the right endpoint, the original lower-median definition gives \(U<1/2\). If it was the left endpoint, that endpoint was selected only on a strict distance inequality, giving \(A<1\).
Let \(N=C_\mu(\{0,1\})\). Directly from the normalized locations,
\[ \text{(written with the requested inline delimiters)} \]
\(N=\sum_{x<0}\mu_x(-x)+\sum_{0<x<1}\mu_x\min\{x,1-x\}\le AU+V/2.\)
For a nonempty subset \(B\) of the support, define
\(D(B)=\min_{t\in\mathbb R}\sum_{x\in B}\mu_x|x-t|\).
A weighted median minimizes this expression. To verify this, between consecutive support points its slope is twice the cumulative mass to the left minus the total mass of \(B\). These slopes are nondecreasing; at a weighted median the left slope is nonpositive and the right slope is nonnegative.
If the support is ordered as \(x_1<\cdots<x_\tau\), then
\(\mathrm{OPT}(\mu)=\min_{1\le j<\tau}\bigl(D(\{x_1,\ldots,x_j\})+D(\{x_{j+1},\ldots,x_\tau\})\bigr).\)
For proof, nearest-facility assignments to two ordered facilities can be chosen contiguous. If one facility receives no points, splitting the occupied group into two nonempty consecutive groups cannot increase the optimized cost. This proves the lower bound by the displayed minimum. Conversely, placing facilities at weighted medians of any two consecutive groups gives nearest-facility cost no larger than their assigned cost, proving the reverse inequality.
Choose a minimizing partition into a prefix \(P\) and a suffix \(Q\), and write \(D_P=D(P)\), \(D_Q=D(Q)\). Thus \(D_P+D_Q=\mathrm{OPT}(\mu)\).
Define
\(r_3(\delta)=\dfrac{\min\{1/2,\,1-2\delta\}}{\delta}.\)
Because \(0<\delta\le1/3\), we have \(r_3(\delta)\ge1\).
We distinguish which optimal group contains the median point \(0\).
Let \(H\) be the mass of points of \(P\) at or to the right of \(0\). Then \(H\ge v\ge\delta\), and all negative points belong to \(P\).
Choose the lower weighted median \(p\) of \(P\). Since the cumulative mass through \(0\) is at least \(1/2\), while half the mass of \(P\) is at most \(1/2\), we have \(p\le0\).
Put \(h=-p\), and decompose its assigned cost as \(D_P=D_-+D_+\), according to negative and nonnegative points. Then \(D_+\ge Hh\). The triangle inequality on negative points, and exact subtraction on nonnegative points, give
\(\sum_{x\in P}\mu_x|x|\le D_-+D_++(U-H)h.\)
If \(U\le H\), this is at most \(D_P\). If \(U>H\), using \(h\le D_+/H\) gives
\(\sum_{x\in P}\mu_x|x|\le D_-+(U/H)D_+\le(U/H)D_P.\)
Consequently, the mechanism’s cost on \(P\) is at most
\(\max\{1,U/H\}D_P\).
The distinct points \(0\) and \(1\) each have mass at least \(\delta\), so
\(U\le\min\{1/2,1-2\delta\}\). Therefore this factor is at most \(r_3(\delta)\).
For \(Q\), let \(K\) be its mass excluding the endpoint \(1\), and choose a weighted median \(r\le1\). With \(h'=1-r\), the same triangle-inequality argument gives
\(\sum_{x\in Q}\mu_x(1-x)\le\max\{1,K/w\}D_Q.\)
Here \(K\le1/2-w\le1/2-\delta\), and also \(K\le1-v-w\le1-2\delta\). Hence \(\max\{1,K/w\}\le r_3(\delta)\). The mechanism’s cost on \(Q\) is no larger than its cost using endpoint \(1\) alone.
Adding the bounds proves
\(\boxed{N\le r_3(\delta)\,\mathrm{OPT}(\mu).}\)
The suffix \(Q\) contains both \(0\) and \(1\). For any center \(r\),
\(\sum_{x\in Q}\mu_x|x-r|\ge v|r|+w|1-r|\ge\delta\bigl(|r|+|1-r|\bigr)\ge\delta.\)
Thus \(\mathrm{OPT}(\mu)\ge\delta\).
If \(V=0\), then \(N\le AU\le U\le\min\{1/2,1-2\delta\}\), yielding the bound \(r_3(\delta)\).
Suppose \(V>0\). The prefix contains a negative point, and there are also the distinct points \(0\), an interior positive point, and \(1\). Therefore \(\tau\ge4\), \(\delta\le1/4\), and \(V\ge\delta\). It follows that
\(U\le\min\{1/2,1-3\delta\}.\)
Using the normalization bound,
\(N\le U+V/2=(1-v-w+U)/2\le1/2-\delta+\tfrac12\min\{1/2,1-3\delta\}.\)
Define
\(r_4(\delta)=\dfrac{1/2-\delta+\tfrac12\min\{1/2,1-3\delta\}}{\delta}.\)
We have proved the universal upper bounds:
The simplifications are
\(r_4(\delta)=3/(4\delta)-1\) for \(0<\delta\le1/6\),
and
\(r_4(\delta)=1/\delta-5/2\) for \(1/6\le\delta\le1/4\).
On the latter interval,
\(r_4(\delta)-r_3(\delta)=1/(2\delta)-5/2\), which changes sign at \(\delta=1/5\). These calculations give exactly the upper bounds in the opening tables.
For \(0<\delta\le1/4\), choose any rational \(t\) with \(1/2<t<1\), and take
| Location | Mass |
|---|---:|
| \(0\) | \(1/2-\delta\) |
| \(t\) | \(\delta\) |
| \(1\) | \(1/2\) |
All masses are at least \(\delta\). The lower median is \(t\), since the cumulative mass there is exactly \(1/2\). MedianFurthest chooses endpoint \(0\), and its cost is \((1-t)/2\).
The two possible partition costs are \(\delta t\) and \(\delta(1-t)\). Hence \(\mathrm{OPT}=\delta(1-t)\), and the ratio is exactly \(1/(2\delta)\).
For \(1/4<\delta\le1/3\), choose any rational \(t\) with \(0<t\le1/2\), and take masses
\((1-2\delta,\delta,\delta)\)
at locations \((0,t,1)\).
All masses are at least \(\delta\), and the lower median is \(t\). MedianFurthest chooses endpoint \(1\). Its cost is \((1-2\delta)t\), while the two partition costs are \(\delta t\) and \(\delta(1-t)\). Thus the ratio is
\((1-2\delta)/\delta=1/\delta-2.\)
Whenever the support contains \(-1,0,1\), each with mass at least \(\delta\), every two-facility solution costs at least \(\delta\).
Indeed, assign these three points to nearest facilities. Two must share a facility. Their separation is at least \(1\), so the sum of their distances to that facility is at least \(1\). Their weighted contribution is therefore at least \(\delta\).
For \(1/6<\delta\le1/5\), take
| Location | Mass |
|---|---:|
| \(-1\) | \(1-3\delta\) |
| \(0\) | \(\delta\) |
| \(1/2\) | \(\delta\) |
| \(1\) | \(\delta\) |
These masses are admissible. The lower median is \(0\), because \(1-3\delta<1/2\) and \(1-2\delta\ge1/2\). The endpoint-distance tie selects \(1\).
The mechanism’s cost is \(1-3\delta+\delta/2=1-5\delta/2\). Facilities at \(-1\) and \(1/2\) cost exactly \(\delta\). The three-anchor lower bound proves this is optimal. Thus the ratio is \(1/\delta-5/2\).
At \(\delta=1/5\), this society and the first three-point family both attain \(5/2\).
For \(0<\delta\le1/6\) and any positive integer \(k\), put \(\varepsilon_k=\delta/k\), and take
| Location | Mass |
|---|---:|
| \(-1\) | \(1/2-\varepsilon_k\) |
| \(0\) | \(\delta\) |
| \(1/2\) | \(1/2+\varepsilon_k-2\delta\) |
| \(1\) | \(\delta\) |
Every mass is at least \(\delta\). The lower median is \(0\), because the mass at \(-1\) is strictly below \(1/2\), while the cumulative mass at \(0\) is at least \(1/2\). MedianFurthest again selects \(1\).
Its cost is \(3/4-\delta-\varepsilon_k/2\). Facilities at \(-1\) and \(1/2\) cost exactly \(\delta\), and the three-anchor bound again proves optimality. Therefore the ratio is
\(\dfrac{3}{4\delta}-1-\dfrac{1}{2k}\),
which approaches the claimed supremum.
In this range, \(r_4(\delta)>r_3(\delta)\), so equality could only arise in Case II with \(V>0\).
That case has \(U>0\). If \(U<1/2\), then
\(N\le(1-v-w+U)/2<3/4-\delta.\)
If \(U=1/2\), the normalization’s strictness property forces \(A<1\), and consequently
\(N\le AU+V/2<U+V/2\le3/4-\delta.\)
Since \(\mathrm{OPT}\ge\delta\), the ratio is always strictly below \(3/(4\delta)-1\). The approaching sequence above therefore establishes a non-attained supremum.
All descriptions below allow rational translation and positive rational scaling of the listed locations.
For \(T=3\) and \(0<\delta\le1/4\), the only attaining societies are the first three-point family: masses \((1/2-\delta,\delta,1/2)\) at \((0,t,1)\), with \(1/2<t<1\).
To justify uniqueness, in Case I the suffix factor is at most
\(\max\{1,1/(2\delta)-1\}<1/(2\delta)\).
Thus equality requires \(D_Q=0\). Equality in the prefix bound then requires \(U=1/2\), \(H=\delta\), and \(D_-=0\). Hence all negative mass occupies one point, the only nonnegative prefix point is \(0\) with mass \(\delta\), and the suffix consists solely of endpoint \(1\). Because \(U=1/2\), the original selected endpoint must have been the left endpoint, selected strictly. Translating back gives exactly the stated family. Case II with \(V=0\) cannot attain this bound: the normalization’s strictness property gives \(AU<1/2\).
For \(T\ge4\) and \(1/6<\delta<1/5\), the only attaining societies are the displayed four-point family.
Here \(r_4(\delta)>r_3(\delta)\). Equality in Case II forces \(A=1\), \(v=w=\delta\), \(U=1-3\delta\), and \(V=\delta\). Equality in the geometric cost bound forces every negative point to be at \(-1\), and every interior positive point to be at \(1/2\). Distinctness of support therefore forces exactly the four listed points. The tie rule requires the original selected endpoint to be the right endpoint.
For \(T\ge4\) and \(\delta=1/5\), the attaining societies are exactly the preceding three-point and four-point families.
Both case bounds coincide, and their equality conditions give precisely these two possibilities.
For \(T\ge4\) and \(1/5<\delta\le1/4\), the only attaining societies are the first three-point family.
Here \(r_4(\delta)<r_3(\delta)\), so the Case I equality argument applies.
For every \(T\ge3\) and \(1/4<\delta<1/3\), an attaining society has exactly three points. Its endpoint opposite the selected endpoint has mass \(1-2\delta\); the median and selected endpoint each have mass \(\delta\). These conditions are also sufficient.
For completeness, let the three masses be \(u,v,w\), and the two gaps be \(\ell,r\). All masses are strictly below \(1/2\), so the middle point is the median. If \(\ell\le r\), the ratio is
\(\max\left\{\dfrac{u}{\min\{u,v\}},\dfrac{u\ell}{\min\{v,w\}r}\right\}.\)
Each term is at most \((1-2\delta)/\delta\). Since this bound exceeds \(1\), equality forces \(u=1-2\delta\), and then \(v=w=\delta\). If \(\ell>r\), the symmetric calculation forces \(w=1-2\delta\). Conversely, either configuration attains the bound.
At \(\delta=1/3\), every admissible society attains ratio \(1\). There are exactly three support points, all with mass \(1/3\); the mechanism and optimum both incur one-third of the smaller adjacent gap.
For the stipulated \(m=2\), MedianFurthest and \(\mathrm{OPT}\) can both be evaluated in
\(O(\tau\log\tau\,\mathrm{poly}(L))\) bit operations, and therefore in
\(O(T\log T\,\mathrm{poly}(L))\).
To obtain this bound, sort the support and compute prefix sums of masses and mass-weighted locations. For each of the \(\tau-1\) splits, binary search the weighted median of its prefix and suffix. Their single-facility costs then follow from the prefix sums using a constant number of rational operations. Taking the minimum gives \(\mathrm{OPT}\) by the partition identity proved above.
This uses \(O(\tau\log\tau)\) rational operations on numbers of \(O(L)\) bits. It does not expand rational masses into a list of agents.
Evaluating the closed-form worst-case ratio requires only a constant number of rational comparisons and arithmetic operations, together with testing whether \(T=3\) or \(T\ge4\).
⟨structured verdict parsed — rendered above⟩
The claimed ratios, attainment statements, and characterization of maximizers are correct in substance. The proof establishes the target with two minor presentation issues and no major gaps. Its polynomial-time computation claim also checks out.
The selected endpoint differs from the median because the support contains at least three distinct points. The affine transformation is rational and invertible, and both costs scale by \(1/|e-q|\), preserving the ratio.
The normalized inequalities
\[
U\le \frac12,\qquad V+w\le \frac12,\qquad v,w\ge\delta
\]
are valid even when reflection changes a lower median into an upper median.
The strictness condition
\[
U<\frac12\quad\text{or}\quad A<1
\]
is correctly justified: selecting the original right endpoint preserves the strict lower-median inequality, whereas selecting the original left endpoint requires a strict endpoint-distance comparison.
Minor issue: “In the transformed society … MedianFurthest uses \(\{0,1\}\)” is ambiguous. The proof tracks the image of the original mechanism’s facility set; recomputing the mechanism after reflection can produce a different set.
A concrete example is the attaining society with locations \((0,3/4,1)\) and masses \((1/4,1/4,1/2)\). Its normalization gives locations \((-1/3,0,1)\) and masses \((1/2,1/4,1/4)\). The image of the original facility set is \(\{0,1\}\), but the transformed society’s lower median is \(-1/3\), so recomputing MedianFurthest gives \(\{-1/3,1\}\).
This does not invalidate the subsequent argument: the proof explicitly acknowledges the median change and uses only inequalities that remain valid. The minimum clarification is to identify \(\{0,1\}\) as the image of the original output throughout the normalized analysis.
The numerator bound
\[
N\le AU+\frac V2
\]
is correct, including the endpoint-median case \(A=0\).
The slope argument correctly establishes that a weighted median minimizes a group’s absolute-distance cost. It also accommodates an interval of minimizers when the cumulative mass equals half the group mass.
The partition identity is justified in both directions:
Thus minimizing over the \(\tau-1\) nonempty consecutive splits is valid. There is no unsupported restriction of the facility locations to the support.
When \(0\in P\), all negative points belong to \(P\), and \(H\ge v\ge\delta>0\). The cumulative mass through \(0\) is at least \(1/2\), so the lower weighted median \(p\) of \(P\) indeed satisfies \(p\le0\).
The inequalities involving \(h=-p\), \(D_-\), and \(D_+\) are valid. In particular, the division by \(H\) is legitimate, and the distinction between \(U\le H\) and \(U>H\) correctly yields
\[
C_\mu(\{0,1\};P)\le \max\{1,U/H\}D_P.
\]
Both bounds on \(U\) hold:
\[
U\le\frac12,\qquad U\le1-2\delta.
\]
Together with \(H\ge\delta\) and \(r_3(\delta)\ge1\), they give the stated prefix factor.
The suffix argument is also valid. The suffix lies strictly to the right of \(0\), contains endpoint \(1\), and has \(w>0\). The bounds on \(K\) justify its claimed factor. Adding the two assigned-cost bounds therefore proves
\[
N\le r_3(\delta)\,\mathrm{OPT}(\mu).
\]
Since \(Q\) contains \(0\) and \(1\), each with mass at least \(\delta\), the displayed triangle-inequality argument proves \(D_Q\ge\delta\), hence \(\mathrm{OPT}\ge\delta\).
If \(V=0\), the claimed \(r_3\) bound follows.
If \(V>0\), the four required distinct support points are correctly identified. Consequently, \(\tau\ge4\), \(\delta\le1/4\), and \(V\ge\delta\). The resulting bound
\[
U\le\min\{1/2,1-3\delta\}
\]
and the subsequent numerator estimate are correct.
The simplifications of \(r_3\) and \(r_4\) check out. The switch in \(r_4\) occurs at \(\delta=1/6\); its comparison with \(r_3\) switches at \(\delta=1/5\). The opening tables correctly handle both boundaries and the support restriction when \(\delta>1/4\).
All displayed masses sum to one, satisfy the floor in their stated ranges, and are rational. Their locations are distinct and rational, and their support sizes meet the stated caps.
For the first three-point family, the cumulative mass at \(t\) is exactly \(1/2\), so the lower median is \(t\). The strict condition \(t>1/2\) correctly forces selection of endpoint \(0\). Both partition costs and the resulting ratio \(1/(2\delta)\) are correct.
For the second three-point family, the lower median and endpoint selection are correct, including \(t=1/2\). The partition costs give the claimed ratio \(1/\delta-2\), including \(\delta=1/3\).
The three-anchor lower bound is rigorous: two of the three anchors must share a facility, and their weighted distance contribution is at least \(\delta\).
For the four-point attaining family, the median inequalities hold throughout \(1/6<\delta\le1/5\). The endpoint tie selects \(1\), the numerator is \(1-5\delta/2\), and the exhibited facilities cost exactly \(\delta\). The anchor bound certifies optimality.
For the approaching sequence, every mass satisfies the floor for every positive integer \(k\), including \(k=1\) and \(\delta=1/6\). The median remains \(0\), and the calculated ratio
\[
\frac{3}{4\delta}-1-\frac{1}{2k}
\]
is correct.
On \(0<\delta\le1/6\), the strict comparison \(r_4>r_3\) correctly eliminates Case I and Case II with \(V=0\).
In the remaining case, the proof obtains a strict numerator bound whether \(U<1/2\) or \(U=1/2\). In the latter situation, \(A<1\) and \(U>0\) ensure strictness. Combining this with \(\mathrm{OPT}\ge\delta\) proves non-attainment throughout the stated interval.
The rational sequence establishes the matching supremum, so non-attainment is fully resolved.
The equality arguments are sound.
In the ranges where the Case I bound is dominant, the strictly smaller suffix factor forces \(D_Q=0\). The remaining equality conditions force \(U=1/2\), \(H=\delta\), and zero negative assigned cost. These conditions leave exactly the stated three-point family. The normalization’s strictness condition correctly excludes the endpoint-distance tie and gives \(t>1/2\).
Where \(r_4>r_3\) and attainment occurs, equality in the numerator chain forces the specified masses and locations. Distinctness then limits the support to the four displayed points. The original right-endpoint requirement follows from the tie rule.
At \(\delta=1/5\), both case bounds coincide, and their equality conditions yield exactly the two stated families.
For \(1/4<\delta<1/3\), the mass floor forces exactly three points, and each mass is strictly below \(1/2\). The displayed three-point ratio formula is correct. Its equality conditions force mass \(1-2\delta\) at the endpoint opposite the selected endpoint and mass \(\delta\) at both remaining points.
At \(\delta=1/3\), exactly three equal masses are possible, and both costs equal one-third of the smaller adjacent gap. The claim that every admissible society attains ratio one is correct.
Sorting, prefix sums, and weighted-median searches across all splits require \(O(\tau\log\tau)\) rational operations. The stated \(O(L)\) intermediate bit-length bound is valid for the sums and products used here. Thus the claimed polynomial bit complexity, and its version using \(T\), are justified for the stipulated \(m=2\).
Evaluating the closed-form ratio uses a constant number of rational operations and comparisons. No expansion into individual agents is required.
The contextual citation is accurate: the source defines the lower-median and right-endpoint tie conventions and states the finite-agent approximation guarantee in Theorem 6. It is not used to establish the mass-based result. [Ferraioli–Serafino–Ventre](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p68.pdf)
Minor issue: The isolated display containing “(written with the requested inline delimiters)” is an editing artifact. Delete it; no mathematical content is missing there.
⟨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.