Multi-issue voting

There are several issues to be decided on. For each issue t, there is a set Ct of candidates or alternatives to choose from. For each issue t, a single candidate from Ct should be elected. Voters may have different preferences regarding the candidates. The preferences can be numeric (cardinal ballots) or ranked (ordinal ballots) or binary (approval ballots). In combinatorial settings, voters may have preferences over combinations of candidates. A multi-issue voting rule is a rule that takes the voters' preferences as an input, and returns the elected candidate for each issue. Multi-issue voting can take place offline or online: • In the offline setting, agents' preferences are known for all issues in advance. Therefore, the choices on all issues can be made simultaneously. This setting is often called public decision making. • In the online setting, the issues represent decisions in different times; each issue t occurs at time t. The voters' preferences for issue t become known only at time t. This setting is often called perpetual voting. 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 Ct that is elected in time t. • Some authors distinguish between a semi-online setting, in which the number of rounds is known in advance and only the preferences in each round are unknown, and a full-online setting, in which even the number of rounds is unknown. == Cardinal preferences ==

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. Offline cardinal ballots Conitzer, Freeman and Shah 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 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. == Binary preferences ==

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 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 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 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 Ai plus the intersection of C\Ai 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(sati), where sati 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 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. 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 (the method of coordinated auctions with equal shares). Teh, Elkind and Neoh study utilitarian welfare and egalitarian welfare optimization in public decision making with approval preferencers. Offline approval voting: multiple candidates per round Brill, Markakis, Papasotiropoulos and Jannik Peters 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 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, 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. == Combinatorial preferences ==

One complication in multi-issue voting is that there may be dependencies between agents' preferences on different issues. For example, suppose the issues to be decided on are different kinds of food that may be given in a meal. Suppose the bread can be either black or white, and the main dish can be either hummus or tahini. An agent may want either black bread with hummus or white bread with tahini, but not the other way around. This problem is called non-separability. Eliciting non-separable preferences There are several approaches for eliciting voters' preferences when they are not separable: • 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. • 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. • In sequential voting, 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. • In iterative voting, 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. and by laboratory experiments. A survey on voting in combinatorial domains is given by Lang and Xia, 2016. Fairness in combinatorial voting Brill, Markakis, Papasotiropoulos and Jannik Peters 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. == Generalizations ==

Participatory budgeting Lackner, Maly and Rey 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 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 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 also 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 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. == Strategic manipulation ==

Multi-issue voting rules are prone to strategic manipulation. A particularly simple form of manipulation is the Free-rider problem: some voters may untruthfully oppose a popular opinion in one issue, in order to receive increased consideration in other issues. Lackner, Maly and Nardi study this problem in detail. They show that: • Almost every rule based on Ordered weighted averaging or on Thiele's rules, either using global optimization or sequential greedy elections, are prone to free-riding. The only exception is the utilitarian rule, which is not fair towards minorities. • For OWA or Thiele rule based on global optimization (except the utilitarian rule), it is NP-hard to compute the outcome; moreover, even when the winner of an issue is known, it is NP-hard to determine whether free-riding is possible (that is, whether a single agent can remove his approval from the winner without changing the winner). However, free-riding can never be harmful. • For sequential OWA and Thiele rules, computing the winner of each issue can be done in polynomial time, and hence it is easy to know whether free-riding is possible. However, free-riding in one issue may decrease the utility of the free-rider in the following issues; it is NP-hard to tell whether or not this will happen, and requires full information about all issues. Without complete information, it is impossible to know for sure whether free-riding is beneficial or harmful. • Simulation experiments consider variants of OWA and Thiele rules parameterized by a factor x; x=0 is the utilitarian rule, and larger x means that the rule is fairer. As x increases, the proportion of voters who can benefit from free-riding increases from 0 to about 50%; but the proportion of voters who can lose from free-riding increases too, from 0 to more than 10%. == See also ==