Voting procedures
We consider a finite set consisting of alternatives, .
Let denote the set of all non-empty subsets of A.
Each agent from a finite set , is assumed to have a preference over alternatives where is the set of linear orders on .
An ordered -tuple of preferences is called a (preference) profile, . A group decision is made by a social choice rule based on and is considered to be an element of . Thus we define a social choice rule as a mapping .
We consider 27 social choice rules. We divided them into 5 groups.
Scoring Rules
1. Plurality Rule.
Choose alternatives that are ranked first by the maximum number of agents, i.e.
where
2. q-Approval rule
Let us define
where is the upper contour set of in .
Let be the number of agents for which is ranked among the first alternatives in their preference ordering.
The integer can be called as the degree of the procedure.
We define q-Approval as follows
i.e., the alternatives which are admitted to be among the best by the highest number of agents are chosen.
It can be easily seen that Plurality Rule is a special case of q-Approval where
3. Borda's Rule
Let be the cardinality of the lower contour set of in , i.e. . The sum of over all is called the Borda score of alternative .
The alternatives with maximum Borda score are chosen., i.e.
4. Black's Procedure
Let us define the majority relation for a given profile
Condorcet winner in the profile is an element undominated in the majority relation (constructed according to the profile), i.e.
Black's rule picks the unique Condorcet winner if it exists and the Borda winner(s) otherwise.
5. Threshold rule (Aleskerov et al. 2010)
Let be the number of agents for which the alternative is the worst in their ordering, – is the number of agents placing the second worst, and so on, – the number of agents considering the alternative x as their best one. Then we order the alternatives lexicographically. The alternative is said to -dominate the alternative if < or, if there exists not more than , s.t. , and <. In other words, first, the number of worst places are compared, if these numbers are equal then the number of second worst places are compared and so on. The alternatives which are not dominated by other alternatives via are chosen.
6. Hare's Procedure (also known as Single Transferable Vote, Aleskerov, Karpov, 2012)
First, if an alternative is chosen by a simple majority of voters, then this alternative is chosen, and the procedure stops.
Otherwise, the alternative a with the minimum number of votes is omitted. Then the procedure is applied to the set and to the profile until the alternative ranked first by a simple majority is found.
7. Antiplurality Rule
The alternative, which is regarded as the worst by the minimum number of agents, is chosen, i.e.,
where .
8. Inverse Borda's Procedure
For each alternative Borda's count is calculated.
Then the alternative with the minimum count is omitted. Borda's count are re-calculated for profile , and procedure is repeated until choice is found.
9. Nanson's Procedure (modified)
For each alternative Borda's count is calculated.
Then average count is calculated, r , and alternatives are omitted for which < r. Then the set r is considered, and the procedure is applied to the profile . Such procedure is repeated until choice set will not be empty.
10. Coombs' Procedure
Alternative a which is the worst for the maximum number of agents is omitted.
Then the profile is contracted to the , and the procedure is repeated until the choice set will not be empty.
Majority Relation-Based Rules
11. Minimal dominant set
A set is called a dominant set, if each alternative in dominates each alternative outside via majority relation. A dominant set is called a minimal dominant set if and only if no its proper subsets are dominant sets. If there are more than one minimal dominant set, the choice is comprised of the union of such minimal dominant sets.
12. Minimal undominated set
A set is called an undominated set, if no alternative outside dominates any alternative in via majority relation. An undominated set is called a minimal undominated set if and only if no its proper subsets are undominated sets. If there are more than one minimal undominated set, the choice is comprised of the union of such minimal undominated sets.
13. Uncovered set I (version used in Aleskerov, Kurbanov, 1999)
We define lower contour set of an alternative x for a certain binary relation as a set such that
For Uncovered set I we define lower contour set in the majority relation and a new binary relation such that
Undominated alternatives on relation are chosen.
14. Uncovered set II (version used in Aleskerov, Kurbanov, 1999)
We define upper contour set of an alternative for a certain binary relation as a set such that
For Uncovered set II we define upper contour set in the majority relation . An alternative is said to B-dominate an alternative , i.e. if and . The result of Uncovered set II aggregation procedure is B-undominated alternatives.
15. Richelson’s rule
First, we construct lower contour set and upper contour set for majority relation. Then, we construct a new binary relation such that:
Undominated alternatives on relation are chosen.
16. Minimal weakly stable set
A set is called a weakly stable set if and only if it satisfies the following property: if for exists , than either or .
An weakly stable set is called a minimal weakly stable set if and only if no its proper subsets are weakly stable sets.
If there are more than one minimal weakly stable set, the choice is comprised of the union of such minimal weakly stable sets.
17. Fishburn’s Rule
First we construct upper contour set for the majority relation. Then, we construct binary relation such that:
Undominated alternatives on relation are chosen.
Value Function Rules
18. Copeland’s rule I (Aleskerov, Kurbanov, 1999)
First, we construct upper contour set and lower contour set in majority relation. Then, we define a function such that
The social choice is comprised of alternatives with largest values of .
19. Copeland’s rule II (Aleskerov, Kurbanov, 1999)
Function is defined as a cardinality of lower contour set in the majority relation for a given alternative .
The social choice is comprised of the alternatives with the maximum values of .
20. Copeland’s rule III (Aleskerov, Kurbanov, 1999)
Function is defined as a cardinality of upper contour set in the majority relation for a given alternative .
The social choice is comprised of the alternatives with the minimum values of .
21-23. k-stable sets, 3 aggregation procedures (Aleskerov, Subochev, 2009)
A set is called k-stable, if for each alternative outside of there is alternative inside, which dominates via majority relation by not more than steps.
A k-stable set is a minimal k-stable set if no its proper subset is a k-stable set. If there are more than one minimal k-stable set, their union is the social choice.
We consider k-stable sets for k=1, 2, 3 as 3 different aggregation procedures
Tournament Matrix Rules
24. Simpson’s procedure (Aleskerov, Kurbanov, 1999)
Define
Social choice is defined as
25. MinMax procedure
Define
Social choice is defined as
Q-Paretian Rules
26. Strong q-Paretian simple majority rule (Aleskerov, Kurbanov, 1999)
Let .
Let be the family of simple majority coalitions.
Define a function
Then the social choice is defined as alternatives which are in between top alternatives for each voter in at least one simple majority coalition. If there are no such alternatives, then the result is defined by increasing by 1 until it is not empty.
27. Strong q-Paretian simple plurality rule (Aleskerov, Kurbanov, 1999)
This rule is based on the previous one with some additions: if several alternatives are chosen, then for each alternative is counted how many coalitions choose this alternative. The alternative with the maximal value of this index is chosen.