Answer: Polynomial-time solvable in binary input length: feasibility holds exactly when $\frac{B}{P}\sum_{j=1}^{\tau}\frac{\mu_jp_j}{u_j}\le\theta$. A direct exact algorithm uses $O(\tau L^2)$ bit operations.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFEASIBLECITIES is NP-hard. Since we reduce from PARTITION, which admits a pseudo-polynomial time algorithm, it is natural to ask whether our problem does too. To show that this is the case, we formulate the problem as a linear program with one vari- able xa for each integral allocation a ∈At. The LP searches for a fair distribution over these, with xa representing the probability assigned to allocation a.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite set of municipality types \(T\), rational masses \(\mu_j\) summing to \(1\), resident counts \(p_j\), invitation caps \(u_j\), a letter budget \(B\) per unit of municipality mass, and a contact limit \(\theta\), does there exist a distribution over assignments \(a_j:[0,\mu_j]\to\{0,\ldots,u_j\}\) such that in every draw \(\sum_{j\in T}\int_0^{\mu_j}a_j(z)\,dz=B\), contacted mass \(\sum_{j\in T}|\{z:a_j(z)>0\}|\le\theta\), and \(\mathbb{E}[a_j(z)]=Bp_j/P\) for almost every \(z\), where \(P=\sum_{j\in T}\mu_jp_j\)?
A society is given by its support: a list \(T=\{1,\ldots,\tau\}\) of types with positive binary rational masses \(\mu_j\), summing to \(1\); \(\tau\) is the support size, not the number of possible types, and is part of the input.
Each type has a positive rational population weight \(p_j\) and a positive integer invitation cap \(u_j\), encoded in binary. Types admit a common ordering with \(p_1\le\cdots\le p_\tau\) and \(u_1\le\cdots\le u_\tau\).
The budget per unit municipality mass is \(B\in\mathbb{Q}_{>0}\), and the contact limit is \(\theta\in\mathbb{Q}\cap(0,1]\). Set \(P=\sum_j\mu_jp_j\), and assume \(Bp_j/P\le u_j\) for every type.
Represent type \(j\) by the Lebesgue interval \([0,\mu_j)\). A randomized assignment consists of jointly measurable maps \(a_j:\Omega\times[0,\mu_j)\to\{0,\ldots,u_j\}\) on a probability space \(\Omega\).
Every draw must satisfy \(\sum_j\int_0^{\mu_j}a_j(\omega,z)\,dz=B\) and \(\sum_j\lambda(\{z:a_j(\omega,z)>0\})\le\theta\), where \(\lambda\) denotes Lebesgue measure.
Fairness requires \(\mathbb{E}_\omega[a_j(\omega,z)]=Bp_j/P\) for Lebesgue-almost every \(z\), for every type. The decision problem asks whether such a randomized assignment exists.
Let \(m=\max_j u_j\) and \(L\) be the total binary input length; state running times in \(m,\tau,L\) and the encoded parameters \(B,\theta\), distinguishing numerical from bit-length dependence.
Is this continuous fair municipality-assignment decision problem solvable in polynomial time in its binary input length, or is it NP-hard?
For finitely many municipalities, the corresponding fair-distribution feasibility problem is NP-hard and admits a pseudopolynomial-time algorithm; minimizing the maximum contacted count admits a polynomial-time additive \(1\)-approximation. [Source](https://arxiv.org/html/2509.07557v1)
No result settling exactly the continuous problem stated here was located in the literature search.
The continuous problem is solvable in polynomial time in its binary input length.
Define the required mean and contact fraction for type $j$ by
$$
q_j=\frac{Bp_j}{P},
\qquad
r_j=\frac{q_j}{u_j}.
$$
The hypotheses imply $0<r_j\le 1$. Define
$$
W=\sum_{j=1}^{\tau}\mu_jr_j
=\frac{B}{P}\sum_{j=1}^{\tau}\frac{\mu_jp_j}{u_j}.
$$
Theorem. A randomized assignment satisfying all the stated requirements exists if and only if
$$
W\le\theta.
$$
The construction below uses only the integer invitation counts $0$ and $u_j$. The common ordering of the types is unnecessary for this characterization.
Suppose a feasible randomized assignment exists. For every type $j$, draw $\omega$, and point $z$,
$$
a_j(\omega,z)
\le
u_j\,\mathbf{1}_{\{a_j(\omega,z)>0\}}.
$$
Consequently, the contacted mass in a draw satisfies
$$
\sum_{j=1}^{\tau}
\lambda\bigl(\{z:a_j(\omega,z)>0\}\bigr)
\ge
\sum_{j=1}^{\tau}\frac{1}{u_j}
\int_0^{\mu_j}a_j(\omega,z)\,dz.
$$
All integrands are nonnegative and jointly measurable. Tonelli’s theorem therefore permits exchanging expectation and integration. Taking expectations, using the contact constraint, and then using fairness almost everywhere gives
$$
\begin{aligned}
\theta
&\ge
\mathbb{E}_{\omega}\left[
\sum_{j=1}^{\tau}
\lambda\bigl(\{z:a_j(\omega,z)>0\}\bigr)
\right]\\
&\ge
\sum_{j=1}^{\tau}\frac{1}{u_j}
\int_0^{\mu_j}\mathbb{E}_{\omega}[a_j(\omega,z)]\,dz\\
&=
\sum_{j=1}^{\tau}\frac{\mu_jq_j}{u_j}
=W.
\end{aligned}
$$
Thus $W\le\theta$ is necessary.
Assume $W\le\theta$. Take the probability space $\Omega=[0,1)$ with its Borel sigma algebra and uniform probability measure. For a real number $x$, write its fractional part as
$$
\operatorname{frac}(x)=x-\lfloor x\rfloor.
$$
Set
$$
a_j(\omega,z)
=
u_j\,
\mathbf{1}_{\left\{
\operatorname{frac}\left(\frac{z}{\mu_j}+\omega\right)<r_j
\right\}}.
$$
These maps are jointly measurable because the fractional-part map is Borel measurable. Their values belong to $\{0,u_j\}$, hence satisfy the integer invitation restrictions.
For any fixed $s\in[0,1)$, the map
$$
t\longmapsto \operatorname{frac}(t+s)
$$
preserves Lebesgue measure on $[0,1)$. Indeed, splitting the domain at $1-s$ makes it a translation on each of two intervals, whose images partition $[0,1)$.
Fix an arbitrary draw $\omega$. Applying this fact and substituting $t=z/\mu_j$ shows that
$$
\lambda\bigl(\{z:a_j(\omega,z)>0\}\bigr)=\mu_jr_j
$$
and
$$
\int_0^{\mu_j}a_j(\omega,z)\,dz
=u_j\mu_jr_j
=\mu_jq_j.
$$
Therefore every draw satisfies the exact budget:
$$
\sum_{j=1}^{\tau}\int_0^{\mu_j}a_j(\omega,z)\,dz
=
\sum_{j=1}^{\tau}\mu_jq_j
=
\frac{B}{P}\sum_{j=1}^{\tau}\mu_jp_j
=B.
$$
Its contacted mass is exactly
$$
\sum_{j=1}^{\tau}\mu_jr_j=W\le\theta.
$$
Finally, fix any $z\in[0,\mu_j)$. Rotation also preserves uniform probability as $\omega$ varies, so
$$
\Pr_{\omega}\left[
\operatorname{frac}\left(\frac{z}{\mu_j}+\omega\right)<r_j
\right]=r_j.
$$
It follows that
$$
\mathbb{E}_{\omega}[a_j(\omega,z)]
=u_jr_j=q_j=\frac{Bp_j}{P}.
$$
Thus fairness holds at every point, which is stronger than the required almost-everywhere condition. This completes the proof.
In particular, $W$ is the minimum achievable bound on contacted mass per draw.
The decision algorithm computes
$$
P=\sum_{j=1}^{\tau}\mu_jp_j,
\qquad
S=\sum_{j=1}^{\tau}\frac{\mu_jp_j}{u_j},
$$
and tests the exact rational inequality
$$
BS\le\theta P.
$$
This requires $O(\tau)$ rational arithmetic operations. Even without reducing fractions, all intermediate numerators and denominators have $O(L)$ bits: denominators can be represented as products of input denominators and caps, whose total binary length is $O(L)$; summing the numerators adds at most $O(\log\tau)$ further bits.
Using schoolbook integer arithmetic therefore gives the conservative bound
$$
O(\tau L^2)
$$
bit operations. The explicit assignment can also be described using $O(\tau L)$ bits by listing the rational thresholds $r_j$ and the formula above.
There is no numerical dependence on $m$, $B$, or $1/\theta$. Their dependence is through their binary encodings included in $L$; in particular, the algorithm does not enumerate invitation counts up to $m$.
The cited paper establishes hardness for finitely many individually constrained municipalities. [Gölz et al., *City Sampling for Citizens’ Assemblies*](https://arxiv.org/html/2509.07557v1).
Here, each type is a nonatomic interval. In every draw, an arbitrary fraction $r_j$ of that interval can receive its cap, and rotating that subset ensures pointwise fairness while preserving its measure. The proof above establishes that this divisibility makes the contact lower bound exactly attainable.
⟨structured verdict parsed — rendered above⟩
Result: proved. The characterization, measurable construction, and binary running-time analysis are correct. No major or minor issues were found.
The output addresses the continuous decision problem as stated, including integer invitation counts, an exact budget in every draw, a contact bound in every draw, and pointwise fairness almost everywhere.
Because the input has positive masses, positive population weights, and positive budget,
$$
P=\sum_{j=1}^{\tau}\mu_jp_j>0.
$$
Thus the definitions
$$
q_j=\frac{Bp_j}{P},
\qquad
r_j=\frac{q_j}{u_j}
$$
are well-defined. The cap hypothesis gives precisely
$$
0<r_j\le 1.
$$
The quantity $W=\sum_j\mu_jr_j$ is therefore well-defined and positive.
The assertion that the common ordering is unnecessary is justified: neither direction of the argument uses it. The construction still applies to every input satisfying the ordering requirement.
The pointwise inequality
$$
a_j(\omega,z)\le u_j\mathbf{1}_{\{a_j(\omega,z)>0\}}
$$
is valid for every allowed invitation count. Dividing by the positive integer $u_j$, integrating, and summing gives the displayed lower bound on contacted mass.
The application of Tonelli’s theorem is justified. The probability measure is finite, each type interval has finite Lebesgue measure, and the functions being integrated are jointly measurable and nonnegative. In particular, the contacted-mass random variables are measurable.
The per-draw contact constraint bounds their expected sum by $\theta$. Fairness holds outside a Lebesgue-null subset of each type interval, which suffices for the subsequent integration. Hence the computation
$$
\theta\ge
\sum_{j=1}^{\tau}\frac{1}{u_j}
\int_0^{\mu_j}\mathbb{E}_{\omega}[a_j(\omega,z)]\,dz
=
\sum_{j=1}^{\tau}\frac{\mu_jq_j}{u_j}
=W
$$
is valid. Necessity is established.
The proposed probability space is valid. The map
$$
(\omega,z)\longmapsto
\operatorname{frac}\left(\frac{z}{\mu_j}+\omega\right)
$$
is Borel measurable, since $\mu_j>0$ and the fractional-part map is Borel measurable. Its threshold indicator is therefore jointly measurable.
The assignment takes only the values $0$ and $u_j$, both of which are permitted integer invitation counts.
The measure-preservation statement is correct. For $s\in[0,1)$, splitting the domain into the two half-open intervals at $1-s$ gives translations whose images partition $[0,1)$. This argument also covers $s=0$, when one interval is empty.
Thus the rotation claim used in both subsequent applications is established within the output.
For each fixed $\omega$, rotation invariance and the substitution $t=z/\mu_j$ give exactly
$$
\lambda(\{z:a_j(\omega,z)>0\})=\mu_jr_j,
\qquad
\int_0^{\mu_j}a_j(\omega,z)\,dz
=u_j\mu_jr_j=\mu_jq_j.
$$
These identities hold for every draw, rather than merely almost surely.
The budget calculation is correct:
$$
\sum_{j=1}^{\tau}\mu_jq_j
=
\frac{B}{P}\sum_{j=1}^{\tau}\mu_jp_j
=B.
$$
Likewise, the contacted mass in every draw is exactly $W$, which satisfies the assumed bound $W\le\theta$.
For every fixed $z\in[0,\mu_j)$, the value $z/\mu_j$ lies in $[0,1)$. Applying the same rotation invariance to the uniform random variable $\omega$ gives contact probability $r_j$. Consequently,
$$
\mathbb{E}_{\omega}[a_j(\omega,z)]
=u_jr_j=q_j.
$$
This proves fairness at every point.
The use of one shared random variable across all types is permissible: the task imposes no independence requirement.
The construction covers $r_j=1$: the threshold event then includes the entire interval. Equality $W=\theta$, contact limit $\theta=1$, and support size $\tau=1$ also require no modification.
The statement that $W$ is the minimum achievable per-draw contact bound follows from the established necessity and the construction attaining contacted mass exactly $W$.
The algorithm’s comparison
$$
BS\le\theta P,
\qquad
S=\sum_{j=1}^{\tau}\frac{\mu_jp_j}{u_j},
$$
is equivalent to $W\le\theta$ because $P>0$.
Computing the two sums and making the comparison uses $O(\tau)$ rational arithmetic operations. The stated intermediate bit-length bound is sound for the described product-denominator representations: the input denominators and caps contribute total bit length $O(L)$, and adding at most $\tau$ numerator terms contributes at most $O(\log\tau)$ additional bits. The final multiplications introduce only further input factors, preserving the $O(L)$ bound.
Schoolbook integer arithmetic therefore supports the claimed
$$
O(\tau L^2)
$$
bit-operation bound. The description-size bound $O(\tau L)$ for the rational thresholds and construction is also valid.
The dependence on $m$, $B$, and $\theta$ is through their encodings in $L$, without pseudopolynomial dependence on their numerical magnitudes.
The cited paper supports the contextual claim of hardness for the finite municipality problem. [Gölz et al., *City Sampling for Citizens’ Assemblies*](https://arxiv.org/html/2509.07557v1). The continuous proof does not depend on that result.
No additional lemma, clarification, or repair is required. The output resolves the assigned decision problem.
⟨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.