Answer: For \(m=1\), the decision problem is in \(\mathrm{P}\). The exact optimum and an optimal support location are computable in \(O(\tau^2L^2)\) bit operations. The exact worst-case ratio is \(R(\kappa)=\min\{2,1/\kappa\}\).
Theorem 4 — class: algorithmic
Given finitely supported rational location types \( x_t\in[0,1]\) with masses \(\mu_t\) summing to one and capacity fraction \(\kappa\in(0,1]\), compute the maximum welfare from placing a facility at \(s\in[0,1]\) and serving the \(\kappa\)-closest mass, allowing a partial endpoint type, and determine the worst-case approximation ratio of the weighted-median mechanism relative to this optimum over all such \(\mu\).
A society is given by its support: distinct rational locations \(x_t\in[0,1]\), with positive binary-rational masses \(\mu_t\) satisfying \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There is one facility, so \(m=1\); its capacity is a binary rational \(\kappa\in(0,1]\). At location \(s\in[0,1]\), serve exactly \(\kappa\) mass in increasing order of \(|x_t-s|\), breaking equal-distance ties by increasing \(x_t\) and splitting the final type as necessary.
If \(a_t(s)\) is the mass served from type \(t\), define \(W_\mu(s,\kappa)=\sum_t a_t(s)(1-|x_t-s|)\); unserved mass has zero utility. Let \(W^*(\mu,\kappa)=\max_{s\in[0,1]}W_\mu(s,\kappa)\).
The weighted-median mechanism chooses the lower median \(s_{\mathrm{med}}=\min\{x_t:\sum_{j:x_j\le x_t}\mu_j\ge 1/2\}\). Define \(R(\kappa)=\sup_\mu W^*(\mu,\kappa)/W_\mu(s_{\mathrm{med}},\kappa)\), over all finite rational supports and positive rational masses of total mass one.
Is deciding \(W^*(\mu,\kappa)\ge q\), for a binary-rational threshold \(q\), in P or NP-hard, and can the exact optimum and an optimal location be computed in polynomial time? State running times in \(m=1\), \(\tau\), and the total input bit length \(L\).
What is the exact worst-case ratio \(R(\kappa)\) for every rational \(\kappa\in(0,1]\)?
For finite agents, the optimal location and welfare are polynomial-time computable; the median's tight ratio is \(2k/(k+1)\) when \(1\le k\le\lceil(n-1)/2\rceil\). [Aziz et al.](https://econcs.seas.harvard.edu/resource/azizgamesecon20pdf)
Related distributional work characterizes welfare and optimal percentile mechanisms in a Bayesian population limit under absolutely continuous distributions; it does not settle this rational-support complexity and worst-case-ratio question. [Auricchio and Zhang](https://arxiv.org/html/2412.00563v1)
For \(m=1\), deciding \(W^*(\mu,\kappa)\ge q\) is in \(\mathrm{P}\). An exact optimum and an optimal support location can be computed using \(O(\tau^2)\) arithmetic operations on \(O(L)\)-bit integers, or \(O(\tau^2L^2)\) bit operations with schoolbook arithmetic.
The exact worst-case ratio is
\[ R(\kappa)=\min\{2,1/\kappa\}. \]
Thus \(R(\kappa)=2\) for \(0<\kappa\le 1/2\), and \(R(\kappa)=1/\kappa\) for \(1/2\le\kappa\le1\). Three-point societies with dyadic masses already approach these bounds.
Relabel the support so that \(x_1<\cdots<x_\tau\). Define the feasible allocations by
\[ \mathcal A_\kappa=\left\{a:0\le a_t\le\mu_t,\ \sum_t a_t=\kappa\right\}, \]
and their welfare at location \(s\) by
\[ U(s,a)=\sum_t a_t(1-|x_t-s|). \]
Lemma 1: the prescribed service rule maximizes welfare at a fixed location. For every \(s\),
\[ W_\mu(s,\kappa)=\max_{a\in\mathcal A_\kappa}U(s,a). \]
Indeed, ordering types by increasing distance orders their per-unit utilities decreasingly. Transferring mass from a later type to an earlier unfilled type cannot decrease welfare. Applying these transfers successively fills each type up to its mass before proceeding to the next, splitting the last type as specified. Equal-distance types have equal utility, so the tie rule does not affect aggregate welfare.
Lemma 2: a weighted median minimizes weighted absolute distance. Let \(w_t\ge0\), with total weight \(B>0\). Suppose a support point \(z\) satisfies
\[ \sum_{x_t<z}w_t\le B/2,\qquad \sum_{x_t>z}w_t\le B/2. \]
Then \(C_w(z)\le C_w(s)\) for every \(s\), where \(C_w(s)=\sum_t w_t|x_t-s|\).
For \(s>z\), types at or left of \(z\) have their distance increased by exactly \(s-z\). For types right of \(z\), the triangle inequality bounds the distance change below by \(-(s-z)\). Consequently,
\[ C_w(s)-C_w(z) \ge \left(B-2\sum_{x_t>z}w_t\right)(s-z) \ge0. \]
For \(s<z\), the same argument gives
\[ C_w(s)-C_w(z) \ge \left(B-2\sum_{x_t<z}w_t\right)(z-s) \ge0. \]
Such a support point always exists: choose the first support point where cumulative weight reaches \(B/2\). Its strictly-left weight is less than \(B/2\), and its strictly-right weight is at most \(B/2\).
Fix any location \(s\), and let \(a\) be its prescribed allocation. Choose a weighted median \(z\) of the allocation weights \(a_t\), whose total is \(\kappa>0\). Lemma 2 gives
\[ U(z,a)=\kappa-C_a(z)\ge\kappa-C_a(s)=W_\mu(s,\kappa). \]
By Lemma 1, the prescribed allocation at \(z\) performs at least as well as \(a\):
\[ W_\mu(z,\kappa)\ge U(z,a). \]
Thus every location is weakly dominated by a support location, proving
\[ W^*(\mu,\kappa)=\max_{1\le i\le\tau}W_\mu(x_i,\kappa). \]
This also proves existence of an optimal location without any continuity assumption.
Sort the support once. For each candidate \(x_i\), its positive distances occur in two already sorted lists:
\[ x_i-x_{i-1},\ldots,x_i-x_1, \qquad x_{i+1}-x_i,\ldots,x_\tau-x_i. \]
Process type \(i\) first, then merge these lists, choosing the left type when distances tie. Fill capacity greedily and calculate welfare exactly. Each candidate takes \(O(\tau)\) arithmetic operations. Sorting takes \(O(\tau\log\tau)\) comparisons, so the overall arithmetic count is \(O(\tau^2)\).
For an explicit bit bound, let \(D\) be the product of all input denominators, including that of \(q\). Since their total encoding length is at most \(L\), \(D\) has \(O(L)\) bits. Write
\[ x_t=X_t/D,\qquad \mu_t=M_t/D,\qquad \kappa=K/D,\qquad q=Q/D. \]
Every greedy allocation has the form \(a_t=A_t/D\), with integer \(A_t\): capacity filling uses only subtraction and minimum operations on the scaled integer masses. At candidate \(x_i\), its exact welfare numerator is
\[ N_i=\sum_t A_t\bigl(D-|X_t-X_i|\bigr), \qquad W_\mu(x_i,\kappa)=N_i/D^2. \]
All these integers have \(O(L)\) bits; in particular, \(0\le N_i\le KD\le D^2\). Preprocessing, sorting, evaluation, and final comparison therefore take \(O(\tau^2L^2)\) bit operations using schoolbook arithmetic. The decision test is simply
\[ \max_i N_i\ge QD. \]
The maximizing input location and the fraction \(\max_iN_i/D^2\) give exact outputs of \(O(L)\) bits.
Hence the problem is in \(\mathrm{P}\); it could be NP-hard under polynomial-time reductions only if \(\mathrm{P}=\mathrm{NP}\). All loops depend on support size \(\tau\), irrespective of how finely the masses are encoded. This establishes the encoded-support analogue of the finite-agent observation in [Aziz et al., Remark 2](https://econcs.seas.harvard.edu/resource/azizgamesecon20pdf).
Let \(z=s_{\mathrm{med}}\), and define full-population welfare by
\[ F(s)=\sum_t\mu_t(1-|x_t-s|). \]
The lower median satisfies the hypotheses of Lemma 2 with weights \(\mu_t\). Thus \(F(z)\ge F(s)\) for every \(s\).
Because utilities are nonnegative and allocations satisfy \(a_t\le\mu_t\),
\[ W_\mu(s,\kappa)\le F(s)\le F(z), \qquad\text{hence}\qquad W^*(\mu,\kappa)\le F(z). \]
The allocation \(a_t=\kappa\mu_t\) is feasible. Lemma 1 therefore implies
\[ W_\mu(z,\kappa)\ge\kappa F(z). \]
Moreover, every type has utility at least \(1/2\) at location \(1/2\). Consequently,
\[ F(z)\ge F(1/2)\ge1/2, \qquad W_\mu(z,\kappa)\ge\kappa/2>0. \]
Dividing the preceding inequalities gives
\[ \frac{W^*(\mu,\kappa)}{W_\mu(z,\kappa)}\le\frac1\kappa. \]
Also \(W^*(\mu,\kappa)\le\kappa\), because exactly \(\kappa\) mass is served and per-unit utility is at most one. Together with \(W_\mu(z,\kappa)\ge\kappa/2\), this yields the second bound:
\[ \frac{W^*(\mu,\kappa)}{W_\mu(z,\kappa)}\le2. \]
Therefore \(R(\kappa)\le\min\{2,1/\kappa\}\).
For a positive dyadic \(\varepsilon<\min\{\kappa,1/2\}\), take the society
| Location | Mass |
|---|---:|
| \(0\) | \(1/2-\varepsilon\) |
| \(1/2\) | \(\varepsilon\) |
| \(1\) | \(1/2\) |
All masses are positive and sum to one. Cumulative mass first reaches \(1/2\) at location \(1/2\), so this is the lower median.
At the median, the central mass is served first, and every other type has utility \(1/2\). Hence
\[ W_\mu(1/2,\kappa) =\varepsilon+\frac{\kappa-\varepsilon}{2} =\frac{\kappa+\varepsilon}{2}. \]
Case \(0<\kappa\le1/2\). Locating at \(1\) serves \(\kappa\) mass at utility one. Since welfare cannot exceed \(\kappa\),
\[ W^*(\mu,\kappa)=\kappa, \qquad \frac{W^*(\mu,\kappa)}{W_\mu(1/2,\kappa)} =\frac{2\kappa}{\kappa+\varepsilon}. \]
Taking \(\varepsilon=2^{-h}\) and letting \(h\) tend to infinity proves \(R(\kappa)\ge2\).
Case \(1/2<\kappa\le1\). Additionally choose \(\varepsilon<\kappa-1/2\). At location \(1\), all mass at \(1\) and \(1/2\) is served; any remaining served mass comes from \(0\) and contributes zero. Therefore
\[ W_\mu(1,\kappa)=\frac12+\frac{\varepsilon}{2}. \]
Full-population welfare at the median is also \((1+\varepsilon)/2\), which Section 4 bounds the optimum above by. Thus
\[ W^*(\mu,\kappa)=\frac{1+\varepsilon}{2}, \qquad \frac{W^*(\mu,\kappa)}{W_\mu(1/2,\kappa)} =\frac{1+\varepsilon}{\kappa+\varepsilon}. \]
Along the same dyadic sequence, this tends to \(1/\kappa\). For \(\kappa=1\), the ratio is exactly one, as also follows from full-population median optimality.
These constructions match both universal upper bounds and settle the stated supremum.
⟨structured verdict parsed — rendered above⟩
The prover resolves both parts of the task correctly. The exact optimization algorithm is polynomial in the encoded input size, and the claimed worst-case ratio \(R(\kappa)=\min\{2,1/\kappa\}\) follows from valid universal bounds and admissible matching constructions. No major or minor mathematical issues were found.
Lemma 1 correctly identifies the prescribed service rule with welfare maximization over \(\mathcal A_\kappa\).
At a fixed location, utility is linear in the served masses. If an allocation serves a more distant type while leaving a closer type unfilled, transferring the available mass between them preserves feasibility and cannot decrease welfare. Processing types in the prescribed order therefore produces the greedy allocation. Because the support is finite, this exchange procedure requires only finitely many transfers.
Equal-distance types have identical utility, so the specified tie rule affects the allocation but not its welfare. Splitting the final type is allowed by the task. Total mass one and \(0<\kappa\le1\) ensure that capacity can always be filled exactly.
Assessment: Correct.
Both distance-change inequalities are valid. For \(s>z\), types at or left of \(z\) contribute exactly their weight times \(s-z\); each type right of \(z\) contributes at least its weight times \(-(s-z)\). The resulting coefficient is \(B-2\sum_{x_t>z}w_t\), which is nonnegative under the stated hypothesis. The argument for \(s<z\) is symmetric.
The existence assertion also handles zero weights correctly: the first support point whose cumulative weight reaches \(B/2\) has strictly-left weight less than \(B/2\) and strictly-right weight at most \(B/2\). Since \(B>0\), such a point exists.
Assessment: Correct, including the hypotheses needed for subsequent applications.
The prescribed allocation at any location \(s\) has total weight \(\kappa>0\), so Lemma 2 applies to its allocation weights. Its weighted median \(z\) is an original support location.
The two inequalities have the correct directions:
Thus every location is weakly dominated by a support location. Taking the maximum over the finite support proves both the displayed equality for \(W^*\) and existence of an optimum.
Zero allocation weights cause no difficulty. The argument also covers \(\tau=1\) and \(\kappa=1\).
Assessment: Correct.
At each candidate \(x_i\), the listed left and right distances are individually increasing. Merging them enumerates all remaining types in increasing distance. Choosing the left type on equality implements the increasing-location tie rule.
Each candidate processes at most \(\tau\) types, giving \(O(\tau^2)\) arithmetic operations overall after sorting.
The common-denominator analysis is sound:
Constructing the common denominator, scaling the inputs, sorting, evaluating candidates, and comparing against the threshold all fit within \(O(\tau^2L^2)\) schoolbook bit operations. The output location and unreduced exact welfare fraction have \(O(L)\) bits.
These bounds apply with \(m=1\); they make no claim about variable \(m\). They depend on support size rather than any expanded number of agents.
The ancillary comparison with [Aziz et al., Remark 2](https://econcs.seas.harvard.edu/resource/azizgamesecon20pdf) is accurate: that remark states polynomial-time computability for the finite-agent problem. The present proof establishes its own encoded-support result independently.
Assessment: Correct.
The lower population median satisfies Lemma 2 with total weight one, so it maximizes full-population welfare \(F\).
The inequality \(W_\mu(s,\kappa)\le F(s)\) correctly uses both nonnegative utilities on \([0,1]\) and \(a_t\le\mu_t\). The proportional allocation \(a_t=\kappa\mu_t\) is feasible because \(0<\kappa\le1\), establishing \(W_\mu(z,\kappa)\ge\kappa F(z)\).
At location \(1/2\), every utility is at least \(1/2\). Thus \(F(z)\ge1/2\) and the median welfare is strictly positive. Both divisions are therefore justified.
The resulting bounds \(1/\kappa\) and \(2\) hold simultaneously for every admissible society.
Assessment: Correct.
The three locations are distinct rational points. The chosen masses are positive dyadic rationals summing to one. Their cumulative masses make \(1/2\) exactly the lower median.
Since \(\varepsilon<\kappa\), its central mass is fully served there, and the remaining served mass has utility \(1/2\). The median welfare calculation is correct.
For \(0<\kappa\le1/2\), the mass at location one fills capacity by itself, attaining the universal welfare ceiling \(\kappa\). The displayed ratio tends to two.
For \(1/2<\kappa\le1\), the additional restriction \(\varepsilon<\kappa-1/2\) ensures that capacity includes all mass at one and at \(1/2\). Remaining mass comes from zero with zero utility. The resulting welfare equals \(F(1/2)\), so the earlier upper bound proves optimality. The ratio tends to \(1/\kappa\).
For each fixed admissible \(\kappa\), all required restrictions hold along a sufficiently late tail of the dyadic sequence. This suffices for the supremum. The boundary \(\kappa=1/2\) is covered by the first case, and \(\kappa=1\) gives ratio exactly one.
Assessment: Correct.
None. Both the complexity classification and the exact supremum are established as written.
⟨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.