Multi-issue voting

To illustrate, consider a group of friends who decide each evening whether to go to a movie or a restaurant.

Multi-issue voting can take place offline or online: With cardinal ballots, each voter assigns a numeric utility to each alternative in each round.

Conitzer, Freeman and Shah[1] studied multi-issue voting with offline cardinal ballots (they introduced the term public decision making).

A natural fairness requirement in this setting is proportional division, by which each agent should receive at least 1/n of their maximum utility.

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

Their family is characterized by a parameter p, which represents a property called "orness" of the OWA rule.

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.

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.

[12] Formally, they define two fairness notions, for voting without abstentions: 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.

Page, Shapiro and Talmon[15] studied a special case in which the "issues" are cabinet offices.

They then present a greedy version of PAV, and show via simulations that it guarantees justified representation to minorities in many cases.

At each round, the candidate with the highest sum of approving weights is elected (breaking ties by a fixed predefined order).

They also report a human study for identifying what outcomes are considered desirable in the eyes of ordinary people.

There are several approaches for eliciting voters' preferences when they are not separable: A survey on voting in combinatorial domains is given by Lang and Xia, 2016.

[26] Brill, Markakis, Papasotiropoulos and Jannik Peters[14] study offline multi-issue voting with a non-binary domain, and possible dependencies between the issues, where the main goal is fair representation.

They prove that: Lackner, Maly and Rey[27] 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.

They provide polynomial-time algorithms finding an additive approximation to the core, with a tiny multiplicative loss.