| paper | Individual Representation in Approval-Based Committee Voting |
| authors | Markus Brill, Jonas Israel, Evi Micha, Jannik Peters |
| venue | AAAI 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), and a rational finite-support distribution \(\mu\) over approval types \(A\subseteq C\), define \(\nu_\mu(S)=\sum_{A\supseteq S}\mu_A\) and \(f_\mu(A)=\max\{|S|:S\subseteq A,\ \nu_\mu(S)\ge |S|/k\}\). Decide whether there exists a committee \(W\subseteq C\) with \(|W|\le k\) such that \(|W\cap A|\ge f_\mu(A)\) for every positive-mass type \(A\).
A finite-support high-multiplicity approval society with rational type masses \(\mu_A\); the decision variable is a committee \(W\) of at most \(k\) candidates, and feasibility requires each type's mass-based justified demand \(f_\mu(A)\) to be met.
The mirrors cover Theorems 5 and 6 directly and propose a weighted extension of Theorem 10; they leave incompatibility propositions, rule-consistency results, experiments, and non-complexity structural bounds aside.
My strongest case is affirmative, with Theorem 5 as the lead anchor. The paper’s central quantity already measures coalitions as fractions of the electorate, so replacing voter counts by population mass is unusually faithful here.
Take candidates \(C\), committee size \(k\), and a finite-support distribution \(\mu\) over approval types \(A\subseteq C\). Type \(A\) means a voter approving exactly \(A\); \(\mu_A\) is the fraction of society of that type. For \(S\subseteq C\), define its common-approval mass by \(\nu_\mu(S)=\sum_{A\supseteq S}\mu_A\), and define the justified demand of type \(A\) by \(f_\mu(A)=\max\{|S|:S\subseteq A,\ \nu_\mu(S)\ge |S|/k\}\). A committee remains a discrete set \(W\subseteq C\), \(|W|\le k\); continuity is only in the population. The objective is feasibility: find \(W\) satisfying \(|W\cap A|\ge f_\mu(A)\) for every positive-mass type \(A\), or report that none exists.
This is a credible high-multiplicity regime in large-scale participatory budgeting or national elections with a finite menu of proposals and many repeated ballot patterns. There may be \(n=q\tau\) voters but only \(\tau\) distinct approval types, with \(q\) large. The types are complete descriptions of the agents for this problem: voters with the same approval set are interchangeable.
The lead anchor is Theorem 5, proved in this paper: “It is NP-hard to decide whether an ABC election admits an IR committee or a semi-strong JR committee.” Its continuous counterpart is the problem just defined, which I would call Continuous IR-Feasibility.
The reduction transfers directly. Given the paper’s Exact Cover by 3-Sets instance with \(3\ell\) elements, make one approval type \(A_x\) for each element \(x\), with mass \(1/(3\ell)\). Each candidate is a 3-set. Set \(k=\ell\). Every candidate then has approval mass \(1/\ell=1/k\), while no set of two or more candidates has enough common mass to justify demand \(2\) or more. Thus every type has \(f_\mu(A_x)=1\), and a feasible committee of at most \(\ell\) candidates is exactly an exact cover.
Moreover, replace every type by \(q\) identical voters. The distribution \(\mu\) is unchanged, while \(n/\tau=q\) can be arbitrarily large. Thus this is not merely a relabelling of individual voters: it is a genuine high-multiplicity representation of a large population. The expected classification is Class B, because the reduction’s combinatorics live in the candidate/set system, not in population multiplicity. The continuous mirror therefore does not dissolve this hardness; it identifies a natural problem whose hardness survives continuization.
A second, independently useful anchor is Theorem 6, also proved here: “Given an ABC instance, a voter \(i\), and \(j\in\mathbb N\), it is NP-complete to decide whether \(f_i\ge j\).” Its mirror is Continuous Justified-Demand Recognition. The input is \(C,k\), a rational distribution \(\mu\) over approval types, a positive-mass type \(A\), and \(j\). The question is whether there exists \(S\subseteq A\) with \(|S|\ge j\) and \(\nu_\mu(S)\ge |S|/k\). A solution is such a set \(S\), or a certificate that no such set exists.
The balanced-complete-bipartite-subgraph reduction in Theorem 6 also survives with uniform masses. The target voter becomes a universal approval type, the other types encode vertices of \(V_1\), and the threshold \(|S|n/k\) becomes precisely the mass threshold \(|S|/k\). Duplicating every type \(q\) times again leaves the continuous instance unchanged while making the represented population arbitrarily large. Under explicit rational-support encoding, the problem remains in NP, since a \(j\)-element set \(S\) is a certificate, so I expect NP-completeness and again Class B. This anchor is valuable because it shows that even computing one type’s entitlement is computationally hard; the difficulty is not created only by having to coordinate all voters’ demands.
The third mirror uses Theorem 10, proved here: “For every approval profile satisfying voter interval, Algorithm 1 returns a \((2,4)\)-IR committee in polynomial time.” I would call its continuous version Weighted Voter-Interval Approximate IR.
An instance consists of candidates \(C\), committee size \(k\), and an ordered sequence of approval blocks \((A_1,w_1),\ldots,(A_q,w_q)\), where \(w_r\ge0\), \(\sum_r w_r=1\), and the voters approving each candidate form a consecutive interval of blocks. Each block represents a contiguous mass of otherwise identical voters. Define \(f_\mu(A_r)\) using the same common-approval mass formula as above. The task is to output \(W\subseteq C\), \(|W|\le k\), such that \(2|W\cap A_r|+4\ge f_\mu(A_r)\) for every block \(r\).
I expect this version to be Class A. The proof of Theorem 10 is based on interval structure, not on the identities of individual voters: common approvers form intervals, and the two rounds split each justified demand into left and right mass. Those arguments suggest a weighted sweep algorithm in which cardinalities are replaced by rational block masses. The paper does not prove this weighted theorem, so this is a proposed research direction rather than a claimed consequence. Natural follow-up questions are whether the \((2,4)\) guarantee survives with binary-encoded weights, whether the additive \(4\) can be reduced in a nonatomic limit, and whether exact IR feasibility becomes tractable on voter-interval societies.
These mirrors cover the paper’s main computational results: unrestricted IR-feasibility and individual-demand recognition through Theorems 5 and 6, and the positive restricted-domain algorithm through Theorem 10. I would not stretch the case to Proposition 1, Proposition 2, Proposition 4, or the experimental section; those are incompatibility, rule-behaviour, or empirical results rather than necessary computational anchors. Theorem 3 and Corollary 7 could also be translated into mass language, but they describe structural impossibility rather than complexity.
The weakest point is that the first two mirrors may look like weighted finite approval profiles rather than a fundamentally new continuum model. That criticism is fair: the paper’s hardness reductions themselves embed into the continuous versions, so they do not demonstrate a tractability gain from taking limits. But the programme explicitly includes Class B outcomes. The point is not that every problem becomes easier; it is that the population can be represented by its distribution, and the resulting computational landscape can be classified. Here the authors’ own \(n/k\)-based definition makes the mass formulation especially convincing, while Theorem 10 offers a plausible place where the continuous representation may genuinely expose an efficient interval-based algorithm.
I cannot honestly make a successful negative case here. The strongest possible objection is that the proposed mirrors are weighted approval elections with a discrete committee, rather than a genuinely new continuum. But ChoCo explicitly treats the population—not the committee—as the continuous object, and it explicitly counts Class B outcomes as worthwhile. Under those rules, the first anchor survives decisively.
For Theorem 5, the mass formulation is exact. Given an Exact Cover by 3-Sets instance with \(3\ell\) elements, assign mass \(1/(3\ell)\) to the approval type \(A_x\) for each element \(x\), let each candidate represent a 3-set, and set \(k=\ell\). Every candidate has approval mass \(1/\ell=1/k\), while no set of at least two candidates has common approval mass sufficient to justify demand \(2\). Hence every type has \(f_\mu(A_x)=1\), and a committee satisfying IR is precisely an exact cover.
This is not invalidated by the fact that the source reduction uses one voter per element. Replacing each type by \(q\) identical voters produces a population of \(3\ell q\) voters with only \(3\ell\) complete types, without changing \(\mu\), \(f_\mu\), or the feasible committees. The approval types are complete descriptions for this problem, and a large participatory electorate with repeated ballot patterns is a sensible high-multiplicity regime. Calling this “only a weighted restatement” would be an objection to high multiplicity itself, not to this mirror.
Theorem 6 survives for the same reason. In its reduction, use one universal target type and one type for each vertex of \(V_1\), all with equal mass, retain \(k=|V_1|+1\), and ask whether the target type has demand at least \(j+1\). A set consisting of \(y\) and \(j\) vertices of \(V_2\) has the required common mass exactly when \(j\) types from \(V_1\) jointly approve those vertices. Thus the \(K_{j,j}\) condition is preserved exactly. Again, cloning every type yields arbitrarily high multiplicity. The difficulty is not an artefact of named individuals.
The third anchor is weaker, because Theorem 10 itself does not establish the weighted version. A negative argument can reasonably say that the proof uses a discrete voter order, integer floors, and cardinality-based charging, so a polynomial-time algorithm for rational-mass blocks still needs to be proved rather than assumed. In particular, the ordered position of a voter may need to be included in the type description, and repeated approval sets occurring at different positions cannot simply be merged.
That objection defeats the proponent’s confidence, but not the mirror. An ordered list of contiguous cohorts with rational masses is a legitimate high-multiplicity population model. The key facts used by the proof—common approvers forming intervals and demands splitting into left and right portions—are additive facts, so a weighted sweep remains a plausible and sharply stated computational question. At worst, this anchor is conjectural; it is not ill-posed.
The only genuine negative conclusion is therefore methodological: Theorems 5 and 6 produce Class B mirrors whose hardness survives unchanged, while the Theorem 10 mirror requires new work before its algorithmic claim is credible. But neither point supports the universal claim that no worthwhile continuous mirror exists. The first two anchors already give exact, natural population distributions and computational problems with preserved hardness. A thoughtful reader should therefore reject the requested negative verdict.
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.