| paper | The Degree of (Extended) Justified Representation and Its Optimization |
| authors | — |
| venue | AAMAS 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), an explicit finite support \(T\subseteq 2^C\), and rational masses \(\mu_A\ge 0\) summing to \(1\), with some candidate supported by mass at least \(1/k\), choose \(W\in\binom{C}{k}\) maximizing \(\operatorname{jrdeg}_\infty(\mu,W)=\min_{c:\sum_{A\ni c}\mu_A\ge 1/k}\max\{0,1/k-\sum_{A\ni c,\,A\cap W=\varnothing}\mu_A\}\); determine whether a polynomial-time algorithm can guarantee \(\operatorname{jrdeg}_\infty(\mu,W)\ge (1/k)^{1-\varepsilon}\operatorname{OPT}_\infty(\mu)\), where \(\operatorname{OPT}_\infty(\mu)=\max_{W'\in\binom{C}{k}}\operatorname{jrdeg}_\infty(\mu,W')\).
A finite high-multiplicity approval society with types \(A\subseteq C\), rational mass vector \(\mu\), and an ordinary integral committee \(W\in\binom{C}{k}\); the objective is the minimum represented mass in any cohesive mass-\(1/k\) group, equivalently the stated aggregate residual-coverage expression.
The mirror covers the MDJR side of Theorem 4, Theorem 1, and Proposition 2. It leaves Theorem 3, Theorems 5 and 6, the \(c_{\max}\)-parameterized algorithms, and MDEJR without a proved transfer.
The strongest honest case is a direct population-continuum mirror of MDJR. I would lead with Theorem 4 and use Theorem 1 as a constructive companion. I would not claim that every result in the paper survives unchanged.
Take a finite candidate set \(C\) and committee size \(k\). A voter type is an approval set \(A\subseteq C\), and the society is an explicitly given rational mass vector \(\mu=(\mu_A)\), with \(\sum_A\mu_A=1\). Thus \(\mu_A\) is the fraction of a large electorate having exactly approval ballot \(A\). The committee remains an ordinary integral \(k\)-subset \(W\subseteq C\); only the population is continuous.
A measurable subgroup of mass at least \(1/k\) is cohesive if all its members approve some common candidate. For a committee \(W\), a voter of type \(A\) is represented when \(A\cap W\neq\varnothing\). Define the continuous JR degree as the minimum represented mass over all cohesive subgroups of mass at least \(1/k\). The problem
\[ \mathrm{MDJR}_\infty: \]
given \((C,k,\mu)\), output a size-\(k\) committee maximizing that degree.
This can be written directly in terms of types. Let \(\mathcal C_\mu=\{c\in C:\sum_{A\ni c}\mu_A\ge 1/k\}\), and let \(u_\mu(W,c)=\sum_{A\ni c,\;A\cap W=\varnothing}\mu_A\) be the mass approving \(c\) but approving no winner. Then the degree is
\[ \operatorname{jrdeg}_\infty(\mu,W) = \min_{c\in\mathcal C_\mu} \max\left\{0,\frac{1}{k}-u_\mu(W,c)\right\}. \]
This is exactly the paper’s “number of represented voters” objective after normalization by population size. The paper itself observes that, for JR, the number and fraction formulations are equivalent. A solution is an integral committee \(W\), not a fractional committee or fractional candidate selection.
The natural regime is a large federation, professional association, union, or online community selecting a small representative committee. Millions of members may fall into a few hundred or thousand approval cohorts because they share the same chapter, role, policy package, or issue-based ballot. The relevant type is the complete approval ballot used by the paper; named voter identity has no role in MDJR. Rational masses can be cleared to clone populations, choosing the denominator divisible by \(k\), so the cohesive threshold becomes exactly integral. Thus this is a genuine high-multiplicity version, not merely arbitrary weighted voting.
My lead anchor is Theorem 4, proved in this paper: “It is NP-hard to approximate MDJR and MDEJR within a factor of \((1/k)^{1-\epsilon}\) for any \(\epsilon>0\).” I use the MDJR half of the theorem.
The corresponding continuous question is: does there exist a polynomial-time algorithm which, for every rational-mass instance \((C,k,\mu)\), returns \(W\) with
\[ \operatorname{jrdeg}_\infty(\mu,W) \ge (1/k)^{1-\epsilon} \max_{|W'|=k}\operatorname{jrdeg}_\infty(\mu,W')? \]
The expected classification is Class B: hardness transfers.
The paper’s sparse-SAT reduction already has the required high-multiplicity structure. Each variable group \(T_j\), clause group \(S_i\), and the groups \(D,D^+\) consist of voters with identical approval sets. Replacing each group by one type with mass equal to its group size divided by the total population gives a continuous instance with only \(O(\bar m+\bar n)\) types but \(\Theta(\bar m^2+\bar n\bar m)\) voters after denominator clearing. Hence the reduction is naturally a reduction over repeated voter types.
If the formula is satisfiable, selecting \(d\) and one literal candidate for each variable represents all population mass, so the continuous optimum is \(1/k\). If it is unsatisfiable, some clause group \(S_i\) is uncovered; the cohesive group \(S_i\cup D\) has mass exactly \(1/k\), but only the \(D\)-mass \(\bar n/N\) is represented. The paper’s padding step makes the resulting gap at most \((1/k)^{1-\epsilon}\). Allowing a cohesive group to split a type does not help: every voter in a type has the same representation status, and the relevant minimum is already captured by the formula above. The combinatorics lives in the literal and clause candidates, not in voter multiplicity. That is precisely the kind of hardness the continuous mirror should preserve.
The second anchor is Theorem 1, also proved here: “GreedyAV runs in polynomial time and provides a \(1/k\)-approximation to MDJR.” Its continuous problem is the same \(\mathrm{MDJR}_\infty\) problem with the specified algorithmic requirement. Continuous GreedyAV repeatedly selects the candidate covering the greatest currently uncovered mass, where “covering” a type means that the type’s approval set intersects the current committee. It runs in time polynomial in \(m\), the explicit number of types \(\tau\), and the bit length of the masses. The proof of Proposition 2 scales to show degree at least \(1/k^2\); since every committee has degree at most \(1/k\), this is a \(1/k\)-approximation. This is Class A for the approximation task, coexisting naturally with Class-B hardness for substantially better approximation and exact optimization.
The mirror covers the MDJR results emphatically: Theorem 1, Proposition 2, and the MDJR part of Theorem 4. It does not claim the paper’s W[2]-hardness theorems or the \(c_{\max}\)-parameterized algorithms, because their omitted reductions and integer parameter dependence require a separate transfer proof. Nor do I rely on MDEJR: its number-based definition has additional scaling choices for different \(\ell\), which deserve their own formulation.
The main further questions are whether exact \(\mathrm{MDJR}_\infty\) admits useful formulations as a weighted min-max coverage problem, whether stronger approximation is possible for bounded \(\tau\) or structured approval domains, and how precisely continuous optima round to finite clone elections. A natural extension is \(\mathrm{MDEJR}_\infty\), using mass at least \(\ell/k\) in every \(\ell\)-cohesive group, but the paper’s warning that number and fraction versions diverge for EJR must be respected.
The weakest point is that the continuum permits a cohesive subgroup to split a type, whereas the original electorate contains indivisible voters. For JR this concern is unusually mild: after denominator clearing with population size divisible by \(k\), the explicit degree formula has an integer optimum and recovers the clone instance exactly. Still, a referee could reasonably request a formal rounding lemma for arbitrary rational inputs. That is a technical obligation, not a reason to reject the mirror: the paper’s own reduction consists of repeated approval types, its committee remains discrete, and its hardness survives precisely because the difficulty is in candidate selection rather than individual population identity.
The strongest negative case is that the proposed mirror contains no genuinely continuous optimization problem. Once voter identity is removed, a cohesive subgroup can be characterized entirely by aggregate mass. For a committee \(W\), the JR degree becomes
\[ \min_{c:\,\mu(\{A:c\in A\})\ge 1/k} \max\left\{0,\frac{1}{k}-\mu(\{A:c\in A,\ A\cap W=\varnothing\})\right\}. \]
Thus the continuum collapses the paper’s central group quantifier into a residual weighted-coverage expression. The committee is still an integral \(k\)-subset, and the only continuous data are rational weights. If types are kept indivisible, the model is merely a weighted finite election; if they are splittable, the fairness notion loses the individual/cohort structure that motivated it. Theorem 1 consequently becomes weighted GreedyAV, while Theorem 4 becomes sparse-SAT encoded through candidate choices. Neither exposes a new continuous phenomenon.
That objection is not sufficient under ChoCo’s rules, however. Weighted high-multiplicity elections are explicitly in scope, and the absence of a fractional committee or LP is not disqualifying. Theorem 4’s construction already consists of \(O(\bar m+\bar n)\) identical voter types with binary-sized multiplicities. Replacing those cohorts by masses preserves the gap: satisfiable instances have degree \(1/k\), while unsatisfiable instances have degree at most \(\bar n/N\). This is a legitimate Class B mirror, not a malformed one. Theorem 1 likewise transfers directly to weighted GreedyAV.
Nor can the mirror be rejected as lacking multiplicity or depending on identity: MDJR is anonymous and its reductions deliberately use repeated approval ballots. Existing high-multiplicity work would support, rather than undermine, this modelling choice. The only way to defeat the anchor would be to require every worthwhile mirror to introduce continuous decision variables or continuum-specific tractability, a criterion the programme expressly does not impose.
So the honest negative case is weak. It can argue that the mirror is algorithmically conventional and may offer little beyond a weighted reformulation, but it cannot establish that no worthwhile continuous mirror exists. The proponent’s MDJR anchor survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.