Answer: Yes. BALANCED evaluated using group masses satisfies all requirements.
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe BALANCED mechanism is strategyproof and has an approximation ratio of 2 for minimizing mge when Ej = wj · P i∈Gj c(f(θ), xi).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support rational distribution \(\mu\) over types \((x,g)\in\mathbb{Q}\times 2^{[m]}\), with rational group weights \(w_j\ge 0\), can one compute in time polynomial in \(m,\tau,L\) a deterministic facility rule \(F\) such that \(F^\mu(y)=\max_j w_j\sum_{(x,g):j\in g}\mu_{x,g}|x-y|\) is at most \(2\min_z F^\mu(z)\), while preserving individual strategyproofness on every finite realization? For each \(N\) with \(N\mu\) integral, a deviation by an agent of type \((x,g)\) to location \(x'\) changes the distribution to \(\mu'=\mu-\frac1N\delta_{(x,g)}+\frac1N\delta_{(x',g)}\), and must satisfy \(|F(\mu)-x|\le |F(\mu')-x|\).
A society is given by its support: the list of the \(\tau\) types \((x,g)\) with positive mass, each mass a binary rational, with \(\sum_{x,g}\mu_{x,g}=1\). Here \(\tau\) is the support size, not the number of possible types. Computational inputs have \(x\in\mathbb Q\), \(g\subseteq[m]\), \(m\ge1\), and public weights \(w_j\in\mathbb Q_{\ge0}\); \(L\) is the total input bit length.
Memberships may overlap. Empty groups contribute zero; assume \(\max_j w_j\sum_{(x,g):j\in g}\mu_{x,g}>0\). For one facility at \(y\in\mathbb R\), define \(C_w^\mu(y)=\max_{j\in[m]}w_j\sum_{(x,g):j\in g}\mu_{x,g}|x-y|\).
A deterministic rule \(F_w\) assigns one facility location to each society, independently of its finite realization size. Extend its domain to finite supports with real locations and rational masses; require an exactly represented rational output on rational inputs.
Realization-wise individual strategyproofness means that, for every society, every positive integer \(N\) with all \(N\mu_{x,g}\) integral, every supported \((x,g)\), and every report \(x'\in\mathbb R\), setting \(\mu'=\mu-N^{-1}\delta_{(x,g)}+N^{-1}\delta_{(x',g)}\) gives \(|F_w(\mu)-x|\le |F_w(\mu')-x|\). Memberships and weights remain fixed, and \(\delta\) denotes unit point mass.
Does there exist a deterministic, realization-wise individually strategyproof rule \(F_w\), evaluable in time polynomial in \(m,\tau,L\) on rational inputs, such that \(C_w^\mu(F_w(\mu))\le2\min_{z\in\mathbb R}C_w^\mu(z)\) for every admissible society?
For finite agent profiles with public overlapping memberships and nonnegative weights, BALANCED is a polynomial-time deterministic strategyproof \(2\)-approximation for maximum weighted total group cost. [Guo and Zhou](https://arxiv.org/html/2602.01048v2).
No result settling this exact support-encoded distribution problem with strategyproofness on every finite realization was located in the literature search.
Yes. BALANCED can be evaluated directly using masses, and the resulting rule satisfies strategyproofness for every finite realization. The proof below is independent of the finite-profile theorem.
Construction and well-definedness. Fix the public weights \(w\). For a society \(\mu\), define
\[
\]
For each group \(j\) and location \(y\), let
\(T_j=\sum_{(x,g):\,j\in g}\mu_{x,g},\qquad L_j(y)=\sum_{(x,g):\,j\in g,\ x\le y}\mu_{x,g},\qquad R_j(y)=T_j-L_j(y).\)
Set
\(A(y)=\max_{j\in[m]}w_jL_j(y),\qquad B(y)=\max_{j\in[m]}w_jR_j(y),\)
and define
\(F_w(\mu)=\min\{y\in\mathbb R:A(y)\ge B(y)\}.\)
This is the mass formulation of the cut rule in [Guo and Zhou, Algorithm 1](https://arxiv.org/html/2602.01048v2).
To verify that the minimum exists, let \(a\) and \(b\) be the smallest and largest supported locations, and put \(M=\max_j w_jT_j>0\). For \(y<a\), we have \(A(y)=0<M=B(y)\). At \(y=b\), we have \(A(b)=M>B(b)=0\). Moreover, \(A\) is nondecreasing, \(B\) is nonincreasing, and both change only at supported locations. Consequently, the rule returns the first supported location satisfying the inequality.
The definition applies equally to finite supports with real locations and rational masses. It makes no reference to a realization size.
Two boundary inequalities. Write \(f=F_w(\mu)\). Define
\(L_j^-=\sum_{(x,g):\,j\in g,\ x<f}\mu_{x,g},\qquad R_j^+=\sum_{(x,g):\,j\in g,\ x\ge f}\mu_{x,g},\)
and
\(A^-=\max_j w_jL_j^-,\qquad B^+=\max_j w_jR_j^+.\)
Then
\(A(f)\ge B(f),\qquad A^-<B^+.\)
The first inequality is the defining condition at \(f\). For the second, finiteness of the support allows us to choose \(t<f\) with no supported location in \((t,f)\). Thus \(L_j(t)=L_j^-\) and \(R_j(t)=R_j^+\) for every group. Since every \(t<f\) fails the defining condition, \(A^-<B^+\).
Proof of the approximation guarantee. Let
\(E_j(y)=w_j\sum_{(x,g):\,j\in g}\mu_{x,g}|x-y|,\qquad C(y)=\max_jE_j(y).\)
We prove \(C(f)\le 2C(z)\) for every \(z\in\mathbb R\).
First suppose \(z>f\), and write \(d=z-f\). For every \(x\le f\),
\(|x-f|-|x-z|=-d.\)
For every \(x>f\), the triangle inequality gives
\(|x-f|-|x-z|\le d.\)
Summing within group \(j\), and discarding the nonpositive contribution from locations at most \(f\), gives
\(E_j(f)-E_j(z)\le d\,w_jR_j(f)\le d\,B(f).\)
On the other hand, every location \(x\le f\) has distance at least \(d\) from \(z\). Hence
\(C(z)\ge d\,A(f)\ge d\,B(f).\)
Combining these inequalities yields \(E_j(f)\le E_j(z)+C(z)\le 2C(z)\) for every \(j\), and therefore \(C(f)\le 2C(z)\).
Now suppose \(z<f\), and write \(d=f-z\). For every \(x\ge f\),
\(|x-f|-|x-z|=-d,\)
whereas for every \(x<f\), the triangle inequality gives
\(|x-f|-|x-z|\le d.\)
Consequently,
\(E_j(f)-E_j(z)\le d\,w_jL_j^-\le d\,A^-.\)
Every location \(x\ge f\) has distance at least \(d\) from \(z\), so
\(C(z)\ge d\,B^+\ge d\,A^-.\)
Again \(E_j(f)\le 2C(z)\) for every group. The case \(z=f\) is immediate.
For completeness, the minimum of \(C\) is attained. Each \(E_j\), and hence \(C\), is continuous. Choose a group with \(w_jT_j>0\). The triangle inequality implies
\(C(y)\ge E_j(y)\ge w_jT_j|y|-w_j\sum_{(x,g):\,j\in g}\mu_{x,g}|x|,\)
which tends to infinity as \(|y|\) tends to infinity. Thus continuity and coercivity imply existence of a minimizer. Applying the established inequality at that minimizer proves
\(C_w^\mu(F_w(\mu))\le 2\min_{z\in\mathbb R}C_w^\mu(z).\)
Proof of realization-wise individual strategyproofness. Fix a supported type \((x,g)\), a permitted realization size \(N\), and a report \(x'\). Put \(\varepsilon=1/N\) and
\(\mu'=\mu-\varepsilon\delta_{(x,g)}+\varepsilon\delta_{(x',g)}.\)
Since \(N\mu_{x,g}\) is a positive integer, \(\varepsilon\le\mu_{x,g}\), so \(\mu'\) is a valid society. Group totals \(T_j\) remain unchanged. Write \(f=F_w(\mu)\) and \(f'=F_w(\mu')\).
We first record a monotonicity fact. For fixed totals \(T_j\), the predicate
\(\max_j w_j\ell_j\ge\max_j w_j(T_j-\ell_j)\)
is nondecreasing in the vector \((\ell_j)_{j\in[m]}\) under coordinatewise order. Indeed, increasing that vector increases the left-hand maximum and decreases the right-hand maximum. In particular, any vector coordinatewise below a failing vector also fails.
If \(x=f\), truthful cost is zero, so the desired inequality holds.
Suppose \(x<f\).
Suppose instead that \(x>f\).
These cases establish
\(|F_w(\mu)-x|\le |F_w(\mu')-x|.\)
The argument works for every permitted \(N\) and every real report \(x'\), proving the required realization-wise strategyproofness.
Polynomial-time evaluation and exact output. On rational inputs, sort the supported types by location. Compute each group total \(T_j\), then scan the distinct locations in increasing order. At each location, add the masses of every type at that location to the appropriate group prefixes before testing \(A(y)\ge B(y)\). Return the first successful location.
This uses \(O(\tau\log\tau+m\tau)\) rational comparisons and arithmetic operations. Their bit complexity is polynomial in \(L\): if \(D\) is the product of the input mass denominators, its bit length is at most the sum of their bit lengths, hence \(O(L)\). Every group prefix can be represented as an integer between zero and \(D\), divided by \(D\). Multiplication by input weights and exact comparison therefore involve integers of polynomial bit length.
The output is one of the input locations, so it is an exactly represented rational of input-bounded bit length. No finite realization is constructed.
Thus the rule satisfies all the requested properties.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The construction, approximation bound, realization-wise strategyproofness, and polynomial bit complexity are all justified. I found no mathematical gaps or false steps.
The definitions of \(L_j(y)\) and \(R_j(y)\) consistently partition group mass using \(x\le y\) and \(x>y\). Nonnegative weights ensure that \(A\) is nondecreasing and \(B\) is nonincreasing.
The assumption \(M=\max_j w_jT_j>0\) is used correctly: every location below the support fails the cut condition, while the largest supported location satisfies it. Finite support and the inclusion of mass at the cut establish that the first successful supported location exists and is the stated minimum.
The construction uses only the society and public weights. It applies to real supported locations and rational masses without referring to a realization size.
The attribution to [Guo and Zhou, Algorithm 1](https://arxiv.org/html/2602.01048v2) is accurate: that algorithm uses the same cut condition with agent counts. The submitted proof independently establishes the required distribution properties; it does not rely on the finite-profile theorem.
The inequality \(A(f)\ge B(f)\) follows from the definition.
The argument for \(A^-<B^+\) is valid. Finiteness permits choosing \(t<f\) with no supported location in \((t,f)\), including when \(f\) is the smallest supported location. The prefix and suffix masses at \(t\) then equal the quantities defined using \(x<f\) and \(x\ge f\). Minimality of \(f\) makes that cut fail strictly.
The treatment of mass located exactly at \(f\) is consistent throughout.
Both pointwise distance comparisons are correct. Multiplication by nonnegative weighted masses preserves the inequalities, and discarding the nonpositive contribution from \(x\le f\) is legitimate. Thus the stated bound
\(E_j(f)-E_j(z)\le dB(f)\)
holds for every group.
The lower bound \(C(z)\ge dA(f)\) correctly uses the distances of all locations at most \(f\). Combining it with \(A(f)\ge B(f)\) justifies the conclusion \(E_j(f)\le 2C(z)\), and taking the maximum over groups is valid.
The reversed distance comparisons and the bound using \(L_j^-\) are correct. The lower bound using \(R_j^+\) includes mass exactly at \(f\), as required.
The established strict boundary inequality implies the weak comparison used here. Consequently, the conclusion \(E_j(f)\le 2C(z)\) follows for every group. The case \(z=f\) is immediate.
Each group cost is a finite sum of continuous functions, and the maximum is over finitely many groups. Hence \(C\) is continuous.
The displayed coercivity bound is correct, and its coefficient is positive for the chosen group. The standard continuous-coercive minimization result applies on the real line, so the minimum is attained.
The approximation argument never divides by the optimum. It therefore covers zero optimal cost as well. Empty groups and groups with zero weight contribute zero and do not invalidate any step.
Integrality and positivity of \(N\mu_{x,g}\) imply \(1/N\le\mu_{x,g}\), so the modified masses remain nonnegative. Total mass stays one, support remains finite, and masses remain rational even for a real report.
Memberships are unchanged, so every group total remains fixed. In particular, the positivity assumption remains satisfied and \(F_w(\mu')\) is well-defined.
The coordinatewise monotonicity of the cut predicate is correct for fixed totals and nonnegative weights.
Every case is justified:
Each resulting location comparison gives the claimed distance inequality. Reports exactly at \(f\), unchanged reports, coincident locations, and empty memberships are covered. The quantification over every permitted \(N\) and every real report is preserved.
Sorting and scanning distinct supported locations implements the definition correctly. Adding all mass at a location before testing respects the convention \(x\le y\).
The operation count is valid, including overlapping memberships. The common-denominator argument bounds prefix numerators and denominators by polynomial bit length. Input weights and rational location comparisons also involve polynomial-length integers, so the operation count yields polynomial bit complexity.
The output is an input location, giving the required exact rational representation. No expansion into a finite realization is needed.
No additional mathematical clarification or repair is required. The empty display after “define” is a harmless typographical artifact.
⟨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.