Multi-issue voting

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting. The first consideration is attaining fairness both for the majority and for minorities. To illustrate, consider a group of friends who decide each evening whether to go to a movie or a restaurant. Suppose that 60% of the friends prefer movies and 40% prefer restaurants. In a one-time vote, the group will probably accept the majority preference and go to a movie. However, making the same decision again and again each day is unfair, since it satisfies 60% of the friends 100% of the time, while the other 40% are never satisfied. Considering this problem as multi-issue voting allows attain a fair sequence of decisions by going 60% of the evenings to a movie and 40% of the evenings to a restaurant. The study of fair multi-issue voting mechanisms is sometimes called fair public decision making. The special case in which the different issues are decisions in different time-periods, and the number of time-periods is not known in advance, is called perpetual voting. The second consideration is the potential dependence between the different issues. For example, suppose the issues are two suggestions for funding public projects.…

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting. The first consideration is attaining fairness both for the majority and for minorities. To illustrate, consider a group of friends who decide each evening whether to go to a movie or a restaurant. Suppose that 60% of the friends prefer movies and 40% prefer restaurants. In a one-time vote, the group will probably accept the majority preference and go to a movie. However, making the same decision again and again each day is unfair, since it satisfies 60% of the friends 100% of the time, while the other 40% are never satisfied. Considering this problem as multi-issue voting allows attain a fair sequence of decisions by going 60% of the evenings to a movie and 40% of the evenings to a restaurant. The study of fair multi-issue voting mechanisms is sometimes called fair public decision making. The special case in which the different issues are decisions in different time-periods, and the number of time-periods is not known in advance, is called perpetual voting. The second consideration is the potential dependence between the different issues. For example, suppose the issues are two suggestions for funding public projects. A voter may support funding each project on its own, but object to funding both projects simultaneously, due to its negative influence on the city budget. 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. The study of this setting is sometimes called combinatorial voting. 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 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 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. 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 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 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. 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%.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371067939 under CC BY-SA 4.0; modifications have been made.