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.

Not to be confused with 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.[1] 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.[2][3][4]

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.[5]

Definitions

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.

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.

Conitzer, Freeman and Shah[1] studied multi-issue 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[6] 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).

Approval preferences

With approval ballots, in each round t, each voter j approves a subset of At,j of Ct. 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[2] 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/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 (n2+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.
  • 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.

Bulteau, Hazon, Page, Rosenfeld and Talmon[4] study perpetual voting with 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[7] study multi-issue 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.

Perpetual multiwinner voting

Bredereck, Fluschnik, and Kaczmarczyk[8] 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. 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.[9]
  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.[10]
  3. In sequential voting,[11][12] 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.[13]
  4. In iterative voting,[14][15] 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[16] and by laboratory experiments.[17]

A survey on voting in combinatorial domains is given by Lang and Xia.[18]

Generalizations

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

See also
  • Storable votes - another way in which minorities can get a fair share of power - by strategically storing votes and spending them later.
  • Dynamic voting[20][21] - single-issue voting, in which the voters' preferences change over time.
  • Free-rider problem in multi-issue voting: some voters may untruthfully oppose a popular opinion in one issue, in order to receive increased consideration in other issues.[22]
  • Fair allocation of public indivisible goods[23][24] - 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[25] 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.
  • Discursive dilemma - a contradiction between majority decisions on each issue separately, and majority decisions on the final outcome.

References
  1. Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017-06-20). "Fair Public Decision Making". Proceedings of the 2017 ACM Conference on Economics and Computation. EC '17. New York, NY, USA: Association for Computing Machinery. pp. 629–646. arXiv:1611.04034. doi:10.1145/3033274.3085125. ISBN 978-1-4503-4527-9. S2CID 30188911.
  2. Lackner, Martin (2020-04-03). "Perpetual Voting: Fairness in Long-Term Decision Making". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 2103–2110. doi:10.1609/aaai.v34i02.5584. ISSN 2374-3468. S2CID 209527302.
  3. Lackner, Martin; Maly, Jan (2021-04-30). "Perpetual Voting: The Axiomatic Lens". arXiv:2104.15058 [cs.GT].
  4. Bulteau, Laurent; Hazon, Noam; Page, Rutvik; Rosenfeld, Ariel; Talmon, Nimrod (2021). "Justified Representation for Perpetual Voting". IEEE Access. 9: 96598–96612. doi:10.1109/ACCESS.2021.3095087. ISSN 2169-3536. S2CID 235966019.
  5. Ahn, David S.; Oliveros, Santiago (2012). "Combinatorial Voting". Econometrica. 80 (1): 89–141. doi:10.3982/ECTA9294. ISSN 0012-9682. JSTOR 41336582.
  6. Freeman, Rupert; Zahedi, Seyed Majid; Conitzer, Vincent (2017-08-19). "Fair and efficient social choice in dynamic settings". Proceedings of the 26th International Joint Conference on Artificial Intelligence. IJCAI'17. Melbourne, Australia: AAAI Press: 4580–4587. ISBN 978-0-9992411-0-3.
  7. Skowron, Piotr; Górecki, Adrian (2022-06-28). "Proportional Public Decisions". Proceedings of the AAAI Conference on Artificial Intelligence. 36 (5): 5191–5198. doi:10.1609/aaai.v36i5.20454. ISSN 2374-3468. S2CID 250293245.
  8. Bredereck, Robert; Fluschnik, Till; Kaczmarczyk, Andrzej (July 2022). "When Votes Change and Committees Should (Not)" (PDF). Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence: 144–150. doi:10.24963/ijcai.2022/21. ISBN 978-1-956792-00-3. S2CID 250636565. Retrieved 27 April 2023.
  9. Lang, Jérôme (2007-01-06). "Vote and aggregation in combinatorial domains with structured preferences". Proceedings of the 20th International Joint Conference on Artificial Intelligence. IJCAI'07. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 1366–1371.
  10. Lacy, Dean; Niou, Emerson M.S. (2000-01-01). "A Problem with Referendums". Journal of Theoretical Politics. 12 (1): 5–31. doi:10.1177/0951692800012001001. ISSN 0951-6298. S2CID 153344141.
  11. Lang, Jérôme; Xia, Lirong (2009-05-01). "Sequential composition of voting rules in multi-issue domains". Mathematical Social Sciences. Special Issue: Voting Theory and Preference Modeling. 57 (3): 304–324. doi:10.1016/j.mathsocsci.2008.12.010. ISSN 0165-4896. S2CID 35194669.
  12. Xia, Lirong; Conitzer, Vincent; Lang, Jérôme (2011-06-05). "Strategic sequential voting in multi-issue domains and multiple-election paradoxes". Proceedings of the 12th ACM conference on Electronic commerce. EC '11. New York, NY, USA: Association for Computing Machinery. pp. 179–188. doi:10.1145/1993574.1993602. ISBN 978-1-4503-0261-6. S2CID 6105649.
  13. Conitzer, Vincent; Lang, Jérôme; Xia, Lirong (2009-07-11). "How hard is it to control sequential elections via the agenda?". Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI'09. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 103–108.
  14. Meir, Reshef; Polukarov, Maria; Rosenschein, Jeffrey; Jennings, Nicholas (2010-07-04). "Convergence to Equilibria in Plurality Voting". Proceedings of the AAAI Conference on Artificial Intelligence. 24 (1): 823–828. doi:10.1609/aaai.v24i1.7624. ISSN 2374-3468. S2CID 15254323.
  15. Kavner, Joshua; Meir, Reshef; Rossi, Francesca; Xia, Lirong (2023-01-20). "Convergence of Multi-Issue Iterative Voting under Uncertainty". arXiv:2301.08873 [cs.GT].
  16. Bowman, Clark; Hodge, Jonathan K.; Yu, Ada (2014-06-01). "The potential of iterative voting to solve the separability problem in referendum elections". Theory and Decision. 77 (1): 111–124. doi:10.1007/s11238-013-9383-2. ISSN 1573-7187. S2CID 255110514.
  17. Grandi, Umberto; Lang, Jérôme; Ozkes, Ali I.; Airiau, Stéphane (2022-12-10). "Voting behavior in one-shot and iterative multiple referenda". Social Choice and Welfare. doi:10.1007/s00355-022-01436-0. ISSN 1432-217X.
  18. Lang, Jérôme; Xia, Lirong (2016). "Voting in Combinatorial Domains". Handbook of Computational Social Choice. pp. 197–222. doi:10.1017/CBO9781107446984.010. ISBN 9781107060432.
  19. Lackner, Martin; Maly, Jan; Rey, Simon (2021-05-03). "Fairness in Long-Term Participatory Budgeting". Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '21. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1566–1568. ISBN 978-1-4503-8307-3.
  20. Tennenholtz, Moshe (2004-05-17). "Transitive voting". Proceedings of the 5th ACM conference on Electronic commerce. EC '04. New York, NY, USA: Association for Computing Machinery. pp. 230–231. doi:10.1145/988772.988808. ISBN 978-1-58113-771-2. S2CID 10062678.
  21. Parkes, David; Procaccia, Ariel (2013-06-30). "Dynamic Social Choice with Evolving Preferences". Proceedings of the AAAI Conference on Artificial Intelligence. 27 (1): 767–773. doi:10.1609/aaai.v27i1.8570. ISSN 2374-3468. S2CID 12490400.
  22. Lackner, Maly and Nardi. "Free-Riding in Multi-Issue Decisions". Proceedings of AAMAS 2023.
  23. Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (2018-06-11). "Fair Allocation of Indivisible Public Goods". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 575–592. doi:10.1145/3219166.3219174. ISBN 978-1-4503-5829-3. S2CID 3331859.
  24. Garg, Jugal; Kulkarni, Pooja; Murhekar, Aniket (2021-07-21). "On Fair and Efficient Allocations of Indivisible Public Goods". arXiv:2107.09871 [cs.GT].
  25. Banerjee, Siddhartha; Gkatzelis, Vasilis; Hossain, Safwan; Jin, Billy; Micha, Evi; Shah, Nisarg (2022-09-30). "Proportionally Fair Online Allocation of Public Goods with Predictions". arXiv:2209.15305 [cs.GT].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.