Boosting Sortition via Proportional Representation

The strongest honest positive case is a credible Class A mirror led by Theorem 3. This is not a claim that the paper studies continuous populations already, nor that its sortition problem has an NP-hardness classification. The paper’s relevant named results are efficient approximation theorems.

The natural regime is a citizens’ assembly drawn from a large population. Let \(T\) be a finite set of complete demographic/representation types, with rational metric \(d:T\times T\to\mathbb{Q}_{\ge0}\) and population distribution \(\mu\). A type includes every feature used by the representation metric. A country may have \(N\) millions of citizens but only \(\tau\) hundreds or thousands of relevant types, while the panel size \(k\) is perhaps \(20\)–\(100\). This is especially plausible here because the paper itself replaces tens of thousands of records by 1,513 or 2,204 weighted unique data points and explicitly treats each as representing a group of at least \(k\) people.

The finite bridge is exact. For rational \(\mu\), take \(N\mu_t\) indistinguishable clones of type \(t\), with \(N\) sufficiently large that every positive-mass type has at least \(k\) clones. A continuous panel is therefore a multiset \(p\in\mathbb{Z}_{\ge0}^{\tau}\) with \(\sum_t p_t=k\). Repeated copies of a type mean distinct citizens with identical representation-relevant characteristics, not repeated selection of one person.

For a panel \(p\), let \(c_q(t,p)\) be the distance from type \(t\) to its \(q\)-th closest representative. For an alternative panel \(p'\) of size \(r\), define \(V_{\mu,q}(p,p',\alpha)=\sum_{t\in T}\mu_t\mathbf{1}[c_q(t,p)>\alpha c_q(t,p')]\). Thus the finite condition \(V_q(P,P',\alpha)\ge rN/k\) becomes exactly \(V_{\mu,q}(p,p',\alpha)\ge r/k\). This is population continuity only: the panel still contains \(k\) discrete representatives, and the fractional objects below are merely compact descriptions of a randomized sampler.

My lead anchor is Theorem 3, proved by the authors in this paper: “for every \(q\in[k]\), FairGreedyCapture\(_k\) is fair and in the ex post \(6\)-\(q\)-core.” The corresponding continuous problem is:

\(\mathrm{FairCore}_{\infty}\): given \((T,d,\mu,k,q)\), find a randomized rule \(\lambda\) over typed panels \(p\) of size \(k\) minimizing the smallest \(\alpha\) such that every panel in the support of \(\lambda\) satisfies \(V_{\mu,q}(p,p',\alpha)<r/k\) for every alternative panel \(p'\) of size \(r\ge q\), subject to fairness \(\mathbb{E}_{p\sim\lambda}[p_t]=k\mu_t\) for every type \(t\).

A solution is a distribution over panels, or equivalently a succinct sampling kernel \(X\in[0,1]^{k\times\tau}\) with each row summing to \(1\) and each column summing to \(k\mu_t\). One representative is sampled from each row, with the rows corresponding to the \(k\) opened balls of FairGreedyCapture. The selected panel remains integral; \(X\) only specifies its distribution.

The paper’s proof transfers almost verbatim. Start each type with residual mass \(k\mu_t\), grow metric balls, open a ball when it captures residual mass \(1\), and assign exactly one unit of mass to it. There are exactly \(k\) balls. Every sampled panel contains one representative from every ball, while the fairness equations give \(\mathbb{E}[p_t]=k\mu_t\). The proof’s counting argument becomes a mass argument: a deviating coalition has mass at least \(r/k\), and the pigeonhole step produces \(q\) balls containing enough of that coalition. Hence the continuous problem should be in Class A, with a polynomial-time \(6\)-approximation in \(\operatorname{poly}(\tau,k,L)\), where \(L\) is the encoding length of \(d\) and \(\mu\). This is a genuine high-multiplicity reformulation, not a fractional-panel relaxation.

The main questions left by this anchor are whether the factor \(6\) can be reduced toward the paper’s lower bound \(2\), whether exact optimization of \(\mathrm{FairCore}_{\infty}\) has a polynomial-time algorithm, and whether Euclidean, \(L_1\), or \(L_\infty\) metrics improve the guarantee. A further useful question is the finite-population rounding rate when \(N\mu_t\) is large but finite.

A second, more explicitly computational anchor is Theorem 6, an authors’ result stated here and proved in the full version [12]: there is an efficient algorithm that approximates the maximum ex post \(q\)-core violation of a given panel \(P\) between \(\widehat{\alpha}\) and \(3\widehat{\alpha}+2\). The continuous problem is:

\(\mathrm{AuditCore}_{\infty}\): given \((T,d,\mu,k,q)\) and a baseline typed panel \(p\), compute \(\alpha^\ast=\sup\{\alpha:\exists p'\text{ of size }r\ge q,\ V_{\mu,q}(p,p',\alpha)\ge r/k\}\), and return \(\widehat{\alpha}\) satisfying \(\widehat{\alpha}\le\alpha^\ast\le3\widehat{\alpha}+2\).

The continuous version of Algorithm 2 examines each positive-mass type \(u\), forms \(\widehat p_u\) from the \(q\) nearest available clone representatives to \(u\), and takes the weighted \(q/k\)-upper quantile of the ratios \(c_q(t,p)/c_q(t,\widehat p_u)\). Since all clones of a type have identical distances, the individual loop collapses to a loop over \(T\). This should also be Class A at the stated approximation level, with exact auditing and separation complexity left open. The natural follow-up is whether exact auditing is hard when \(k\) is part of the input, or whether bounded \(q\), bounded \(\tau\), or geometric metrics yield stronger algorithms.

For calibration, Theorem 5 also transfers naturally: the authors show that for \(q<k\), sufficiently large finite populations contain instances where no fair rule achieves an ex ante factor below \(2\). In continuous notation, define \(\rho_{\mathrm{ea}}(\lambda)\) by requiring \(\sum_p\lambda(p)V_{\mu,q}(p,p',\alpha)<r/k\) for every alternative \(p'\), and minimize this over fair \(\lambda\). The finite counterexample lifts to a rational \(\mu\), so the continuous optimum is at least \(2\). Together with Theorem 4’s factor-\(4\) guarantee for uniform selection, this gives a meaningful continuous approximation window rather than an artificially easy model.

The weakest point is that the paper’s implementation uses an \(N\times N\) Birkhoff decomposition over named individuals, whereas the continuous algorithm needs a type-level coupling or sampling kernel and a proof that it preserves the ex post support guarantee. That is a real technical obligation, not notation. The defence is that the proof of Theorem 3 uses only residual mass, metric balls, and the fact that every opened ball contributes a representative; all of these survive the clone limit. The paper’s own weighted-data construction also makes the regime recognizable to its authors.

I would therefore submit only these mirrors: FairCore\(_\infty\) as the lead, AuditCore\(_\infty\) as the second, and the ex ante optimization as a supporting boundary result. They cover the paper’s algorithmic core while leaving its experiments, subjective metrics, volunteer-pool variants, and unrelated outcome-space notions outside scope.