Offline cardinal ballots

Conitzer, Freeman and Shah^[1] studied multi-issue voting with offline cardinal ballots (they introduced the term public decision making). They focus on fairness towards individual agents. 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).

These relaxations make sense when the number of voters is small and the number of issues is large, so a difference of one issue is small w.r.t. 1/n. 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.

Online cardinal ballots

Freeman, Zahedi and Conitzer^[7] study multi-issue voting with online cardinal ballots. They present two greedy algorithms that aim to maximize the long-term Nash welfare (product of all agents' utilities). They evaluate their algorithms on data gathered from a computer systems application.

Offline approval voting: one candidate per round

The simplest multi-issue voting setting is that there is a set of issues, and each agent votes either for or against each issue (effectively, there is a single candidate in each round). Amanatidis, Barrot, Lang, Markakis and Ries^[8] present several voting rules for this setting, based on the Hamming distance:

• The utilitarian rule (which they call "minisum") just follows the majority vote of each issue independently of the others, This rule may be unfair towards minorities, but it is strategyproof.
• The egalitarian rule (which they call "minimax") accepts a subset of issues that minimizes the maximum Hamming distance to the voters' ballots (that is, minimizes disagreement). This rule might arguably give too much power to minorities; additionally, it is not strategyproof.
• A family of rules based on Ordered weighted averaging can be used to interpolate between the utilitarian and egalitarian rule. This family allows to attain a trade-off between fairness towards minorities and strategyproofness.

Barrot, Lang and Yokoo^[9] study the manipulability of these OWA-based rules. They prove that the only strategyproof OWA rule with non-increasing weights is the utilitarian rule. They also study empirically a sub-family of the OWA-based rules. Their family is characterized by a parameter p, which represents a property called "orness" of the OWA rule. p=0.5 yields utilitarian AV, whereas p=1 yields egalitarian AV. They show empirically that increasing p results in a larger fraction of random profiles that can be manipulated by at least one voter.

Freeman, Kahng and Pennock^[10] study multiwinner approval voting with a variable number of winners. In fact, they treat each candidate as a binary issue (yes/no), so their setting can be seen as multi-issue voting with one candidate per round. They adapt the justified representation concepts to this setting as follows:

• Each voter gains satisfaction, not only from an elected candidate that he approves, but also from a non-elected candidate that he does not approve (this makes the problem similar to multi-issue voting, where each candidate is a binary issue).
• A group is L-large if it contains at least L*n/m voters (where m is the total number of candidates), and L-cohesive if in addition the group members agree on the placement of at least L candidates (that is: the intersection of A_i plus the intersection of C\A_i is at least L).
• A committee is r-AS (r-average-satisfaction) if for every L-cohesive group, the average of the members' satisfaction is at least r*L. The JR, PJR and EJR conditions are generalized in a similar way.
• The PAV rule chooses a committee that maximizes the sum of Harmonic(sat_i), where sat_i is the satisfaction of voter i. The sequential Phragmen rule and the Method of Equal Shares divide the load of each elected candidate among the voters who approve it, and the load of each unelected candidate among the voters who do not approve it. All these rules satisfy PJR. MES violates EJR; it is not known whether the other two satisfy it.
• A deterministic rule cannot guarantee r-AS for r = (m-1)/m+epsilon, for any epsilon>0. PAV, Phragmen and MES cannot guarantee r-AS for r = 1/2+epsilon. But there is a randomized rule that satisfies (29/32)-AS.

Skowron and Gorecki^[11] study a similar setting: multi-issue voting with offline approval voting, where in each round t 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. This is in contrast to justified-representation axioms, which consider only cohesive groups. This difference is important, since empirical studies show that cohesive groups are rare.^[12] Formally, they define two fairness notions, for voting without abstentions:

• Proportionality: in each group of size k, the utility of at least one voter should be larger than (m/2)*(k/n)-1. The multiplicative factor of 1/2 is essential; as a simple example, suppose n/2 voters always vote "yes" and the other n/2 voters always vote "no". Then, any fair rule must decide "yes" exactly m/2 times, so the utility of each voter would be m/2. Therefore, for the group of all voters (k=n), we cannot guarantee a higher utility than (m/2)*(k/n).
• Proportional average representation: a function d(*) such that, in every group of voters with size k, the average satisfaction is at least d(k/n)

For voting with abstentions, the definitions must be adapted (since if all voters abstain in all issues, their utility will necessarily be 0): instead of m, the factor changes to the number of issues on which all group members do not abstain.

They study two rules:

• Proportional approval voting (PAV) - without abstentions, it guarantees the maximum possible average representation, which is d(r)=(m/2)*r-1; this implies that it is proportional. Moreover, for cohesive groups it has average representation d(L) > 3L/4-1. It is proportional also in voting with abstentions.
• and Method of Equal Shares (MES) - without abstentions, it is proportional, and has average representation d(r)>((m+1)/3)*r-1. With abstentions, the naive implementation of MES is not proportional; but it has a variant that is proportional (they call it Method of Coordinated Auctions with Equal Shares).

Offline approval voting: multiple candidates per round

Brill, Markakis, Papasotiropoulos and Jannik Peters^[13] extended the results of Skowron and Gorecki to issues with multiple candidates per round, and possible dependencies between the issues; see below, the subsection on Fairness in combinatorial voting.

Page, Shapiro and Talmon^[14] studied a special case in which the "issues" are cabinet offices. For each office, there is a set of candidates; all sets are pairwise disjoint. Each voter should vote for a single candidate per office. The goal is to elect a single minister per office. In contrast to the public decision-making setting,^[1] here the number of voters is large and the number of issues is small. They present two generalizations of the justified representation property:

• The weaker generalization is Global proporional justified representation (G-PJR): for every group S of agents of size Ln/k, whose approval sets in all offices have a non-empty intersection, there are at least L offices in which the elected candidate is approved by at least one member of S. A G-PJR allocation always exists (using a super-polynomial time cohesive-greedy algorithm), and it is fixed-parameter tractable w.r.t. the number of voters.
• The stronger generalization is Partial proportional justified representation (P-PJR): for every group S of agents of size Ln/x, whose approval sets in some x out of k offices have a nonempty intersection, there are at least L offices in which the elected candidate is approved by at least one member of S. A P-PJR allocation always exists (using a super-polynomial time cohesive-greedy algorithm).

They generalize the setting by considering that different issues (offices) have different weight (importance, power). They consider both an objective power function, and subjective power functions. For an objective power function, they define a generalization of justified representation, which they call most important power allocation. They then present a greedy version of PAV, and show via simulations that it guarantees justified representation to minorities in many cases.

Online approval voting: multiple candidates per round

In online approval voting, it is common to assume that in each round t there are multiple candidates; the set of candidates is denoted by C_t. Each voter j approves a subset of A_t,j of C_t.

Martin Lackner^[2] 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: 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. 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 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.
• 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: no agent has a dry spell of length (n²+3n)/4. This rule is related to an apportionment method of Frege.^[3]
• Perpetual Phragmen - Each round, the budget of each voter is increased continuously, until some group of voters can "purchase" a candidate. It satisfies simple proportionality and bounded dry spells: no agent has a dry spell of length 2n-1. This rule is related to Phragmen's voting rules. It can be computed in polynomial time.
• 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^[3] 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. In particular, they discuss Perpetual Phragmen, Perpetual Quota and Perpetual Consensus.

Bulteau, Hazon, Page, Rosenfeld and Talmon^[4] 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^[6] 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.^[3] It satisfies strong PJR (some-periods-intersection-PJR), but fails even weak EJR (all-periods-intersection-EJR).^[6]: 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.^[6]: 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.

Perpetual multiwinner voting

Bredereck, Fluschnik, and Kaczmarczyk^[15] 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.

Eliciting non-separable preferences

There are several approaches for eliciting voters' preferences when they are not separable:

1. If there are only few issues, it is possible to ask each voter to rank all possible combinations of candidates. However, the number of combinations increases exponentially in the number of issues, so it is not practical when there are many issues. There is some research on languages for concise representation of preferences.^[16]
2. It is possible to ask for each voters' favorite alternative in each issue separately. This option is simpler, but might lead to multiple-election paradoxes, where the collective decision is worst for all agents. For example, suppose there are three issues, and for each issue there are two candidates - 1 and 0. Suppose Alice's top choice is (1, 1, 0), Bob's top choice is (1, 0, 1), and Chana's top choice is (0, 1, 1), and all agents' last choice is (1, 1, 1). A majority voting in each issue separately would lead to the outcome (1,1,1), which is worst for all voters.^[17]
3. In sequential voting,^[18][19] the issues are decided in order, so that each agent can vote on an issue based on the outcomes in previously-decided issues. This method is useful when there is a natural order of dependence on the issues. However, if some issues depend on decisions in future issues, the voters will have a hard time deciding what to vote.^[20]
4. In iterative voting,^[21][22] we ask for each voters' favorite alternative in each issue separately, but allow them to revise their vote based on other people's votes. Voters are allowed to update only one issue at a time. The problem is that the iterative dynamics might not converge. However, in certain special cases, a Nash equilibrium exists.^[5] Iterative voting can improve the social welfare and prevent some of the multiple-election paradoxes; this was shown both by computer simulations^[23] and by laboratory experiments.^[24]

A survey on voting in combinatorial domains is given by Lang and Xia, 2016.^[25]

Fairness in combinatorial voting

Brill, Markakis, Papasotiropoulos and Jannik Peters^[13] study offline multi-issue voting with a non-binary domain, and possible dependencies between the issues, where the main goal is fair representation. They define generalizations of PAV and MES that handle conditional ballots; they call them conditional PAV and conditional MES. They prove that:

• Under different assumptions, conditional-PAV and conditional-MES satisfy alpha-proportionality, for some alpha that depends on the maximum degree of the dependency graphs and the maximum number of candidates per issue.
• Computing the winner of conditional-MES is NP-hard even when all voters have a common dependency graph; and when voters may have different depency graph, even when the in-degree of each dependency graph is constant. But with both common dependency graph and bounded in-degree, the outcome can be computed in polynomial time. The same holds if each connected component of the global dependency graph has at most a constant number of vertices.

Participatory budgeting

Lackner, Maly and Rey^[26] extend the concept of perpetual voting to participatory budgeting. A city running PB every year may want to make sure that the outcomes are fair over time, not only in each individual application.

Fair allocation of indivisible public goods

In fair allocation of indivisible public goods (FAIPG), society has to choose a set of indivisible public goods, where there is are feasibility constraints on what subsets of elements can be chosen. Fain, Munagala and Shah^[27] focus on three types of constraints:

• Matroid constraints: there is a fixed matroid M over the items, and the chosen items must form a basis of M. This problem of fair public decision making^[1] is a special case in which each issue is a category (containing all candidates for that issue), and there is partition matroid constraint such that a single candidate must be selected for each issue.
• Matching constraints: there is a fixed graph G=(V,E), where the items are the edges, and the chosen items must form a matching in G.
• Packing constraints: there is a fixed matrix A and a fixed vector b, and the indicator vector of the items x must satisfy the inequality A x ≤ b. The problem of participatory budgeting is a special case in which the matrix A has a single row containing the item costs, and b is the budget. Packing constraints allow a more general budgeting setting, in which there are different kinds of resources, each of which has a different budget.

Fain, Munagala and Shah^[27] present a fairness notion for FAIPG, based on the core. They provide polynomial-time algorithms finding an additive approximation to the core, with a tiny multiplicative loss. With matroid constraints, the additive approximation is 2. With matching constraints, there is a constant additive bound. With packing constraints, with mild restrictions, the additive approximation is logarithmic in the width of the polytope. The algorithms are based on the convex program for maximizing the Nash social welfare.

Garg, Kulkarni and Murhekar^[28] study FAIPG with budget constraints. They show polynomial-time reductions for the solutions of maximum Nash welfare and leximin, between the models of private goods, public goods, and public decision making. They prove that Max Nash Welfare allocations are Prop1, RRS and Pareto-efficient. However, finding such allocations as well as leximin allocations is NP-hard even with constantly many agents, or binary valuations. They design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for constantly many agents, and for constantly many goods with additive valuations. They alsao present an O(n)-factor approximation for max Nash welfare, which also satisfies RRS, Prop1, and 1/2-Prop.

Banerjee, Gkatzelis, Hossain, Jin, Micah and Shah^[29] study FAIPG 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.