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. 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.

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 or ranked or binary. 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 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 : 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 : 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 .
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 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. 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. Amanatidis, Barrot, Lang, Markakis and Ries present several voting rules for this setting, based on the Hamming distance:
  • The utilitarian rule 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 accepts a subset of issues that minimizes the maximum Hamming distance to the voters' ballots. 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, 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.
  • A group is L-large if it contains at least L*''n/m'' voters, and L-cohesive if in addition the group members agree on the placement of at least L candidates.
  • A committee is r-AS 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, 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+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 -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. 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 *-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, we cannot guarantee a higher utility than *.
  • Proportional average representation: a function d such that, in every group of voters with size k, the average satisfaction is at least d
For voting with abstentions, the definitions must be adapted : 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 – without abstentions, it guarantees the maximum possible average representation, which is d=*r-1; this implies that it is proportional. Moreover, for cohesive groups it has average representation d > 3L/4-1. It is proportional also in voting with abstentions.
  • and method of equal shares – without abstentions, it is proportional, and has average representation d>*r-1. With abstentions, the naive implementation of MES is not proportional; but it has a variant that is proportional.
Teh, Elkind and Neoh study utilitarian welfare and egalitarian welfare optimization in public decision making with approval preferencers.