Disclaimer: Please note that this web site is still under developement and some data may be not fully validated or incomplete!

Voting procedures


We consider a finite set A consisting of m alternatives, m=3, 4. Let A=2A{ } denote the set of all non-empty subsets of A. Each agent from a finite set N={1,...,n},n>1, is assumed to have a preference PiL over alternatives where L is the set of linear orders on A. An ordered n-tuple of preferences Pi is called a (preference) profile, P. A group decision is made by a social choice rule based on P and is considered to be an element of A. Thus we define a social choice rule as a mapping C:LnA. 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. aC(P)[xA   n+(a,P)n+(x,P)], where n+(a,P)=card{iN|yA   aPiy}

2. q-Approval rule

Let us define n+(a,P,q)=card{iN|card{Di(a)}q1}, where Di(a)={yA:yPia} is the upper contour set of aA in PiL. Let n+(a,P,q) be the number of agents for which a is ranked among the first q alternatives in their preference ordering. The integer q can be called as the degree of the procedure. We define q-Approval as follows aC(P)[xA   n+(a,P,q)n+(x,P,q)], i.e., the alternatives which are admitted to be among the q 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 q=1

3. Borda's Rule

Let ri(x,P) be the cardinality of the lower contour set of xA in PiP, i.e. ri(x,P)=|Li(x)|=|{bA:xPib}|. The sum of ri(x,P) over all iN is called the Borda score of alternative a. r(a,P)=i=1nri(a,Pi). The alternatives with maximum Borda score are chosen., i.e. aC(P)[bA,   r(a,P)r(b,P)].

4. Black's Procedure

Let us define the majority relation μ for a given profile P xμycardiN|xPiy>cardiN|yPix. Condorcet winner CW(P) in the profile P is an element undominated in the majority relation μ (constructed according to the profile), i.e. CW(P)=[a|¬xA,   xμa] 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 v1(x) be the number of agents for which the alternative x is the worst in their ordering, v2(x) – is the number of agents placing the second worst, and so on, vm(x) – the number of agents considering the alternative x as their best one. Then we order the alternatives lexicographically. The alternative x is said to V-dominate the alternative y if v1(x)<v1(y) or, if there exists not more than m, s.t. vi(x)=vi(y),i=1,...,k1, and vk(x)<vk(y). 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 V 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 X=A{a} and to the profile P/X 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., aC(P)[xA   n(a,P)n(x,P)], where n(a,P)=card{iN|yAyPia}.

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 P/X,X=A{a}, 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 =(aAr(a,P))/|A|, and alternatives cA are omitted for which r(c,P) < r. Then the set X=aA:r(a,P) r is considered, and the procedure is applied to the profile P/X. 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 P/X,X=A{a}, and the procedure is repeated until the choice set will not be empty.

Majority Relation-Based Rules

11. Minimal dominant set

A set Qis called a dominant set, if each alternative in Q dominates each alternative outside Q 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 Q is called an undominated set, if no alternative outside Q dominates any alternative in Q 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 P as a set L(x) such that L(x)={yA |xPy} For Uncovered set I we define lower contour set in the majority relation μ and a new binary relation δ such that xδy L(x)L(y) Undominated alternatives on relation δ are chosen.

14. Uncovered set II (version used in Aleskerov, Kurbanov, 1999)

We define upper contour set of an alternative x for a certain binary relation P as a set D(x) such that D(x)={yA |yPx} For Uncovered set II we define upper contour set in the majority relation μ. An alternative x is said to B-dominate an alternative y, i.e. xBy if xμy and D(x)D(y). 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: xσy [L(x)L(y)D(x)D(y)([L(x)L(y)][D(x)D(y)])] Undominated alternatives on relation σ are chosen.

16. Minimal weakly stable set

A set Q is called a weakly stable set if and only if it satisfies the following property: if for xQ exists yμx, than either yQ or z Q s.t. zμy. 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 D(x) for the majority relation. Then, we construct binary relation γ such that: xγyD(x)D(y) Undominated alternatives on relation γ are chosen.

Value Function Rules

18. Copeland’s rule I (Aleskerov, Kurbanov, 1999)

First, we construct upper contour set D(x) and lower contour set L(x) in majority relation. Then, we define a function u(x) such that u(x)=card{L(x)}card{D(x)} The social choice is comprised of alternatives with largest values of u(x).

19. Copeland’s rule II (Aleskerov, Kurbanov, 1999)

Function u(x) is defined as a cardinality of lower contour set in the majority relation for a given alternative x. The social choice is comprised of the alternatives with the maximum values of u(x).

20. Copeland’s rule III (Aleskerov, Kurbanov, 1999)

Function u(x) is defined as a cardinality of upper contour set in the majority relation for a given alternative x. The social choice is comprised of the alternatives with the minimum values of u(x).

21-23. k-stable sets, 3 aggregation procedures (Aleskerov, Subochev, 2009)

A set Q is called k-stable, if for each alternative y outside of Q there is alternative x inside, which dominates y via majority relation by not more than k 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 n(a, b)=card{iN |aPib}, n(a,a)=+
Social choice is defined as xC(P)x=arg maxaϵA minbϵA(n(a,b))

25. MinMax procedure

Define n(a, b)=card{iN |aPib}, n(a,a)=
Social choice is defined as xC(P)x=arg minbϵA maxaϵA(n(b,a))

Q-Paretian Rules

26. Strong q-Paretian simple majority rule (Aleskerov, Kurbanov, 1999)

Let f(P;i, q)={xA|card(Di(x))q}.
Let τ={IN|card(i)=n2} be the family of simple majority coalitions.
Define a function C(A)=IϵτiϵIf(P;i,q) 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 q 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.