# proportional_decisions_in_perpetual_voting__ce25592d.pdf

Proportional Decisions in Perpetual Voting

Martin Lackner1 and Jan Maly2

1 TU Wien, Vienna, Austria 2 ILLC, University of Amsterdam, Netherlands lackner@dbai.tuwien.ac.at, j.f.maly@uva.nl

Perpetual voting is a framework for long-term collective decision making. In this framework, we consider a sequence of subsequent approval-based elections and try to achieve a fair overall outcome. To achieve fairness over time, perpetual voting rules take the history of previous decisions into account and identify voters that were dissatisfied with previous decisions. In this paper, we look at perpetual voting rules from an axiomatic perspective. First, we define two classes of perpetual voting rules that are particularly easy to explain to voters and we explore the bounds imposed by this simplicity. Second, we study proportionality in the perpetual setting and identify two rules with strong proportionality guarantees. However, both rules yield different guarantees and we prove them to be incompatible with each other.

Introduction In many voting scenarios, a group of voters, for example a committee or working group, has to make several decisions at different points in time. If standard voting rules are used (such as approval, Borda, plurality, etc.), it may happen that a majority dictates all decisions while some voters disagree with every outcome. This can lead to unrepresentative results and, eventually, to dissatisfied voters dropping out of the decision process. Such situations are particularly undesirable if participation in the process is valued highly and if no extreme views are present in the electorate. If a group of colleagues has to regularly agree on a meeting time, it is not acceptable if always the same colleague has to compromise. Similarly, if a committee of volunteers in a sports club is tasked with the organization of a party, no committee member s opinion should be completely ignored. Perpetual voting, recently introduced by Lackner (2020), is a formalism for tackling these types of long-term decision making processes. From a formal point of view, a perpetual voting instance is a sequence of approval-based elections where each decision has to be made online , i.e., in the knowledge of past decisions but without information about future elections. Perpetual voting rules are deterministic, resolute functions that take perpetual voting instances as input and that output a winning alternative for the current decision to be made. Lackner (2020) introduced several

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

perpetual voting rules that aim to achieve a fairer outcome over time as well as basic axioms that formalize desirable properties in the perpetual setting. However, as of now, it was unclear which perpetual rules provide proportional outcomes, i.e., outcomes that reflect the opinions of both large and small groups in a proportional fashion. Our main goal in this paper is to close this gap and study proportionality in the setting of perpetual voting. This is more difficult than, e.g., proportionality in multi-winner voting (Aziz et al. 2017; S anchez-Fern andez et al. 2017) due to the sequential and dynamic nature of perpetual voting. The main technical difficulty is that voters preferences (and the set of alternatives) are different each round. Additionally, the online character of perpetual voting prohibits standard methods of (offline) optimization. Despite these obstacles, proportionality is clearly desirable in perpetual voting as it strikes a balance between majoritarian decisions (ignoring minorities) and consensus-based decision (which may result in disproportional power for individuals). Our starting point, however, is a much more modest desideratum of voting rules: ideally, they should be simple to explain and understand. Thus, we consider two classes of particularly simple perpetual voting rules: win-based and loss-based weighted approval methods (WAMs). Both classes have the advantage of a rather simple definition based on voter weights, which are modified depending on whether a decision was in favour of the voter. Importantly, we require that the magnitude of a change in voter weights is not depending on other voters, i.e., it is always apparent to voters how an outcome influences their weight. We start our analysis by considering two axioms from Lackner (2020): (i) bounded dry spells guarantee each voter a satisfying outcome on a regular basis, and (ii) simple proportionality is a weak proportionality requirement. Our results show that no voting rule in these two classes can satisfy bounded dry spells. In addition, we characterize all voting rules that satisfy simple proportionality. This sets the stage for our analysis of proportionality. We introduce two proportionality axioms in the perpetual setting: lower and upper quota for closed groups. In contrast to simple proportionality, these axioms are applicable in dynamic settings with changing preferences. Our first result is a negative one: while some win-based WAMs satisfy simple proportionality, none of them satisfies one of the stronger

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

properties. Thus, we turn to two more complex perpetual voting rules: Perpetual Consensus (introduced by Lackner 2020) and Perpetual Phragm en (new to the perpetual setting, based on Phragm en 1895). We prove that Perpetual Consensus satisfies the upper quota axiom and Perpetual Phragm en the lower quota axiom. In addition, both rules have bounded dry spells. Finally, we show that Perpetual Phragm en satisfies perpetual priceability, an axiom based on work in the multi-winner setting by Peters and Skowron (2020). We prove that this axiom implies the lower quota axiom, but it is incompatible with the upper quota axiom. Thus, we see that Perpetual Phragm en and Perpetual Consensus adhere to two fundamentally incompatible proportionality requirements.

Related work In the last few years, the study of longterm (or repeated) collective decision making has received growing attention. This includes the work of Freeman, Zahedi, and Conitzer (2017), who proposed a sequential mechanism for the aggregation of utility functions over time with the goal to maximize long-term Nash welfare. Variants of this formalism have been studied by Conitzer, Freeman, and Shah (2017) and Freeman et al. (2018). Additionally, Bulteau et al. (2021) studied an offline variant of perpetual voting, focussing on proportionality guarantees achievable in this setting. Notably, this work contains an experimental evaluation of perpetual voting with human participants. Lackner, Maly, and Rey (2021) studied a perpetual version of participatory budgeting. Other approaches that consider either temporal aspects of voting or sequences of decisions include storable votes (Casella 2005, 2012), sequential voting rules (Lang and Xia 2009), online approval elections (Do et al. 2022), Frege s method (Frege 2000; Harrenstein, Lackner, and Lackner 2020), and dynamic fair division (Kash, Procaccia, and Shah 2014; Benade et al. 2018; Zeng and Psomas 2020).

The Perpetual Voting Framework We will now introduce the perpetual voting formalism, as defined by Lackner (2020), alongside necessary basic definitions. Let N t1, . . . , nu be a set of voters (agents). Given a set of alternatives C, we assume that each voter v P N approves some non-empty subset of C. An approval profile A p Ap1q, . . . , Apnqq for C is an n-tuple of subsets of C, i.e., Apvq Ď C for v P N. We call the triple p N, A, Cq a decision instance. A k-decision sequence D p N, A, Cq is a triple consisting of a set of voters N, a k-tuple of sets of alternatives C p C1, . . . , Ckq and a k-tuple of approval profiles A p A1, A2, . . . , Akq such that Ai is an approval profile for Ci. Thus, for 1 ď i ď k, the triple p N, Ai, Ciq is a decision instance and can be seen as an individual decision to be made; we refer to it as the decision instance in round i. We write w P C as a short hand for w P Śk i 1 Ci, i.e., w pw1, . . . , wkq satisfies wi P Ci for i P t1, . . . , ku; we refer to w as a k-outcome. This tuple represents the chosen alternatives in rounds 1 to k. If we combine a k-decision sequence p N, A, Cq and a k-outcome w P C, we speak of a k-decision history H p N, A, C, wq, which can be seen as the history of past decision instances alongside the made

choices. We thus know, for any i ď k, that in case of decision instance p N, Ai, Ciq alternative wi was chosen. An important statistic of k-decision histories is the satisfaction of each voter: Given a decision history H p N, A, C, wq, the satisfaction of voter v P N with w in round k is satkpv, wq |t1 ď i ď k : wi P Aipvqu|. Thus, the satisfaction of a voter is the number of past decisions that have satisfied this voter. Note that although satisfaction clearly depends on H, we do not explicitly mention that in the notation as H will always be clear from the context. The same holds for other definitions throughout the paper.

Example 1. As an example, consider the following 4decision sequence with four voters N t1, . . . , 4u and four alternatives a, b, c, d (the same in all rounds):

voters 1 2 3 4

A1 tau tau tbu tc, du A2 tau ta, b, cu tdu tcu A3 tau tb, cu ta, cu tbu A4 tau tbu tcu tdu

If we assume that we always select the alternative with the highest number of approvals and use alphabetic tiebreaking, then a wins in all rounds. The corresponding 4outcome is w pa, a, a, aq. This means voter 1 is satisfied with every decision (sat4p1, wq 4) while 4 does not agree with any decision (sat4p4, wq 0).

Assume that a group of voters N wants to take a decision and looks back at k decisions already taken. That is, we are presented with a k-decision history H p N, A, C, wq and a decision instance p N, Ak 1, Ck 1q. The question now is which alternative in Ck 1 should be chosen, subject to the preferences in Ak 1 and under consideration of H. An (approval-based) perpetual voting rule R is a function that maps a pair of a decision instance p N, Ak 1, Ck 1q and a k-decision history H to an alternative in Ck 1. Given a k-decision sequence D p N, A, Cq, we write Rp Dq to denote the k-outcome w P C which is selected by applying the perpetual voting rule R in every round, that is, Rp Dq w is inductively defined by wi Rp N, p A1, . . . , Aiq, p C1, . . . , Ciq, pw1, . . . , wi 1qq for i ď k. We expect perpetual voting rules to be resolute, i.e., return exactly one winning alternative, therefore we require a tie-breaking order to resolve ties. Throughout the paper, we assume that there exists some arbitrary and fixed order for each set of alternatives that settles ties.

Perpetual Voting Rules Let us now introduce the perpetual voting rules that we will study in this paper. All of these rules except Perpetual Phragm en have been introduced by Lackner (2020). First, we consider a natural approach to define perpetual voting rules via weights: voters that have been previously neglected receive a higher weight, voters that are satisfied with previous outcomes receive a lower weight. In each round, the alternative that receives the highest sum of weighted approvals is selected. This idea is captured

in a broad sense by the class of perpetual weighted approval methods1 (WAMs), which contains most rules proposed in (Lackner 2020). These approval-based perpetual voting rules are defined as follows: Each voter has an assigned positive weight, which may change each round; a larger weight corresponds to being assigned a higher importance. Let αkpvq denote voter v s weight in round k. Weights are initialized with α1pvq 1 for all v P N. The weights of voters in the following rounds are a consequence of the previous history. Formally, there exists a weight function h such that for all v P N, αk 1pvq hpv, Hq. Given a k-decision history H p N, A, C, wq and a decision instance p N, Ak 1, Ck 1q, the rule selects an alternative wk 1 P Ck 1 with maximum weighted approval score. That is, the score of an alternative c is defined as

v PN with c PAk 1pvq αk 1pvq.

Observe that WAMs can be computed in polynomial time as long as the function h is computable in polynomial time. This holds for all WAMs considered in this paper. In this paper, we consider two subclasses subclasses of WAMs: win-based and loss-based WAMs. These have the benefit of a particularly straight-forward way of calculating weights and thus can be easily explained to voters. For both types, a voter s weight depends only on the voter s weight in the previous round and whether the voter was satisfied with the previous decision. For win-based (loss-based) WAMs, the weights only change for voters who approved (did not approve) a winning alternative. Win-based WAMs can be seen as the perpetual equivalent of the well-known class of the (sequential) Thiele methods used in multi-winner voting (Lackner and Skowron 2023). Similarly, loss-based WAMs are related to dissatisfaction counting rules (Lackner and Skowron 2018). Definition 1. We call a WAM loss-based if the weights of voters v P N can be computed as follows:

αk 1pvq "αkpvq if wk P Akpvq, fpαkpvqq if wk R Akpvq,

where f : R Ñ R is a function satisfying fpxq ě x. We call a WAM win-based if the weights of voters v P N can be computed as follows:

αk 1pvq "gpαkpvqq if wk P Akpvq, αkpvq if wk R Akpvq,

where g: R Ñ R is a function satisfying 0 ă gpxq ď x. We require gpxq ą 0 for win-based WAMs as otherwise the voter s weight would remain at 0 since it never increases (gpxq ď x and fpxq x). Observe that, while the function f resp. g can be arbitrarily complex, by definition, the weight of a voter in a win-based WAM only depends on how many rounds she has already won (i.e., how many rounds she was satisfied with). Similarly, the weight

1We note that WAMs in this paper are defined slightly more general than in (Lackner 2020).

of a voter in a loss-based WAM only depends on how many rounds she already lost. In particular, this means that a winor loss-based WAM is fully defined by an infinite sequence p Gp0q, Gp1q, Gp2q, . . . q such that Gpiq is the weight of a voter that has won resp. lost i rounds. In this sense, we believe that winand loss-based WAMs are simple to explain and understand. The simplest example of a WAM is approval voting (AV), which completely ignores the history of past decisions.

AV. AV is the win-based WAM with gpxq x. Observe that AV is also a loss-based WAM with fpxq x and thus the unique rule that is win-based and loss-based. The next method is inspired by Proportional Approval Voting and is thus based on the harmonic series.

Perpetual PAV. Perpetual PAV is a WAM defined by the following weight function:

αk 1pvq 1 satkpv, wq 1

# αkpvq αkpvq 1 if wk P Akpvq, αkpvq if wk R Akpvq.

The last equality shows that Perpetual PAV is indeed a winbased WAM. An example of a loss-based WAM is Perpetual Unit Cost (Lackner 2020), where the weight of dissatisfied voters is increased by 1.

Perpetual Unit-Cost. Perpetual Unit-Cost is a loss-based WAM defined by fpxq x 1. Next, we define two more complicated rules, Perpetual Consensus, introduced by Lackner (2020), and Perpetual Phragm en, a new rule based on Phragm en s sequential rule. As we will see later in Section , both of them can be viewed as proportional but each in a different sense.

Perpetual Consensus. Let wkpvq be the weight of voter v P N in round k. Each voter starts with a weight of w0pvq 1{n. This WAM is based on the idea that the weight of voters that are satisfied with a decision is reduced in total by 1 and this number is divided equally among them. Consequently, voters can have negative weights2; voters with negative weights are not taken into account when determining the winning alternative. After each decision, the weight of all voters is increased by 1{n. Formally, N k pcq tv P N : c P Akpvq and αkpvq ą 0u, for all v P N, α1pvq 1{n and

n 1 |N k pwkq| if wk P Akpvq,

n if wk R Akpvq,

Thus, the score of an alternative c is defined as

v PNk 1pcq maxp0, αk 1pvqq.

Finally, Perpetual Phragm en is a new perpetual rule and is not a WAM. It is inspired by Phragm en s Sequential Rule (Phragm en 1894; Brill et al. 2017).

2Although negative weights are not allowed in the definition of

Perpetual Phragm en. This rule can be described as a load distribution procedure. We assume that winning a round incurs a load of 1, which is distributed to a set of voters that jointly approve the winning alternative. Let ℓkpvq denote the load assigned to voter v in rounds 1 to k (ℓ1pvq 0). In round k 1, for each set of voters N 1 that jointly approves at least one alternative (Ş v PN 1 Ak 1pvq H), we calculate

ℓk 1p N 1q 1 ř v PN 1 ℓkpvq |N 1| ;

this is the load that each of voter in N 1 would bear if they were selected to choose the winning alternative. We then select a group N 1 for which ℓk 1p N 1q is minimal. If more than one set of voters exists with minimal ℓk 1p N 1q, then one of these sets is chosen according to an arbitrary tie-breaking order. Finally, a winning alternative is chosen from Ş v PN 1 Ak 1pvq, which is non-empty by the definition of N 1, according to another arbitrary tie-breaking order. Let N 1 be the set of voters selected to choose an alternative. Then the loads in the next round are defined as

ℓk 1pvq "ℓkpvq if v R N 1, ℓk 1p N 1q if v P N 1.

Conceptually, Perpetual Consensus and Perpetual Phragm en have an important similarity: both are based on distributing a cost (load) of 1 to all voters approving the winning alternative. They differ, however, in the way they distribute this cost. Perpetual Consensus strictly enforces an equal distribution; Perpetual Phragm en assigns a lower load to voters that already have a high load. Example 2. Consider the instance from Example 1. In the first round we can distribute the load of a between both of its supporters 1 and 2. This leads to a load distribution where 1 and 2 have load 0.5 while 3 and 4 have load 0. This is clearly better than placing all the load of an alternative on one voter. Hence a wins in round 1. In round 2, both a and c have two supporters. However, due to the higher previous load of the supporters of a, selecting c leads to a more favourable load distribution, where the load of 1 and 3 remains the same at 0.5 and 0 respectively. Moreover, the load of 2 and 4 is set to 1 0.5

2 0.75. In round 3, all alternatives have two supporters, but the supporters of a have the lowest previous load, hence it is selected. This leads to a load distribution where all voters have the same load of 0.75. Finally, in round 4 all voters have the same load and all alternatives are supported by exactly one voter. Hence all alternatives would lead to a equally good load distribution. We select some alternative according to a fixed tie-breaking order. Proposition 1. Perpetual Phragm en is not equivalent to any WAM and is computable in polynomial time. We note that the Method of Equal Shares (Peters and Skowron 2020), a multi-winner voting rule closely related to

WAMs, the definition can easily be adapted to that framework by defining a voting rule that assigns the same weights as Perpetual Consensus if αkpvq is positive and 0 otherwise. Moreover, observe that compared to Lackner (2020), we divided all weights by n to highlight the similarity to Perpetual Phragm en.

Phragm en s Sequential Rule with even stronger proportionality guarantees, has no obvious counter-part in perpetual voting. This is because it requires a priori knowledge about the number of rounds and it is not committee monotone.

Winand Loss-Based Voting Rules First, we want to investigate under which conditions winand loss-based perpetual voting rules can be proportional. To do so, we first consider simple proportionality, a basic axiom proportionality axiom introduced by Lackner (2020). Simple proportionality considers groups of voters that have identical preferences and guarantees them a proportional representation, at least in very simple perpetual voting instances. Definition 2 (Simple proportionality). We say that a kdecision sequence D p N, A, Cq is simple if A1 Ak, C1 Ck, and |A1pvq| 1 for all v P N. Given a simple decision sequence D and a voter v P N, let #v denote the number of voters with identical preferences, i.e., #v |tv1 P N : Apv1q Apvqu|. A perpetual voting rule R satisfies simple proportionality if for any simple n-decision sequence D with |N| n it holds that satnpv, Rp Dqq #v for every voter v P N. Although this is a quite weak proportionality requirement, similar to weak proportionality in the apportionment setting (Balinski and Young 1982), it is sufficiently strong to reveal that some perpetual voting rules are not proportional. For example, AV fails simple proportionality. On the other hand, Perpetual PAV satisfies simple proportionality (Lackner 2020), witnessing that win-based WAMs can satisfy simple proportionality. Surprisingly, loss-based WAMs are never proportional: Theorem 2. There is no loss-based WAM that satisfies simple proportionality.

Proof. Assume for the sake of a contradiction that R is a loss-based WAM that satisfies simple proportionality. Now, consider for an arbitrary k ě 1 a simple k 1-decision sequence p N, A, Cq such that N tv1, . . . , vk 1u, C1 Ck 1 ta, bu and v1 always votes tau and vi votes tbu for all i P t2, . . . , k 1u. Because R satisfies simple proportionality there are two possible cases in round k 1: either a has won one or zero times. In the first case, the score of a in round k 1 is f k 1p1q and the score of b is k fp1q and b must win round k 1. Hence,

f k 1p1q ď k fp1q (1)

must hold. In the second case,

f i 1p1q ď k for all i ď k. (2)

Now consider a second simple k 1-decision sequence p N, A1, Cq where A1 is defined by v1, v2 always voting tau and v3, . . . , vk 1 always voting tbu. Then, there must be a round i where a wins the second time. In this round, the score of b is pk 1qfp1q and the score of a is at most 2 f k 1p1q. As we know that a wins in round i we have

1{2pk 1qfp1q ď f k 1p1q. (3)

In summary, we know that for all k ě 1 that either 1{2 kfp1q ď f kp1q ď pk 1qfp1q or 1{2 kfp1q ď f kp1q ď k 1 holds. Consider a simple 2k-decision sequence p N 2, A2, C2q such that N tv1, . . . , vk, w1, . . . , wku, C1 C|N| ta, b1, . . . , bku, vi always votes tau and wi votes tbiu for all i P t1, . . . , ku. Furthermore, assume w.l.o.g. that a tie-breaking is applied that always picks bi over bj if i ă j. We claim that bk does not win any of the 2k first rounds. By assumption, for all i ď k 1, bi must win before bk. Then, the score of a is k f k 1p1q which is larger than 1{2 kpk 1qfp1q by (3) while the score of bk is at most f 2k 1p1q. In the first case we have f 2k 1p1q ď 2kfp1q by (1). Clearly, for any k large enough, 2kfp1q ă 1{2pk2 kqfp1q. Hence, R does not satisfy simple proportionality. In the second case, we have f 2k 1p1q ď 2k by (2). Furthermore, we know fp1q ě 1. Now, for any k large enough, 2k ă 1{2pk2 kq ď 1{2pk2 kqfp1q. Hence, R does not satisfy simple proportionality.

For win-based WAMs, we can precisely characterize which rules satisfy simple proportionality.

Theorem 3. Let R be a win-based WAM. Furthermore, define the sequence G as Gp0q 1, Gp1q gp1q, Gp2q gpgp1qq, etc. Then, R satisfies simple proportionality if and only if x Gpxq ă py 1q Gpyq for all integers x, y ě 0.

Examples of such rules include Perpetual PAV, i.e., G p1, 1{2, 1{3, . . . q, but also, for example, G p1, 1{c 1, 1{2c 1, . . . q for all c ě 1. We see that simple proportionality is satisfied by many win-based WAMs. As we will see in Section , this changes drastically with stronger proportionality axioms. Moreover, as it turns out, all winand loss-based WAMs fail another central desideratum of perpetual voting: bounded dry spells. The bounded dry spells property guarantees that every voter is satisfied with at least one decision in a bounded number of rounds. This property is very important for creating an incentive to participate in the decision making process.

Definition 3 (Dry spells). Given a k-decision history H p N, A, C, wq, we say that a voter v P N has a dry spell of length ℓif there exists t ď k ℓsuch that sattpv, wq satt ℓpv, wq, i.e., voter v is not satisfied with any outcome in rounds t 1, . . . , t ℓ. Let d be a function from N to N. A perpetual voting rule R has a dry spell guarantee of d if for any decision sequence D p N, A, Cq and w Rp Dq, no voter has a dry spell of length dp|N|q. A perpetual voting rule R has bounded dry spells if R has a dry spell guarantee of some d.

As winand loss-based WAMs only consider the number of wins respectively losses but not the round in which they occur, a long winning streak can be followed by an arbitrarily long dry spell.

Proposition 4. Every win-based and loss-based WAM has unbounded dry spells.

In contrast, if we move beyond winand loss-based WAMs, we find perpetual rules that satisfy both simple proportionality and bounded dry spells. Perpetual Consensus

has a dry spell guarantee of at most 1{4 pn2 3nq (Lackner 2020). Here, we show a tight bound for Perpetual Phragm en:

Proposition 5. Perpetual Phragm en satisfies simple proportionality, and has a dry spell guarantee of 2n 1 (this bound is tight).

Proportionality in Perpetual Voting Simple proportionality, as the name implies, is a very rudimentary notion of proportionality. In particular, it requires identical preferences in all rounds. We will now significantly weaken this assumption and introduce proportionality axioms that are applicable in more dynamic settings. Let us first define closed groups, which are groups with identical preferences that have no overlapping interests with other voters.

Definition 4. Given a k-decision sequence D p N, A, Cq, we say that a group N 1 Ď N is closed if for every v P N 1, w P N, and i P t1, . . . , ku it holds that (i) Aipvq Aipwq if w P N 1 and (ii) Aipvq X Aipwq H otherwise.

The following axioms establish the minimum and maximum influence of a closed group on a decision sequence.

Definition 5 (Perpetual lower/upper quota for closed groups). A perpetual voting rule R satisfies perpetual lower quota for closed groups (LQC) if, for every k-decision sequence D, it holds for every voter v P N who is part of a closed group N 1 that satkpv, Rp Dqq ě Y k |N 1|

n ] . A perpetual voting rule R satisfies perpetual upper quota for closed groups (UQC) if, for every k-decision sequence D, it holds for every voter v P N who is part of a closed group N 1 that satkpv, Rp Dqq ď Q k |N 1|

LQC and UQC identify groups that deserve representation (due to their size and uniformity). These groups should have a roughly proportional influence on the outcome. LQC sets a lower bar for their influence, UQC an upper bar.3

Remark 1. When applying the definitions of LQC and UQC to simple k-decision sequences with k n (Definition 2), we observe that Q k |N 1|

n U Y k |N 1|

n ] |N 1|. Thus, both LQC and UQC imply simple proportionality.

As it turns out, these stronger notions of proportionality cannot be satisfied with a win-based WAM.

Theorem 6. Every win-based WAM fails both LQC and UQC.

Proof. Let us first show that every win-based WAM fails UQC. Consider an arbitrary win-based WAM defined by the function g. Now, we construct a simple 2-decision sequence with 2N voters. In both rounds, for i P t1, . . . , Nu voter i approves ci, and the voters N 1, . . . , 2N approve alternative c N 1. In round 1, alternative c N 1 wins with

3We remark that LQC is strictly weaker than perpetual lower quota as introduced by Lackner (2020) (which is too strong to be satisfiable in general). The same holds for UQC and perpetual upper quota (defined analogously).

sc1pc N 1q N. In the second round, the winning alternative c must be chosen so that sat2pv, pc N 1, cqq ď Q 2 #v

for all v P N. If v P t N 1, . . . , 2Nu it holds that Q k #v

n U 1, hence c N 1 must not win a second time. Consequently N gp1q sc2pc N 1q ă sc2pc1q 1. As N can be chosen arbitrarily large, we conclude that gp1q 0. This, however, contradicts the definition of win-based WAMs, where gpxq ą 0 is required.4 Now, we show that every win-based WAM fails LQC. Fix a function g defining a win-based WAM. By Theorem 3, we know that gp1q ă gp0q 1. Let k Q 1 gp1q U . We construct a k 1-decision sequence as follows. There are k 1 voters. In each round, the set of alternatives is C tc1, . . . , ck 1u. The approval profiles are defined as follows:

voters 1 2 . . . k k 1

A1 Ak tc1u tc2u . . . tcku tck 1u Ak 1 tc1u tc1u . . . tc1u tck 1u

We assume that ties are broken in favour of alternatives with smaller index. Thus, in the first round alternative c1 is winning, in the second round c2 is winning, etc., until ck wins in round k. In round k 1, alternative c1 is approved by voters 1 to k and thus sck 1pc1q k gp1q. Further, sck 1pck 1q gp0q 1. Since sck 1pc1q k gp1q Q 1 gp1q U gp1q ą 1, alternative c1 is winning. This violates LQC since voter k 1 is a closed group with satisfaction 0 but deserving a satisfaction of at least Q pk 1q 1 k 1 U 1.

Next, we will show that Perpetual Consensus and Perpetual Phragm en are proportional in a different sense, as the former satisfies UQC while the later satisfies LQC. We begin with Perpetual Consensus. Theorem 7. Perpetual Consensus satisfies UQC but fails LQC. Before looking at Perpetual Phragm en, we will strengthen LQC by introducing the concept of perpetual priceability. This is motivated by the priceability property from the multiwinner voting setting which was introduced by Peters and Skowron (2020).5 We first define price systems. Definition 6. Given a k-decision sequence D and an outcome w pw1, . . . , wkq, we say w is supported by the price system p B, tpiuiďkq where the real number B ą 0 is the budget that each voter starts with and for each i P t1, . . . , ku, pi is a function from N ˆ Ci to r0, 1s such that the following properties hold:

4Observe that even if we would change the definition of winbased WAMs to allow g-functions with 0-values, such rules would never satisfy simple proportionality, as follows immediately from Theorem 3 with x 1 and y 2. 5Priceability is a rather strong proportionality axiom in the multi-winner setting. It implies Proportional Justified Representation (S anchez-Fern andez et al. 2017) and is incomparable to Extended Justified Representation (Aziz et al. 2017).

(P1) pipv, cq 0 if c R Aipvq, i.e., no voter pays for an alternative that she does not approve. (P2) řk j 1 ř c PCj pjpv, cq ď B, i.e., voters cannot spend more than their budget. (P3) ř v PN pipv, wiq 1 for i P t1, . . . , ku, i.e., each alternative included in w gathers a total payment of 1.6

(P4) ř v PN pipv, wq 0 for i P t1, . . . , ku and w wi, i.e., alternatives not in w do not receive any payments. These four conditions are essentially the same as for priceability in multi-winner voting. In this setting, a fifth condition is present which states that there is no group of voters that supports a common alternative and has a remaining budget of more than 1. Unfortunately, translating this requirement directly into perpetual voting does not work, as the following example shows: Example 3. Consider the following 2-decision sequence:

voters 1 2 3 4 5 6

rounds A1 tau tbu tcu tdu teu tfu A2 tau tau tau tau tbu tbu

Furthermore, let w be an arbitrary outcome for this decision sequence. Assume that there exists a price system p B, tpiuiďkq supporting w. By construction, the winning alternative in the first round has only one supporter. Therefore, the budget of each voter (B) must be at least 1. However, then after the second round, at least two supporters of the non-winning alternative still have a budget of 1, together strictly more than the price to pay for an alternative (1). This shows that we need a different minimality condition to use priceability in perpetual voting. Due to the sequential nature of perpetual voting, it turns out that an inductive minimality condition works well. Definition 7. Given a k-decision sequence D and an outcome w pw1, . . . , wkq, we say w is supported by a minimal price system p B, tpiuiďkq if there exists a B ď B such that the following two conditions hold: (P5) there exists a minimal price system p B , tp i uiďk 1q that supports pw1, . . . , wk 1q7

(P6) there are no B1, w1 k and p1 k such that B ď B1 ă B and p B1, tpiuiďk 1 Y tp1 kuq is a price system supporting pw1, . . . , wk 1, w1 kq. A perpetual voting rule R satisfies perpetual priceability if for any k-decision sequence D with Rp Dq w there exists a minimal price system p B, tpvuv PNq that supports w. Using this definition, we can show that perpetual priceability implies LQC. Proposition 8. Perpetual priceability implies LQC.

6Priceability in multi-winner voting is defined slightly differently by fixing the budget of each voter at 1 and varying the price of an alternative. Both definitions are equivalent in the multi-winner setting. The definition with variable budget is better suited for perpetual voting as it allows to extend price-systems to future rounds. 7We assume that p0, Hq is a minimal price system supporting the empty sequence.

Proof. Let R be a perpetual voting rule that satisfies perpetual priceability. We proceed by contradiction. To this end, let D be a k-decision sequence, such that Rp Dq violates LQC and let N 1 be a closed group that witnesses this violation. Furthermore, let Rp Dq pw1, . . . , wkq and let p B, tpiuiďkq be a minimal price system that supports pw1, . . . , wkq. We first observe that we must have B ě k{n, as otherwise it would not be possible to pay for k alternatives. Furthermore, if B k{n, then no budget is left after round k, formally řk j 1 ř c PCj pjpv, cq B for all v P N. As N 1 is a closed group, we know Aipvq Aipwq for all v, w P N 1 and i ď k. Furthermore, we know that if c R Aipvq, then also pipv, cq 0. Therefore, for every voter in v P N 1 we have řk j 1 ř c PAjpcq pjpv, cq |N 1| k{n. As money can only be spent on alternatives that are elected and every alternative costs 1, this means every voter in N 1 approves of at least |N 1| k{n alternatives in Rp Dq and hence LQC is is satisfied. Let us now assume B ą k{n. As we assume that LQC is violated, there is a voter v P N 1 such that satkpv, Rp Dqq ă Y k |N 1|

n ] . In particular, that means that only Y k |N 1|

n ] 1 alternatives supported by the closed group have been elected. Then we know the following for the budget that the voters in N 1 have left after round k:

c PCi pipv, cq

|N 1|B ˆZ k |N 1|

|N 1|k{n Z k |N 1|

Hence there is an ϵ such that the budget of the voters in N 1 is 1 ϵ. By the definition of minimal price systems, for every l ď k, there is a price system p Bl 1, tpl 1 i uiďl 1q that witnesses the minimality of the price system p Bl, tpl iuiďlq, where p Bk, tpk i uiďkq p B, tpiuiďkq. We claim that B1 ă B. Observe that in the first round B1 ď 1{|N 1| must hold, as with a budget of 1{|N 1| the voters in N 1 can already afford one of the alternatives that they jointly approve; this would contradict minimality in round 1. Moreover, we can assume that k |N 1|{n ě 1 as otherwise LQC is vacously satisfied. It follows that k ě n{|N 1|. Finally, by assumption B ą k{n. Put together, we have

B1 ď 1 |N 1| n n|N 1| ď k

Now let l be the largest index l for which Bl ă B. We claim that there is a B1 with Bl ď B1 ă Bl 1 B such that there are w1 P Cl 1 and p1 l 1 such that p B1, tpl i uiďl Y tp1 l 1q is a price system supporting pw1, . . . , wl , w1q. This would be a contradiction to the minimality of p Bl 1, tpl 1 i uiďl 1q. Let w1 be an alternative supported by the voters in the closed group in round l 1. Furthermore, let B1 maxp B ϵ{|N 1|, Bl q. Observe that Bl ď B1 ă B.

SP BD LQC UQC

AV ˆ 8 ˆ ˆ Per. Unit-Cost ˆ 8 ˆ ˆ Per. PAV 8 ˆ ˆ Per. Consensus ď n2 3n

4 ˆ Per. Phragm en 2n 1 ˆ

Table 1: Axiomatic results for selected perpetual voting rules: bounded dry spells (BD), simple proportionality (SP), and lower/upper quota for closed groups (LQC/UQC). Entries marked with are due to Lackner (2020).

Now, define p1 l 1 such that ř v PN 1 p1 l 1pv, w1q 1 and p1 l 1pv1, cq 0 whenever v1 R N 1 or c w1. This is possible, because the voters in N 1 have at least a budget of 1 in round l 1. Hence this is a price system that supports pw1, . . . , wk 1, w1q. Contradiction to the minimality of p B, tpiuiďkq.

It can be shown that one can always turn the load balancing procedure of Perpetual Phragm en into a minimal price system. Therefore it satisfies perpetual priceability.

Proposition 9. Perpetual Phragm en satisfies perpetual priceability.

Finally, we observe that perpetual priceability is incompatible with UQC.

Proposition 10. A perpetual voting rule cannot satisfy both perpetual priceability and UQC.

Corollary 11. Perpetual Phragm en satisfies LQC but fails UQC.

Discussion and Research Directions We provide a summary of our axiomatic results in Table 1. Two rules appear to be most promising: Perpetual Consensus and Perpetual Phragm en. Their most notable difference is in which sense they are proportional: Perpetual Phragm en satisfies a lower quota axiom (guaranteeing groups a certain satisfaction), whereas Perpetual Consensus satisfies an upper quota axiom (limiting excessive influence of groups on the decision process). Moreover, we have seen that the simplicity of winand loss-based WAMs is too restrictive to achieve proportional outcomes. Perpetual Consensus or Perpetual Phragm en are more proportional but also conceptually more difficult. Whether the conceptual complexity of these rules is problematic can only be answered in the context of a concrete application. A natural open question is whether a voting rule exists that satisfies both LQC and UQC. The Quota apportionment method of Balinski and Young (1975) may be a useful starting point. Note that such a rule cannot satisfy perpetual priceability (Proposition 10). Currently, Perpetual Phragm en is the only perpetual voting rule satisfying perpetual priceability. Another candidate for this property is an an adaption of the minimax support method (Fern andez et al. 2022) to the perpetual setting.

Acknowledgements This research was funded by the Austrian Science Fund (FWF), research grants P31890 and J4581.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified representation in approvalbased 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. Balinski, M. L.; and Young, H. P. 1975. The quota method of apportionment. The American Mathematical Monthly, 82(7): 701 730. Benade, G.; Kazachkov, A. M.; Procaccia, A. D.; and Psomas, C.-A. 2018. How to make envy vanish over time. In Proceedings of the 19th ACM Conference on Economics and Computation (EC 2018), 593 610. Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017. Phragm en s Voting Methods and Justified Representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), 406 413. AAAI Press. Bulteau, L.; Hazon, N.; Page, R.; Rosenfeld, A.; and Talmon, N. 2021. Justified Representation for Perpetual Voting. IEEE Access, 9: 96598 96612. Casella, A. 2005. Storable votes. Games and Economic Behavior, 51(2): 391 419. Casella, A. 2012. Storable Votes: Protecting the Minority Voice. Oxford University Press. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair public decision making. In Proceedings of the 2017 ACM Conference on Economics and Computation, 629 646. Do, V.; Hervouin, M.; Lang, J.; and Skowron, P. 2022. Online Approval Committee Elections. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022). Fern andez, L. S.; Garc ıa, N. F.; Fisteus, J. A.; and Brill, M. 2022. The maximin support method: an extension of the D Hondt method to approval-based multiwinner elections. Math. Program. Freeman, R.; Zahedi, S. M.; and Conitzer, V. 2017. Fair and efficient social choice in dynamic settings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017), 4580 4587. ijcai.org. Freeman, R.; Zahedi, S. M.; Conitzer, V.; and Lee, B. C. 2018. Dynamic proportional sharing: A game-theoretic approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1): 3:1 3:36. Frege, G. 2000. Vorschl age f ur ein Wahlgesetz. In Gabriel, G.; and Dathe, U., eds., Gottlob Frege: Werk und Wirkung. Mit den unver offentlichten Vorschl agen f ur ein Wahlgesetz von Gottlob Frege, 297 313. Mentis. Harrenstein, P.; Lackner, M.; and Lackner, M. 2020. A Mathematical Analysis of an Election System Proposed by Gottlob Frege. Erkenntnis.

Kash, I.; Procaccia, A. D.; and Shah, N. 2014. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research, 51: 579 603. Lackner, M. 2020. Perpetual Voting: Fairness in Long-Term Decision Making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020). AAAI Press. Lackner, M.; Maly, J.; and Rey, S. 2021. Fairness in Long Term Participatory Budgeting. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, (IJCAI 2021), 299 305. ijcai.org. Lackner, M.; and Skowron, P. 2018. Approval-Based Multi Winner Rules and Strategic Voting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), 340 436. ijcai.org. Lackner, M.; and Skowron, P. 2023. Multi-Winner Voting with Approval Preferences. Springer. Lang, J.; and Xia, L. 2009. Sequential composition of voting rules in multi-issue domains. Mathematical Social Sciences, 57(3): 304 324. Peters, D.; and Skowron, P. 2020. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC 2020), 793 794. Phragm en, E. 1894. 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. Phragm en, E. 1895. Proportionella val. En valteknisk studie. Svenska sp orsm al 25. Lars H okersbergs f orlag, Stockholm. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Val, P. B.; and Skowron, P. 2017. Proportional Justified Representation. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI-2017), 670 676. AAAI Press. Zeng, D.; and Psomas, A. 2020. Fairness-efficiency tradeoffs in dynamic fair division. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC 2021), 911 912.