# individual_representation_in_approvalbased_committee_voting__6a1262b9.pdf Individual Representation in Approval-Based Committee Voting Markus Brill,1 Jonas Israel,1 Evi Micha,2 Jannik Peters1 1 Research Group Efficient Algorithms, TU Berlin, Germany 2 Department of Computer Science, University of Toronto, Canada brill@tu-berlin.de, j.israel@tu-berlin.de, emicha@cs.toronto.edu, jannik.peters@tu-berlin.de When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are represented in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between voter interval and candidate interval preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles. 1 Introduction We consider the problem of selecting a fixed-size subset of candidates (a so-called committee) based on the approval preferences of agents. This problem has been extensively studied in recent years (Lackner and Skowron 2021) and has a wide variety of applications, including political elections (Brill et al. 2020), recommender systems (Skowron et al. 2017), medical diagnostic decision-making (Gangl et al. 2019), and participatory budgeting (Peters, Pierczy nski, and Skowron 2021). A central concern in committee voting is the principle of proportional representation, which states that the agents interests and opinions should be reflected proportionately in the committee. While proportional representation is intuitive to understand in scenarios such as apportioning parliamentary seats based on vote shares (Balinski and Young 1982; Pukelsheim 2014), it is less straightforward to formalize in the context of approval-based committee elections. Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Indeed, the literature has defined a number of different concepts aiming to capture proportional representation. Most (if not all) of these approval-based proportionality notions focus on the representation of groups of agents. Specifically, it is usually required that each sufficiently large group of agents is represented in the committee,1 where the interpretation of representation differs across different notions. For example, extended justified representation (Aziz et al. 2017) prescribes that there exists at least one agent in the group approving a certain number of committee members, whereas proportional justified representation (S anchez-Fern andez et al. 2017) demands that there are sufficiently many committee members that are each approved by at least one agent in the group. Notably, neither definition comprises any representation requirements for individual agents in a group. Thus, a group may count as represented even though some agents in the group do not approve a single committee member. In this paper, we adopt an individualistic point of view: our goal is to provide all members of a voter group equal guarantees. Intuitively, when a population consists of n agents and a committee of k representatives is elected, we expect every cohesive voter group of size ℓ n/k to be represented by ℓrepresentatives in the committee; thus, each individual group member might reasonably hope that at least ℓcandidates represent her in the committee. This notion, which we call individual representation, is aligned with the notion of individual fairness that was recently introduced in clustering (and in particular in facility location problems) by Jung, Kannan, and Lutz (2020): there, each individual expects to be served by a facility in distance proportional to the radius of the ball that captures its n/k closest neighbors, where n is the number of individuals and k is the number of facilities. Individual representation, as defined in this paper, is a strengthening of a notion called semi-strong justified representation by Aziz et al. (2017). The latter property requires that all members of a group are represented in the committee at least once, given that the group is large and cohesive 1Often, there is also a condition on the cohesiveness of the group, stating that the approval preferences of group members need to be sufficiently aligned. The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) enough. Individual representation strengthens this requirement by demanding that all members of cohesive groups are represented multiple times (in proportion to the group size). Aziz et al. (2017) observed that semi-strong JR cannot be provided in all instances; this immediately implies our stronger requirement is not universally attainable either. Our contribution. In this paper, we systematically study individual representation (IR). Notwithstanding the observation that IR demands cannot always be met, we clarify how IR relates to existing axioms and we show that a large range of common approval-based committee voting rules can fail to provide IR even in cases where IR is achievable. We observe that even committees approximating IR may fail to exist. Moreover, we answer a question by Aziz et al. (2017) by showing that it is computationally intractable to decide whether a given instance admits a committee providing semi-strong JR or individual representation. We then turn our attention to restricted domains of preferences (Elkind and Lackner 2015; Yang 2019) and demonstrate that positive results can be obtained. Doing so, we uncover a striking difference between the candidate interval and voter interval domains: whereas the former restriction does not admit any non-trivial approximation of IR, we devise an efficient algorithm for selecting committees approximating IR for the latter. This is surprising insofar as these two domain restrictions often exhibit similar behavior (Pierczy nski and Skowron 2021; Terzopoulou, Karpov, and Obraztsova 2021). Finally, we experimentally study how often IR is achievable for a wide variety of generated preference data, and how often established voting rules select IR outcomes. 2 Preliminaries For t N = {1, 2, . . . }, let [t] denote the set {1, 2, . . . , t}. Let N = [n] be a set of n voters (or agents) and C = {c1, . . . , cm} be a set of m candidates. Each voter i N approves a subset Ai C of candidates. An (approval) profile A = (A1, . . . , An) contains the approval set Ai for each i N. Given a committee size k [m], we want to select a subset W C of size |W| = k, referred to as a committee. We call (A, k) an approval-based committee (ABC) election. An ABC voting rule takes as input an ABC election (A, k) and outputs one or more committees of size k. As is standard in the ABC election literature, we assume that voters only care about the number of approved candidates in the committee, i.e., voter i evaluates a committee W by |Ai W|. Given a subset S C of candidates, we let N(S) denote the set of voters who approve all candidates in S, i.e., N(S) = {i N : S Ai}. Given an ABC election (A, k) and ℓ N, we call a group V N of voters ℓ-cohesive if The following representation notions are due to Aziz et al. (2017). A committee W C of size k provides justified representation (JR) if for each 1-cohesive group V N, there is a voter i V with |W Ai| 1; extended justified representation (EJR) if for each ℓ N and each ℓ-cohesive group V N, there is a voter i V with |W Ai| ℓ; and core stability if for each group V N (independent of V being ℓ-cohesive) and S C with |S| |V | n k there is a voter i V with |W Ai| |S Ai|. All of these notions have in common that they consider a group of voters represented as long as at least one voter in the group is sufficiently represented. This point of view might be hard to justify in many contexts. In the following section, we present our approach to representation that takes into account every voter in a group individually. 3 Individual Representation In this section, we define the main concept of this paper: individual representation. This notion builds on the idea of (semi-)strong justified representation defined by Aziz et al. (2017) and the notion of individual fairness in clustering as defined by Jung, Kannan, and Lutz (2020). Similarly to the proportionality notions defined above, we assume that a voter i N deserves some representation in an ABC election if i can find enough other voters who all approve a subset of candidates in common. This follows the rationale that everyone in a group of voters that makes up a sizable part of the electorate and can come to an agreement on how (part of) the committee ought to be filled, should be represented accordingly. Given an ABC election (A, k), we determine the number of seats that voter i N can justifiably demand as fi := max S Ai{|S|: |N(S)| |S| n/k}. In words, fi is the largest value f such that voter i can find enough like-minded voters to form an f-cohesive group. Definition 1 (Individual Representation). Given an ABC election (A, k), a committee W C of size at most k provides individual representation (IR) if |W Ai| fi for all voters i N. When only requiring |W Ai| 1 for every voter with fi 1 we get semi-strong justified representation (semistrong JR) as defined by Aziz et al. (2017). The authors of that paper provide an example showing that semi-strong JR committees do not always exist. Since individual representation clearly is a more demanding property, it immediately follows that IR committees (i.e., committees providing IR) do not need to exist either. IR not only implies semi-strong JR, but also EJR. More precisely, every IR committee also provides EJR. To build intuition on how our notion differs from established ones, and on how it leads to the election of committees that are fair from an individual voter perspective, consider the following examples, illustrated in Figure 1. Example 1. The first part of Figure 1 shows an approval profile with 8 voters and 3 candidates. Assuming k = 2, 1 2 3 4 5 6 7 8 c1 c2 c3 1 2 3 4 5 6 7 8 9 10 11 12 c1 c2 c3 c4 c1 c2 c3 c2 c3 c4 c5 c6 c7 c8 Figure 1: Two profiles admitting IR committees that are not identified by common voting rules or other representation axioms. Voters correspond to integers and approve all candidates placed above them. every voter i N has fi = 1. Thus, the only committee providing IR is W = {c1, c2}, which represents every voter once and, moreover, satisfies core stability. However, both W = {c1, c3} and W = {c2, c3} are core stable as well (and in fact would be selected when choosing a committee maximizing social welfare). Many common ABC voting rules would select either W or W (see Proposition 4). One can argue that committee W is a much fairer or more representative choice in this example. Example 2. The second part of Figure 1 shows an approval profile with 12 voters and 10 candidates. For k = 6 we have fi = 1 for i {1, . . . , 4} and fi = 2 for i {5, . . . , 12}. Here, the only committee providing IR is W = {c1, c2, c3, c4, c9, c10} representing each of the first four voters once, while representing all other voters at least twice. This committee is not core stable, because the voter group {5, . . . , 12} would prefer {c5, c6, c7, c8} to W. In order to appreciate the IR committee W, consider voters 1 to 4 and observe that these voters are completely symmetric. Hence, from an equal treatment of equals perspective, if one of them is represented by an approved candidate in the committee, the same should hold for the others. In fact, the only core-stable committees that provide this kind of symmetry are {c5, . . . , c10}, in which one third of the electorate is not represented at all, or committees containing only two candidates among c5 to c8. In the latter case, by noticing that voters 9 to 12 are symmetric as well, we can argue similarly as above that they are not treated equally. Thus, the committee W that uniquely provides IR can be considered the fairest choice under an individualistic point of view. The instance in Example 2 shows that core stability and individual representation are incompatible, in the strong sense that the (nonempty) set of IR committees and the (nonempty) set of core-stable committees are disjoint. core stability EJR JR IR semi-strong JR Figure 2: Relationships between individual representation (IR) and the representation notions introduced by Aziz et al. (2017). An arrow from X to Y depicts that X implies Y (if X is possible in the given instance). Proposition 1. IR is incompatible with core stability. Next, we show a further incompatibility result. Proposition 2. Semi-strong JR is incompatible with EJR. Proof. Consider an ABC election with n = 8, k = 4 and the following approval profile: A1 = = A4 = {c1, c2}, A5 = {c3, c4, c5}, A6 = {c3}, A7 = {c4}, and A8 = {c5}. As f6 = f7 = f8 = 1, every committee W that provides semi-strong JR must satisfy {c3, c4, c5} W. But then we have |W Ai| < 2 for all i [4], even though these four voters form a 2-cohesive group. A graphical representation of these results can be found in Figure 2. Approximate notions. As we mentioned above, IR is not always attainable. The immediate next question is whether we can guarantee IR in an approximate sense. To study this question, we introduce the notion of (α, β)-individual representation, which uses additive and multiplicative approximation parameters. Definition 2 ((α, β)-Individual Representation). Given an ABC election (A, k), a committee W provides (α, β)- individual representation ((α, β)-IR) if for every voter i N, α |Ai W| + β fi, with α 1 and β 0. Unfortunately, non-trivial approximation guarantees are impossible to obtain without restricting the set of profiles. Theorem 3. There exists an instance that does not admit an (α, β)-IR committee for β < k 1, and any α 1. Proof. Assume that n = k (k + 1). Then it holds that n/k = k+1 > k. Consider a profile in which for each voter i [n/k], Ai = {c(k 1) (i 1)+1, . . . , c(k 1) i} and all remaining n n/k voters approve all candidates. Thus, for every voter i [n/k] we get that |N(Ai)| = 1+n n/k = 1 + (k 1)(k + 1). Since n/k = k + 1, this implies that fi k 1. Further, for all distinct voters i, i [n/k] it holds that |Ai Ai | = 0. However, since n/k > k, for each W C with |W| = k there is a voter i [n/k] with |Ai W| = 0. Thus, for any α 1 and β < k 1 this instance does not admit a (α, β)-IR committee. To see that this bound is worst-possible, note that if fi = k for some voter i, this means that all voters have a set of at least k jointly approved candidates (and a committee consisting of such candidates would provide IR). On the other hand, every committee trivially provides (1, k 1)-IR whenever fi < k for all i N. 3.1 ABC Rules Violating IR While the inapproximability result in the previous section is quite discouraging, a natural follow-up question is whether we can at least find IR committees whenever they exist. This question was already raised by Aziz et al. (2017) in the context of semi-strong JR, but remained open. In other words, we look for rules that are consistent with individual representation. Definition 3 (IR-consistency). An ABC rule is consistent with individual representation, or short IR-consistent, if it outputs at least one IR committee for every ABC election that admits one. Consistency with semi-strong JR can be defined analogously. We show that all common ABC voting rules fail consistency with respect to both IR and semi-strong JR.2 Example 1 already rules out any rule that always selects one of the candidates with the highest numbers of approvals, so-called approval winners. In particular, this class of rules includes all common committee-monotonic ABC rules as well as other sequential rules like Rule X, as these rules select one of the approval winners in the very first round. 3 Proposition 4. No ABC voting rule that always selects one of the approval winners into the winning committee is IR-consistent. Moreover, the rules PAV, Satisfaction-AV, and reverseseq PAV select only committees including c3 in Example 1, and thus fail IR-consistency. In the full version of the paper (Brill et al. 2021), we provide additional examples showing that all remaining ABC rules mentioned in Table 1 of the survey by Lackner and Skowron (2021) fail IR-consistency as well. 3.2 Computational Complexity Another open problem stated by Aziz et al. (2017) concerns the computational complexity of deciding whether a given ABC election admits a committee providing semi-strong JR. We settle this question and the analogous one for individual representation by showing that both problems are NP-hard. Theorem 5. It is NP-hard to decide whether an ABC election admits an IR committee or a semi-strong JR committee. Proof. We reduce from exact cover by 3-sets. Here, we are given a set of elements X = {x1, . . . , x3ℓ} and a family of sets T 2X such that |T| = 3 for all T T . The goal is to find a partition of X into sets from T . The problem is NP-hard even if each element appears in exactly three sets (Garey and Johnson 1979). We construct an ABC instance by setting N = X and C = T . Further, each set T T = 2Since neither IR nor semi-strong JR is always achievable (and semi-strong JR may be achievable in instances where IR is not) we can, in general, not deduce consistency regarding one of the notions from consistency regarding the other. However, all our examples in this section satisfy fi 1 for all voters i, such that semi-strong JR and IR coincide. 3For the common rules defined in this paper, we refer the reader to the survey (Lackner and Skowron 2021). {xi, xj, xl} is approved exactly by voters xi, xj, and xl. We set k = ℓ. Hence, only groups of 3 voters corresponding to sets in T are 1-cohesive, and we get fxi = 1 for each xi X. Every exact cover by 3-sets corresponds to a committee of size k where every voter is represented exactly once and thus provides IR in this instance. Conversely, every IR committee of the constructed ABC instance corresponds to a selection of sets from T such that every element in X is covered exactly once. Since fi = 1 for every voter, the same argument holds for semi-strong JR as well. Moreover, it is hard to decide whether a given voter s fi-value exceeds a given value. Theorem 6. Given an ABC instance, a voter i, and j N, it is NP-complete to decide whether fi j. Proof. It is easy to see that this problem is in NP since any subset of voters including voter i of size j |N| k and any subset of candidates of size j approved by all selected voters serves as a witness. We reduce from balanced complete bipartite subgraph. Here, we are given a bipartite graph G = (V1 V2, E) and an integer j and the goal is to decide whether G has Kj,j as a subgraph, i.e., a subgraph consisting of j vertices from V1 and j vertices from V2 forming a bipartite clique. The problem is known to be NP-hard (Garey and Johnson 1979). We construct an ABC instance by setting N = V1 {x}, C = V2 {y} and k = |V1|+1. Thus, n k = 1. Each v V1 approves exactly its neighbors in G, as well as y, while x approves all candidates. It follows that fx j + 1 if and only if there is a set of j voters different from x approving at least a common set of j + 1 candidates. Since all voters approve y, this is equivalent to these j voters all approving j candidates different from y and therefore by definition all being connected to these j vertices in V2. Thus, they form a Kj,j if and only if fx j + 1. 4 Domain Restrictions We have seen in Theorem 3 that non-trivial approximations of individual representation are impossible to obtain in general. In this section, we explore whether this negative result can be circumvented by considering restricted domains of preferences. Domain restrictions for dichotomous (i.e., approval) preferences have been studied by Elkind and Lackner (2015) and Yang (2019). Restricting attention to a well-structured domain often allows for axiomatic and algorithmic results that are not achievable otherwise (Elkind, Lackner, and Peters 2017). In the ABC setting, for example, it has recently been shown that a core-stable committee always exists in certain restricted domains (Pierczy nski and Skowron 2021), whereas the existence of such committees is an open problem for the unrestricted domain. 2We start by recalling the definitions of two classic restricted domains of dichotomous preferences: candidate interval and voter interval (Elkind and Lackner 2015). Definition 4 (Candidate Interval). An approval profile A satisfies candidate interval (CI) if there is a linear order over the candidates C such that for every voter i N, Ai consists of an interval of that order. Definition 5 (Voter Interval). An approval profile A satisfies voter interval (VI) if there is a linear order over the voters N such that for every candidate cj C, the voters that approve cj build an interval of that order. The profile in Example 1 satisfies both candidate interval and voter interval. In fact, a voter order witnessing VI is given in Figure 1. To see that the profile satisfies CI as well, consider the order (c1, c3, c2). The profile in Example 2, on the other hand, satisfies neither CI nor VI. Elkind and Lackner (2015) have shown that it can be checked in polynomial time whether a profile satisfies CI or VI. (If the answer is yes, a linear order over candidates/voters can be found efficiently as well.) Our first observation is that the candidate interval domain is not helpful for our purposes: Indeed, the approval profile used to establish Theorem 3 can easily be seen to satisfy CI. Thus, restricting preferences in this way does not yield any improved bounds. Corollary 7. There exists a CI profile that does not admit an (α, β)-IR committee with β < k 1 and any α 1. Now, we turn our attention to the voter interval domain. Due to the similarity between VI and CI, one might expect a similar result here. Surprisingly, however, we can prove a positive result for VI: We provide an algorithm that finds a (2, 4)-IR committee in polynomial time for any VI profile. (In the full version of the paper, we show that such a guarantee cannot be provided by common ABC rules.) Before describing the high level idea of our algorithm we state a useful property of VI profiles. Without loss of generality, we assume that the linear order witnessing VI is given by (1, . . . , n). Moreover, for a, b Z with a b, we let [a, b] denote the integer interval {a, a + 1, . . . , b}. Observation 8. Let i1, i2, i3 [n] such that i1 < i2 < i3. For any S C, if i1 N(S) and i3 N(S), then i2 N(S). Let S i := arg max S Ai{|S|: |N(S)| |S| n/k}, i.e., a largest subset of Ai approved by sufficiently many voters to validate the fi-value. (If multiple such sets exist, ties are broken arbitrarily.) From Observation 8 we know that if i1, i2, i [n] such that i1 < i2 < i or i < i2 < i1, and if i1 N(S i ), then i2 N(S i ), i.e., N(S i ) forms an interval of the order of voters including i. Further, let N 0. First, using induction, we show that |Wt| = |Wt r| + f t/2 |Wt r At| for any r [1, t + 1]. For r = 1, the claim immediately follows from Equation (1). Assume that for all q < q it holds that |Wt| = |Wt q | + f t/2 |Wt q At|. Now, we have |Wt (q 1) At| = f t (q 1)/2 |Wt q At (q 1)| + |Wt q At| (2) as at iteration t (q 1), f t (q 1)/2 |Wt q At (q 1)| candidates from S t (q 1) are added to Wt (q 1), and as t N(S t (q 1)), these candidates are approved by t, too. Then, |Wt| = |Wt (q 1)| + f t/2 |Wt (q 1) At| = |Wt q| + f t (q 1)/2 |Wt q At (q 1)| + f t/2 |Wt (q 1) At| = |Wt q| + f t/2 |Wt q At|, where the second transition follows since at iteration t (q 1), f t (q 1)/2 |Wt q At (q 1)| candidates are added to Wt (q 1), and the third transition follows from Equation (2). Now, we distinguish two cases. Case 1: t = t 1. Here, we have |Wt| = |Wt (t +1)| + f t/2 |Wt (t +1) At| = |W0| + f t/2 |W0 At| = |N t| k Case 2: t > 1. Here, we have |Wt| =|Wt (t +1)| + f t/2 |Wt (t +1) At| (t (t + 1) 1 + |N t (t +1)|) k (t 1 + |N t|) k where the third inequality follows from the fact that |N t (t +1)| t (t (t + 1)), as t is not in N(S t (t +1)). As Rounds 1 and 2 of Algorithm 1 are symmetric, with similar arguments, we can show the following lemma. Lemma 12. | ˆ Wi| ((i 1)+|N 2 and m = 2(k 1). All the voters i [2, n 1] approve all the candidates, while A1 = {c1, . . . , ck 1} and An = {cm k+2, . . . , cm}. Notice that this profile is VI. Indeed, if we order the voters as 1, 2, . . . , n, then the voters that approve each candidate form an interval of the ordering. Now, we can see that f1 = fn = k 1, but for each W C, with |W| = k, either |A1 W| k/2 or |An W| k/2. Beyond VI and CI, many other domain restrictions have been studied in the literature. In the full version of the paper, we provide lower and upper bounds for (α, β)-IR for all domain restrictions introduced by Elkind and Lackner (2015) and Yang (2019). Any domain that is more restrictive than VI inherits the guarantee of a (2, 4)-IR committee from VI but we show that in some cases we can achieve better approximation guarantees. On the other hand, any domain that is more general than CI inherits the inapproximability from CI. In fact, we show that the same lower bound applies even in a slightly more restricted domain introduced by Yang (2019). We also determined for which of the considered domain restrictions a semi-strong JR committee is guaranteed to exist. 1 5 10 15 20 25 30 35 40 45 50 k Fraction of profiles Profiles Admitting an IR Committee VI CI 2D IC Urn Mallows VI CI 2D IC Urn Mallows Models Fraction of profiles Individual Representation Consistency of ABC Rules AV PAV seq-PAV greedy Monroe Rule X seq-Phragmén seq-CC Figure 3: The figure on the left shows the ratio of generated profiles that admit an IR committee. In the figure on the right, for each model and each voting rule, the bold colored part of the bar indicates the ratio of instances the rule returned an IR committee, while the pale-colored part indicates the same ratio for semi-strong JR, averaged over all values k with 2 k 20. For each model, the black line indicates the fraction of instances admitting an IR committee, while the gray dashed line indicates the ratio of instances admitting a semi-strong JR committee. 5 Experimental Results To complement our theoretical results, we performed experiments on generated approval profiles. Setup. Inspired by Peters et al. (2021), we used six models to generate approval profiles: a voter-interval model (VI), a candidate-interval model (CI), a two-dimensional Euclidean model (2D), an impartial culture model (IC), an urn model (Urn), and a Mallows model (Mallows). For detailed descriptions of these models, we refer to the full version of the paper. We considered the ABC rules AV, PAV, seq-PAV, greedy Monroe, Rule X, seq-Phragm en, and sequential Chamberlin Courant (seq-CC). For all conducted experiments, we have 100 voters and 50 candidates and generated 500 instances for each model and for each k [50]. Results. First, we studied how often the generated approval profiles admit an IR committee. The results are shown in the left graph of Figure 3. We found that IR committees exist quite often, especially for larger values of k. In particular, profiles generated by the VI model or by the urn model almost always admit IR committees. On the other hand, profiles generated by the CI model almost never admit IR committees (except for k 35). This striking contrast between VI and CI, which is reminiscent of our theoretical results in Section 4, can be explained with a feature of the preference generation model: Due to the way we generate CI preferences, almost 20% of voters have an approval set spanning at least 20% of the candidates. These voters approving many candidates are then part of multiple cohesive groups, not all of which can be represented in an IR manner. (A similar situation can be observed in the profile that proves Theorem 3.) Second, we studied how often different ABC rules select a committee providing IR (or semi-strong JR). In order not to dilute our results, we restricted k to the interesting range between 2 and 20. The results are shown in the right graph of Figure 3. Of course, the fraction of profiles for which a rule selects an IR (or semi-strong JR) committee is upper-bounded by the fraction of profiles that admit such a committee. For each model, the latter fraction is depicted in the graph as a solid black line for IR, and a dashed gray line for semi-strong JR. While no rule manages to find an IR committee every time one exists, the rules PAV, sequential PAV, sequential Phragm en, and Rule X select IR committees often. For the small fraction of CI profiles that admit an IR committee, all considered rules do a good job in finding one. Since seq-CC greedily optimizes the amount of voters that are represented at least once, it finds a committee providing semi-strong JR in almost all profiles that admit one. But as the rule does not aim at representing voters more than once, it almost never produces IR committees. In the profiles generated by the IC model, IR often coincides with semi-strong JR (for k 20) because almost all nonzero fi-values are 1. This is in line with the effect noticed by Bredereck et al. (2019), whose experiments showed that EJR and JR are very likely to coincide under IC. 6 Discussion Based on the observations that common axioms in approvalbased committee voting do not address the representation of individual voters, and that common voting rules sometimes unfairly distinguish between such voters, we formalize individual representation (IR) as a requirement for committees. We find that all common voting rules fail to provide IR committees, even when these exist. Nevertheless, for some restricted domains most prominently, voter interval preferences we provide polynomial-time algorithms for finding committees that provide a good approximation to IR. Our experimental results suggest that IR is achievable in many instances that follow somewhat realistic preferences. It remains an open problem to find intuitive voting rules that provide (approximate) IR whenever possible. Acknowledgments We would like to thank Nisarg Shah and the anonymous reviewers for their helpful comments. This work was supported by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1 and the Graduiertenkolleg Facets of Complexity (GRK 2434). 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(2): 461 485. Balinski, M.; and Young, H. P. 1982. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press. Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; and Niedermeier, R. 2019. An Experimental View on Committees Providing Justified Representation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 109 115. Brill, M.; G olz, P.; Peters, D.; Schmidt-Kraepelin, U.; and Wilker, K. 2020. Approval-Based Apportionment. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 1854 1861. AAAI Press. Brill, M.; Israel, J.; Micha, E.; and Peters, J. 2021. Individual Representation in Approval-Based Committee Voting. Technical report, ar Xiv:2112.05193 [cs.GT]. Elkind, E.; and Lackner, M. 2015. Structure in Dichotomous Preferences. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 2019 2025. AAAI Press. Elkind, E.; Lackner, M.; and Peters, D. 2017. Structured Preferences. In Endriss, U., ed., Trends in Computational Social Choice, chapter 10. Gangl, C.; Maly, J.; Lackner, M.; and Woltran, S. 2019. Aggregating Expert Opinions in Support of Medical Diagnostic Decision-Making. In Proceedings of the 11th International Workshop on Knowledge Representation for Health Care (KR4HC-2019). Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Jung, C.; Kannan, S.; and Lutz, N. 2020. A Center in your Neighborhood: Fairness in Facility Location. In Proceedings of the Symposium on Foundations of Responsible Computing (FORC), 5:1 5:15. Lackner, M.; Regner, P.; Krenn, B.; and Forster, S. S. 2021. abcvoting: A Python Library of Approval-Based Committee Voting Rules. https://github.com/martinlackner/ abcvoting. Accessed: 2022-03-24. Lackner, M.; and Skowron, P. 2021. Approval-Based Committee Voting: Axioms, Algorithms, and Applications. Technical report, ar Xiv:2007.01795 [cs.GT]. Peters, D.; Pierczy nski, G.; Shah, N.; and Skowron, P. 2021. Market-Based Explanations of Collective Decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5656 5663. AAAI Press. Peters, D.; Pierczy nski, G.; and Skowron, P. 2021. Proportional Participatory Budgeting with Additive Utilities. In Advances in Neural Information Processing Systems (Neur IPS), volume 34. Forthcoming. Pierczy nski, G.; and Skowron, P. 2021. Core-Stable Committees under Restricted Domains. Technical report, ar Xiv:2108.01987 [cs.GT]. Pukelsheim, F. 2014. Proportional Representation: Apportionment Methods and Their Applications. Springer. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017. Proportional Justified Representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 670 676. AAAI Press. Skowron, P.; Lackner, M.; Brill, M.; Peters, D.; and Elkind, E. 2017. Proportional Rankings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 409 415. IJCAI. Terzopoulou, Z.; Karpov, A.; and Obraztsova, S. 2021. Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5726 5733. AAAI Press. Yang, Y. 2019. On the Tree Representations of Dichotomous Preferences. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 644 650.