# dynamic_proportional_rankings__9d3712ce.pdf

Dynamic Proportional Rankings

Jonas Israel and Markus Brill Research Group Efﬁcient Algorithms Technische Universit at Berlin 10587 Berlin, Germany {j.israel, brill}@tu-berlin.de

Proportional ranking rules aggregate approval-style preferences of agents into a collective ranking such that groups of agents with similar preferences are adequately represented. Motivated by the application of live Q&A platforms, where submitted questions need to be ranked based on the interests of the audience, we study a dynamic extension of the proportional rankings setting. In our setting, the goal is to maintain the proportionality of a ranking when alternatives (i.e., questions) not necessarily from the top of the ranking get selected sequentially. We propose generalizations of well-known aggregation rules to this setting and study their monotonicity and proportionality properties. We also evaluate the performance of these rules experimentally, using realistic probabilistic assumptions on the selection procedure.

1 Introduction From ask-me-anything sessions to panel discussions and town hall meetings, an increasing number of both virtual and in-person discussion formats are enhanced by digital tools that aim to make the event more interactive and responsive to the audience. Using live Q&A platforms such as slido (www.sli.do), Mentimeter (www.mentimeter.com) or Pigeonhole Live (www.pigeonholelive.com), participants in the audience can submit questions and upvote questions submitted by others; a moderator then selects the most popular questions for the discussion. By reducing barriers to participation (e.g., by allowing anonymous submissions), these tools aim to better represent the diversity in the audience. The moderator of the discussion is presented with an aggregated list, in which audience questions are ranked by popularity (i.e., number of upvotes). Based on this ranking, the moderator then picks the next question. When selecting a question, it is usually not required to follow the ranking strictly; rather, the choice is at the moderator s discretion, allowing him or her to take into account other factors such as discussion ﬂow, etc. That being said, it is generally expected that questions at the top of the ranking are more likely to be selected than questions further down in the list. After a question has been selected, it is removed from the ranking.

Ranking questions solely by popularity, though intuitively appealing, has a major downside: minority opinions might go completely unrepresented, even when the minority makes up a substantial proportion of the audience. To illustrate this phenomenon, which is often referred to as tyranny of the majority, consider a situation in which the audience is composed of two groups. One group makes up 60% of the entire audience and is only interested in questions related to topic A; the remaining 40% of participants are only interested in questions on a different topic B. Now, assuming that sufﬁciently many questions on topic A have been submitted, and that participants only upvote questions related to their own interest, questions on topic B are unlikely to appear anywhere near the top of the ranking, which is populated exclusively by questions on topic A. As a consequence, questions on topic B are very unlikely to be selected, despite the fact that these questions are supported by 40% of the audience. In this paper, we propose an approach to avoid the problem of underrepresenting minority opinions. Speciﬁcally, we model the scenario described above as a proportional representation problem and employ ranking algorithms based on (approval-based) proportional voting rules [Aziz et al., 2017; Brill et al., 2017]. The algorithms we consider aggregate the upvotes of the participants into a proportional ranking over questions, such that each minority (i.e., group of participants with similar preferences) is represented in the ranking to an extent that is proportional to the group s size. Whenever a question is selected by the moderator, our methods dynamically recompute the ranking, pushing questions supported by underrepresented groups closer to the top. At a technical level, our point of departure is the theory of proportional rankings [Skowron et al., 2017], which studies how a collective ranking over a set of alternatives can be constructed in such a way that majority and minority opinions are represented adequately. The question we are interested in is how proportional ranking algorithms can be adapted to the dynamic setting. More speciﬁcally, we ask: How can the proportional representativeness of a collective ranking be maintained in a dynamic setting, where alternatives get selected sequentially? To answer this question, we consider two well-known aggregation rules dating back to the late 19th century: sequential Phragm en [Phragm en, 1894] and sequential PAV [Thiele, 1895]. These two rules, together with a few variants of the

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

latter, performed best in the analysis conducted by Skowron et al. [2017]. For both rules, we propose two distinct generalizations to the sequential selection setting: a dynamic variant and a myopic variant (see Section 3 for details). As a benchmark, we also consider the rule that simply orders questions by the number of received upvotes. Our contribution. In this paper, (i) we formalize the setting of dynamic ranking rules and generalize the rules of Phragm en and Thiele to this setting (Section 3); (ii) we deﬁne a notion of satisfaction monotonicity and analyze to what extent the considered rules satisfy it (Section 4); (iii) we provide theoretical bounds regarding two different proportionality notions (Section 5); and (iv) we experimentally evaluate our dynamic ranking rules (Section 6). Omitted proofs and further details can be found in the full version of this paper [Israel and Brill, 2021]. Related work. Proportional representation is a fundamental desideratum in multiwinner elections [Monroe, 1995; Faliszewski et al., 2017; Lackner and Skowron, 2020]. For approval preferences in particular, a wide variety of proportionality axioms have been studied [Aziz et al., 2017; S anchez-Fern andez et al., 2017; Janson, 2018; Peters and Skowron, 2020]. Proportionality in the context of rankings has been considered in the aforementioned paper by Skowron et al. [2017] and (for linear preferences) by Schulze [2011]. Notions of fairness over multiple elections among a ﬁxed set of voters have received considerable attention in previous years. This line of work includes, e.g., the study of long-term fairness over different decisions [Freeman et al., 2017; Lackner, 2020], single decisions under changing preferences [Tennenholtz, 2004; Boutilier and Procaccia, 2012; Parkes and Procaccia, 2013; Oren and Lucier, 2014; Hemaspaandra et al., 2017], and storable votes [Casella, 2005; Casella, 2012]. In a practical attempt to avoid the underrepresentation of minorities, the live Q&A app Speak Up (www.speakup.digital) allows audience members to add attributes (relating to, e.g., gender or education) to submitted questions. The moderator can then manually ﬁlter questions with attributes that have been underrepresented in the discussion. Requiring organizers to identify relevant attributes poses the risk of overlooking important subgroups or introducing unwanted biases; it also presumes the willingness of participants to reveal potentially sensitive information. In contrast, the ranking algorithms considered in this paper do not require attributes in order to ensure the representation of minority opinions.

2 Preliminaries We brieﬂy introduce some basic concepts from the theory of approval-based preference aggregation; for details, see the survey by Lackner and Skowron [2020]. Let C be a ﬁnite set of candidates and N = {1, . . . , n} a ﬁnite set of voters. An (approval) proﬁle A = (A1, . . . , An) is a list that contains, for each i N, the approval set Ai C of voter i. Given an approval proﬁle A and a candidate c C, we let Nc = {i N : c Ai} denote the supporters of c. The approval score of c is given by |Nc|. In the motivating application, C consists of all submitted questions and Ai contains

the questions that have been upvoted by participant i. For a ﬁnite set S, we let L(S) denote the set of all linear orders, or rankings, over S. We often write a ranking r L(S) as a sequence r = (r1, r2, . . . , r|S|), and for j |S|, we let r j denote the set {r1, r2, ..., rj} of the ﬁrst j elements in r. An approval-based ranking rule maps an approval proﬁle A to a ranking r L(C) of all candidates. We will make use of the following three (non-dynamic) ranking rules.1

Approval Voting (AV) ranks the candidates according to their approval score. This rule is not proportional and we use it mainly as a benchmark. Sequential PAV (seq PAV) ranks candidates iteratively, in each iteration choosing an unranked candidate maximizing the marginal contribution in terms of weighted voter satisfaction. Formally, for a subset S C of candidates, deﬁne sc(S) = P i N P|Ai S| j=1 1 j . If k candidates have already been ranked, the marginal contribution of an unranked candidate c is given by mc(c) = sc(r k {c}) sc(r k). Sequential Phragm en can be described in terms of voters buying candidates.2 Every candidate costs 1 credit. All voters start without any credits but earn them continuously over time (at a constant and identical rate). As soon as a group of voters who all approve the same candidate c together own 1 credit, they immediately buy that candidate; at this point, their balance is reset to 0 and candidate c is added in the next position of the ranking. This is done until all candidates are ranked.

3 Dynamic Ranking Rules

In this section, we formally introduce the setting of dynamic ranking rules and we adapt existing (non-dynamic) ranking rules to this setting. The input of a dynamic ranking rule consists of two parts: an approval proﬁle and a (potentially empty) sequence of candidates that have already been implemented or executed ; the output is a ranking of all notyet-implemented candidates. To formalize this notion, we let X = (x1, x2, . . . , xj) denote the sequence of implemented candidates (where j {0, . . . , |C| 1}); whenever the order of elements in X does not matter, we slightly abuse notation and treat X as the set X = {x1, x2, . . . , xj}.

Deﬁnition 1. An (approval-based) dynamic ranking rule R maps a proﬁle A and a sequence X = (x1, x2, . . . , xj) of candidates to a ranking R(A, X) L(C \ X).

Applying a dynamic ranking rule to a sequential selection process (as outlined in the introduction) is now straightforward: At the beginning, when no candidate has yet been implemented, X = () and the ranking R(A, ()) ranks all candidates in C. Given this ranking, a decision maker (DM) selects an alternative x1 C to be implemented. The updated ranking of the remaining candidates is then given by R(A, (x1)), and the process is repeated. At iteration t N, when t 1 candidates have been implemented and

1All rules may encounter ties; we assume that a priority ordering over candidates is used as a tiebreaker. In the motivating example, the submission time of a question yields a natural priority ordering. 2Another (equivalent) formulation of this method is in terms of a load balancing procedure [Janson, 2016; Brill et al., 2017].

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

thus X = (x1, x2, . . . , xt 1), we let rt denote the ranking R(A, X) L(C\X) from which the DM can make a choice. We will sometimes make the assumption that the DM only ever implements alternatives that appear near the top of the ranking. In this depth-restricted setting, we are given a natural number h and we assume that xt rt h for all time steps t. This setting models situations in which the DM does not have the resources (or the ability) to consider the whole ranking. The straightforward ranking rule AV trivially translates to the dynamic setting: When a candidate is implemented, it is simply removed from the ranking; the order between the remaining candidates does not change. AV is used in all of the live Q&A platforms mentioned in Section 1. In the following, we propose dynamic variants of other ranking rules.

Dynamic seq PAV. For this straightforward dynamization of seq PAV, we modify the notion of marginal contribution to also take into account the satisfaction derived from previously implemented candidates:

mcdyn(c) = sc(X r k {c}) sc(X r k).

Dynamic seq PAV ranks candidates iteratively, adding in each round a candidate c maximizing mcdyn(c).

Dynamic Phragm en. Our ﬁrst dynamization of sequential Phragm en works in two phases. As before, voters buy candidates and every candidate has a cost of 1 credit. Voters do not start with 0 credits, however; they may have an initial debt due to previously implemented candidates they approve. The debts of voters are determined in the ﬁrst phase, which iterates through the sequence X (starting with x1) and, for each implemented candidate xj X, divides the cost of 1 among the voters in Nxj. More precisely, this assignment of debts is done in such a way that, in each iteration j, the maximum total debt across all voters in Nxj is as small as possible. (The assignment of debts, therefore, mimics the assignment of loads in the load-balancing formulation of sequential Phragm en.) We let di 0 denote the total debt of voter i N resulting from this ﬁrst phase. In the second phase, we run sequential Phragm en to obtain the desired ranking of candidates in C \ X. At the beginning of this phase, each voter i has a credit balance of di 0. As in sequential Phragm en, voters continuously earn credits, and voters starting with debts can only participate in the purchase of a candidate once they have a positive balance. Voters are not allowed to go into debt for buying candidates. These dynamic rules rank candidates in the same fashion as their non-dynamic counterparts, while taking the sequence X of previously implemented candidates into account. (Note that the implementation order matters for dynamic Phragm en, but not for dynamic seq PAV.) In particular, both dynamic rules coincide with their non-dynamic counterpart when X = (). Moreover, the ranking among the remaining candidates does not change whenever the top-ranked candidate is implemented: if rt = (r1, r2, r3, . . .) and xt = r1, then rt+1 = (r2, r3, . . .). We also consider two myopic dynamic ranking rules.

Myopic seq PAV. In this myopic dynamization of seq PAV, we compute the marginal contribution of each candidate c

C \ X only with respect to the set X of previously implemented candidates, i.e., mcmyopic(c) = sc(X {c}) sc(X). Then, we simply rank those candidates according to decreasing mcmyopic(c)-value.

Myopic Phragm en. In this myopic dynamization of sequential Phragm en, we ﬁrst run the ﬁrst phase of dynamic Phragm en in order to determine the debts {di}i N of voters. Then, for each candidate c C \ X, we compute the voter debts that would result from adding candidate c to X (and running the ﬁrst phase for one more iteration). Let the debts induced by candidate c be {dc i}i N. Myopic Phragm en ranks the candidates in C \ X according to increasing maxi Nc dc i, breaking ties according to the second highest debt, and so on. Intuitively, myopic seq PAV and myopic Phragm en rank candidates according to their suitability of being the next implemented candidate. In contrast to dynamic seq PAV and dynamic Phragm en, this way of comparing candidates does not lead to rankings that are representative by themselves. In particular, both myopic rules coincide with AV when X = (). We illustrate these rules with a simple example.

Example 2. Let C = {a, b, c, d, e} and assume alphabetic tiebreaking. Consider a set of 9 voters with the following approval sets:

5 {a, b}, 3 {c, d}, 1 {e}.

Let V denote the group consisting of the 5 {a, b}-voters and V the group consisting of the 3 {c, d}-voters. First, consider dynamic seq PAV and dynamic Phragm en. In the ﬁrst iteration, both rules output r1 = (a, c, b, d, e), effectively alternating between candidates supported by voter groups V and V . Let us assume that the DM implements candidate x1 = b, i.e., X = (b). Then, the two rules output r2 = (c, a, d, e). Next, consider myopic seq PAV and myopic Phragm en. In the ﬁrst iteration, both rules (and AV) rank the candidates according to their approval scores: r1 = (a, b, c, d, e). After the implementation of b, both rules output r2 = (c, d, a, e), which differs from the AV ranking r2 = (a, c, d, e).

In this example, all of our ranking rules demote candidate a in r2 because voter group V is already (partially) satisﬁed with X = (b). The myopic rules even rank both c and d higher than a in r2, since implementing either c or d would yield a more proportional sequence X than choosing a would. All presented ranking rules can be computed in polynomial time; see the full version of this paper for an asymptotic runtime analysis and pseudocode.

4 Monotonicity of Voter Satisfaction

We start our analysis of dynamic ranking rules by considering the satisfaction of voters during the sequential selection process. In doing so, we assume that voters derive satisfaction not only from implemented candidates they approve, but also possibly to a lesser extent from approved candidates appearing near the top of the ranking: high positions in the ranking come with increased attention (and, presumably, high selection probabilities in future iterations) for the respective

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

candidates. In particular, improved ranking positions of supported candidates can be viewed as a kind of compensation for (groups of) voters who are not (yet) well-represented by the implemented alternatives. To make this concrete, consider an iteration t, where the DM is confronted with ranking rt and chooses to implement candidate xt. Following the logic outlined above, it might be natural to expect that voters not approving xt (or, more precisely, the candidates approved by these voters) should get a boost in the ranking. At the very least, it seems reasonable to expect that the satisfaction of such voters with the new ranking rt+1 is at least as high as with the old ranking rt. AV trivially satisﬁes this property, which we informally refer to as satisfaction monotonicity. Somewhat surprisingly, however, the following simple example demonstrates that this intuitive monotonicity notion is not achievable for dynamic ranking rules that satisfy a minimal degree of representativeness.3

Example 3. Consider the following proﬁle with 7 voters:

1 {a}, 3 {b}, 3 {a, c}.

All rules considered in this paper rank the approval winner a ﬁrst in r1. If the DM chooses to implement candidate x1 = c, all of our rules except AV output r2 = (b, a) in the second iteration. Intuitively, the rules give more voting power to the 3 supporters of b (all of which are unrepresented by c) than to the 4 supporters of a (3 of which are already partially represented). Observe that the satisfaction of the voter approving a decreases when going from r1 to r2, despite the fact that this voter does not approve the candidate being implemented. The following deﬁnition is motivated by the question whether monotonicity failures can be prevented by moving to the depth-restricted setting and putting lower bounds on the size of voter groups for which monotonicity should hold. To measure satisfaction of a group V N of voters with a set S C of candidates, we use the average satisfaction of V with S, i.e., avg V (S) = 1 |V | P i V |Ai S|.

Deﬁnition 4. For h 1 and α (0, 1], a dynamic ranking rule satisﬁes (h, α)-monotonicity if, for all proﬁles and all groups of voters V N of size |V | α |N|, the following holds for every iteration t:

i V Ai, then avg V (rt+1 h ) avg V (rt h).

That is, (h, α)-monotonicity requires that satisfaction monotonicity holds for groups that make up at least an αfraction of the electorate, and when measuring average satisfaction with respect to the ﬁrst h positions in a ranking. AV trivially satisﬁes (h, α)-monotonicity for all h and all α. On the other hand, all other considered rules violate this notion unless we consider rather large groups of voters. Proposition 5. Consider the depth-restricted setting for some h 3. Then, dynamic seq PAV and dynamic Phragm en fail to satisfy (h, α)-monotonicity for all α < 6 2h+5.

3Example 3 can be turned into an impossibility result: Every dynamic ranking rule that (i) ranks the approval winner at the top in the ﬁrst iteration and (ii) gives priority to less satisﬁed voter groups fails satisfaction monotonicity.

Furthermore, myopic seq PAV and myopic Phragm en fail to satisfy (h, α)-monotonicity for all α < 1

h. The monotonicity requirement can be weakened further by only requiring satisfaction monotonicity in cases in which the implemented candidate is never co-approved with any candidate that is approved by a member of the group under consideration (i.e., there is no c S k V Ak with {c, xt} Ai for some i N). Both myopic rules satisfy this weak implementation monotonicity, whereas the two dynamic versions fail it. For a thorough discussion of this weaker version of monotonicity, we refer to the full version of this paper. Despite the negative results in this section, we rarely found monotonicity violations of any kind in our experiments (see Section 6).

5 Proportional Representation We now turn to analyzing the proportional representativeness that is provided by our dynamic ranking rules. The following two sections capture different perspectives on representation, focusing on the representativeness of the ranking rt at any given iteration t (Section 5.1) and on the representativeness of the set X of implemented candidates (Section 5.2).

5.1 Proportionality of Rankings In certain applications of dynamic ranking rules, such as the live Q&A platforms mentioned in the introduction, it is desirable for the ranking rt to provide a representative overview of the opinions of the voters at any given iteration t. In this section, we prove proportionality guarantees that are satisﬁed by ranking rt for any ﬁxed iteration t. Measures for the proportionality of a ranking have been proposed by Skowron et al. [2017]. In particular, κ-group representation measures, informally speaking, how far down in the ranking a group of voters needs to look in order to obtain a given amount of satisfaction. In order to adapt the notion of κ-group representation to the dynamic ranking setting, we need the following notation. For iteration t, let Xt = {x1, . . . , xt 1} denote the set of candidates implemented in the ﬁrst t 1 rounds and, for a group V N of voters, let λt(V ) = | T i V Ai \ Xt| denote the cohesiveness of V with respect to the remaining candidates C \ Xt. Deﬁnition 6 (Group representation). Let κ(α, λ) be a function from ((0, 1] Q) N) to N. A dynamic ranking rule satisﬁes κ-group representation if the following holds for all proﬁles A, groups of voters V N, rational numbers α (0, 1], and integers λ, t |C|: If |V | α n and λt(V ) λ, then avg V (rt κ(α,λ)) λ.

In words: If a group V of voters makes up an α-fraction of the electorate and has at least λ commonly approved candidates remaining at iteration t, then this group derives an average satisfaction of at least λ from the candidates ranked in the top κ(α, λ) positions of ranking rt.4

4A natural lower bound for κ(α, λ) is given by λ/α . Note that the κ functions used in this section not only depend on α and λ, but also on the set V and on the sequence X of previously implemented candidates. In an attempt to simplify notation, we decided to not make this dependencies explicit in Deﬁnition 6.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

Our ﬁrst result in this section is for dynamic Phragm en. We recall that di denotes the initial debt of voter i at the end of the ﬁrst phase of the method, and let d V avg = 1 |V | P i V di denote the average debt of voters in V . Theorem 7. Dynamic Phragm en satisﬁes κ-group representation for κ(α, λ) = 2(λ + m + 1) + s |V |

where m = | S i V Ai X| and s = P i V (di d V avg)2. Observe that this function is increasing both in the number m of already implemented candidates that are approved by some voter in V and in the variance s of debts of voters in V . For the special case X = (), Theorem 7 implies a group representation of 2λ+2

α for (non-dynamic) sequential Phragm en. For λ 2, this is an improvement over the κgroup representation bound of 5λ

α proved by Skowron et al. [2017]. The proof of Theorem 7 employs the notion of proportionality degree [Skowron, 2018]. In particular, we ﬁrst prove a bound on the proportionality degree of dynamic Phragm en, using a potential function approach that is similar to the one used by Skowron [2018] for the non-dynamic setting. Then, we establish a relationship between the proportionality degree and group representation, and use it to translate the bound on the former into a bound on the latter. For dynamic seq PAV we prove the following generalisation of Theorem 3 by Skowron et al. [2017]; the latter theorem corresponds to the special case X = (). Theorem 8. Dynamic seq PAV satisﬁes κ-group representation for κ(α, λ) = 2(λ + 1 + avg V (X))2

AV does not perform any different in the dynamic ranking setting compared to the non-dynamic one. Thus, it satisﬁes the same bounds on group representation as those stated in Theorem 2 by Skowron et al. [2017]. Since myopic seq PAV and myopic Phragm en both agree with AV in the case X = (), the same bounds hold for these two rules. Proposition 9. Myopic seq PAV and myopic Phragm en fail κgroup representation for κ(α, λ) l λ α 2α 1 m 1 and for all

functions κ(α, λ) if α m+1

m+2, where m = | S i V Ai X|.

5.2 Proportionality of Implemented Candidates In this section, we study worst-case bounds on the representativeness of the set X of implemented candidates. Clearly, no non-trivial bounds are obtainable without restricting the selection behavior of an adversarial DM. Therefore, we will make the following two assumptions throughout this section: (A1) The DM is depth-restricted and always implements a candidate from the top h positions of the ranking. (A2) Every candidate c C has sufﬁciently5 many clones, i.e., candidates c with identical supporter set Nc = Nc.

5Given an upper bound T on the number of iterations, h + T 1 clones sufﬁce (as at least h clones will always remain in the ranking).

Assumptions (A1) and (A2) together ensure that the DM can be forced to implement a candidate approved by a voter, by populating the top h positions exclusively with such candidates. Arguably the most natural way to ensure (A2) is to assume that we are in the party-approval setting [Brill et al., 2020], where candidates are interpreted as parties and can be selected arbitrarily often. In the motivating example of live Q&A platforms, party-approval preferences could result from assigning attributes to questions and eliciting participants approval preferences over attributes. Recall that Xt+1 denotes the set containing the implemented candidates from the ﬁrst t rounds. The following property is a natural adaption of the well-studied proportionality axiom proportional justiﬁed representation (PJR) [S anchez-Fern andez et al., 2017]. Deﬁnition 10. A dynamic ranking rule satisﬁes proportional justiﬁed selection (PJS) if the following holds for all t, ℓ N and for all groups V N of voters: If |V | ℓ

t |N| and | T i V Ai| ℓ, then |Xt+1 S i V Ai| ℓ. A weaker version of this axiom is obtained by ﬁxing ℓ= 1; in analogy to a well-known notion due to Aziz et al. [2017], we refer to the resulting property as justiﬁed selection (JS). We prove the following theorem by treating the set Xt+1 of implemented alternatives as a committee and using the fact that sequential Phragm en satisﬁes PJR [Brill et al., 2017]. Theorem 11. Under assumptions (A1) and (A2), myopic Phragm en satisﬁes PJS. Analogously, we can translate a representation guarantee for sequential PAV [S anchez-Fern andez et al., 2017] into a guarantee for myopic seq PAV. Proposition 12. Under assumptions (A1) and (A2), myopic seq PAV satisﬁes JS for t 5. Similar positive results are not possible for the other rules we consider. Proposition 13. Dynamic seq PAV and dynamic Phragm en fail to satisfy JS, even under assumptions (A1) and (A2) and for t = 2.

6 Experimental Evaluation In order to better understand the behavior of the dynamic ranking rules considered in this paper, we conducted computational experiments using randomly generated approval proﬁles. Since we were mainly interested in the proportional representation of groups of voters with similar preferences, we generated proﬁles according to two probabilistic models that lead to polarized electorates with easily identiﬁable groups. We measured (1) how the satisfaction of a voter group with the set of implemented candidates varies with the size of the group, and (2) how the satisfaction of a voter group with the current ranking varies over time. Setup. All of our proﬁles consist of 60 voters and 20 candidates, and the approval sets are generated according to two different models. In the blurred parties model, we assign each voter and each candidate to one of two parties. The size of the voter group V associated with the ﬁrst party varies over the experiments; the candidates are always divided equally. Each

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

voter approves a candidate from their own party with 95% probability and a candidate of the other party with 5% probability. The spatial model is an adaption of the 4-Gaussian model used by Elkind et al. [2017] for linear preferences. Voters and candidates correspond to points in the Euclidean plane and voters approve nearby candidates. There are three parties with equidistant center locations, and candidates as well as voters get sampled as points around the party centers according to a normal distribution. We let the size of the voter group V associated with the ﬁrst party grow, and divide the remaining voters equally among the two remaining parties. There are 7 candidates associated with the ﬁrst party. The selection behavior of the DM is modeled via Google clickthrough rates. In particular, the probability of selection decreases when going down the ranking. In Figure 1 we plot the averages of 100 generated elections. More details about the setup can be found in the full version of this paper.

Satisfaction with implemented candidates. We measure the average satisfaction of voter group V N with Xk+1, where k is the number of candidates associated with that group (i.e., k = 10 for the blurred parties model and k = 7 for the spatial model). We plot this value against the relative size α = |V |/|N| of the group V . The graphs in the ﬁrst row of Figure 1 show that for both models, AV is not proportional: avg V (Xk+1) starts out very low and only jumps up as soon as V becomes the biggest group (which happens at α = 1/2 and α = 1/3, respectively). In other words, AV underrepresents minorities and overrepresents majorities. The performance of the other four rules are indistinguishable, as all yield proportionally increasing satisfaction values.

Satisfaction with rankings. The graphs in the second row of Figure 1 depict the average satisfaction of a group V of size α = 1/4 with the ﬁrst 5 candidates of the ranking over the ﬁrst 11 iterations. Again, AV behaves poorly, as it gives satisfaction to V only once the larger groups have been satisﬁed. The satisfaction values under the two myopic rules jump heavily from one iteration to the next, as these rules tend to mainly represent one group of voters per iteration. On the other hand, the two dynamic rules keep the satisfaction of V relatively constant at around one fourth of the maximum possible satisfaction. These rules provide proportional representation in each single iteration, which is in line with the theoretical results in Section 5.1.

7 Conclusion

Motivated by the problem of how submitted questions in a live Q&A session can be ranked in a more representative way, we have introduced dynamic ranking rules. We proposed two paradigms of dynamizing existing ranking rules: under the dynamic paradigm, we target proportional representation of voter interests at each individual time step; under the myopic paradigm, we try to make the set of implemented candidates as representative as possible. While the former approach lends more ﬂexibility for the decision maker and guarantees a proportional exposure of candidates in each ranking, the latter approach is computationally more efﬁcient and yields stronger selection guarantees. Our experimental

0.0 0.2 0.4 0.6 0.8 1.0 α

0.0 0.2 0.4 0.6 0.8 1.0 α

1 2 3 4 5 6 7 8 9 10 11 t

avg V(rt 5)

1 2 3 4 5 6 7 8 9 10 11 t

avg V(rt 5)

Figure 1: Experimental results for the blurred parties model (left) and the spatial model (right). The graphs in the ﬁrst row show the average satisfaction of V with the ﬁrst k implemented candidates, for relative group size α [0, 1]. The graphs in the second row show the average satisfaction of V with rt 5, for 1 t 11.

results illustrate the difference between the two approaches, and verify that both approaches lead to proportional results. The application of live Q&A platforms gives rise to some interesting extensions of our model. In realistic scenarios, neither the electorate nor the set of candidates is static, as people enter or leave the audience and new questions come up continuously. Moreover, participants can change their approval preferences throughout the event. Our approach can take these dynamic aspects into account in a straightforward manner: After each implementation, we can apply our ranking rules to the current set of not-yet-implemented candidates and to the current approval preferences the only necessary information from previous iterations is the sequence of implemented candidates. The dynamic ranking rules proposed in this paper are applicable to a wide variety of sequential selection procedures in which proportional representation is desired and, at the same time, some ﬂexibility on the part of the decision maker is necessary (e.g., think of human-in-the-loop decision support systems for hiring or budgeting decisions). Other applications of dynamic ranking rules include committee election scenarios in which some part of the committee is ﬁxed (e.g., due to external constraints) and the remaining seats need to be ﬁlled in such a way that the committee as a whole is representative.

Acknowledgments We would like to thank the anonymous reviewers for their insightful comments. This work was partially supported by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1. We thank Paula Blechschmidt, Cristina Cornelio, Benny Kimelfeld, Phokion Kolaitis, Kunal Relia, and Julia Stoyanovich for helpful comments and discussions.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)

References [Aziz et al., 2017] Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justiﬁed representation in approval-based committee voting. Social Choice and Welfare, 48(2):461 485, 2017. [Boutilier and Procaccia, 2012] Craig Boutilier and Ariel Procaccia. A dynamic rationalization of distance rationalizability. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1278 1284. AAAI Press, 2012. [Brill et al., 2017] Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. Phragm en s voting methods and justiﬁed representation. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 406 413. AAAI Press, 2017. [Brill et al., 2020] Markus Brill, Paul G olz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker. Approvalbased apportionment. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1854 1861. AAAI Press, 2020. [Casella, 2005] Alessandra Casella. Storable votes. Games and Economic Behavior, 51(2):391 419, 2005. [Casella, 2012] Alessandra Casella. Storable Votes: Protecting the Minority Voice. Oxford University Press, 2012. [Elkind et al., 2017] Edith Elkind, Piotr Faliszewski, Jean Franc ois Laslier, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. What do multiwinner voting rules do? An experiment over the two-dimensional euclidean domain. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 494 501. AAAI Press, 2017. [Faliszewski et al., 2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice, chapter 2. 2017. [Freeman et al., 2017] Rupert Freeman, Seyed Majid Zahedi, and Vincent Conitzer. Fair social choice in dynamic settings. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 4580 4587. IJCAI, 2017. [Hemaspaandra et al., 2017] Edith Hemaspaandra, Lane A. Hemaspaandra, and J org Rothe. The complexity of controlling candidate-sequential elections. Theoretical Computer Science, 678:14 21, 2017. [Israel and Brill, 2021] Jonas Israel and Markus Brill. Dynamic proportional rankings. Technical report, ar Xiv:2105.08043 [cs.GT], 2021. [Janson, 2016] Svante Janson. Phragm en s and Thiele s election methods. Technical report, ar Xiv:1611.08826 [math.HO], 2016. [Janson, 2018] Svante Janson. Thresholds quantifying proportionality criteria for election methods. Technical report, ar Xiv:1810.06377 [cs.GT], 2018.

[Lackner and Skowron, 2020] Martin Lackner and Piotr Skowron. Approval-based committee voting: Axioms, algorithms, and applications. Technical report, ar Xiv:2007.01795 [cs.GT], 2020. [Lackner, 2020] Martin Lackner. Perpetual voting: Fairness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 2103 2110. AAAI Press, 2020. [Monroe, 1995] Burt L. Monroe. Fully proportional representation. The American Political Science Review, 89(4):925 940, 1995. [Oren and Lucier, 2014] Joel Oren and Brendan Lucier. Online (budgeted) social choice. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1456 1462. AAAI Press, 2014. [Parkes and Procaccia, 2013] David Parkes and Ariel Procaccia. Dynamic social choice with evolving preferences. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 767 773. AAAI Press, 2013. [Peters and Skowron, 2020] Dominik Peters and Piotr Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC), pages 793 794. ACM Press, 2020. [Phragm en, 1894] L. Edvard Phragm en. Sur une m ethode nouvelle pour r ealiser, dans les elections, la repr esentation proportionnelle des partis. Ofversigt af Kongliga Vetenskaps-Akademiens F orhandlingar, 51(3):133 137, 1894. [S anchez-Fern andez et al., 2017] Luis S anchez-Fern andez, Edith Elkind, Martin Lackner, Norberto Fern andez Garc ıa, Jes us A. Fisteus, Pablo Basanta Val, and Piotr Skowron. Proportional justiﬁed representation. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 670 676. AAAI Press, 2017. [Schulze, 2011] Markus Schulze. Free riding and vote management under proportional representation by the single transferable vote. http://m-schulze.9mail.de/schulze2.pdf, 2011. Accessed: 2021-01-21. [Skowron et al., 2017] Piotr Skowron, Martin Lackner, Markus Brill, Dominik Peters, and Edith Elkind. Proportional rankings. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 409 415. IJCAI, 2017. [Skowron, 2018] Piotr Skowron. Proportionality degree of multiwinner rules. Technical report, ar Xiv:1810.08799 [cs.GT], 2018. [Tennenholtz, 2004] Moshe Tennenholtz. Transitive voting. In Proceedings of the 5th ACM Conference on Electronic Commerce (ACM-EC), pages 230 231. ACM Press, 2004. [Thiele, 1895] Thorvald N. Thiele. Om ﬂerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger, pages 415 441, 1895.

Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI-21)