Paper deep dive
Multi-Winner Voting with Argumentative Ballots
Ryuta Arisaka, Hirotaka Ono
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4.
Tags
Links
- Source: https://arxiv.org/abs/2608.23247v1
- Canonical: https://arxiv.org/abs/2608.23247v1
Trouble viewing inline? Open PDF directly →
Full Text
106,591 characters extracted from source content.
Expand or collapse full text
Multi-Winner Voting with Argumentative Ballots Ryuta Arisaka Hirotaka Ono Abstract We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms , JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4. 1 Introduction From parliamentary elections and participatory budgeting to recommendation formation, collective decision making requires selecting multiple winners. A prominent model for such tasks is approval-based multi-winner voting, where each voter records a set of acceptable candidates and a voting rule aggregates the resulting approval profile into a fixed-size set of winners. A central concern in approval-based multi-winner voting is proportional representation. Intuitively, a sufficiently large set of voters that agrees on sufficiently many candidates should see its preferred candidates represented in the winning set, in proportion to the group’s degree of cohesion. This idea has led both to methods for selecting winner sets (Lackner and Skowron 2023) and to justified representation axioms, such as , JR, PJR and EJR (Aziz et al. 2017; Sánchez-Fernández et al. 2026), which provide qualitative fairness criteria for evaluating such methods. These ideas have also influenced real participatory budgeting processes (Peters and Skowron 2020). Notwithstanding this success, a recent social experiment suggests that voters perceive more expressive input formats as better reflecting their preferences than approval voting (Yang et al. 2024). Full rankings are, of course, unrealistic both computationally and operationally in many settings (Lang and Xia 2016). Nevertheless, finding an alternative format that allows voters to express their preferences in more detail remains desirable. With this motivation, we propose argumentative ballots for multi-winner voting. The underlying principle is that of abstract argumentation frameworks (Dung 1995), originally introduced for reasoning about argumentative dialogues. An abstract argumentation framework models argumentative information as a directed graph of entities. It encodes attack and defence relationships among entities. As a very simple example, c3→c2→c1c_3→ c_2→ c_1 expresses that c3c_3 attacks c2c_2 which attacks c1c_1. Normally (Dung 1995), c3c_3 then defends c1c_1 and both c3c_3 and c1c_1 (but not c2c_2) are acceptable. In multi-winner voting with argumentative ballots, every voter receives a ballot on which the candidates are written. Instead of marking each candidate as approved or not approved as in an ordinary approval ballot, the voter can draw arrows between candidates to express attack claims. Approval by a set of voters is determined with respect to the combined directed graph obtained from their attack claims. c3 @inpgf@ignorespaces c_3c2 @inpgf@ignorespaces c_2c1 @inpgf@ignorespaces c_1Alice’s ballotc3 @inpgf@ignorespaces c_3c2 @inpgf@ignorespaces c_2c1 @inpgf@ignorespaces c_1Bob’s ballot With these two argumentative ballots, Alice approves both c3c_3 and c2c_2 but not c1c_1. Bob approves both c3c_3 and c1c_1 but not c2c_2. Collectively, Alice and Bob approve c3c_3 and c1c_1 but not c2c_2. The corresponding ordinary approval ballots would yield collective approval only of c3c_3 (from the individual approvals c3,c2\c_3,c_2\ and c3,c1\c_3,c_1\). So, argumentative ballots allow collective approvals to be more expressive: the same individual approval sets may give rise to different collective approvals depending on the underlying attack and defence relations. This additional expressiveness raises the central questions of this paper: how should voter cohesion and justified representation be defined when approvals are induced argumentatively, and to what extent are the computational advantages of approval-based multi-winner voting preserved in this setting? After technical preliminaries in Section 2, we make the following contributions. 1. We introduce multi-winner voting with argumentative ballots (MVArg) (Section 3.1). 2. We show that MVArg is a conservative generalisation of the standard approval-based multi-winner voting (MV) (Lackner and Skowron 2023). At the same time, MVArg is strictly more expressive: for fixed individual approval sets, MV determines a unique collective approval outcome, whereas MVArg may induce different collective approvals (Section 3.2). 3. We define notions of voter cohesion for MVArg and establish several of their theoretical properties (Section 3.3). 4. We formulate the MVArg counterparts of , JR, PJR and EJR (Section 4.1). 5. We show that they are conservative generalisations of , JR, PJR and EJR (Section 4.2). A winner set providing (the fairness defined in) the MVArg’s counterpart of JR always exists. For the MVArg counterparts of PJR and EJR, we identify additional cohesion constraints that restore existence (Section 4.3). Verifying whether a given winner set provides (the fairness defined in) the MVArg counterpart of JR is already coNP-hard, even though such a winner set can be constructed in polynomial time (Section 4.4). Technically, we introduce a direct inductive covering argument for the existence theorems, which to the best of our knowledge is a novel proof strategy in the study of justified representation. Together, these results show what remains valid, what changes, and what becomes computationally harder when approval ballots are replaced by argumentative ballots. A Lean 4 formalisation of all definitions, propositions (Propositions 1 through 7), auxiliary lemmas (Lemmas 1 through 3) and theorems (Theorems 1 through 8), together with the accompanying Java implementation of GreedyGrounded for Theorem 8, is provided as supporting material with the arXiv submission. Related work Approval-based multi-winner voting. (Aziz et al. 2017) introduced JR and EJR for approval-based multi-winner voting, and (Sánchez-Fernández et al. 2026) introduced PJR, which lies between them. These axioms formalise group fairness: sufficiently large groups of voters that agree on sufficiently many candidates should be represented in the winning set. In this classical setting, approvals are primitive and collective approvals are monotonic. MVArg differs in that approvals are induced by voters’ argumentative ballots and may become non-monotonic when ballots are combined. Justified representation therefore needs to be reformulated for MVArg. Collective choice and participatory institutions. In institutional settings such as participatory budgeting, a limited portfolio should provide representation to cohesive groups of citizens (Peters and Skowron 2020; Peters, Pierczyński, and Skowron 2021; Brill et al. 2023). Approval-based models generally treat reported approvals as primitive. In policy decisions, however, alternatives may be evaluated relationally: one project may substitute for another (Jain, Sornat, and Talmon 2020), undermine its rationale, or answer an objection to it. MVArg allows for retaining such relations. While our contribution remains axiomatic and computational, MVArg offers a foundation for studying representation when collective evaluations depend on explicitly reported reasons. Structured and conditional preferences. MVArg is also related to voting in combinatorial domains (Lang and Xia 2016) and conditional preference languages such as CP-nets (Boutilier et al. 2004), where outcomes are structured and preferences may depend on relations among issues or variables. The source of these dependences is different in MVArg: dependencies arise from attack and defence relations inside argumentative ballots, and candidate approvals are induced by acceptability semantics. Specifically, instead of representing preferences over bundles of candidates, MVArg represents justificatory relations among individually selectable candidates. Accepting one candidate may undermine or defend another. Our concern is therefore not preference optimisation over structured outcomes, but proportional representation when the acceptability of candidates is reason-dependent. Argumentation and voting. Abstract argumentation frameworks were introduced by (Dung 1995) as directed graphs of arguments and attacks, together with semantics determining acceptability. Several works combine argumentation and voting. (Leite and Martins 2011) incorporate positive and negative votes into argumentation frameworks; (Awad et al. 2017) study judgment aggregation over argument labels in a fixed framework; and (Bernreiter et al. 2024) combine approval voting and abstract argumentation to select representative acceptable sets of arguments. These works largely assume a fixed underlying argumentation framework and primitive votes or approvals over its arguments. More recently, (Naoki Susami and Ryuta Arisaka 2026) have explicitly assumed local abstract argumentation frameworks and one global abstract argumentation framework. Still, their work does not materialise collective approvals and its objective remains to filter acceptability semantics. In contrast, MVArg uses an argumentation framework as each voter’s ballot: approvals are derived from those ballots, and can therefore become non-monotonic under ballot combination. Rather than aggregating evaluations of arguments within a fixed framework, we generalise approval-based multi-winner voting by allowing argumentation frameworks as ballots. Figure 1: The first row from left to right: a blank ballot; v1v_1’s ballot approving c1c_1 and c5c_5; v2v_2’s ballot approving c1,c2c_1,c_2 and c4c_4; and v3v_3’s ballot approving c1,c2,c3c_1,c_2,c_3 and c6c_6. The second row from left to right: v1,v2\v_1,v_2\’s collective approval of c1c_1 and c4c_4; v1,v3\v_1,v_3\’s collective approval of c1c_1; v2,v3\v_2,v_3\’s collective approval of c1,c2c_1,c_2 and c4c_4; and v1,v2,v3\v_1,v_2,v_3\’s collective approval of c1,c3c_1,c_3 and c6c_6. 2 Technical Preliminaries Multi-winner voting and justified representation. Let V≡v1,…,vnV≡\v_1,…,v_n\ be a set of voters, let C≡c1,…,cmC≡\c_1,…,c_m\ be a set of candidates, let A≡(Av1,…,Avn)A≡(A_v_1,…,A_v_n)—where AviA_v_i is a subset of C—be the voters’ approval profile, and let k be the number of winners not greater than |C||C|. Then, (V,C,A,k)(V,C,A,k) is a multi-winner voting profile. In this paper, M M denotes the set of all multi-winner voting profiles. Let AV′∀A^∀_V denote ⋂v∈V′Av _v∈ V A_v. For any subset V′V of V and any candidate c∈Cc∈ C, V′V approves c iff (if and only if) c∈AV′∀c∈ A^∀_V . So, AV′∀A^∀_V is the set of all candidates V′V approves. For any subset V′V of V and any positive integer l, V′V is l-cohesive iff (1) |V′|≥l⋅(|V|/k)|V |≥ l·(|V|/k), and (2) |AV′∀|≥l|A^∀_V |≥ l.11 1 Here, (|V|/k)(|V|/k) is the Hare Quota for a subset of V to rightly demand 1 winner allocation to it. For any winner set W, which is a subset of C with |W|=k|W|=k, W satisfies, or, following the terminology in (Aziz et al. 2017), provides: • JR iff, for any subset V′V of V, if V′V is 11-cohesive, then there is some v∈V′v∈ V such that |W∩Av∀|≥1|W∩ A^∀_\v\|≥ 1. • PJR iff, for any subset V′V of V, if V′V is l-cohesive, then |W∩⋃v∈V′Av∀|≥l|W∩ _v∈ V A^∀_\v\|≥ l. • EJR iff, for any subset V′V of V, if V′V is l-cohesive, then there is some v∈V′v∈ V such that |W∩Av∀|≥l|W∩ A_\v\^∀|≥ l. These are justified representation axioms. For x∈x∈ M M, let ν be a member of JR,PJR,EJR\JR,PJR,EJR\, and let ν(x)ν(x) be the set of all subsets W of C such that W provides: JR if ν is JRJR; PJR if ν is PJRPJR; and EJR if ν is EJREJR. Then: • ∅⊂EJR(x)⊆PJR(x)⊆JR(x) ⊂ EJR(x) PJR(x) JR(x). • Some member of ν(x)ν(x) is polynomial-time computable. • Verification of membership of W in EJR(x)EJR(x), as well as that in PJR(x)PJR(x), is coNP-complete. • Verification of membership of W in JR(x)JR(x) is polynomial-time decidable. Grounded acceptance in abstract argumentation. Let (Arg,R)(Arg,R) be an abstract argumentation framework (Dung 1995) where ArgArg is a finite set of entities (called arguments) and R is a subset of Arg×ArgArg× Arg. a attacks a′a iff (a,a′)∈R(a,a )∈ R. Let Arg′Arg be a subset of ArgArg. Arg′Arg is conflict-free iff, for any a1∈Arg′a_1∈ Arg and a2∈Arg′a_2∈ Arg , (a1,a2)∉R(a_1,a_2) ∈ R. Arg′Arg defends an argument a∈Arga∈ Arg iff, for any a′∈Arga ∈ Arg, if (a′,a)∈R(a ,a)∈ R, then there is some a′∈Arg′a ∈ Arg such that (a′,a′)∈R(a ,a )∈ R. Arg′Arg is admissible iff Arg′Arg is conflict-free and, for any a∈Arg′a∈ Arg , Arg′Arg defends a. The grounded extension is then defined as a set of arguments Arg′Arg satisfying the following conditions. • Arg′Arg is admissible and, for any argument a∈Arga∈ Arg, if Arg′Arg defends a, then a is in Arg′Arg . • Arg′Arg is the least such set of arguments. The following facts hold for every (Arg,R)(Arg,R) (Dung 1995). • Let (…)P(...) denote the power set of ..., the grounded extension is polynomial-time computable as the least fixpoint of F:(Arg)→(Arg)F:P(Arg) (Arg) defined as: F(Arg′)=a∈Arg∣Arg′ defends aF(Arg )=\a∈ Arg Arg defends a\. • Every (Arg,R)(Arg,R) has a unique grounded extension. Other types of extensions exist (Baroni and Giacomin 2007), but in general they encode more disputable acceptance, are not unique and can be computationally more demanding. 3 Multi-Winner Voting with Argumentative Ballots 3.1 Conceptualisation As briefly described in Section 1, argumentative ballots allow voters to report their attack claims. Example 1 (City projects) . A city receives daily complaints about congestion on the main road between Districts A and B. It has proposed six projects to mitigate congestion: c1:build a new subway line,c2:widen the main road,c3:build a new tram line,c4:build high-frequency bus lanes,c5:introduce congestion pricing,c6:build a large parking garage. array[]lc_1:&build a new subway line,\\ c_2:&widen the main road,\\ c_3:&build a new tram line,\\ c_4:&build high-frequency bus lanes,\\ c_5:&introduce congestion pricing,\\ c_6:&build a large parking garage. array Three projects will be selected. Voters v1,v2,v3v_1,v_2,v_3 cast argumentative ballots over these candidates. A blank ballot, shown in the first column of the first row of Figure 1, contains all candidates and no attacks; by default, they are all approved. By drawing arrows, voters supply their attack claims. ci→cjc_i→ c_j on a ballot specifically means that acceptance of cic_i undermines the case for cjc_j. The ballots by v1v_1, v2v_2 and v3v_3 are in the second, third and fourth columns of the first row. v1v_1: Approves c1c_1 and c5c_5 with the attack claims: • c1→c2c_1→ c_2: “A new subway line undermines the case for widening main road.” • c5→c3,c4,c6c_5→\c_3,c_4,c_6\: “Congestion pricing undermines the case for a new tram line, high-frequency bus lanes and a large parking garage.” v2v_2: Approves c1,c2c_1,c_2 and c4c_4 with the attack claims: • c1→c5c_1→ c_5, c2→c3c_2→ c_3 and c4→c3,c6c_4→\c_3,c_6\: (All similarly) v3v_3: Approves c1,c2,c3,c6c_1,c_2,c_3,c_6 with the attack claims: • c3→c4c_3→ c_4: (Similarly) • c5→c5c_5→ c_5: “The case for congestion pricing is unconditionally undermined.” Each voter individually approves the candidates in the grounded extension of the corresponding argumentation framework. For a set of voters, the attack claims in their ballots are pooled together, and the group collectively approves the candidates in the grounded extension of the combined framework, as shown in the second row. This produces non-monotonic collective approvals. For example, voter v1v_1 alone does not approve c4c_4, because v1v_1 approves c5c_5 and c5c_5 attacks c4c_4. However, in the combined ballot of v1,v2\v_1,v_2\, c1c_1 is approved and c1c_1 attacks c5c_5. The attack claim c5→c4c_5→ c_4 is therefore neutralised, and c4c_4 becomes approved by v1,v2\v_1,v_2\. In other words, adding a voter’s ballot can turn a previously non-approved candidate into an approved one. This is impossible in standard approval ballots, where approvals are primitive and do not change when ballots are combined. ♠ We now formalise this intuition by defining argumentative voting profiles and approvals. Definition 1 (Argumentative voting profile) Let V≡v1,…,vnV≡\v_1,…,v_n\ be a set of voters, let C≡c1,…,cmC≡\c_1,…,c_m\ be a set of candidates, and let B≡(Bv1,…,Bvn)B≡(B_\v_1\,…,B_\v_n\)—where BviB_\v_i\ is an abstract argumentation framework (C,Rvi)(C,R_v_i)—be voters’ argumentative ballots, and let k be the number of winners not greater than |C||C|. Then, (V,C,B,k)(V,C,B,k) is an argumentative voting profile. M A denotes the set of all argumentative voting profiles. ♣ Example 1 gives rise to an argumentative voting profile (v1,v2,v3,c1,…,c6,B,3)(\v_1,v_2,v_3\,\c_1,…,c_6\,B,3) where B is as given in the second, third and fourth columns of the first row in Figure 1. Unless stated otherwise, we fix an arbitrary argumentative voting profile (V,C,B,k)(V,C,B,k). When we write V, it is the first component of the argumentative voting profile, and similarly for all other symbols. Definition 2 (Approvals in argumentative voting profile) For any subset V′V of V and any candidate c∈Cc∈ C, V′V approves c iff c is in the grounded extension of (C,⋃v∈V′Rv)(C, _v∈ V R_v). BV′∀B^∀_V denotes the set of all candidates approved by V′V . ♣ In Example 1, Bv1∀B^∀_\v_1\ is c1,c5\c_1,c_5\, Bv2∀B^∀_\v_2\ is c1,c2,c4\c_1,c_2,c_4\, Bv1,v2∀B^∀_\v_1,v_2\ is c1,c4\c_1,c_4\, Bv1,v2,v3∀B^∀_\v_1,v_2,v_3\ is c1,c3,c6\c_1,c_3,c_6\ with the remaining collective approvals shown in Figure 1. 3.2 Relationship between M M and M A A multi-winner voting profile is encoded into M A preserving approvals. Proposition 1 (Approval-preserving transformation) There is some function τ:→τ: M M→ M A such that, for any (V,C,A,k)∈(V,C,A,k)∈ M M, τ(V,C,A,k)=(V,C,B,k)τ(V,C,A,k)=(V,C,B,k) (for some B) and that AV′∀=BV′∀A^∀_V =B^∀_V for any non-empty subset V′V of V. τ can be instantiated in many ways, but (Bv1,…,Bv|V|)(B_\v_1\,…,B_\v_|V|\) where BviB_\v_i\ is (C,(c,c)∣c∉Avi)(C,\(c,c) c ∈ A_v_i\) is one of the simplest. In this instantiation, an unconditional non-approval on the standard approval ballot is a self-loop around the candidate. Continuing Example 1, let (v1,v2,v3,c1,…,c6,A,3)(\v_1,v_2,v_3\, \c_1,…,c_6\,A,3) be such that, for any v∈v1,v2,v3v∈\v_1,v_2,v_3\, Av∀=Bv∀A_\v\^∀=B_\v\^∀. The above concrete τ returns (v1,v2,v3,c1,…,c6,B′,3)(\v_1,v_2,v_3\,\c_1,…,c_6\,B ,3) where B′B comprises the following argumentative ballots. c1 @inpgf@ignorespaces c_1c2 @inpgf@ignorespaces c_2c3 @inpgf@ignorespaces c_3c4 @inpgf@ignorespaces c_4c5 @inpgf@ignorespaces c_5c6 @inpgf@ignorespaces c_6′ B _\v_1\c1 @inpgf@ignorespaces c_1c2 @inpgf@ignorespaces c_2c3 @inpgf@ignorespaces c_3c4 @inpgf@ignorespaces c_4c5 @inpgf@ignorespaces c_5c6 @inpgf@ignorespaces c_6′ B _\v_2\c1 @inpgf@ignorespaces c_1c2 @inpgf@ignorespaces c_2c3 @inpgf@ignorespaces c_3c4 @inpgf@ignorespaces c_4c5 @inpgf@ignorespaces c_5c6 @inpgf@ignorespaces c_6′ B _\v_3\ It holds that Bv′∀=Av∀B ∀_\v\=A^∀_\v\. This approval-preserving transformation offers an argumentative interpretation of ballot combination in M M: collective approval by a set of voters is the result of pooling the attack claims in their ballots and obtaining approved candidates in the resulting framework. Aggregation of attacks by union reproduces exactly the collective approvals in M M. As for monotonicity of collective approvals in M M: Fact 1 (Approval monotonicity in M M) Let (V,C,A,k)(V,C,A,k) be a multi-winner voting profile in M M. If V1′V _1 and V2′V _2 are non-empty subsets of V and if V1′⊆V2′V _1 V _2, then AV2′∀⊆AV1′∀A^∀_V _2 A^∀_V _1. τ preserves it in M A, but, as evidenced in Figure 1, it is not the universal property of M A. In fact, for some argumentative voting profile, approval sets can strictly grow in size e.g. Bv1,v3∀⊂Bv1,v2,v3∀B^∀_\v_1,v_3\⊂ B^∀_\v_1,v_2,v_3\ in Figure 1, for some, they can shrink in size, and for some other, the size of approval sets stays the same but their members change e.g. Bv1∀≠Bv1,v2∀B^∀_\v_1\ =B^∀_\v_1,v_2\ but |Bv1∀|=|Bv1,v2∀|=2|B^∀_\v_1\|=|B^∀_\v_1,v_2\|=2. Proposition 2 (No bijection) There is no function τ′:→τ : M A→ M M such that, for any (V,C,B,k)∈(V,C,B,k)∈ M A, τ′(V,C,B,k)τ (V,C,B,k) is (V,C,A,k)(V,C,A,k) (for some A) and that BV′∀=AV′∀B^∀_V =A^∀_V for any non-empty subset V′V of V. Proposition 2 clarifies the sense in which M A is more expressive than M M. In M M, once the individual approval sets are fixed, the collective approval of every voter set is fixed as their intersection. In M A, by contrast, two voting profiles may induce the same individual approvals but different collective approvals, because attacks from different ballots can interact through defence after combination. Argumentative ballots therefore retain relational information that is lost in ordinary ballots. Propositions 1 and 2 together show that M A reproduces every multi-winner voting profile while also admitting collective-approval patterns that are not realised in M M. 3.3 Argumentative cohesion and (l,m,n)(l,m,n)-cohesion We now formulate the notions of cohesion in ℳM A. In ordinary approval voting, cohesion is hereditary: if a set of voters collectively approves at least l candidates, then every non-empty subset also does so. Argumentative approvals are non-monotonic, so this hereditary property may fail. We therefore measure cohesion by how widely approval of l candidates persists across the set’s subsets. We make the following observation about l-cohesion in (V,C,A,k)∈(V,C,A,k)∈ M M: if V′⊆V V is l-cohesive, there are at least 2l⋅(|V|/k)−12^l·(|V|/k)-1 distinct subsets of V′V such that, for each V′V of them, |AV′∀|≥l|A^∀_V |≥ l. So, the key idea is to shift our focus to sufficiently agreeing subsets. With this insight, we define l-eligibility. Definition 3 (l-eligibility) Let V′V be a subset of V. V′V is l-eligible iff V′V is non-empty and |BV′∀|≥l|B_V ^∀|≥ l. By (l,V′) eligible(l,V ), we denote the set of all l-eligible subsets of V’, i.e. V′⊆V′∣V′ is l-eligible\V V V is $l$-eligible\. ♣ In Example 1, v1\v_1\ is 1- and 2- eligible—or up to 2-eligible. v1,v3\v_1,v_3\ is 1-eligible. v1,v2,v3\v_1,v_2,v_3\ is up to 3-eligible. Generally, V′V is up to |BV′∀||B^∀_V |-eligible. We now formulate argumentative l-cohesion based on the counts of eligible sets: Definition 4 (Argumentative l-cohesion) Let V′V be a subset of V, let (V′)P(V ) be the set of all subsets of V′V , and let l be a positive integer. V′V is argumentative l-cohesive iff there exists a subset V′V of V′V such that V′V is l-eligible and |(l,V′)|≥2l⋅|V|/k−1| eligible(l,V )|≥ 2^l·|V|/k-1. ♣ The number of winners (=k=k) is 3 in Example 1. • Any non-empty subset of v1,v2,v3\v_1,v_2,v_3\ is argumentative 1-cohesive. • v1,v2\v_1,v_2\, v2,v3\v_2,v_3\ and v1,v2,v3\v_1,v_2,v_3\ are argumentative 2-cohesive. The others are not. The size requirement that a l-cohesive set contains at least l⋅|V|/kl·|V|/k voters is implicit in Definition 4. Proposition 3 (Implicit size requirement) Let V′V be a non-empty subset of V and let l be a positive integer. If |(l,V′)|≥2l⋅|V|/k−1| eligible(l,V )|≥ 2^l·|V|/k-1, then necessarily |V′|≥l⋅|V|/k|V |≥ l·|V|/k. Monotonicity holds for argumentative l-cohesion. Proposition 4 (Monotonicity of argumentative cohesion) Let V′V be a non-empty subset of V and let l be a positive integer. If V′V is argumentative l-cohesive, then for any superset VsuperV_super of V′V , VsuperV_super is argumentative l-cohesive. This relaxation (even if we apply the same relaxation for M M and make the standard l-cohesion similarly monotonic) will turn out to be completely harmless for winner selection (Theorem 1 in Section 4). At times, though, stronger notions of cohesion are desirable. To this end, we introduce two conditions on cohesion. The first one requires that at least m (m≤lm≤ l) common candidates are approved by all eligible subsets. The second one requires that every non-empty subset approves at least n (n≤ln≤ l) candidates. Definition 5 ((l,m,n)(l,m,n)-cohesion) Let V′V be a subset of V, let l be a positive integer and let m,nm,n be non-negative integers not greater than l. V′V is (l,m,n)(l,m,n)-cohesive iff 1. V′V is argumentative l-cohesive. 2. m≤|⋂V′∈(l,V′)BV′∀|m≤| _V ∈ eligible(l,V )B^∀_V |. (Common candidates) 3. n≤min∅≠V′⊆V′|BV′∀|n≤ min_ =V V |B^∀_V |. (Minimum approval count) ♣ In Example 1, for instance, • v1\v_1\ is (1,m1,n1)(1,m_1,n_1)-cohesive for all 0≤m1≤10≤ m_1≤ 1 and all 0≤n1≤10≤ n_1≤ 1. • v2\v_2\ is 1.m2.n21.m_2.n_2-cohesive for all 0≤m2≤10≤ m_2≤ 1 and all 0≤n2≤10≤ n_2≤ 1. • v1,v2\v_1,v_2\ is (l12,m12,n12)(l_12,m_12,n_12)-cohesive for all 1≤l12≤21≤ l_12≤ 2, all 0≤m12≤10≤ m_12≤ 1 and all 0≤n12≤l120≤ n_12≤ l_12. • v1,v3\v_1,v_3\ is (1,m13,n13)(1,m_13,n_13)-cohesive for all 0≤m13≤10≤ m_13≤ 1 and all 0≤n13≤10≤ n_13≤ 1. • v1,v2,v3\v_1,v_2,v_3\ is (l123,m123,n123)(l_123,m_123,n_123)-cohesive for all 1≤l123≤21≤ l_123≤ 2, all 0≤m123≤10≤ m_123≤ 1 and all 0≤n123≤10≤ n_123≤ 1. Proposition 5 (Conservation) Let V′V be a subset of V and let l be a positive integer. V′V is argumentative l-cohesive iff V′V is (l,0,0)(l,0,0)-cohesive. Proposition 6 (Cohesion monotonicity) Let V′V be a subset of V, let l be a positive integer, and let m,nm,n be non-negative integers. Let m′m be a non-negative integer not greater than m, and let n′n be a non-negative integer not greater than n. If V′V is (l,m,n)(l,m,n)-cohesive, then V′V is (l,m′,n′)(l,m ,n )-cohesive. In a limited case, (l,m,n)(l,m,n)-cohesion can be lifted to (l,(m+1),n)(l,(m+1),n)-cohesion or (l,m,(n+1))(l,m,(n+1))-cohesion. Proposition 7 (Lifting) Let V′V be a subset of V, let l be a positive integer and let n be a non-negative integer. If V′V is (l,0,n)(l,0,n)-cohesive and l-eligible, then V′V is (l,1,n)(l,1,n)-cohesive. 4 Justified Representation 4.1 Justified representation axioms We now introduce justified representation axioms for M A. The main difficulty is as follows. On the one hand, for a multi-winner voting profile (V,C,A,k)(V,C,A,k), AV′∀=⋂v∈V′Av∀A^∀_V = _v∈ V A^∀_\v\, so any candidate approved by a set of voters is also approved individually; on the other hand, for an argumentative voting profile (V,C,B,k)(V,C,B,k), it can be that BV′∀≠⋂v∈V′Bv∀B^∀_V = _v∈ V B^∀_\v\. Example 1 is a concrete such case. Some candidate approved by a set of voters may only be approved by the particular set and not by its strict super-/sub-sets. Recall JR, PJR and EJR from Section 2, even though they are meant to satisfy the demands of sets of voters, any winner set W providing // JR/ PJR/ EJR is necessarily a subset of ⋃v∈VAv _v∈ VA_v; hence W is identifiable by comparing it against individuals’ approvals alone. The above-described difference suggests that, with an argumentative voting profile, we may genuinely have to select winners from among collectively approved candidates. To account for this distinction, we anchor W’s provision to approvals of eligible sets, which gives us: Definition 6 (Justified representation axioms) Let W be a size-k subset of C. Let h:ℕ→ℕ×ℕh:N ×N be such that: h(l)=(h1(l),h2(l))h(l)=(h_1(l),h_2(l)); 0<l0<l; 0≤h1(l)≤l0≤ h_1(l)≤ l; and 0≤h2(l)≤l0≤ h_2(l)≤ l. With respect to h, W provides • ArgJR iff, for any (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive subset V′V of V, there is some V′∈(1,V′)V ∈ eligible(1,V ) such that |W∩BV′∀|≥1|W∩ B^∀_V |≥ 1. • ArgPJR iff, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, it holds that |W∩(⋃V′∈(l,V′)BV′∀)|≥l|W∩( _V ∈ eligible(l,V )B_V ^∀)|≥ l. • ArgEJR iff, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, there is some v∈V′v∈ V such that |W∩(⋃V′∈(l,V′),v∈V′BV′∀)|≥l|W∩( _V ∈ eligible(l,V ),v∈ V B_V ^∀)|≥ l. • - ArgEJR- Spot iff, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, there is some V′∈(l,V′)V ∈ eligible(l,V ) such that |W∩BV′∀|≥l|W∩ B_V ^∀|≥ l. ♣ If V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive, • For ArgPJR: for each of l winners c1,…,cl∈Wc_1,…,c_l∈ W, it has to be approved by some l-eligible subset of V′V . • For ArgEJR: there has to be some individual v∈V′v∈ V such that, for each of l winners c1,…,cl∈Wc_1,…,c_l∈ W, it is approved by some l-eligible subset of V′V that contains v. Clearly, they do not just compare W against approvals at individual level. It is, however, possible to require that W be compared against a single eligible set. Hence, we have a stronger axiom - ArgEJR- Spot of ArgEJR. ArgJR and ArgPJR can be equally strengthened into - ArgJR- Spot and - ArgPJR- Spot, but - ArgJR- Spot is ArgJR itself, and - ArgPJR- Spot collapses onto - ArgEJR- Spot. In Example 1, k=3k=3, so there are twenty possibilities for W. With respect to h where each of h(1)h(1) and h(2)h(2) is either (0,0)(0,0) or (1,1)(1,1), • Ten of them provide - ArgEJR- Spot. – Any W with c1∈Wc_1∈ W and W≠c1,c3,c6W =\c_1,c_3,c_6\, plus c2,c4,c5\c_2,c_4,c_5\ provide it. • Eleven of them provide ArgEJR. – c4,c5,c6\c_4,c_5,c_6\ provides ArgEJR but not - ArgEJR- Spot. • Fourteen of them provide ArgPJR. – c2,c3,c5\c_2,c_3,c_5\, c2,c5,c6\c_2,c_5,c_6\ and c3,c4,c5\c_3,c_4,c_5\ provide ArgPJR but not ArgEJR. • Fifteen of them provide ArgJR. – c1,c3,c6\c_1,c_3,c_6\ provides ArgJR but not ArgPJR. With respect to h where h(l)=(l,l)h(l)=(l,l) (l∈1,2l∈\1,2\), v1,v2\v_1,v_2\ ceases to be (2,h1(2),h2(2))(2,h_1(2),h_2(2))-cohesive. Provision of ArgPJR and ArgJR remains unchanged. For the others: • Twelve of them provide - ArgEJR- Spot. – c2,c3,c5\c_2,c_3,c_5\ and c2,c5,c6\c_2,c_5,c_6\ additionally provide - ArgEJR- Spot. • Fourteen of them provide ArgEJR. – c3,c4,c5\c_3,c_4,c_5\ and c4,c5,c6\c_4,c_5,c_6\ provide ArgEJR but not - ArgEJR- Spot. As this illustration shows, greater values for h1(l)h_1(l) and h2(l)h_2(l) lead to fewer, or at best the same number of, requirements for a size-k subset of C to satisfy in order to provide the axioms. As such, two particular h make canonical cases: the permissive h is such that h(l)=(0,0)h(l)=(0,0) for all l; and the robust h is such that h(l)=(l,l)h(l)=(l,l) for all l. In the remainder, we establish: correspondence with JR, PJR and EJR (Section 4.2); unconditional provision of ArgJR and provision under robust h for the stronger axioms (Section 4.3); and polynomial-time construction but coNP-hard verification for ArgJR (Section 4.4). 4.2 Representation correspondence results Proposition 1 gave an approval-preserving embedding of multi-winner voting profiles into argumentative ones. Let ν be a member of ArgJRh,ArgPJRh,ArgEJRh,ArgEJRSh\ArgJR^h,ArgPJR^h,ArgEJR^h, ArgEJRS^h\, and let ν(V,C,B,k)ν(V,C,B,k) be the set of all size-k subsets W of C such that W provides: ArgJR with respect to h if ν is ArgJRhArgJR^h; ArgPJR with respect to h if ν is ArgPJRhArgPJR^h; ArgEJR with respect to h if ν is ArgEJRhArgEJR^h; and - ArgEJR- Spot with respect to h if ν is ArgEJRShArgEJRS^h. Then, the following correspondence results hold. Theorem 1 (Preservation of M M representations) Let x≡(V,C,A,k)x≡(V,C,A,k) be a member of M M. For any size-k subset W of C and any h, • W∈JR(x)W∈ JR(x) iff W∈ArgJRh(τ(x))W∈ ArgJR^h(τ(x)). • W∈PJR(x)W∈ PJR(x) iff W∈ArgPJRh(τ(x))W∈ ArgPJR^h(τ(x)). • W∈EJR(x)W∈ EJR(x) iff W∈ArgEJRh(τ(x))W∈ ArgEJR^h(τ(x)) iff W∈ArgEJRSh(τ(x))W∈ ArgEJRS^h(τ(x)). The set inclusions among justified representation axioms in M A are as expected. Theorem 2 (Inclusion hierarchy) Let x≡(V,C,B,k)x≡(V,C,B,k) be a member of M A, then, with respect to every h, ArgEJRSh(x)⊆ArgEJRh(x)⊆ArgPJRh(x)⊆ArgJRh(x)ArgEJRS^h(x) ArgEJR^h(x) ArgPJR^h(x) ArgJR^h(x). Also, they are separable. Theorem 3 (Separations) For each of the following statements, there exist an argumentative voting profile x≡(V,C,B,k)x≡(V,C,B,k), a size-k subset W of C and an h for which the statement holds. • W∈ArgEJRh(x)W∈ ArgEJR^h(x) and W∉ArgEJRSh(x)W ∈ ArgEJRS^h(x). • W∈ArgPJRh(x)W∈ ArgPJR^h(x) and W∉ArgEJRh(x)W ∈ ArgEJR^h(x). • W∈ArgJRh(x)W∈ ArgJR^h(x) and W∉ArgPJRh(x)W ∈ ArgPJR^h(x). 4.3 Existence results Provision of only ArgJR is unconditionally guaranteed. Theorem 4 (Existence for ArgJR) For any (V,C,B,k)∈(V,C,B,k)∈ M A, with respect to any h, there is some size-k subset W of C such that W provides ArgJR. Theorem 5 (Impossibility for //- ArgPJR/ ArgEJR/ ArgEJR- Spot) For any ρ∈,,-ρ∈\ ArgPJR, ArgEJR, ArgEJR- Spot\, there is some (V,C,B,k)∈(V,C,B,k)∈ M A and some h such that, with respect to h, no size-k subset W of C provides ρ. Nonetheless, the robust h gives us the following result. Theorem 6 (Existence for all) For any ρ∈,,-ρ∈\ ArgPJR,\\ ArgEJR, ArgEJR- Spot\ and for any argumentative voting profile (V,C,B,k)∈(V,C,B,k)∈ M A there is some size-k subset W of C such that W provides ρ with respect to the robust h. 4.4 Computational complexity results Verification is coNP-hard for ArgJR and thus for all axioms. Theorem 7 (Verification hardness) With respect to any h, determining if a given size-k subset W of C provides ArgJR, ArgPJR, ArgEJR or ArgEJR- Spot is coNP-hard. Algorithm 1 GreedyGrounded algorithm Input: An argumentative voting profile (V,C,B,k)(V,C,B,k) Output: A size-k subset of C. 1: out←∅out← . Alloc←(v,0)∣v∈VAlloc←\(v,0) v∈ V\. D←∅D← . waiting←(C,V′⊆V∣for some c∈C,V′=(V\v∈V∣∃c′.(c′,c)∈Rv)V′ is a maximal set satisfying: ∀c′∈C.(c′,c)∉⋃v∈V′Rv and |V′|≥|V|/k)waiting← notAttkd(C,\V V some c∈ C,V =(V \v∈ V ∃ c .(c ,c)∈ R_v\)V is a maximal set satisfying: ∀ c ∈ C.(c ,c) ∈ _v∈ V R_v and |V |≥|V|/k\). // initialise. 2: while true do 3: while waiting≠∅waiting = do 4: (c,V′)←(c,V )← a greatest member of waitingwaiting. waiting←waiting\(c,V′)waiting← waiting \(c,V )\. out←out∪cout← out∪\c\. for each v∈V′v∈ V , Alloc[v]←Alloc[v]+1Alloc[v]← Alloc[v]+1. 5: if |out|=k|out|=k then 6: return outout. 7: end if 8: if V′V is not a key in D then 9: D←D∪(V′,c)D← D∪\(V ,\c\)\. 10: else 11: D[V′]←D[V′]∪cD[V ]← D[V ]∪\c\. 12: end if 13: end while 14: waiting←⋃V′∈keys(D)(C\(D[V′]∪c∈C∣∃c′∈D[V′].(c′,c)∈⋃v∈V′Rv),V′)waiting← _V ∈ keys(D) notAttkd(C (D[V ]∪\c∈ C ∃ c ∈ D[V ].(c ,c)∈ _v∈ V R_v\),\V \). 15: if waiting=∅waiting= then 16: return a size-k subset of C that contains outout. 17: end if 18: end while Nevertheless, a size-k winner set providing ArgJR with respect to any h can be constructed in polynomial time. GreedyGrounded in Algorithm 1 takes (V,C,B,k)(V,C,B,k) as the input and outputs a size-k subset of C. There are three auxiliary data structures. 1. Alloc:V→ℕAlloc:V records an allocation score of each voter. For v∈Vv∈ V, the greater its value Alloc[v]Alloc[v] is, the more allocated v is considered to be. 2. D is a partial map from voter subsets (⊆(V) (V)) to candidate subsets (⊆(C) (C)). It records the candidates selected on behalf of each stored subset of voters. keys(D)keys(D) denotes the set of keys in D, and D[V′]D[V ] denotes the value of V′∈keys(D)V ∈ keys(D). 3. The priority set waitingwaiting contains pairs of C×(V)C×P(V) ranked in the following order: (c1,V1′)≥(c2,V2′)(c_1,V _1)≥(c_2,V _2) (with non-empty V1′V _1 and V2′V _2) iff there is some integer 0≤x0≤ x such that, for every integer 0≤y<x0≤ y<x, the same number of y occurs in the multisets ⊎v∈V1′Alloc[v] _v∈ V _1\Alloc[v]\ and ⊎v∈V2′Alloc[v] _v∈ V _2\Alloc[v]\, and the multiplicity of x is greater in ⊎v∈V1′Alloc[v] _v∈ V _1\Alloc[v]\. Thus, pairs representing more voters with low allocation scores receive higher priority. The waitingwaiting set is generated by a function :(C)×((V))→(C×(V)) notAttkd:P(C)×P(P(V)) (C×P(V)), which is such that (C′,V1′,…,Vj′)=(c,V′)∣c∈C′ and ∃1≤i≤j.(V′=Vi′ and ∀c′∈C′.(c′,c)∉((C′×C′)∩(⋃v∈Vi′Rv))) notAttkd(C ,\V _1,…,V _j\)=\(c,V ) c∈ C and ∃ 1≤ i≤ j.(V =V _i and ∀ c ∈ C .(c ,c) ∈((C × C )∩( _v∈ V _iR_v)))\. For example, (C′,V1′,V2′) notAttkd(C ,\V _1,V _2\) contains every pair (ci,Vi′)(c_i,V_i ) (i∈1,2i∈\1,2\) such that ci∈C′c_i∈ C and Vi′V _i does not attack cic_i in the graph (C′,(C′×C′)∩⋃v∈Vi′Rv)(C ,(C × C )∩ _v∈ V _iR_v). With these, GreedyGrounded constructs its output. For each c∈Cc∈ C, if V′⊆V V does not attack c in (C,⋃v∈V′Rv)(C, _v∈ V R_v), |V′|≥|V|/k|V |≥|V|/k, and is a maximal such set, then (c,V′)(c,V ) is added into waitingwaiting (line 1). The algorithm repeatedly removes a highest-priority pair (cx,Vx′)(c_x,V _x) from waitingwaiting, cxc_x is added to outout, and AllocAlloc is updated for members of V′V (line 4). D is also updated (lines 8∼ 12). If the initial waitingwaiting set yields fewer than k winners, the algorithm tries to favour members of keys(D)keys(D) with more winners. So, it generates a new waitingwaiting set comprising all (cx,Vx′)(c_x,V _x) where cx∈(C [Vx′])c_x∈(C D[V_x ]), Vx′∈keys(D)V _x∈ keys(D) and D[Vx′]D[V _x] defends cxc_x in (C,⋃v∈Vx′Rv)(C, _v∈ V _xR_v) (line 14).22 2 Algorithm 1 achieves this with notAttkd. Selection continues (line 4) until k distinct winners are selected (lines 5∼ 7) or a new waitingwaiting set is empty (line 15) in which case the remaining winners are arbitrary (line 16). The invariants that D[V′]⊆BV′∀D[V ] B^∀_V for every V′∈keys(D)V ∈ keys(D) and that keys(D)<kkeys(D)<k hold at every execution of line 3. Theorem 8 (Polynomial-time construction) For any (V,C,B,k)∈(V,C,B,k)∈ M A and any h, GreedyGrounded computes in polynomial time a size-k subset W of C providing ArgJR with respect to h. With adjacency-matrix representations, its running time is O(k2⋅|V|⋅|C|2)O(k^2·|V|·|C|^2). The running time with an incremental implementation of: the union graphs; grounded-extension computations for each fixed V′∈keys(D)V ∈ keys(D); and priority updates, is O(k⋅|V|⋅|C|2)O(k·|V|·|C|^2). 5 Conclusions We introduced multi-winner voting with argumentative ballots, where approvals are induced by grounded acceptance. The framework conservatively generalises approval voting while retaining relational information that ordinary approval ballots do not capture. Individual approvals may be fixed, but combining ballots can lead to different collective approvals through attack and defence. This non-monotonicity demands that justified representation be reformulated. Our argumentative cohesion notions and justified representation axioms ArgJR, ArgPJR, ArgEJR and ArgEJR- Spot conservatively generalise JR, PJR and EJR, and preserve their inclusion hierarchy. We showed that a winner set providing ArgJR always exists, whereas winner sets providing the stronger axioms need not exist. The robust h restores existence for all of them. Identifying a more precise boundary remains open. Computationally, a winner set satisfying ArgJR is polynomial-time constructible, even though verifying whether a given winner set provides it is coNP-hard. Future work includes adapting further representation axioms (Kalayci, Jiu, and Kempe 2025; Brill et al. 2023), incorporating candidate costs (Peters, Pierczyński, and Skowron 2021), understanding strategic behaviour, and developing practical methods for eliciting argumentative ballots. Author Contributions R.A.: Conceptualisation, methodology, formal analysis, investigation, software, validation and writing - original draft. H.O.: Formal analysis of the proof of Theorem 7. Acknowledgements This work was supported in part by JSPS KAKENHI Grant Number 25K15245. References Awad et al. (2017) Awad, E.; Booth, R.; Tohmé, F.; and Rahwan, I. 2017. Judgement Aggregation in Multi-Agent Argumentation. Journal of Logic and Computation, 27(1): 227–259. Aziz et al. (2017) Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified representation in approval-based committee voting. Social Choice and Welfare, 48: 461–485. Baroni and Giacomin (2007) Baroni, P.; and Giacomin, M. 2007. On principle-based evaluation of extension-based argumentation semantics. Artificial Intelligence, 171(10-15): 675–700. Bernreiter et al. (2024) Bernreiter, M.; Maly, J.; Nardi, O.; and Woltran, S. 2024. Combining Voting and Abstract Argumentation to Understand Online Discussions. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS’24), 170–179. Boutilier et al. (2004) Boutilier, C.; Brafman, R. I.; Domshlak, C.; Hoos, H. H.; and Poole, D. 2004. CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements. Journal of Artificial Intelligence Research, 21: 135–191. Brill et al. (2023) Brill, M.; Forster, S.; Lackner, M.; Maly, J.; and Peters, J. 2023. Proportionality in approval-based participatory budgeting. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence (AAAI’23/IAAI’23/EAAI’23), 5524–5531. Dung (1995) Dung, P. M. 1995. On the Acceptability of Arguments and Its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games. Artificial Intelligence, 77(2): 321–357. Jain, Sornat, and Talmon (2020) Jain, P.; Sornat, K.; and Talmon, N. 2020. Participatory Budgeting with Project Interactions. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (IJCAI’20), 386–392. Kalayci, Jiu, and Kempe (2025) Kalayci, Y. H.; Jiu, J.; and Kempe, D. 2025. Full Proportional Justified Representation. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’25), 1070–1078. Lackner and Skowron (2023) Lackner, M.; and Skowron, P. 2023. Multi-Winner Voting with Approval Preferences. Springer Cham. Lang and Xia (2016) Lang, J.; and Xia, L. 2016. Voting in Combinatorial Domains. In Handbook of Computational Social Choice, 197–222. Cambridge University Press. Leite and Martins (2011) Leite, J.; and Martins, J. 2011. Social Abstract Argumentation. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI’11), 2287–2292. Naoki Susami and Ryuta Arisaka (2026) Naoki Susami and Ryuta Arisaka. 2026. Representation Guarantees for Multi-Agent Knowledge Integration via Abstract Argumentation and Their Computational Complexity. In Proceedings of the Eleventh International Conference on Computational Models of Argument (COMMA’26) (to appear). Peters, Pierczyński, and Skowron (2021) Peters, D.; Pierczyński, G.; and Skowron, P. 2021. Proportional Participatory Budgeting with Additive Utilities. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS’21), 12726–12737. Peters and Skowron (2020) Peters, D.; and Skowron, P. 2020. Proportionality and the Limits of Welfarism. In Proceedings of the Twenty First ACM Conference on Economics and Computation (EC’20), 793–794. Sánchez-Fernández et al. (2026) Sánchez-Fernández, L.; Elkind, E.; Lackner, M.; García, N. F.; Festeus, J. A.; Val, P. B.; and Skowron, P. 2026. Proportional Justified Representation. Artificial Intelligence, 353: 104503. Yang et al. (2024) Yang, J. C.; Hausladen, C. I.; Peters, D.; Pournaras, E.; Hnggli Fricker, R.; and Helbing, D. 2024. Designing Digital Voting Systems for Citizens: Achieving Fairness and Legitimacy in Participatory Budgeting. Digital Government: Research and Practice. Appendix: Proofs This appendix contains all proofs of the claims in the main text. To prove Proposition 2, we use Lemma 1. To prove Theorem 1, we use Lemma 3. To prove Theorem 5, we use Lemmas 1 and 2. These lemmas appear in the final section. The existence proofs for Theorem 4 and in particular Theorem 6, use a direct inductive covering argument, rather than optimisation of a specific voting rule. To the best of our knowledge, this proof strategy is novel in the study of justified representation. All proofs are certified in Lean 4. A1 Proofs of Propositions Proof of Proposition 1. Let κ:→κ: M M→ M A be a function with the same domain and co-domain as τ. If κ satisfies the following condition, κ is an instantiation of τ: for any (V,C,A,k)∈(V,C,A,k)∈ M M, let (V,C,B,k)(V,C,B,k) denote κ(V,C,A,k)κ(V,C,A,k), for any v∈Vv∈ V and any c∈Cc∈ C, • if c∈Avc∈ A_v, then there is no c′∈Cc ∈ C such that (c′,c)(c ,c) is an edge in BvB_\v\. • for any (C,Rv′)(C,R_v ) where Rv′R_v includes all edges in BvB_\v\, if c∉Avc ∈ A_v, then c is not in the grounded extension of (C,Rv′)(C,R_v ). One such κ is: for any x∈x∈ M M, κ(x)≡(V,C,B,k)κ(x)≡(V,C,B,k) comes with B=(Bv1,…,Bv|V|)B=(B_\v_1\,…,B_\v_|V|\) where BviB_\v_i\ is (C,(c,c)∣c∉Avi)(C,\(c,c) c ∈ A_v_i\). □ Proof of Proposition 2. Use collective approval gadgets; Lemma 1. Obvious, since Fact 1 holds for τ′(V,C,B,k)τ (V,C,B,k) but does not need hold for (V,C,B,k)(V,C,B,k). □ Proof of Proposition 3. If |V′|<l⋅|V|/k|V |<l·|V|/k, the number of subsets of V′V is strictly smaller than 2l⋅|V|/k2^l·|V|/k. Even if every non-empty subset is l-eligible, |(l,V′)|| eligible(l,V )| is strictly smaller than 2l⋅|V|/k−12^l·|V|/k-1. □ Proof of Proposition 4. VsuperV_super contains all l-eligible subsets of V′V . □ Proof of Proposition 5. If: Vacuous. Only if: The first condition holds by assumption. The second condition holds because |⋂V′∈(l,V′)BV′∀|| _V ∈ eligible(l,V )B^∀_V | is at least 0. The third condition holds because minV′⊆V′|BV′∀|min_V V |B^∀_V | is at least 0. □ Proof of Proposition 6. If V′V is (l,m,n)(l,m,n)-cohesive, then: • Every member of (l,V′) eligible(l,V ) approves at least m same candidates, which means at least m′m same candidates are approved. • Every non-empty subset of V′V approves at least n candidates, which means at least n′n candidates are approved. □ Proof of Proposition 7. By assumption, V′V is l-eligible. So, BV′∀≠∅B^∀_V = . Thus, there must exist a candidate c in ⋂v∈V′Bv∀ _v∈ V B^∀_\v\ which is not attacked in BV′B_V . For, otherwise, BV′B_V would contain no unattacked candidate and BV′∀B^∀_V would be an empty set. Hence, for any subset V′V of V′V , c∈BV′∀c∈ B^∀_V . □ A2 Proofs of Theorems Proof of Theorem 1. Let (V,C,B,k)(V,C,B,k) denote τ(x)τ(x). By Proposition 1, for any non-empty subset V′V of V, (⋂v∈V′Av)=AV′∀=BV′∀( _v∈ V A_v)=A^∀_V =B^∀_V . For the first obligation, Only if: Let Γ(1) (1) denote the set of all non-empty subsets V′V of V such that V′V is 11-cohesive in x and that there is no strict non-empty subset V′V of V′V such that V′V is 11-cohesive in x. Since W provides JR, for each V′∈Γ(1)V ∈ (1), there is some v∈V′v∈ V such that |W∩Av∀|≥1|W∩ A^∀_\v\|≥ 1. For any 11-cohesive subset Vo′V _o in x not in Γ(1) (1), there is some V′∈Γ(1)V ∈ (1) such that V′⊂Vo′V ⊂ V _o. By Lemma 3, V′V is (1,1,1)(1,1,1)-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is argumentative 11-cohesive in τ(x)τ(x). Since v∈(l,V′)\v\∈ eligible(l,V ), |W∩Bv∀|≥1|W∩ B^∀_\v\|≥ 1. By Proposition 6, V′V is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive in τ(x)τ(x). By Proposition 4, for any superset VsuperV_super of V′V , VsuperV_super is argumentative 11-cohesive. If VsuperV_super is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive, v∈(1,Vsuper)\v\∈ eligible(1,V_super); otherwise, there is nothing to show. If: Let Δ(h,1) (h,1) denote the set of all non-empty subsets V′V of V such that V′V is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive in τ(x)τ(x). Since W provides ArgJR with respect to h, for each V′∈Δ(h,1)V ∈ (h,1), there is some V′∈(1,V′)V ∈ eligible(1,V ) such that |W∩BV′∀|≥1|W∩ B^∀_V |≥ 1. Since, by Fact 1 and Proposition 1, V′V is (1,1,1)(1,1,1)-cohesive in τ(x)τ(x), there is in particular some v∈V′v∈ V such that |W∩Bv∀|≥1|W∩ B^∀_\v\|≥ 1. For any (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive subset Vo′V _o in τ(x)τ(x) not in Δ(h,1) (h,1), there is some V′∈Δ(h,1)V ∈ (h,1) such that V′⊂Vo′V ⊂ V _o and that v∈(1,Vo′)v∈ eligible(1,V _o) for each v∈V′v∈ V . By Lemma 3, V′V is 11-cohesive in x and that there is no strict non-empty subset V′V of V′V such that V′V is 11-cohesive in x. Trivially, |W∩Av∀|≥1|W∩ A^∀_\v\|≥ 1. For any superset VsuperV_super of V′V , v∈Vsuperv∈ V_super. For the second obligation, Only if: For each 1≤l≤k1≤ l≤ k, let Γ(l) (l) denote the set of all non-empty subsets V′V of V such that V′V is l-cohesive in x and that there is no strict non-empty subset V′V of V′V such that V′V is l-cohesive in x. Since W provides PJR, for each 1≤l≤k1≤ l≤ k and each V′∈Γ(l)V ∈ (l), |W∩⋃v∈V′Av∀|≥l|W∩ _v∈ V A^∀_\v\|≥ l. For any l-cohesive subset Vo′V _o in x not in Γ(l) (l), there is some V′∈Γ(l)V ∈ (l) such that V′⊂Vo′V ⊂ V _o. By Lemma 3, V′V is (l,l,l)(l,l,l)-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is argumentative l-cohesive in τ(x)τ(x). Since v∈(l,V′)\v\∈ eligible(l,V ) for each v∈V′v∈ V , |W∩⋃v∈V′Bv∀|≥l|W∩ _v∈ V B^∀_\v\|≥ l. Then, clearly, |W∩(⋃V′∈(l,V′)BV′∀)|≥l|W∩( _V ∈ eligible(l,V )B_V ^∀)|≥ l. For any superset VsuperV_super of V′V , if VsuperV_super is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x), then for each v∈V′v∈ V , v∈(l,Vsuper)\v\∈ eligible(l,V_super); otherwise, there is nothing to show. If: For each 1≤l≤k1≤ l≤ k, let Δ(h,l) (h,l) denote the set of all non-empty subsets V′V of V such that V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x). Since W provides ArgPJR with respect to h, for each 1≤l≤k1≤ l≤ k and each V′∈Δ(h,l)V ∈ (h,l), there is some V′∈(l,V′)V ∈ eligible(l,V ) such that |W∩(⋃V′∈(l,V′)BV′∀)|≥l|W∩( _V ∈ eligible(l,V )B^∀_V )|≥ l. Since, by Fact 1 and Proposition 1, V′V is (l,l,l)(l,l,l)-cohesive in τ(x)τ(x), ⋃V′∈(l,V′)BV′∀⊆⋃v∈V′Bv∀ _V ∈ eligible(l,V )B^∀_V _v∈ V B^∀_\v\, so, in particular, we have |W∩(⋃v∈V′Bv∀)|≥l|W∩( _v∈ V B^∀_\v\)|≥ l. Hence, |W∩⋃v∈V′Av∀|≥l|W∩ _v∈ V A^∀_\v\|≥ l. For any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset Vo′V _o in τ(x)τ(x) not in Δ(h,l) (h,l), there is some V′∈Δ(h,l)V ∈ (h,l) such that V′⊂Vo′V ⊂ V _o and that v∈(l,Vo′)v∈ eligible(l,V _o) for each v∈V′v∈ V . For the third obligation, firstly for: W∈ArgEJRh(τ(x))W∈ ArgEJR^h(τ(x)) iff W∈ArgEJRSh(τ(x))W∈ ArgEJRS^h(τ(x)), Only if: Since W provides ArgEJR with respect to h, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, there is some v∈V′v∈ V such that |W∩(⋃V′∈(l,V′),v∈V′BV′∀)|≥l|W∩( _V ∈ eligible(l,V ),v∈ V B^∀_V )|≥ l. Since ⋃V′∈(l,V′),v∈V′BV′∀=Bv∀ _V ∈ eligible(l,V ),v∈ V B^∀_V =B^∀_\v\ by Fact 1 and Proposition 1, it follows that |W∩Bv∀|≥l|W∩ B^∀_\v\|≥ l. If: Since W provides ArgEJR- Spot with respect to h, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, there is some V′∈(l,V′)V ∈ eligible(l,V ) such that |W∩BV′∀|≥l|W∩ B^∀_V |≥ l. By Fact 1 and Proposition 1, it follows that |W∩Bv∀|≥l|W∩ B^∀_\v\|≥ l for any v∈V′v∈ V . So, let v be a member of V′V . By Fact 1 and Proposition 1, it follows that |W∩(⋃Vo′∈(l,V′),v∈Vo′BVo′∀)|≥l|W∩( _V _o∈ eligible(l,V ),v∈ V _oB^∀_V _o)|≥ l. Now for: W∈EJR(x)W∈ EJR(x) iff W∈ArgEJRSh(τ(x))W∈ ArgEJRS^h(τ(x)), Only if: For each 1≤l≤k1≤ l≤ k, let Γ(l) (l) denote the set of all non-empty subsets V′V of V such that V′V is l-cohesive in x and that there is no strict non-empty subset V′V of V′V such that V′V is l-cohesive in x. Since W provides EJR, for each 1≤l≤k1≤ l≤ k and each V′∈Γ(l)V ∈ (l), there is some v∈V′v∈ V such that |W∩Av∀|≥l|W∩ A^∀_\v\|≥ l. For any l-cohesive subset Vo′V _o in x not in Γ(l) (l), there is some V′∈Γ(l)V ∈ (l) such that V′⊂Vo′V ⊂ V _o. By Lemma 3, V′V is (l,l,l)(l,l,l)-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is argumentative l-cohesive in τ(x)τ(x). Since v∈(l,V′)\v\∈ eligible(l,V ), |W∩Bv∀|≥l|W∩ B^∀_\v\|≥ l. By Proposition 6, V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x). By Proposition 4, for any superset VsuperV_super of V′V , VsuperV_super is argumentative l-cohesive. If VsuperV_super is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive, v∈(l,Vsuper)\v\∈ eligible(l,V_super); otherwise, there is nothing to show. If: For each 1≤l≤k1≤ l≤ k, let Δ(h,l) (h,l) denote the set of all non-empty subsets V′V of V such that V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x) and that there is no strict non-empty subset V′V of V′V such that V′V is (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive in τ(x)τ(x). Since W provides ArgEJR- Spot with respect to h, for each 1≤l≤k1≤ l≤ k and each V′∈Δ(h,l)V ∈ (h,l), there is some V′∈(l,V′)V ∈ eligible(l,V ) such that |W∩BV′∀|≥l|W∩ B^∀_V |≥ l. Since, by Fact 1 and Proposition 1, V′V is (l,l,l)(l,l,l)-cohesive in τ(x)τ(x), there is in particular some v∈V′v∈ V such that |W∩Bv∀|≥l|W∩ B^∀_\v\|≥ l. For any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset Vo′V _o in τ(x)τ(x) not in Δ(h,l) (h,l), there is some V′∈Δ(h,l)V ∈ (h,l) such that V′⊂Vo′V ⊂ V _o and that v∈(l,Vo′)v∈ eligible(l,V _o) for each v∈V′v∈ V . By Lemma 3, V′V is l-cohesive in x and that there is no strict non-empty subset V′V of V′V such that V′V is l-cohesive in x. Trivially, |W∩Av∀|≥l|W∩ A^∀_\v\|≥ l. For any superset VsuperV_super of V′V , v∈Vsuperv∈ V_super. □ Proof of Theorem 2. Let W be a member of ArgEJRSh(x)ArgEJRS^h(x). By assumption, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, there is some V′∈(l,V′)V ∈ eligible(l,V ) such that |W∩BV′∀|≥l|W∩ B_V ^∀|≥ l. Implicitly, |(l,V′)|≥1| eligible(l,V )|≥ 1. Let v be a member of V′V . Since BV′∀⊆⋃Vx∈(l,V′),v∈VxBVx∀B_V ^∀ _V_x∈ eligible(l,V ),v∈ V_xB_V_x^∀, it holds that W∈ArgEJRh(x)W∈ ArgEJR^h(x), as required. Next, let W be a member of ArgEJRh(x)ArgEJR^h(x). It is straightforward to see that W∈ArgPJRh(x)W∈ ArgPJR^h(x). Next, let W be a member of ArgPJRh(x)ArgPJR^h(x). It is straightforward to see that W∈ArgJRh(x)W∈ ArgJR^h(x). □ Proof of Theorem 3. As we saw in section 4.1, Example 1 is the witness. But also, in general, the second and the third are immediate from Theorem 1 and the known results that JR, PJR and EJR do not coincide. This leaves the first obligation still to verify. Let x be (v1,v2,c1,…,c8,B,3)(\v_1,v_2\,\c_1,…,c_8\,B,3) where Bv1B_\v_1\ and Bv2B_\v_2\ are as shown below. c1 @inpgf@ignorespaces c_1c8 @inpgf@ignorespaces c_8c2 @inpgf@ignorespaces c_2c3 @inpgf@ignorespaces c_3c4 @inpgf@ignorespaces c_4c5 @inpgf@ignorespaces c_5c6 @inpgf@ignorespaces c_6c7 @inpgf@ignorespaces c_7 B_\v_1\c1 @inpgf@ignorespaces c_1c8 @inpgf@ignorespaces c_8c2 @inpgf@ignorespaces c_2c3 @inpgf@ignorespaces c_3c4 @inpgf@ignorespaces c_4c5 @inpgf@ignorespaces c_5c6 @inpgf@ignorespaces c_6c7 @inpgf@ignorespaces c_7 B_\v_2\ We have: Bv1∀=c1,c3,c8B_\v_1\^∀=\c_1,c_3,c_8\, Bv2∀=c1,c5,c8B_\v_2\^∀=\c_1,c_5,c_8\, Bv1,v2∀=c1,c7,c8B_\v_1,v_2\^∀=\c_1,c_7,c_8\. So, v1,v2\v_1\,\v_2\ and v1,v2\v_1,v_2\ are 1-eligible, 2-eligible and 3-eligible. Hare Quota is |v1,v2|/3|\v_1,v_2\|/3, so v1\v_1\ and v2\v_2\ are argumentative 1-cohesive, and v1,v2\v_1,v_2\ is argumentative 1-, 2- and 3-cohesive. Let h be the permissive h, i.e. h(l)=(0,0)h(l)=(0,0) for every positive integer l. Then, v1\v_1\ and v2\v_2\ are (1,0,0)(1,0,0)-cohesive, and v1,v2\v_1,v_2\ is (1,0,0)(1,0,0)-, (2,0,0)(2,0,0)- and (3,0,0)(3,0,0)-cohesive. Let W be c1,c3,c7\c_1,c_3,c_7\. Then, • |Bv1,v2∀∩W|=2|B^∀_\v_1,v_2\∩ W|=2. • |Bv1∀∩W|=2|B^∀_\v_1\∩ W|=2. • |Bv2∀∩W|=1|B^∀_\v_2\∩ W|=1. So, for each subset V′V of v1,v2\v_1,v_2\, 3>|BV′∀∩W|3>|B^∀_V ∩ W| and W∉ArgEJRSh(x)W ∈ ArgEJRS^h(x). On the other hand, • |(⋃V′∈(3,v1,v2),v1∈V′BV′∀)∩W|=3≥3|( _V ∈ eligible(3,\v_1,v_2\),v_1∈ V B^∀_V )∩ W|=3≥ 3. • |(⋃V′∈(2,v1,v2),v1∈V′BV′∀)∩W|=3≥2|( _V ∈ eligible(2,\v_1,v_2\),v_1∈ V B^∀_V )∩ W|=3≥ 2. |(⋃V′∈(1,v1,v2),v1∈V′BV′∀)∩W|=3≥1|( _V ∈ eligible(1,\v_1,v_2\),v_1∈ V B^∀_V )∩ W|=3≥ 1. • |(⋃V′∈(1,v1),v1∈V′BV′∀)∩W|=2≥1|( _V ∈ eligible(1,\v_1\),v_1∈ V B^∀_V )∩ W|=2≥ 1. • |(⋃V′∈(1,v2),v2∈V′BV′∀)∩W|=1≥1|( _V ∈ eligible(1,\v_2\),v_2∈ V B^∀_V )∩ W|=1≥ 1. So, W∈ArgEJRh(x)W∈ ArgEJR^h(x). □ Proof of Theorem 4. Proof strategy. We establish existence directly through an inductive covering argument, rather than by identifying a size-k winner set that optimises a preselected scoring objective. The induction maintains a residual-capacity invariant relating the remaining seats (≤k(≤ k) to the voters whose cohesive demands are not yet covered. The same proof strategy is used in Theorem 6. We say that a subset C′C of C covers a subset Vx′V _x of V iff, for any (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive subset V′V of V, if V′∩Vx′≠∅V ∩ V _x = , then there is some V′∈(1,V′)V ∈ eligible(1,V ) such that V′∩Vx′≠∅V ∩ V _x = and that 1≤|BV′∀∩C′|1≤|B^∀_V ∩ C |. By (C′) cover(C ) (C′⊆C C), we denote the largest subset V′V of V covered by C′C . For any subset C′C of C, let cohesion rank of C′C be: • 1 if some subset of (V\(C′))(V cover(C )) is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive; • 0 if there is no such subset, and let residual of C′C be |V\(C′)||V cover(C )|. For any subset C′C of C, we prove by induction on cohesion rank of C′C and subinduction on residual of C′C that, if (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ), then the claim holds. Base case: Cohesion rank of C′C is 0. Then, necessarily, residual of C′C is 0. W is any size-k subset of C such that C′⊆WC W. Inductive case: Assume that the claim holds for any subset C′C of C with (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ) for cohesion rank of 00. We prove it for any subset C′C of C with (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ) and cohesion rank of 11. By the definition of residual, necessarily (C′)≥1⋅(|V|/k) residual(C )≥ 1·(|V|/k). Then, necessarily (k−|C′|)⋅(|V|/k)≥1⋅(|V|/k)(k-|C |)·(|V|/k)≥ 1·(|V|/k), so necessarily k≥|C′|+1k≥|C |+1. Let V′V be an (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive subset of (V\(C′))(V cover(C )). By the definition of argumentative 11-cohesion, there exists a subset V′V of V′V such that V′V is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive and 11-eligible. By Proposition 7, there exists some v∈V′v∈ V such that |Bv∀∩BV′∀|≥1|B_\v\^∀∩ B^∀_V |≥ 1. Let c be a member of Bv∀∩BV′∀B^∀_\v\∩ B^∀_V and let C′C be C′∪cC ∪\c\. Then, |(C′)|≥|(C′)|+1⋅(|V|/k)| cover(C )|≥| cover(C )|+1·(|V|/k). It holds that (C′)≤(C′)−1⋅(|V|/k) residual(C )≤ residual(C )-1·(|V|/k). In the meantime, (k−|C′|)≥(k−|C′|)−1(k-|C |)≥(k-|C |)-1. So, (k−|C′|)⋅(|V|/k)≥(C′)−1⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C )-1·(|V|/k)≥ residual(C ). If cohesion rank of C′C is 0, we apply induction hypothesis of main induction. If cohesion rank of C′C is 11, we apply induction hypothesis of subinduction. □ Proof of Theorem 5. Suppose an argumentative voting profile (v1,…,v12,C,B,12)(\v_1,…,v_12\,C,B,12) where B is such that it satisfies all the following conditions. • for any 1≤i≤121≤ i≤ 12, Bvi∀=c0B_\v_i\^∀=\c_0\. • for any 1≤i1<i2≤121≤ i_1<i_2≤ 12, Bvi1,vi2∀=c0,ci1i21B_\v_i_1,v_i_2\^∀=\c_0,c^1_i_1i_2\. • for any 1≤i1<i2<i3≤121≤ i_1<i_2<i_3≤ 12, Bvi1,…,vi3∀=c0,ci1i2i31B_\v_i_1,…,v_i_3\^∀=\c_0,c^1_i_1i_2i_3\. • for any 1≤i1<i2<i3<i4≤121≤ i_1<i_2<i_3<i_4≤ 12, Bvi1,…,vi4∀=c0,ci1…i41,ci1…i42B_\v_i_1,…,v_i_4\^∀=\c_0,c^1_i_1… i_4,c^2_i_1… i_4\. • for any 1≤i1<i2<i3<i4<i5≤121≤ i_1<i_2<i_3<i_4<i_5≤ 12, Bvi1,…,vi5∀=c0,ci1…i51,ci1…i52B_\v_i_1,…,v_i_5\^∀=\c_0,c^1_i_1… i_5,c^2_i_1… i_5\. • for any 1≤i1<⋯<i6≤121≤ i_1<·s<i_6≤ 12, Bvi1,…,vi6∀=c0,ci1…i61,ci1…i62B_\v_i_1,…,v_i_6\^∀=\c_0,c^1_i_1… i_6,c^2_i_1… i_6\. • for any 1≤i1<⋯<i7≤121≤ i_1<·s<i_7≤ 12, Bvi1,…,vi7∀=c0,ci1…i71,ci1…i72,ci1…i73B_\v_i_1,…,v_i_7\^∀=\c_0,c^1_i_1… i_7,c^2_i_1… i_7,c^3_i_1… i_7\. • for any 1≤i1<⋯<i8≤121≤ i_1<·s<i_8≤ 12, Bvi1,…,vi8∀=c0,ci1…i81,ci1…i82,ci1…i83B_\v_i_1,…,v_i_8\^∀=\c_0,c^1_i_1… i_8,c^2_i_1… i_8,c^3_i_1… i_8\. • for any 1≤i1<⋯<i9≤121≤ i_1<·s<i_9≤ 12, Bvi1,…,vi9∀=c0,ci1…i91,ci1…i92,ci1…i93B_\v_i_1,…,v_i_9\^∀=\c_0,c^1_i_1… i_9,c^2_i_1… i_9,c^3_i_1… i_9\. • for any 1≤i1<⋯<i10≤121≤ i_1<·s<i_10≤ 12, Bvi1,…,vi10∀=c0,ci1…i101,ci1…i102,ci1…i103,ci1…i104B_\v_i_1,…,v_i_10\^∀=\c_0,c^1_i_1… i_10,c^2_i_1… i_10,c^3_i_1… i_10,c^4_i_1… i_10\. • for any 1≤i1<⋯<i11≤121≤ i_1<·s<i_11≤ 12, Bvi1,…,vi11∀=c0,ci1…i111,ci1…i112,ci1…i113,ci1…i114B_\v_i_1,…,v_i_11\^∀=\c_0,c^1_i_1… i_11,c^2_i_1… i_11,c^3_i_1… i_11,c^4_i_1… i_11\. • Bvi1,…,vi12∀=c0,ci1…i121,ci1…i122,ci1…i123,ci1…i124B_\v_i_1,…,v_i_12\^∀=\c_0,c^1_i_1… i_12,c^2_i_1… i_12,c^3_i_1… i_12,c^4_i_1… i_12\. By Lemmas 1 and 2, this B is constructible. C contains all that appear above, and all that are needed to construct B with collective approval gadgets and non-approval gadgets. Let h be the permissive h, i.e. h1(l)=0h_1(l)=0 and h2(l)=0h_2(l)=0. Hare Quota is |v1,…,v12|/12=1|\v_1,…,v_12\|/12=1, so, if a subset W of C is to provide ArgPJR, then: 1. |W∩Bv1∀||W∩ B^∀_\v_1\| must be at least 1. So W must contain c0c_0. 2. |W∩(⋃V′∈(2,v1,v2,v3)BV′∀)||W∩( _V ∈ eligible(2,\v_1,v_2,v_3\)B^∀_V )|, |W∩(⋃V′∈(2,v4,v5,v6)BV′∀)||W∩( _V ∈ eligible(2,\v_4,v_5,v_6\)B^∀_V )|, |W∩(⋃V′∈(2,v7,v8,v9)BV′∀)||W∩( _V ∈ eligible(2,\v_7,v_8,v_9\)B^∀_V )| and |W∩(⋃V′∈(2,v10,v11,v12)BV′∀)||W∩( _V ∈ eligible(2,\v_10,v_11,v_12\)B^∀_V )| must be at least 2. Since the four sets v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12\v_1,v_2,v_3\,\v_4,v_5,v_6\,\v_7,v_8,v_9\,\v_10,v_11,v_12\ do not share size-2 or size-3 subsets, and since no size-1 subsets are 2-eligible, W must contain one of ci1i21,ci1i31,ci2i31,ci1i2i31\c^1_i_1i_2,c^1_i_1i_3,c^1_i_2i_3,c^1_i_1i_2i_3\ for the (2,h1(2),h2(2))(2,h_1(2),h_2(2))-cohesive subset v1,v2,v3\v_1,v_2,v_3\. With no loss of generality,33 3 In this proof, we are showing impossibility of generating a winner set providing ArgPJR, so we mean no generality is lost for that objective. we assume W contains ci1i21c^1_i_1i_2. Similarly for the others, with no loss of generality, we assume W contains ci4i51c^1_i_4i_5, ci7i81c^1_i_7i_8 and ci10i111c^1_i_10i_11. 3. |W∩(⋃V′∈(3,v1,…,v6)BV′∀)||W∩( _V ∈ eligible(3,\v_1,…,v_6\)B^∀_V )| and |W∩(⋃V′∈(3,v7,…,v12)BV′∀)||W∩( _V ∈ eligible(3,\v_7,…,v_12\)B^∀_V )| must be at least 3. Now, the two sets v1,…,v6\v_1,…,v_6\ and v7,…,v12\v_7,…,v_12\ do not share size-4 or size-5 subsets, and no size-1, size-2 or size-3 subset is 3-eligible. With no loss of generality, we assume W contains ci1i2i3i41c^1_i_1i_2i_3i_4 and ci1i3i4i51c^1_i_1i_3i_4i_5 for the (3,h1(3),h2(3))(3,h_1(3),h_2(3))-cohesive set v1,…,v6\v_1,…,v_6\, and ci7i8i9i101c^1_i_7i_8i_9i_10 and ci7i9i10i111c^1_i_7i_9i_10i_11 for v7,…,v12\v_7,…,v_12\. 4. |W∩(⋃V′∈(4,v1,…,v9)BV′∀)||W∩( _V ∈ eligible(4,\v_1,…,v_9\)B^∀_V )| must be at least 4. No size-1, size-2, size-3, size-4, size-5 or size-6 subset of v1,…,v9\v_1,…,v_9\ is 4-eligible. With no loss of generality, we assume W contains ci1i2i3i4i5i6i71c^1_i_1i_2i_3i_4i_5i_6i_7, ci1i3i4i5i6i7i81c^1_i_1i_3i_4i_5i_6i_7i_8 and ci1i4i5i6i7i8i91c^1_i_1i_4i_5i_6i_7i_8i_9. 5. |W∩(⋃V′∈(5,v1,…,v12)BV′∀)||W∩( _V ∈ eligible(5,\v_1,…,v_12\)B^∀_V )| must be at least 5. No size-1, size-2, size-3, size-4, size-5 or size-6, size-7, size-8 or size-9 subset of v1,…,v12\v_1,…,v_12\ is 5-eligible. With no loss of generality, we assume W contains ci1i2i3i4i5i6i7i8i9i101c^1_i_1i_2i_3i_4i_5i_6i_7i_8i_9i_10, ci1i3i4i5i6i7i8i9i10i111c^1_i_1i_3i_4i_5i_6i_7i_8i_9i_10i_11, ci1i4i5i6i7i8i9i10i11i121c^1_i_1i_4i_5i_6i_7i_8i_9i_10i_11i_12 and ci1i2i4i5i6i7i8i9i10i111c^1_i_1i_2i_4i_5i_6i_7i_8i_9i_10i_11. |W|=16|W|=16 is now strictly greater than 12. So, there is no W providing ArgPJR for this argumentative voting profile and h. By contrapositive of Theorem 2, this impossibility result extends to ArgEJR and - ArgEJR- Spot. □ Proof of Theorem 6. We say that a subset C′C of C covers a subset Vx′V _x of V iff, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V′V of V, if V′∩Vx′≠∅V ∩ V _x = , then there is some V′∈(l,V′)V ∈ eligible(l,V ) such that V′∩Vx′≠∅V ∩ V _x = and that l≤|BV′∀∩C′|l≤|B^∀_V ∩ C |. By (C′) cover(C ) (C′⊆C C), we denote the largest subset V′V of V covered by C′C . For any subset C′C of C, let cohesion rank of C′C be: • the maximum integer i with which some subset of (V\(C′))(V cover(C )) is (i,h1(i),h2(i))(i,h_1(i),h_2(i))-cohesive; • 0 if there is no such subset, and let residual of C′C be |V\(C′)||V cover(C )|. For any subset C′C of C, we prove by induction on cohesion rank of C′C and subinduction on residual of C′C that, if (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ), then the claim holds. Base case: Cohesion rank of C′C is 0. Then, necessarily, residual of C′C is 0. W is any size-k subset of C such that C′⊆WC W. Inductive case: Assume that the claim holds for any subset C′C of C with (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ) up to cohesion rank of i. We prove it for any subset C′C of C with (k−|C′|)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C ) and cohesion rank of i+1i+1. By the definition of residual, necessarily (C′)≥(i+1)⋅(|V|/k) residual(C )≥(i+1)·(|V|/k). Then, necessarily (k−|C′|)⋅(|V|/k)≥(i+1)⋅(|V|/k)(k-|C |)·(|V|/k)≥(i+1)·(|V|/k), so necessarily k≥|C′|+(i+1)k≥|C |+(i+1). Let V′V be an ((i+1),h1(i+1),h2(i+1))((i+1),h_1(i+1),h_2(i+1))-cohesive subset of (V\(C′))(V cover(C )), and let c1,…,ci+1c_1,…,c_i+1 be i+1i+1 members of ⋂V′∈(i+1,V′)BV′∀ _V ∈ eligible(i+1,V )B^∀_V . Since h1(i+1)=h2(i+1)=i+1h_1(i+1)=h_2(i+1)=i+1, there is some v∈V′v∈ V such that these i+1i+1 members are in Bv∀B^∀_\v\. Thus, for any (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset V1′V _1 of V, if V1′V _1 contains v, it holds that there is some V1′∈(l,V1′)V _1∈ eligible(l,V _1) (namely, v\v\) such that l≤|BV1′∀∩W|l≤|B^∀_V _1∩ W|. Hence, |(C′∪c1,…,ci+1)|≥|(C′)|+(i+1)⋅(|V|/k)| cover(C ∪\c_1,…,c_i+1\)|≥| cover(C )|+(i+1)·(|V|/k). Let C′C be C′∪c1,…,ci+1C ∪\c_1,…,c_i+1\. It holds that (C′)≤(C′)−(i+1)⋅(|V|/k) residual(C )≤ residual(C )-(i+1)·(|V|/k). In the meantime, (k−|C′|)≥(k−|C′|)−(i+1)(k-|C |)≥(k-|C |)-(i+1). So, (k−|C′|)⋅(|V|/k)≥(C′)−(i+1)⋅(|V|/k)≥(C′)(k-|C |)·(|V|/k)≥ residual(C )-(i+1)·(|V|/k)≥ residual(C ). If cohesion rank of C′C is strictly smaller than i+1i+1, we apply induction hypothesis of main induction. If cohesion rank of C′C is i+1i+1, we apply induction hypothesis of subinduction. Hence, with respect to h, W provides ArgEJR- Spot, and by Theorem 2, also ArgEJR and ArgPJR. □ Proof of Theorem 7. We prove coNP-hardness by reducing Clique to the complement of the verification problem. Let G≡(U,E)G≡(U,E) be an undirected graph and let q be an integer greater than or equal to 2. We construct, in polynomial time, an argumentative voting profile (V,C,B,k)(V,C,B,k) and a size-k winner set W⊆CW C such that G has a clique of size q iff W fails to provide the axiom under consideration. Construction of (V,C,B,k)(V,C,B,k). Let k be ⌈|U|/q⌉ |U|/q . For every u∈Uu∈ U, we create a distinct voter vuv_u. We also create qk−|U|qk-|U| voters different from them, so that |V|=qk|V|=qk. Let W be c1,…,ck\c_1,…,c_k\ and let c0c_0 be such that c0∉Wc_0 ∈ W. For each t∈1,…,kt∈\1,…,k\, we create a candidate ct∘c _t. For each e≡u,u′∉Ee≡\u,u \ ∈ E, we create five candidates ce∙,ce,u⋄,ce,u′⋄,ce,u⋆c _e,c _e,u,c _e,u ,c _e,u and ce,u′⋆c _e,u . Also, let v1×,…,vqk−|U|×\v^×_1,…,v^×_qk-|U|\ be (V\vu1,…,vu|U|)(V \v_u_1,…,v_u_|U|\). For each vj×v^×_j (1≤j≤qk−|U|1≤ j≤ qk-|U|), we create a candidate cvj×c_v^×_j. C is then W∪c0∪c1∘,…,ck∘∪⋃e≡u,u′∉Ece∙,ce,u⋄,ce,u′⋄,ce,u⋆,ce,u′⋆∪cv1×,…,cvi×W∪\c_0\∪\c _1,…,c _k\∪ _e≡\u,u \ ∈ E\c _e,c _e,u,c _e,u ,c _e,u,c _e,u \∪\c_v^×_1,…,c_v^×_i\. Now, for every v∈Vv∈ V, every t∈1,…,kt∈\1,…,k\ and every e≡u,u′∉Ee≡\u,u \ ∈ E, we introduce the following attacks in v’s ballot: 1. (ct∘,ct)(c _t,c_t). So, unless ct∘c _t is defeated, ct∈Wc_t∈ W is not accepted. 2. (ce,u⋄,ce∙)(c _e,u,c _e), (ce,u′⋄,ce∙)(c _e,u ,c _e) and (ce∙,ct∘)(c _e,c _t). So, every ballot contains |u,u′∣u,u′∉E||\\u,u \ \u,u \ ∈ E\| attackers of ct∘c _t and two attackers for each of the attackers. Second, for every e≡u,u′∉Ee≡\u,u \ ∈ E, we introduce (ce,u⋆,ce,u⋄)(c _e,u,c _e,u) in vuv_u’s ballot, and (ce,u′⋆,ce,u′⋄)(c _e,u ,c _e,u ) in vu′v_u ’s ballot. So, in a combined ballot of voters including vuv_u and vu′v_u , ce∙c _e is accepted, and thus all candidates in W are accepted. Finally, for every vj×v^×_j (1≤j≤qk−|U|1≤ j≤ qk-|U|) and every t∈1,…,kt∈\1,…,k\, we introduce (cvj×,ct∘)(c_v^×_j,c _t) in vj×v^×_j’s ballot. So, in a combined ballot of voters including any vj×v^×_j, all candidates in W are accepted. B comprises all these ballots, and this concludes the polynomial-time construction of (V,C,B,k)(V,C,B,k). Correctness of the reduction. Let us first show that, for any non-empty subset V′V of V, W⊆BV′∀W B^∀_V iff there is some j∈1,…,qk−|U|j∈\1,…,qk-|U|\ such that vj×∈V′v^×_j∈ V or there is some e≡u,u′∉Ee≡\u,u \ ∈ E such that vu,vu′⊆V′\v_u,v_u \ V . If: vacuous from the construction. Only if: we show the contrapositive. Suppose there is no j∈1,…,qk−|U|j∈\1,…,qk-|U|\ such that vj×∈V′v^×_j∈ V and no e≡u,u′∉Ee≡\u,u \ ∈ E such that vu,vu′⊆V′\v_u,v_u \ V . Then, for every e=u,u′∉Ee=\u,u \∉ E, it holds that ce∙c _e is not accepted in BV′∀B^∀_V , and that at least one attacker of ce∙c _e is in BV′∀B^∀_V . Hence, for every t∈1,…,kt∈\1,…,k\, every attacker ce∙c _e of ct∘c _t is attacked by some accepted candidate. Therefore ct∘∈BV′∀c _t∈ B^∀_V . Since ct∘c _t attacks ctc_t, it follows that ct∉BV′∀c_t∉ B^∀_V . We now show correctness of the reduction. Only if: Suppose G has a size-q clique Q⊆UQ U. Let VQ′V _Q be vu∣u∈Q\v_u u∈ Q\, then for every non-empty subset V′V of VQ′V _Q, c0∈BV′∀c_0∈ B^∀_V and V′V is 1-eligible. Hence, |(1,VQ′)|=2|VQ′|−1=2q−1=2|V|/k−1| eligible(1,V _Q)|=2^|V _Q|-1=2^q-1=2^|V|/k-1. Therefore, VQ′V _Q is (1,1,1)(1,1,1)-cohesive. By Proposition 6, VQ′V _Q is (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive for every h. Now, because Q is a clique, VQ′V _Q contains no vj×v^×_j, j∈1,…,qk−|U|j∈\1,…,qk-|U|\, and there is no u,u′∉E\u,u \ ∈ E such that vu,vu′⊆VQ′\v_u,v_u \ V _Q. Hence, for any subset V′V of VQ′V _Q, it holds that W∩BV′∀=∅W∩ B^∀_V = . Therefore, with respect to any h, W fails to provide ArgJR. For l=1l=1, ArgPJR, ArgEJR and ArgEJR- Spot also require the existence of at least one candidate in W approved by an appropriate eligible subset. Since no eligible subset of VQ′V _Q approves any candidate in W, with respect to every h, W fails to provide these axioms. If: We show the contrapositive. Suppose that G has no size-q clique. Then, we must show that W provides every axiom. Let l be a positive integer not greater than k and let V′V be a (l,h1(l),h2(l))(l,h_1(l),h_2(l))-cohesive subset of V. Since V′V is argumentative l cohesive, by Proposition 3, |V′|≥l⋅|V|/k=l⋅q|V |≥ l·|V|/k=l· q. We consider cases. Case vj×∈V′v^×_j∈ V for some j∈1,…,qk−|U|j∈\1,…,qk-|U|\ : W⊆Bvj×∀W B^∀_\v^×_j\. Since |W|=k|W|=k and l≤kl≤ k, vj×\v^×_j\ is l-eligible and |W∩Bvj×∀|≥l|W∩ B^∀_\v^×_j\|≥ l. Case, otherwise : Since |V′|≥l⋅q≥q|V |≥ l· q≥ q and G has no size-q clique, there exist u,u′∈Uu,u ∈ U such that vu,vu′⊆V′\v_u,v_u \ V and that u,u′∉E\u,u \ ∈ E. Since W⊆Bvu,vu′∀W B^∀_\v_u,v_u \, vu,vu′\v_u,v_u \ is l-eligible. Also, |W∩Bvu,vu′∀|≥l|W∩ B^∀_\v_u,v_u \|≥ l. Hence, W provides ArgEJR- Spot with respect to any h. By Theorem 2, W provides every axiom with respect to any h. We have proved that the complement of the verification problem is NP-hard. Hence, verification is coNP-hard for each axiom with respect to any h. □ Proof of Theorem 8. Run-time of Algorithm 1. We assume that each ballot is represented by an adjacency matrix over C, so that whether c1c_1 attacks c2c_2 in a voter’s ballot can be checked in constant time. Alternative standard representations, such as edge lists, do not affect polynomial-time computability, although they may change the precise running time. Set operations over subsets of V and C are implemented by lists or arrays, and therefore take polynomial time in |V||V| and |C||C|. To construct the initial waitingwaiting set, Algorithm 1 computes, for each candidate c∈Cc∈ C, the largest voter set Vc=v∈V∣v’s ballot contains no attack against c.V_c=\v∈ V $v$'s ballot contains no attack against $c$\. For a fixed pair (c,v)(c,v), checking whether v attacks c requires scanning all possible attackers c′∈Cc ∈ C and testing whether (c′,c)∈Rv(c ,c)∈ R_v. This takes O(|C|)O(|C|) time. Since there are |C||C| candidates and |V||V| voters, constructing all sets VcV_c takes O(|V||C|2)O(|V||C|^2) time. The size checks |Vc|≥|V|/k|V_c|≥|V|/k take at most O(|V||C|)O(|V||C|) time in total, and are therefore dominated by O(|V||C|2)O(|V||C|^2). Next consider an update step. The algorithm works with pairs (c,V′)(c,V ), where c∈Cc∈ C and V′⊆V V. For a fixed voter set V′V , computing which candidates are unattacked under the combined ballot of V′V can be done by scanning all voters in V′V and all ordered pairs of candidates. This costs at most O(|V||C|2)O(|V||C|^2) time. All other operations in the same update step, such as updating outout, AllocAlloc, and D, testing set membership, and comparing priorities, are polynomially bounded by O(|V||C|2)O(|V||C|^2). It remains to bound the total cost of recomputing waitingwaiting. Since Algorithm 1 terminates once |out|=k|out|=k, and since by construction there are at most k−1k-1 voter sets in keys(D)keys(D), we have |keys(D)|<k|keys(D)|<k throughout the execution. For each V′∈keys(D)V ∈ keys(D), the pairs that can be newly added to waitingwaiting are computed by inspecting the combined ballot (C,⋃v∈V′Rv)(C, _v∈ V R_v) and the candidates that remain relevant after taking D[V′]D[V ] into account. This computation can be performed in O(|V||C|2)O(|V||C|^2) time for each fixed V′V . Since |keys(D)|<k|keys(D)|<k, one recomputation of waitingwaiting takes O(k|V||C|2)O(k|V||C|^2) time. Finally, the number of recomputations of waitingwaiting is bounded by k. Let k′k denote |out||out| right before the first execution of line 14. It holds that k′=|keys(D)|k =|keys(D)|. If k′=0k =0, then after the execution of line 14, waiting=∅waiting= and line 16 is executed. Otherwise, by the definition of line 14, for each V′∈keys(D)V ∈ keys(D) and any pair (c,V′)∈waiting(c,V )∈ waiting, c∉D[V′]c ∈ D[V ]. Thus, if the main loop is executed k times, there is at least one V′∈keys(D)V ∈ keys(D) such that |D[V′]|≥k|D[V ]|≥ k. This means that |out|=k|out|=k. Hence the total cost of all recomputations is O(k2|V||C|2)O(k^2|V||C|^2). Adding the O(|V||C|2)O(|V||C|^2) initialisation cost does not change the bound. Therefore Algorithm 1 runs in O(k2|V||C|2)O(k^2|V||C|^2) time under the present assumption that each ballot is represented by an adjacency matrix over C. With other representations such as edge lists, Algorithm 1 still runs in polynomial time. The Java implementation is in the supplementary material, as the greedyGrounded method in GreedyGroundedDemo.java, and runs in O(k2|V||C|2)O(k^2|V||C|^2). A better run-time bound. Note that the waitingwaiting set needs to be updated only incrementally. After a pair (c,V′)(c,V ) is selected, the incremental implementation recomputes only the candidate pairs associated with the affected voter set V′V , rather than recomputing waitingwaiting from all voter sets in keys(D)keys(D). For a fixed V′V , this update costs O(|V||C|2)O(|V||C|^2). Since at most k recomputations are done before |out|=k|out|=k, the total update cost is O(k|V||C|2)O(k|V||C|^2). Since the initialisation cost is O(|V||C|2)O(|V||C|^2), the overall running time is O(k|V||C|2)O(k|V||C|^2). The Java implementation of this incremental version is in the supplementary material, as the greedyGroundedIncremental method in GreedyGroundedDemo.java, and runs in O(k|V||C|2)O(k|V||C|^2). Correctness of Algorithm 1. Theorem 4 proved that a size-k subset W of C providing ArgJR with respect to any h exists for every member of M A. For each candidate c∈Cc∈ C, Algorithm 1 computes the largest voter set Vc′⊆V _c V whose members do not attack c. Hence, if there is a (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive set of voters, then for every maximal (1,h1(1),h2(1))(1,h_1(1),h_2(1))-cohesive set of voters V′V that is itself 1-eligible, the initial waitingwaiting set contains at least one pair (c,Vc′)(c,V _c) such that Vc′=V′V _c=V . We divide cases by the size of the initial waitingwaiting set. Case |waiting|≤k|waiting|≤ k : Algorithm 1 adds every c∈Cc∈ C occurring in the members of waitingwaiting to outout. Thus, any size-k subset of C that contains outout provides ArgJR (with respect to any h). Case |waiting|>k|waiting|>k : Algorithm 1 selects a highest-priority pair (c,Vc′)(c,V _c) in waitingwaiting each time. With Theorem 4’s cover, c\c\ covers at least Vc′V _c which is at least as large as |V|/k|V|/k. If c\c\ covers V, then any size-k subset of C that includes c provides ArgJR with respect to any h. If c\c\ does not cover V, there are at least ⌈|V|/k⌉ |V|/k voters who have not been covered. Necessarily, their scores are 0. The highest-priority pair (cx,Vx′)(c_x,V _x) in waiting\(c,Vc′)waiting \(c,V _c)\ is therefore such that |Vx′|≥|V|/k|V _x|≥|V|/k. This selection process continues, and it takes at most k additions to outout before outout covers V. □ A3 Claims and Proofs of Auxiliary Lemmas Lemma 1 (Collective approval gadgets) Let an argumentative voting profile (V,C,B,k)(V,C,B,k) be such that it satisfies the following conditions. 1. V has a non-empty subset V′≡v1,…,vjV ≡\v_1,…,v_j\. 2. C has a subset c0,cv1,…,cvj,cV′\c_0,c_v_1,…,c_v_j,c_V \. 3. B satisfies the following conditions. (a) c0∈⋂v∈V′Bv∀c_0∈ _v∈ V B^∀_\v\. (b) for any x,y∈1,…,jx,y∈\1,…,j\, (cvx,cvx)∈Rvy(c_v_x,c_v_x)∈ R_v_y and (cvx,cV′)∈Rvy(c_v_x,c_V )∈ R_v_y. (c) for any y∈1,…,jy∈\1,…,j\, (c0,cvy)∈Rvy(c_0,c_v_y)∈ R_v_y and (c0,cvy)∉⋃v∈(V\vy)Rv(c_0,c_v_y) ∈ _v∈(V \v_y\)R_v. (d) for any y∈1,…,jy∈\1,…,j\, no other attacks among members of c0,cv1,…,cvj,cV′\c_0,c_v_1,…,c_v_j,c_V \ exist in RvyR_v_y. For any non-empty subset Vx′V _x of V, if cV′∈BVx′∀c_V ∈ B^∀_V _x, then V′⊆Vx′V V _x. Proof. Bv1B_\v_1\ is shown below for c0,cv1,…,cvj,cV′\c_0,c_v_1,…,c_v_j,c_V \. cV′ @inpgf@ignorespaces c_V cv1 @inpgf@ignorespaces c_v_1⋯ @inpgf@ignorespaces·scvj @inpgf@ignorespaces c_v_jc0 @inpgf@ignorespaces c_0 B_\v_1\ If cV′c_V is approved by Vx′V _x, it has to be that V′⊆Vx′V V _x. □ Lemma 2 (Non-approval gadgets) Let an argumentative voting profile (V,C,B,k)(V,C,B,k) be such that it satisfies the following conditions. 1. V has a non-empty subset V1′V _1 such that V2′≡(V 1′)V _2≡(V V _1) is non-empty. 2. C has a subset c0,c1\c_0,c_1\. 3. for any v∈Vv∈ V, (c0,c0)∈Rv(c_0,c_0)∈ R_v. 4. for any v∈V1′v∈ V _1, (c0,c1)∈Rv(c_0,c_1)∈ R_v. 5. for any v∈Vv∈ V, no other attacks among c0,c1\c_0,c_1\ exist in RvR_v. For any non-empty subset V′V of V, if V′∩V1′≠∅V ∩ V _1 = , then c1∉BV′∀c_1 ∈ B^∀_V . Proof. Bv′B_\v \ for v′∈V1′v ∈ V _1 and Bv′B_\v \ for v′∈V2′v ∈ V _2 are shown below. c1 @inpgf@ignorespaces c_1c0 @inpgf@ignorespaces c_0′ B_\v \c1 @inpgf@ignorespaces c_1c0 @inpgf@ignorespaces c_0′ B_\v \ Since c0∉BV′∀c_0 ∈ B^∀_V for any V′⊆V V, v′∈V′v ∈ V implies that c1∉BV′∀c_1 ∈ B^∀_V . □ Lemma 3 (Cohesion correspondence in τ) Let x≡(V,C,A,k)x≡(V,C,A,k) be a member of M M. For any non-empty subset V′V of V and any positive integer l, 1. If V′V is l-cohesive in x, then V′V is (l,l,l)(l,l,l)-cohesive in τ(x)τ(x). 2. If V′V is argumentative l-cohesive in τ(x)τ(x), then there is a non-empty subset V′V of V′V such that V′V is argumentative l-cohesive in τ(x)τ(x) and l-cohesive in x. 3. If V′V is argumentative l-cohesive in τ(x)τ(x) and l-cohesive in x, then for any non-empty subset V′V of V′V , if V′V is argumentative l-cohesive in τ(x)τ(x), then V′V is l-cohesive in x. Proof. For the first obligation, if V′V is l-cohesive in (V,C,A,k)(V,C,A,k), then |V′|≥l⋅(|V|/k)|V |≥ l·(|V|/k) and |AV′∀|≥l|A^∀_V |≥ l. By Fact 1, for any non-empty subset V′V of V′V , it holds that AV′∀⊆AV′∀A^∀_V A^∀_V . So, (l,V′) eligible(l,V ) comprises all non-empty subsets of V′V . Then, |(l,V′)|≥2l⋅(|V|/k)−1| eligible(l,V )|≥ 2^l·(|V|/k)-1 and l≤|⋂V′∈(l,V′)BV′∀|l≤| _V ∈ eligible(l,V )B^∀_V | and l≤min∅≠V′⊆V′|BV′∀|l≤ min_ =V V |B^∀_V |. So, V′V is (l,l,l)(l,l,l)-cohesive. For the second obligation, suppose V′V is argumentative l-cohesive in τ(V,C,A,k)τ(V,C,A,k). If V′V is (l,l,l)(l,l,l)-cohesive, then clearly V′V is l-cohesive in (V,C,A,k)(V,C,A,k). Otherwise, there is a non-empty subset Vx′V _x of V′V such that (V′ ′)(V V _x) is (l,l,l)(l,l,l)-cohesive in τ(V,C,A,k)τ(V,C,A,k) but V′∪vV ∪\v\ is not (l,l,l)(l,l,l)-cohesive in τ(V,C,A,k)τ(V,C,A,k) for each v∈Vx′v∈ V _x. Let V′V denote (V′ ′)(V V _x), then V′V is l-cohesive in (V,C,A,k)(V,C,A,k). For the third obligation, suppose V′V is argumentative l-cohesive in τ(V,C,A,k)τ(V,C,A,k) and l-cohesive in (V,C,A,k)(V,C,A,k). Since V′V is then (l,l,l)(l,l,l)-cohesive in τ(V,C,A,k)τ(V,C,A,k), for any subset V′V of V′V , if V′V is argumentative l-cohesive in τ(V,C,A,k)τ(V,C,A,k), then V′V is necessarily l-cohesive in (V,C,A,k)(V,C,A,k). □