Dynamic Proportional Rankings

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 flow, 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 sufficiently 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. Specifically, 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 specifically, 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 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 define 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 fixed 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 SpeakUp (www.speakup.digital) allows audience members to add attributes (relating to, e.g., gender or education) to submitted questions. The moderator can then manually filter 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 briefly 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 finite set of candidates and N = {1, . . . , n} a finite set of voters. An (approval) profile A = (A1, . . . ,An) is a list that contains, for each i ∈ N, the approval set Ai ⊆ C of voter i. Given an approval profile 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 finite 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 first j elements in r.

An approval-based ranking rule maps an approval profile 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 (seqPAV) 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, define sc(S) = ∑i∈N ∑|Ai∩S| j=1 1j . 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 profile 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}.

Definition 1. An (approval-based) dynamic ranking rule R maps a profile 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 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.

1 All 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.

2 Another (equivalent) formulation of this method is in terms of a load balancing procedure [Janson, 2016; Brill et al., 2017].

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 seqPAV. For this straightforward dynamization of seqPAV, we modify the notion of marginal contribution to also take into account the satisfaction derived from previously implemented candidates:

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

Dynamic Phragm´en. Our first 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 first 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 first 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 seqPAV.) 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 seqPAV. In this myopic dynamization of seqPAV, 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 first run the first 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 first phase for one more iteration). Let the debts induced by candidate c be {dci }i∈N . Myopic Phragm´en ranks the candidates in C \ X according to increasing maxi∈Nc dci , breaking ties according to the second highest debt, and so on.

Intuitively, myopic seqPAV and myopic Phragm´en rank candidates according to their suitability of being the next implemented candidate. In contrast to dynamic seqPAV 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:

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 seqPAV and dynamic Phragm´en. In the first 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 seqPAV and myopic Phragm´en. In the first 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) satisfied 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 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 satisfies 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 profile with 7 voters:

All rules considered in this paper rank the approval winner a first 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 definition 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., avgV (S) = 1 |V | · ∑i∈V |Ai ∩S|.

Definition 4. For h ≥ 1 and α ∈ (0, 1], a dynamic ranking rule satisfies (h, α)-monotonicity if, for all profiles and all groups of voters V ⊆ N of size |V | ≥ α · |N|, the following holds for every iteration t:

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 first h positions in a ranking.

AV trivially satisfies (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 seqPAV and dynamic Phragm´en fail to satisfy (h, α)-monotonicity for all α < 6 2h+5 .

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

Furthermore, myopic seqPAV and myopic Phragm´en fail to satisfy (h, α)-monotonicity for all α < 1h .

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 ∈ ⋃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 satisfied by ranking rt for any fixed 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 first t - 1 rounds and, for a group V ⊆ N of voters, let λt (V ) = | ⋂i∈V Ai \ Xt | denote the cohesiveness of V with respect to the remaining candidates C \ Xt .

Definition 6 (Group representation). Let κ(α, λ) be a function from ((0, 1] ∩Q) ×N) to N. A dynamic ranking rule satisfies κ-group representation if the following holds for all profiles A, groups of voters V ⊆ N, rational numbers α ∈ (0, 1], and integers λ, t ≤ |C|:

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

4 A 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 Definition 6.

Our first 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 first phase of the method, and let dVavg = 1 |V | ∑i∈V di denote the average debt of voters in V .

Theorem 7. Dynamic Phragm´en satisfies κ-group representation for

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λ α2 + 1α ⌉ proved by Skowron et al. [2017].

The proof of Theorem 7 employs the notion of proportionality degree [Skowron, 2018]. In particular, we first 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 seqPAV 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 seqPAV satisfies κ-group representation for

AV does not perform any different in the dynamic ranking setting compared to the non-dynamic one. Thus, it satisfies the same bounds on group representation as those stated in Theorem 2 by Skowron et al. [2017]. Since myopic seqPAV and myopic Phragm´en both agree with AV in the case X = (), the same bounds hold for these two rules.

Proposition 9. Myopic seqPAV and myopic Phragm´en fail κgroup representation for κ(α, λ) ≤ ⌈ λ·α 2α-1 ⌉ - 1 and for all functions κ(α, λ) if α ≤ m+1 m+2 , where m = | ⋃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 sufficiently 5 many "clones," i.e., candidates c′ with identical supporter set Nc′ = Nc.

5 Given an upper bound T on the number of iterations, h+T -1 clones suffice (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 first t rounds. The following property is a natural adaption of the well-studied proportionality axiom proportional justified representation (PJR) [S´anchez-Fern´andez et al., 2017].

Definition 10. A dynamic ranking rule satisfies proportional justified selection (PJS) if the following holds for all t, ℓ ∈ N and for all groups V ⊆ N of voters: If |V | ≥ ℓt · |N| and | ⋂i∈V Ai| ≥ ℓ, then |Xt+1 ∩ ⋃i∈V Ai| ≥ ℓ.

A weaker version of this axiom is obtained by fixing ℓ = 1; in analogy to a well-known notion due to Aziz et al. [2017], we refer to the resulting property as justified 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 satisfies PJR [Brill et al., 2017].

Theorem 11. Under assumptions (A1) and (A2), myopic Phragm´en satisfies PJS.

Analogously, we can translate a representation guarantee for sequential PAV [S´anchez-Fern´andez et al., 2017] into a guarantee for myopic seqPAV.

Proposition 12. Under assumptions (A1) and (A2), myopic seqPAV satisfies JS for t ≤ 5.

Similar positive results are not possible for the other rules we consider.

Proposition 13. Dynamic seqPAV 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 profiles. Since we were mainly interested in the proportional representation of groups of voters with similar preferences, we generated profiles according to two probabilistic models that lead to polarized electorates with easily identifiable 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 profiles consist of 60 voters and 20 candidates, and the approval sets are generated according to two different models. In the blurred partiesmodel, we assign each voter and each candidate to one of two parties. The size of the voter group V associated with the first party varies over the experiments; the candidates are always divided equally. Each 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 first party grow, and divide the remaining voters equally among the two remaining parties. There are 7 candidates associated with the first 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 first row of Figure 1 show that for both models, AV is not proportional: avgV (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 first 5 candidates of the ranking over the first 11 iterations. Again, AV behaves poorly, as it gives satisfaction to V only once the larger groups have been satisfied. 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 flexibility for the decision maker and guarantees a proportional exposure of candidates in each ranking, the latter approach is computationally more efficient and yields stronger selection guarantees. Our experimental 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 flexibility 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 fixed (e.g., due to external constraints) and the remaining seats need to be filled 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.