Answer: \(W_g(\tau)=\sum_{i=0}^{\tau-1}(2/g)^i\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe approximation ratio of SD with augmentation factor g in facility assignment instances with n agents is 1. ratio(SD) ≤2n −1, 2. ratio2(SD) ≤log(n + 1), 3. ratiog(SD) ≤ g g−2 when g ≥3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite metric facility set \(F_1,\ldots,F_m\), rational per-capita capacities \(q_j\), rational type masses \(\mu_t\), preferred points \(a_t\), a fixed priority order, and augmentation factor \(g\), compute the block-Serial-Dictatorship mass assignment \(x\), compute \(\operatorname{OPT}_q(\mu)=\min\{\sum_{t,j}d(a_t,F_j)z_{tj}:\sum_jz_{tj}=\mu_t,\ \sum_tz_{tj}\le q_j,\ z_{tj}\ge0\}\), and characterize the worst-case ratio \(R_g(\mu)=\sum_{t,j}d(a_t,F_j)x_{tj}/\operatorname{OPT}_q(\mu)\) as a function of \(g\) and the number of types \(\tau\).
A society is given by its support: the list of \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input specifies \(m\ge1\) facilities \(F_j\), preferred points \(a_t\), and a binary-rational distance matrix defining a metric on their distinct locations; coincident locations are allowed. Original per-capita capacities satisfy \(q_j\in\mathbb Q_{>0}\) and \(\sum_jq_j\ge1\). The augmentation factor is an integer \(g\ge1\).
A fixed total priority order processes each type as one contiguous block. Block Serial Dictatorship starts with capacities \(gq_j\); it repeatedly sends as much of the current type's remaining mass as possible to its nearest facility with positive residual capacity, until that type is fully assigned. Distance ties are broken by facility index. Write \(x_{tj}\) for the resulting assigned mass.
Define \(\operatorname{OPT}_q(\mu)=\min\{\sum_{t,j}d(a_t,F_j)z_{tj}:\sum_jz_{tj}=\mu_t,\ \sum_tz_{tj}\le q_j,\ z_{tj}\ge0\}\). The associated computational tasks are to compute \(x\) and \(\operatorname{OPT}_q(\mu)\); measure running times in \(m,\tau,L\), where \(L\) is the total binary input length, including \(g\).
For inputs with \(\operatorname{OPT}_q(\mu)>0\), let \(R_g(I)=\sum_{t,j}d(a_t,F_j)x_{tj}/\operatorname{OPT}_q(\mu)\), and let \(W_g(\tau)=\sup_I R_g(I)\), over all such inputs with exactly \(\tau\) support types, arbitrary facility counts, and all priority orders.
What is the tight worst-case approximation ratio \(W_g(\tau)\) of block Serial Dictatorship, as a function of integer \(g\ge1\) and support size \(\tau\)?
Discrete SD with \(n\) agents has approximation upper bounds \(2^n-1\), \(\log_2(n+1)\), and \(g/(g-2)\) for \(g=1\), \(g=2\), and integer \(g\ge3\), respectively. Matching lower bounds occur for \(g=1\), for \(g=2\) at \(n=2^k-1\), and asymptotically as \(n\) grows for \(g\ge3\). [Source](https://link.springer.com/article/10.1007/s10107-022-01902-8).
No result settling this precise block mass approximation question was located in the literature search.
The tight ratio is
\[ \boxed{W_g(\tau)=\sum_{i=0}^{\tau-1}\left(\frac{2}{g}\right)^i.} \]
Equivalently,
\[ W_g(\tau)= \begin{cases} 2^\tau-1,&g=1,\\ \tau,&g=2,\\ \displaystyle\frac{g}{g-2}\left(1-\left(\frac{2}{g}\right)^\tau\right),&g\ge3. \end{cases} \]
Both computational tasks are solvable exactly in polynomial bit time in \(m,\tau,L\).
The [cited paper, Theorem 1](https://link.springer.com/article/10.1007/s10107-022-01902-8) bounds discrete SD using the number of individual agents. The following proof establishes the bound directly using the number of contiguous blocks.
All distances below come from the given metric; coincident facility locations cause no difficulty.
Lemma. Let \(q,v,w\) be nonnegative facility-load vectors satisfying \(v_j,w_j\le q_j\) and \(\sum_jv_j=\sum_jw_j\). Suppose an assignment \(z\) has facility loads \(r_j=\sum_tz_{tj}\le q_j-v_j\).
Let \(h_{jk}\ge0\) transport \(w\) to \(v\), meaning
\[ \sum_kh_{jk}=w_j,\qquad \sum_jh_{jk}=v_k. \]
Then there is an assignment \(z'\), preserving every type’s assigned mass, with facility loads at most \(q_j-w_j\), and
\[ \operatorname{cost}(z') \le \operatorname{cost}(z)+\sum_{j,k}h_{jk}d(F_j,F_k). \]
Proof. Put \(b_j=w_j-v_j\), and write \(b_j^+=\max\{b_j,0\}\) and \(b_j^-=\max\{-b_j,0\}\).
The directed flow \(h\) has net outflow \(b_j\) at facility \(j\). Add a source sending \(b_j^+\) into each facility and a sink receiving \(b_j^-\). The resulting flow conserves mass at every facility. Decomposing it into source-to-sink paths and directed cycles, discard the cycles and replace each path between facilities \(j\) and \(k\) by a direct transfer. The triangle inequality shows that this produces a transport \(H\) satisfying
\[ \sum_kH_{jk}=b_j^+,\qquad \sum_jH_{jk}=b_k^-,\qquad \sum_{j,k}H_{jk}d(F_j,F_k) \le \sum_{j,k}h_{jk}d(F_j,F_k). \]
Here flow decomposition is finite: repeatedly extract a path or cycle and subtract its minimum positive edge flow, thereby eliminating at least one positive edge.
The amount that must leave facility \(j\) is
\[ \delta_j=\max\{r_j-(q_j-w_j),0\}. \]
Since \(r_j\le q_j-v_j\), we have \(\delta_j\le b_j^+\). Also \(\delta_j\le r_j\), because \(q_j-w_j\ge0\).
At every facility with \(b_j>0\), move \(\delta_j\) of its assigned mass, proportionally across types, using the destination proportions \(H_{jk}/b_j^+\). If \(\delta_j=0\), move nothing.
A source facility’s final load is \(r_j-\delta_j\le q_j-w_j\). A destination facility \(k\) receives at most \(b_k^-=v_k-w_k\), so its final load is at most
\[ r_k+b_k^-\le(q_k-v_k)+(v_k-w_k)=q_k-w_k. \]
Facilities with \(b_j=0\) need no change. Every type’s total mass is preserved.
Moving type \(t\) from facility \(j\) to facility \(k\) increases its per-unit cost by at most \(d(F_j,F_k)\), by the triangle inequality. Each transfer in \(H\) is used with a fraction at most one. Consequently, the total cost increase is at most the cost of \(H\), and hence at most the cost of \(h\). This proves the lemma.
Define
\[ C_k=\sum_{i=0}^{k-1}\left(\frac{2}{g}\right)^i. \]
Then \(C_1=1\), \(C_k=1+(2/g)C_{k-1}\), and \(C_k\ge C_{k-1}\).
We prove by induction that block SD’s cost is at most \(C_k\) times the original-capacity optimum whenever there are \(k\) positive-mass blocks. For the induction, allow arbitrary total mass and nonnegative capacities, subject to total capacity being at least total mass. Zero-capacity facilities can be omitted.
For one block, all mass has the same preferred point. Filling facilities in nondecreasing distance order minimizes that block’s cost subject to the available capacities: any allocation using a farther facility while a nearer one has unused capacity can transfer mass to the nearer facility without increasing cost.
Thus greedy assignment under capacities \(gq\) costs no more than any feasible assignment under capacities \(q\), proving the bound \(C_1=1\).
Process the first block, and denote its SD allocation by \(u_j\) and its cost by
\[ S_1=\sum_ju_jd(a_1,F_j). \]
Fix an optimal assignment \(z\) under the original capacities. Write
\[ O_1=\sum_jz_{1j}d(a_1,F_j),\qquad O_{\mathrm{rem}}=\sum_{t=2}^k\sum_jz_{tj}d(a_t,F_j). \]
The first block’s greedy allocation minimizes its cost under \(gq\), while \(z_{1\cdot}\) is feasible under \(q\). Therefore \(S_1\le O_1\).
Define reduced comparison capacities
\[ q'_j=q_j-\frac{u_j}{g}. \]
They are nonnegative, and their augmented capacities \(gq'_j=gq_j-u_j\) are precisely the residual capacities seen by the remaining blocks. Moreover,
\[ \sum_jq'_j \ge \sum_{t=1}^k\mu_t-\frac{\mu_1}{g} \ge \sum_{t=2}^k\mu_t. \]
We now repair the remaining rows of \(z\) to fit \(q'\). Apply the lemma with
\[ w_j=\frac{u_j}{g},\qquad v_j=\frac{z_{1j}}{g},\qquad h_{j\ell}=\frac{u_jz_{1\ell}}{g\mu_1}. \]
Both reserve vectors have total mass \(\mu_1/g\), and the stated \(h\) has their required marginals. The remaining assignment has loads at most \(q_j-z_{1j}\le q_j-v_j\). Finally,
\[ \sum_{j,\ell}h_{j\ell}d(F_j,F_\ell) \le \sum_{j,\ell}h_{j\ell} \bigl(d(F_j,a_1)+d(a_1,F_\ell)\bigr) = \frac{S_1+O_1}{g}. \]
The lemma therefore gives
\[ \operatorname{OPT}_{q'}(\mu_{\mathrm{rem}}) \le O_{\mathrm{rem}}+\frac{S_1+O_1}{g}. \]
Applying the induction hypothesis to the remaining \(k-1\) blocks yields
\[ \begin{aligned} S_{\mathrm{total}} &\le S_1+ C_{k-1}\left(O_{\mathrm{rem}}+\frac{S_1+O_1}{g}\right)\\ &\le \left(1+\frac{2C_{k-1}}{g}\right)O_1 +C_{k-1}O_{\mathrm{rem}}\\ &\le C_k(O_1+O_{\mathrm{rem}}). \end{aligned} \]
The second inequality uses \(S_1\le O_1\); the third uses the recurrence for \(C_k\) and \(C_k\ge C_{k-1}\).
This proves \(W_g(\tau)\le C_\tau\), including instances whose optimum is zero before taking ratios.
Use the usual metric on the real line. Put
\[ N=\sum_{t=1}^{\tau}g^{\tau-t},\qquad \mu_t=\frac{g^{\tau-t}}{N},\qquad a_t=2^{t-1}, \]
and process types in increasing order.
Use \(\tau+1\) facilities: facility \(F_j\) is at \(2^j\) for \(1\le j\le\tau\), and \(F_{\tau+1}\) is at \(0\). Set
\[ q_j=\mu_{j+1}\quad(1\le j<\tau),\qquad q_\tau=\mu_\tau,\qquad q_{\tau+1}=\mu_1. \]
All capacities are positive, and their sum is \(1+\mu_\tau\ge1\).
For \(j<\tau\), we have \(gq_j=\mu_j\). Inductively, when type \(t\) is processed, facilities with indices below \(t\) are exhausted. Facility \(F_t\) and the facility at \(0\) are both at distance \(2^{t-1}\) from \(a_t\); every higher-index facility other than the one at \(0\) is farther away. Index tie-breaking selects \(F_t\). Its residual capacity accommodates the whole block, including for \(t=\tau\).
Hence SD costs \(\sum_t\mu_t2^{t-1}\).
An original-capacity assignment sends type \(1\) to the facility at \(0\), and each type \(t\ge2\) to \(F_{t-1}\), at zero cost. Its cost is \(\mu_1\). Conversely, every facility is at distance at least one from \(a_1=1\), so \(\operatorname{OPT}_q(\mu)\ge\mu_1\). Thus the optimum is exactly \(\mu_1>0\), and
\[ R_g(I) = \frac{\sum_t\mu_t2^{t-1}}{\mu_1} = \sum_{t=1}^{\tau}\left(\frac{2}{g}\right)^{t-1} = C_\tau. \]
All data are rational with finite binary encodings. The upper bound is therefore attained.
If “binary rational” is intended to mean only dyadic rationals, the same supremum follows. Choose positive dyadic \(\alpha\) tending to \(1/N\) from below, put \(\delta=1-N\alpha\), and replace the masses by \(\mu_1=\alpha g^{\tau-1}+\delta\) and \(\mu_t=\alpha g^{\tau-t}\) for \(t\ge2\). Use the same capacity formulas. The additional mass \(\delta\) of the first block goes to the facility at \(0\), while all subsequent blocks follow the same chain. The resulting ratios tend to \(C_\tau\).
For block SD, sort each type’s facilities by distance and then index. Scan its list, assigning the smaller of its remaining mass and the facility’s residual capacity. Total augmented capacity is at least total mass, so every block is assigned fully.
This uses \(O(\tau m\log(m+1))\) comparisons and scanning operations. There are only \(O(m+\tau)\) positive allocation steps: each step exhausts a facility or completes a block. Using a common denominator for the input masses and capacities, all residual quantities have \(O(L)\) bits, including multiplication by binary-encoded \(g\). With schoolbook integer arithmetic, a sufficient bit-time bound is
\[ O\!\left(\tau m\log(m+1)L^2\right). \]
For \(\operatorname{OPT}_q(\mu)\), use the stated rational linear program with \(m\tau\) variables. It is feasible: writing \(Q=\sum_jq_j\ge1\), the assignment \(z_{tj}=\mu_tq_j/Q\) satisfies all constraints. Its feasible region is compact because \(0\le z_{tj}\le\mu_t\). Polynomial-time rational linear programming therefore returns the exact optimum in \((m+\tau+L)^{O(1)}\) bit time.
Neither computation requires expanding rational masses into individual agents.
⟨structured verdict parsed — rendered above⟩
The claimed formula \(W_g(\tau)=\sum_{i=0}^{\tau-1}(2/g)^i\) is established in substance. The capacity-repair lemma, upper-bound induction, rational matching construction, and polynomial-time claims are correct.
There is one minor edge-case error in the optional dyadic-rational construction. It does not affect the conclusion.
The hypotheses and flow directions are consistent.
The transport has outgoing mass \(w_j\) and incoming mass \(v_j\), so its net outflow is \(b_j=w_j-v_j\). Adding source inflow \(b_j^+\) and sink outflow \(b_j^-\) therefore gives conservation at every facility.
The stated finite flow decomposition is valid. Removing cycles and replacing each source-to-sink path by a direct facility transfer preserves the required endpoint marginals. The triangle inequality justifies the transport-cost bound, including when distinct facility indices have coincident locations.
The required load repair is correctly bounded.
From \(r_j\le q_j-v_j\), the claimed inequality \(\delta_j\le b_j^+\) follows. The separate inequality \(\delta_j\le r_j\) uses \(q_j-w_j\ge0\), which is explicitly assumed through \(w_j\le q_j\).
Transfers leave only facilities with \(b_j>0\) and enter only facilities with \(b_j<0\). Thus the source and destination load estimates do not overlook simultaneous incoming and outgoing transfers. Scaling each source row of \(H\) by at most one bounds every destination’s received mass by its corresponding \(b_k^-\).
Proportional removal across types preserves nonnegativity and each type’s total mass. If a source has no assigned mass, then \(\delta_j=0\), and the instruction to move nothing avoids division by zero.
Finally, the metric inequality bounds each moved unit’s cost increase by the corresponding facility-to-facility distance.
Assessment: The lemma is correct and sufficiently justified.
Allowing arbitrary total mass and nonnegative capacities is appropriate: the reduced instances need not have total mass one or strictly positive capacities. Omitting zero-capacity facilities does not affect allocation, provided the remaining facilities retain their original index order for tie-breaking.
For one positive-mass block, filling facilities in distance order minimizes cost. The exchange argument given is sufficient. Since every assignment feasible under \(q\) is feasible under \(gq\), the comparison with the original optimum is valid.
The first block satisfies \(u_j\le gq_j\), so \(q'_j=q_j-u_j/g\) is nonnegative. Its augmented capacity is exactly the residual capacity after the first block.
The displayed total-capacity inequalities are correct, using \(g\ge1\). Hence the remaining instance satisfies the induction hypothesis.
Every required hypothesis is satisfied:
The denominator \(\mu_1\) is positive because the induction concerns positive-mass blocks.
The transport-cost computation is correct: its two distance terms sum to \(S_1/g\) and \(O_1/g\), respectively. The resulting bound on the reduced optimum follows directly from the lemma.
The substitution \(S_1\le O_1\) is valid because its coefficient is positive. The recurrence \(C_k=1+(2/g)C_{k-1}\) gives the coefficient of \(O_1\), and \(C_k\ge C_{k-1}\) justifies enlarging the coefficient of \(O_{\mathrm{rem}}\).
No division by the optimum occurs in the induction. Consequently, the assertion covering zero-optimum instances is also justified.
Assessment: The upper bound is established for every permitted priority order, facility count, and integer augmentation factor.
The masses are positive and sum to one. The preferred points are distinct, giving exactly \(\tau\) support types. All capacities are positive, and their stated total \(1+\mu_\tau\) is correct, including when \(\tau=1\).
The line metric supplies integer distances and accommodates the stated coincident preferred-point and facility locations. All data have finite binary rational encodings under the general rational interpretation.
For \(j<\tau\), the identity \(gq_j=\mu_j\) is correct. Therefore each earlier selected facility is exhausted by its corresponding block.
At type \(t\), the facility \(F_t\) and the facility at zero have equal distance from \(a_t\). The index rule selects \(F_t\); all remaining higher-index facilities are farther away. Its capacity suffices, including at the final block, where \(gq_\tau=g\mu_\tau\ge\mu_\tau\).
The claimed SD cost follows.
The described comparison assignment is feasible: the facility at zero accommodates type one, and facility \(F_{t-1}\) accommodates type \(t\) for every \(t\ge2\). Those latter assignments have zero cost.
Every facility is at distance at least one from the first preferred point, so the stated lower bound on the optimum is valid. Together with the feasible assignment, this establishes \(\operatorname{OPT}_q(\mu)=\mu_1>0\).
The ratio calculation and geometric-series expressions are correct. The construction therefore attains the upper bound under the general rational interpretation.
The sentence
“The additional mass \(\delta\) of the first block goes to the facility at \(0\), while all subsequent blocks follow the same chain.”
is false when \(\tau=1\).
For example, take \(\tau=1\), \(g=1\), and \(\alpha=1/2\). Then \(N=1\), \(\delta=1/2\), and the modified mass is \(\mu_1=1\). The capacity formulas give \(q_1=q_2=1\). Both facilities are equally distant from the preferred point, so index tie-breaking sends the entire block to \(F_1\); no mass goes to zero.
This is minor because the original one-type construction already has dyadic masses and capacities and attains the asserted ratio. For \(\tau\ge2\), the stated dyadic allocation behavior and limiting ratio are valid.
Minimum clarification needed: Restrict the additional-mass statement to \(\tau\ge2\), and explicitly distinguish the already-covered one-type case.
Sorting by distance and facility index implements the stipulated preference order. A scan per type suffices because capacities only decrease: facilities passed during that scan cannot become available later.
Each positive assignment either exhausts a facility or completes a block, so the claimed bound on positive allocation steps is valid.
The common-denominator argument also holds. The denominator’s binary length is bounded by the combined input denominator lengths, and multiplication by \(g\) adds only its input bit length. Thus residual masses and capacities have \(O(L)\)-bit representations.
The displayed schoolbook bit-time bound is sufficient, including rational distance comparisons and the scans. Binary encoding of \(g\) does not require expanding the population.
The proposed feasible assignment satisfies both row equalities and capacity inequalities. The feasible region is closed and bounded, and the objective has rational coefficients.
The standard polynomial-time theorem for rational linear programming applies to this explicitly represented, feasible, bounded program and permits exact optimal-value computation with polynomial bit complexity. The variable count, constraint count, and coefficient encoding lengths are polynomial in the stated input parameters.
Assessment: Both computational claims stand.
The introductory description of the cited discrete result is accurate: [Theorem 1 of the cited paper](https://link.springer.com/article/10.1007/s10107-022-01902-8) states bounds indexed by the number of individual agents. The prover does not apply that theorem to block masses; the block bound is independently established by the written induction.
There are no major issues or blocking gaps. The only required correction is the scope of the optional dyadic allocation statement.
⟨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.