Perpetual voting

Perpetual voting proceeds in rounds. In each round t, there is a set C_t of candidates or alternatives to choose from. The set of candidates can, in general, vary between rounds. In each round t, a single candidate from C_t is elected. A perpetual voting rule is a rule that, in each round t, takes as input the voters' preferences, as well as the sequence of winners in rounds 1,...,t-1, and returns an element of C_t that is elected in time t.

Perpetual voting settings differ in the type of agents' preferences: the preferences can be numeric (cardinal ballots) or binary (approval ballots). They also differ in whether the agents' preferences are known for all rounds in advance (offline) or revealed before each round (online).

With cardinal ballots, each voter assigns a numeric utility to each alternative in each round. The total utility of a voter is the sum of utilities he assigns to the elected candidates in each round. The problem is often called fair public decision making.

Conitzer, Freeman and Shah[4] studied perpertual voting with offline cardinal ballots. A natural fairness requirement in this setting is proportional division, by which each agent should receive at least 1/n of their maximum utility. Since proportionality might not be attainable, they suggest three relaxations:

• Proportionality up to one issue (PROP1): for each voter, there exists a round such that, if the decision on that round would change to the voter's best candidate in that round, the voter would have his fair share.
• Round robin share (RRS): each voter receives at least as much utility as he could attain if the rounds were divided by round-robin item allocation and he would play the last.
• Pessimistic proportional share (PPS).

They show that the Maximum Nash Welfare solution (maximizing the product of all agents' utilities) satisfies or approximates all three relaxations. They also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without Pareto efficiency.

Freeman, Zahedi and Conitzer[5] study perpetual voting with online cardinal ballots. They present two greedy algorithms that aim to maximize the long-term Nash welfare (product of all agents' utilities).

With approval ballots, in each round t, each voter j approves a subset of A_t,j of C_t. 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.

Martin Lackner[1] studied perpetual voting with online approval ballots. 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: 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 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. 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. Several common weighting schemes are:

• Perpetual Harmonic - as in sequential proportional approval voting: the weight of a voter with current satisfaction k is 1/(k+1).
• 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.
• 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 Consensus - the weight of an unsatisfied voter is increased by 1. The weights of all voters are increased by 1; then, the total weight of satisfied voters is decreased n (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). This rule is related to an apportionment method of Frege.[2]
• 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 Nash - maximizes the product of the voters' satisfaction scores.

Maly and Lackner[2] discuss general classes of simple perpetual voting rules for online approval ballots, and analyze the axioms that can be satisfied by rules of each class.

Bulteau, Hazon, Page, Rosenfeld and Talmon[3] study perpetual voting with offline approval ballots. They adapt the properties of justified representation and proportional justified representation to this setting. They show 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.

Skowron and Gorecki[6] study perpetual voting with offline approval voting, where in each round there is a single candidate (a single yes/no decision). Their main fairness axiom is proportionality: each group of size k should be able to influence at least a fraction k/n of the decisions. They study two rules: proportional approval voting and Method of Equal Shares. They show that both rules perform well in terms of proportionality.

Bredereck, Fluschnik, and KaczMarczyk[7] study perpetual multiwinner voting: at each round, each voter votes for a single candidate. The goal is to elect a committee of a given size. In addition, the difference between the new committee and the previous committee should be bounded: in the conservative model the difference is bounded from above (two consecutive committees should have a slight symmetric difference), and in the revolutionary model the difference is bounded from below (two successive committees should have a sizeable symmetric difference). Both models are NP-hard, even for a constant number of agents.

Lackner, Maly and Rey extend the concept of perpetual voting to participatory budgeting.[8]

• Storable votes - another way in which minorities can get a fair share of power - by strategically storing votes and spending them later.
• Dynamic voting[9][10] - single-issue voting, in which the voters' preferences change over time.
• Sequential voting[11] - a voting procedure for decision making in complex combinatorial domains (without fairness requirements).
• Fair allocation of public indivisible goods[12][13] - a group of agents has to choose a set of indivisible public goods, where there is are feasibility constraints on what subsets of elements can be chosen. This model generalizes both fair public decision making, and participatory budgeting. Banerjee, Gkatzelis, Hossain, Jin, Micah and Shah[14] study this problem with predictions: in each round, a public good arrives, each agent reveals his value for the good, and the algorithm should decide how much to invest in the good (subject to a total budget constraint). There are approximate predictions of each agent's total value for all goods. The goal is to attain proportional fairness for groups. With binary valuations and unit budget, proportional fairness can be achieved without predictions. With general valuations and budget, predictions are necessary to achieve proportional fairness.

• Python code for some perpetual voting rules and experiments