Fractional approval voting

Last updated

In fractional social choice, fractional approval voting refers to a class of electoral systems using approval ballots (each voter selects one or more candidate alternatives), in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins (pj = 1) and the other candidates lose (pj = 0). The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

Contents

Fractional approval voting is a special case of fractional social choice in which all voters have dichotomous preferences . It appears in the literature under many different terms: lottery, [1] sharing, [4] portioning, [3] mixing [5] and distribution. [2]

Formal definitions

There is a finite set C of candidates (also called: outcomes or alternatives), and a finite set N of n voters (also called: agents). Each voter i specifies a subset Ai of C, which represents the set of candidates that the voter approves.

A fractional approval voting rule takes as input the set of sets Ai, and returns as output a mixture (also called: distribution or lottery) - a vector p of real numbers in [0,1], one number for each candidate, such that the sum of numbers is 1.

It is assumed that each agent i gains a utility of 1 from each candidate in his approval set Ai, and a utility of 0 from each candidate not in Ai. Hence, agent i gains from each mixture p, a utility of . For example, if the mixture p is interpreted as a budget distribution, then the utility of i is the total budget allocated to outcomes he likes.

Desired properties

Efficiency properties

Pareto-efficiency (PE) means no mixture gives a higher utility to one agent and at least as high utility to all others.

Ex-post PE is a weaker property, relevant only for the interpretation of a mixture as a lottery. It means that, after the lottery, no outcome gives a higher utility to one agent and at least as high utility to all others (in other words, it is a mixture over PE outcomes). For example, suppose there are 5 candidates (a,b,c,d,e) and 6 voters with approval sets (ac, ad, ae, bc, bd, be). Selecting any single candidate is PE, so every lottery is ex-post PE. But the lottery selecting c,d,e with probability 1/3 each is not PE, since it gives an expected utility of 1/3 to each voter, while the lottery selecting a,b with probability 1/2 each gives an expected utility of 1/2 to each voter.

PE always implies ex-post PE. The opposite is also true in the following cases:

Fairness properties

Fairness requirements are captured by variants of the notion of fair share (FS).

Individual-FS [5] (also called Fair Welfare Share [1] ) means that the utility of each voter i is at least 1/n, that is, at least 1/n of the budget is allocated to candidates approved by i.

Individual-Outcome-FS [1] means that the utility of each voter i is at least his utility in a lottery that selects a candidate randomly, that is, at least k/|C|, where k is the number of candidates approved by i.

Single-vote-FS (also called faithful [3] ) means that, if each voter approves a single candidate, then the fraction assigned to each candidate j equals the number of voters who approve j divided by n.

Unanimous-FS [5] means that, for each set S of voters with identical preferences, the utility of each member in S is at least |S|/n.

Group-FS [1] :2002draft (also called proportional sharing [4] ) means that, for each voter set S, the total budget allocated to candidates approved by at least one member of S, is at least |S|/n.

Average-FS [5] means that, for each voter set S with at least one approved candidate in common, the average utility of voters in S is at least |S|/n.

Core-FS means that, for each voter set S, there is no other distribution of their |S|/n budget, which gives all members of S a higher utility.

Strategic properties

Several variants of strategyproofness (SP) have been studied for voting rules:

A weaker variant of SP is excludable SP. It is relevant in situations where it is possible to exclude voters from using some candidate alternatives. For example, if the candidates are meeting times, then it is possible to exclude voters from participating in the meeting in times which they did not approve. This makes it harder to manipulate, and therefore, the requirement is weaker. [5]

Participation properties

Rules should encourage voters to participate in the voting process. Several participation criteria have been studied:

A stronger property is required in participatory budgeting settings in which the budget to distribute is donated by the voters themselves:

Rules

Utilitarian rule

The utilitarian rule aims to maximize the sum of utilities, and therefore it distributes the entire budget among the candidates approved by the largest number of voters. In particular, if there is one candidate with the largest number of votes, then this candidate gets 1 (that is, all the budget) and the others get 0, as in single-winner approval voting. If there are some k candidates with the same largest number of votes, then the budget is distributed equally among them, giving 1/k to each such candidate and 0 to all others. The utilitarian rule has several desirable properties: [1] :Prop.1 it is anonymous, neutral, PE, individual-SP, and preference-monotone. It is also easy to compute.

However, it is not fair towards minorities - it violates Individual-FS (as well as all stronger variants of FS). For example, if 51% of the voters approve X and 49% of the voters approve Y, then the utilitarian rule gives all the budget to X and no budget at all to Y, so the 49% who vote for Y get a utility of 0. In other words, it allows for tyranny of the majority.

The utilitarian rule is also not weak-group-SP (and hence not group-SP). For example, suppose there are 3 candidates (a,b,c) and 3 voters, each of them approves a single candidate. If they vote sincerely, then the utilitarian mixture is (1/3,1/3,1/3) so each agent's utility is 1/3. If a single voter votes insincerely (say, the first one votes for both a and b), then the mixture is (0,1,0), which is worse for the insincere voter. However, if two voters collude and vote insincerely (say, the first two voters vote for the first two outcomes), then the utilitarian mixture is (1/2, 1/2, 0), which is better for both insincere voters.

Nash-optimal rule

The Nash-optimal rule maximizes the sum of logarithms of utilities. It is anonymous and neutral, and satisfies the following additional properties:

The Nash-optimal rule can be computed by solving a convex program. There is another rule, called fair utilitarian, which satisfies similar properties (PE and group-FS) but is easier to compute. [1] :Thm.3 in 2002 draft

Egalitarian rule

The egalitarian (leximin) rule maximizes the smallest utility, then the next-smallest, etc. It is anonymous and neutral, and satisfies the following additional properties: [5]

Other welfarist rules

For any monotonically increasing function f, one can maximize the sum of f(ui). The utilitarian rule is a special case where f(x)=x, and the Nash rule is a special case where f(x)=log(x). Every f-maximizing rule is PE, and has the following additional properties: [1] :Prop.5,6,7

Priority rules

A priority rule (also called serial dictatorhip ) is parametrized by a permutation of the voters, representing a priority ordering. It selects an outcome that maximizes the utility of the highest-priority agent; subject to that, maximizes the utility of the second-highest-priorty agent; and so on. Every priority rule is neutral, PE, weak-group-SP, and preference-monotone. However, it is not anonymous and does not satisfy any fairness notion.

The random priority rule selects a permutation of the voters uniformly at random, and then implements the priority rule for that permutation. It is anonymous, neutral, and satisfies the following additional properties: [1] :Prop.5

A disadvantage of this rule is that it is computationally-hard to find the exact probabilities (see Dictatorship mechanism#Computation).

Conditional utilitarian rule

In the conditional utilitarian rule, [5] each agent receives 1/n of the total budget. Each agent finds, among the candidates that he approves, those that are supported by the largest number of other agents, and splits his budget equally among them. It is anonymous and neutral, and satisfies the following additional properties:

Majoritarian rule

The majoritarian rule [8] aims to concentrate as much power as possible in the hands of few candidates, while still guaranteeing fairness. It proceeds in rounds. Initially, all candidates and voters are active. In each round, the rule selects an active candidate c who is approved by the largest set of active voters, Nc. Then, the rule "assigns" these voters Nc to c, that is, it assumes that voters in Nc voted only for c, and assigns c the fraction |Nc|/n. Then, the candidate c and the voters in Nc become inactive, and the rule proceeds to the next round. Note that the conditional-utilitarian rule is similar, except that the voters in Nc do not become inactive.

The majoritarian rule is anonymous, neutral, guarantees individual-FS and single-vote-FS.[ clarification needed ]

Impossibility results

Some combinations of properties cannot be attained simultaneously.

Summary table

In the table below, the number in each cell represents the "strength" of the property: 0 means none (the property is not satisfied); 1 corresponds to the weak variant of the property; 2 corresponds to a stronger variant; etc.

Anon.Neut.EfficiencyFair-shareStrategyproofnessParticipationMonotonicityComputation
0=no

1=yes

0=no

1=yes

0=none

1=ex-post

2=ex-ante

0=none

0.5=positive 1=individual

2=unanimous

3=group

4=core

0=none

1=excludable

2=individual

3=weak-group

4=group

0=none

1=weak

2=strict

3=pooling

0=none

1=preference

Rules

Utilitarian:1120211Polynomial
Egalitarian:1121110Polynomial
Nash:1124 (+average)030?
Priority:0120311Polynomial
Random-priority:111332 (3?)0NP-Hard
Fair-utilitarian:112301 (2? 3?)0Polynomial
Conditional-

utilitarian

11132 (3?)2 (3?)1Polynomial
Majoritarian:11?1 (2? 3?)???Polynomial
Sequental-

utilitarian: [2]

1121?0?0?1Polynomial

Impossible combinations

n≥3, c≥3:14
n≥4, c≥61113
n≥3, c≥3:11[outcome]2
n≥5, c≥17:11222
n≥6, c≥6:20.51
n≥6, c≥4:20.52
n≥5, c≥4:11232

Open combinations

221
212

See also

Related Research Articles

<span class="mw-page-title-main">Approval voting</span> Single-winner electoral system

Approval voting is a single-winner electoral system in which voters mark all the candidates they support, instead of just choosing one. The candidate with the highest approval rating is elected.

In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves everyone in a society better-off. A situation is called Pareto efficient or Pareto optimal if all possible Pareto improvements have already been made; in other words, there are no longer any ways left to make one person better-off, unless we are willing to make some other person worse-off.

Arrow's impossibility theorem is a key result in social choice showing that no rank-order method for collective decision-making can behave rationally or coherently. Specifically, any such rule violates independence of irrelevant alternatives, the principle that a choice between and should not depend on the quality of a third, unrelated option .

In welfare economics and social choice theory, a social welfare function—also called a socialordering, ranking, utility, or choicefunction—is a function that ranks a set of social states by their desirability. A social welfare function takes two possible outcomes, then combines every person's preferences to determine which outcome is considered better by society as a whole. Inputs to the function can include any variables that affect the well-being of a society.

Social choice theory or social choice is a branch of welfare economics that studies the process of collective decision-making. Social choice incorporates insights from economics, mathematics, and game theory to find the best ways to combine individual opinions, preferences, or beliefs into a single coherent measure of the quality of different outcomes, called a social welfare function. Because of its connections to political philosophy and voting, social choice is often also called voting theory. The field is closely tied to mechanism design, which can be thought of as applying social choice in a game theoretic context.

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single predetermined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".

Fair random assignment is a kind of a fair division problem.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

  1. The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome.
  2. The process limits the possible outcomes to two options only.
  3. The process is not straightforward; the optimal ballot for a voter depends on their beliefs about other voters' ballots.

Combinatorial participatory budgeting,also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

Multiwinner approval voting, sometimes also called approval-based committee (ABC) voting, refers to a family of multi-winner electoral systems that use approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected.

Fractional social choice is a branch of social choice theory in which the collective decision is not a single alternative, but rather a weighted sum of two or more alternatives. For example, if society has to choose between three candidates: A B or C, then in standard social choice, exactly one of these candidates is chosen, while in fractional social choice, it is possible to choose "2/3 of A and 1/3 of B".

The method of equal shares is a proportional method of counting ballots that applies to participatory budgeting, to committee elections, and to simultaneous public decisions. It can be used when the voters vote via approval ballots, ranked ballots or cardinal ballots. It works by dividing the available budget into equal parts that are assigned to each voter. The method is only allowed to use the budget share of a voter to implement projects that the voter voted for. It then repeatedly finds projects that can be afforded using the budget shares of the supporting voters. In contexts other than participatory budgeting, the method works by equally dividing an abstract budget of "voting power".

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.

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

Donor coordination is a problem in social choice. There are several donors, each of whom wants to donate some money. Each donor supports a different set of targets. The goal is to distribute the total donated amount among the various targets in a way that respects the donors' preferences.

Participatory budgeting experiments are experiments done in the laboratory and in computerized simulations, in order to check various ethical and practical aspects of participatory budgeting. These experiments aim to decide on two main issues:

  1. Front-end: which ballot type to use as an input? See Participatory budgeting ballot types for common types of ballots.
  2. Back-end: Which rule to use for aggregating the voters' preferences? See combinatorial participatory budgeting for detailed descriptions of various aggregation rules.

References

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). "Collective choice under dichotomous preferences" (PDF). Journal of Economic Theory. 122 (2): 165–184. doi:10.1016/j.jet.2004.05.005. ISSN   0022-0531.
  2. 1 2 3 4 5 6 7 8 Brandl, Florian; Brandt, Felix; Peters, Dominik; Stricker, Christian (2021-07-18). "Distribution Rules Under Dichotomous Preferences: Two Out of Three Ain't Bad". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: ACM. pp. 158–179. doi: 10.1145/3465456.3467653 . ISBN   9781450385541. S2CID   232109303.. A video of the EC'21 conference talk
  3. 1 2 3 Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). "Approval-Based Apportionment". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1854–1861. arXiv: 1911.08365 . doi:10.1609/aaai.v34i02.5553. ISSN   2374-3468. S2CID   208158445.
  4. 1 2 3 4 Duddy, Conal (2015-01-01). "Fair sharing under dichotomous preferences". Mathematical Social Sciences. 73: 1–5. doi: 10.1016/j.mathsocsci.2014.10.005 . ISSN   0165-4896.
  5. 1 2 3 4 5 6 7 8 9 10 11 12 Aziz, Haris; Bogomolnaia, Anna; Moulin, Hervé (2019-06-17). "Fair Mixing: The Case of Dichotomous Preferences" (PDF). Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19. Phoenix, AZ, USA: Association for Computing Machinery. pp. 753–781. doi:10.1145/3328526.3329552. ISBN   978-1-4503-6792-9. S2CID   7436482.
  6. 1 2 Brandl, Florian; Brandt, Felix; Greger, Matthias; Peters, Dominik; Stricker, Christian; Suksompong, Warut (2021-10-01). "Funding Public Projects: A Case for the Nash Product Rule". Journal of Mathematical Economics. 99: 102585. arXiv: 2005.07997 . doi:10.1016/j.jmateco.2021.102585. S2CID   213188260.
  7. A. Guerdjikova and K. Nehring (2014). "Weighting experts, weighting sources" (PDF).
  8. Speroni di Fenizio, Pietro; Gewurz, Daniele A. (2019-04-01). "The space of all proportional voting systems and the most majoritarian among them". Social Choice and Welfare. 52 (4): 663–683. doi: 10.1007/s00355-018-1166-9 . ISSN   1432-217X.
  9. Michorzewski, Marcin; Peters, Dominik; Skowron, Piotr (2020-04-03). "Price of Fairness in Budget Division and Probabilistic Social Choice". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 2184–2191. doi: 10.1609/aaai.v34i02.5594 . ISSN   2374-3468.
  10. Tang, Zhongzheng; Wang, Chenhao; Zhang, Mengqi (2020). "Price of Fairness in Budget Division for Egalitarian Social Welfare". In Wu, Weili; Zhang, Zhongnan (eds.). Combinatorial Optimization and Applications. Lecture Notes in Computer Science. Vol. 12577. Cham: Springer International Publishing. pp. 594–607. arXiv: 2010.09637 . doi:10.1007/978-3-030-64843-5_40. ISBN   978-3-030-64843-5. S2CID   224710712.
  11. Fain, Brandon; Goel, Ashish; Munagala, Kamesh (2016). "The Core of the Participatory Budgeting Problem". In Cai, Yang; Vetta, Adrian (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 10123. Berlin, Heidelberg: Springer. pp. 384–399. arXiv: 1610.03474 . doi:10.1007/978-3-662-54110-4_27. ISBN   978-3-662-54110-4. S2CID   13443635.