Perpetual voting

Individual fairness

Martin Lackner studied perpetual voting with online approval ballots. He defined the following concepts:

• The satisfaction of a voter is the number of rounds in which one of his approved candidates is elected.
• The support of a voter in some round is the fraction of voters who support one of his approved candidates.
• The quota of a voter is the sum of his supports over all previous round.

Based on these concepts, he defined three fairness axioms:

1. Simple proportionality - in any simple instance, in which each agent votes for the same single candidate each time, the satisfaction of each agent should be at least his quota (this means that each group of voters, who support the same candidate, should have their candidate elected a number of times proportional to the group size).
2. Independence of unanimous decisions (aka Independence of uncontroversial decisions): if there is an issue on which all voters agree, then the decision on this issue should not affect future decisions (this axiom prevents obvious manipulations by adding uncontroversial issues to the agenda).
3. Bounded dry spells: for each voter should be satisfied with at least one decision in a given (bounded) time-period. The bound may depend on the number of voters.

He also defines two quantitative properties:

1. Perpetual lower/upper quota compliance - the likelihood of a voter to be satisfied with a proportional fraction of the decisions;
2. Gini coefficient of influence - the inequality in the degree of influence of different voters.

He defined a class of perpetual voting rules, called weighted approval voting (WAM). Each voter is assigned a weight, which is usually initialized to 1. At each round, the candidate with the highest sum of approving weights is elected (breaking ties by a fixed predefined order). The weights of voters who approved the winning candidate are decreased, and the weights of other voters are increased. The weight update function can be arbitrarily complex; however, in a Basic WAM, the update is controlled by only two functions: the win-based function updates the weight of a voter who approves the winning candidate, and the loss-based function updates the weight of a voter who disapproves him. Several common WAM rules are:

• Perpetual PAV - as in sequential proportional approval voting: the weight of a voter with current satisfaction k is 1/(k+1). It satisfies simple proportionality, but not bounded dry spells, nor any quota compliance.
• Perpetual Unit-cost - the weight of a satisfied voter remains the same while the weight of an unsatisfied voter increases by 1. So the weight of a voter with current satisfaction k in time t is t-k.
• Perpetual Reset - the weight of a satisfied voter drops to 1 while the weight of an unsatisfied voter increases by 1. Its dry-spell guarantee is at most 2n-2.
• Perpetual Equality - the weight of a voter with satisfaction k is n^−k. So the vote of a voter with satisfaction k is larger than all vote of voters with satisfaction larger than k.
• Perpetual Quota - the weight of a voter is the difference between this voter's satisfaction and his quota. This rule satisfies simple proportionality and independence of unanimous decisions, but not bounded dry spell. However, it performs best in the experimental evaluation, in the two metrics: perpetual lower-quota compliance and Gini coefficient of influence.
• Perpetual Consensus - The weights of all voters are increased by 1; then, the total weight of satisfied voters is decreased n (so the weight of each satisfied voter decreases by n/s, where s is the number of satisfied voters). This rule achieves the best results in the axiomatic analysis: it is the only rule that satisfies all three axioms (simple proportionality, independence of unanimous decisions, and bounded dry spells: no agent has a dry spell of length (n²+3n)/4. This rule is related to an apportionment method of Frege.
• Perpetual Nash - maximizes the product of the voters' satisfaction scores.

Individual and group fairness

Lackner and Maly discuss general classes of perpetual voting rules for online approval ballots, and analyze the axioms that can be satisfied by rules of each class. They define the following new rules:

• Perpetual Phragmen - an online adaptation of the sequential Phragmen's voting rule. Each round, the budget of each voter is increased continuously, until some group of voters can "purchase" a candidate.
• Exponential rule - a WAM with an exponential win-based and loss-based update functions.

They prove the following results:

• Every WAM which has only a win-based update function, or only a loss-based update function, has unbounded dry spells.^: Thm.4
• There is a simple characterization of basic WAM that satisfy independence of uncontroversial decisions.
• The Exponential rule satisfies both bounded dry spells and independence of uncontroversial decisions.
• Every WAM which has only a loss-based update function, violates simple proportionality.^: Thm.2 There is a simple characterization of win-based WAM rules that satisfy simple proportionality.^: Thm.3
• No win-based WAM satisfies both simple proportionality and independence of uncontroversial decisions.
• It is open whether basic WAMs can satisfy all three axioms: simple proportionality, independence of uncontroversial decisions, and bounded dry spells.
• Perpetual Phragmen is not a WAM. It satisfies simple proportionality, guarantees dry spell at most 2n-1,^: Prop.5 and can be computed in polynomial time. It fails independence of uncontroversial decisions.
• Perpetual PAV is the unique win-based WAM that satisfies Apportionment Lower-Quota (though there are other WAMs satisfying it).
• Perpetual PAV and Perpetual Phragmen, when restricted to the apportionment setting, are both equivalent to Jefferson's method, and thus satisfy apportionment lower-quota but violate apportionment upper quota.
• Perpetual Consensus, when restricted to the apportionment setting, is equivalent to Adams method, and thus satisfies apportionment upper quota but violates apportionment lower-quota.
• Perpetual Phragmen has a perpetual proportionality degree (- an adaptation of proportionality degree) of at least (L-1)/2. The perpetual proportionality degree of other rules remains open.
• Every win-based WAM fails both upper-quota for closed groups and lower-quota for closed groups.^: Thm.6
• Perpetual Consensus satisfies upper-quota for closed groups but fails lower-quota for closed groups.^: Thm.7
• Perpetual Phragmen satisfies Perpetual Priceability, which implies lower-quota for closed groups, but is incompatible with upper-quota for closed groups.^{: Prop.8--11}

Group fairness

Bulteau, Hazon, Page, Rosenfeld and Talmon focus on fairness notions to groups of voters, rather than to individual voters. They adapt some justified representation properties to this setting. In particular, they define two variants of proportional justified representation (PJR). In both variants, we say that a group of agents agree in round t if there is at least one candidate in C_t that they all approve.

• The weaker variant is all-periods-intersection-PJR. It requires that, for every group S of agents of size Ln/T who agree in all T rounds, there are at least L rounds in which the elected candidate is approved by at least one member of S.
• The stronger variant is some-periods-intersection-PJR. It requires that, for every group S of agents of size Ln/k who agree in some k out of T rounds, there are at least L rounds in which the elected candidate is approved by at least one member of S. This variant is stronger, as it does not require that the group agrees in all T rounds. However, if they agree on fewer rounds, then their "entitlement" is proportionately smaller.

They prove that these axioms can be satisfied both in the static setting (where voters' preferences are the same in each round) and in the dynamic setting (where voters' preferences may change between rounds). They also report a human study for identifying what outcomes are considered desirable in the eyes of ordinary people.

Chandak, Goel and Peters strengthen both axioms from PJR to EJR (the difference is that, in EJR, there must be at least L rounds in which the elected candidate is approved by the same member of S). They call their new axioms "EJR" and "strong-EJR". They also adapt three voting rules to this setting:

• The Sequential Phragmen rule is fully online - it makes decisions round by round, and does not need to know the total number of decisions. It works as follows. For each voter i, we keep a variable x_i, which we call the load of i. Initially, all loads are set to 0. In each round t, for each candidate c in C_t, we check how to divide a total load of 1 among the voters who approve c in that round, such that the maximum total load assigned to a single voter will be as small as possible (figuratively, one can think of each voter as a bottle filled with x_i liters of water; we have to pour 1 liter of water into the bottles that support c, such that the maximum water height will be as low as possible). In each round t, we choose the candidate for which the maximum total load is as small as possible. The rule can be computed in polynomial time. The rule can be computed in polynomial time. It satisfies strong PJR (some-periods-intersection-PJR), but fails even weak EJR (all-periods-intersection-EJR).^: 4.1
• The method of equal shares is semi-online – it needs to know the total number of rounds, but still works round by round. For each voter i, we keep a variable b_i, which we call the budget of i. Initially, all budgets are set to 1. In each round t, for each candidate c in C_t, we check how to divide a total cost of n/T among the voters who approve c in that round. We choose the candidate for which the maximum price that has to be paid is as small as possible. If, in some round t, no candidate is affordable by the voters who approve it, then we elect a candidate who minimizes the amount that has to be paid by voters who do not approve it, and zero the budget of voters who approve it. The rule can be computed in polynomial time. It satisfies weak-EJR, but fails strong-PJR (and strong-EJR).
• Proportional Approval Voting is offline. It chooses the decision sequence that maximizes the PAV-score, which is the sum over all voters i of the Harmonic number of the number of elected candidates approved by i. It satisfies strong-EJR. Finding the optimal sequence is NP-hard; however, using local search, it is possible to find a locally-optimal sequence that satisfies strong-EJR too.
• It remains open whether there exists a fully-online rule that satisfies EJR (it would imply the existence of an EJR rule that satisfies House monotonicity, which is another open problem).
• Stronger variants of these properties, where groups of voters may have a slightly smaller size or agree on fewer rounds, may be impossible to satisfy.^: Sec.5
• They empirically compared various rules for their average utility (utilitarian value), 25% percentile utility (inspired by egalitarian value), and Gini coefficient. For the average utility, utilitarian approval voting is best; the order among proportional rules was: PAV > Seq.Phragmen > MES > Perpetual Quota > Perpetual Consensus, but the differences are small. For the egalitarian value and Gini coefficient, utilitarian approval voting is worst; there is no consistent difference between the proportional rules. The datasets were (a) random, (b) taken from USA voting data, (c) taken from machine-learning models trained on the Moral Machine dataset.