Voting procedures

We consider a finite set \(A\) consisting of \(m\) alternatives, \(m=3,\ 4\). Let \(A=2^A\backslash\left\{\emptyset\ \right\}\) denote the set of all non-empty subsets of A. Each agent from a finite set \(N=\left\{1,...,n\right\}, n>1\), is assumed to have a preference \(P_i \in L\) over alternatives where \(L\) is the set of linear orders on \(A\). An ordered \(n\)-tuple of preferences \(P_i\) is called a (preference) profile, \(\vec{P}\). A group decision is made by a social choice rule based on \(\vec{P}\) and is considered to be an element of \(A\). Thus we define a social choice rule as a mapping \(C:L^n\rightarrow A\). 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. \[a\in C(\vec{P})\Leftrightarrow[\forall x\in A\ \ \ n^+(a,\vec{P})\geq n^+(x,\vec{P})],\] where \(n^+(a,\vec{P})=card\left\{i\in N|\forall y\in A\ \ \ aP_iy\right\}\)

2. q-Approval rule

Let us define \[n^+(a,\vec{P},q)=card\{i\in N|card\{D_i(a)\}\le q-1\},\] where \(D_i(a)=\left\{y\in A:yP_ia\right\}\) is the upper contour set of \(a\in A\) in \(P_i\in L\). Let \(n^+(a,\vec{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 \[a\in C(\vec{P})\Leftrightarrow[\forall x\in A\ \ \ n^+(a,\vec{P},q)\geq n^+(x,\vec{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 \(r_i(x,\vec{P})\) be the cardinality of the lower contour set of \(x\in A\) in \(P_i\in\vec{P}\), i.e. \(r_i(x,\vec{P})=\left|L_i(x)\right|=\left|\left\{b\in A:xP_ib\right\}\right|\). The sum of \(r_i(x,\vec{P})\) over all \(i\in N\) is called the Borda score of alternative \(a\). \[r(a,\vec{P})=\sum_{i=1}^{n}r_i(a,P_i).\] The alternatives with maximum Borda score are chosen., i.e. \[a\in C(\vec{P})\Leftrightarrow[\forall b\in A,\ \ \ r(a,\vec{P})\geq r(b,\vec{P})].\]

4. Black's Procedure

Let us define the majority relation \(\mu\) for a given profile \(\vec{P}\) \[x\mu y\Leftrightarrow card{i\in N|xP_iy}>card{i\in N|yP_ix}.\] Condorcet winner \(CW(\vec{P})\) in the profile \(\vec{P}\) is an element undominated in the majority relation \(\mu\) (constructed according to the profile), i.e. \[CW(\vec{P})=\left[a|\lnot\exists x\in A,\ \ \ x\mu a\right]\] 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 \(v_1(x)\) be the number of agents for which the alternative \(x\) is the worst in their ordering, \(v_2(x)\) – is the number of agents placing the second worst, and so on, \(v_m(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 \(v_1(x)\)<\(v_1(y)\) or, if there exists not more than \(m\), s.t. \(v_i(x)=v_i(y), i=1,...,k-1\), and \(v_k(x)\)<\(v_k(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\backslash\{a\}\) and to the profile \(\vec{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., \[a\in C(\vec{P})\Leftrightarrow[\forall x\in A\ \ \ n^-(a,\vec{P})\le n^-(x,\vec{P})],\] where \(n^-(a,\vec{P})=card\{i\in N|\forall y\in A yP_ia\}\).

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

Majority Relation-Based Rules

11. Minimal dominant set

A set \(Q\)is 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\left(x\right)=\left\{y\in A\ \right|xPy\}\] For Uncovered set I we define lower contour set in the majority relation \(\mu\) and a new binary relation \(\delta\) such that \[x\delta y\ \leftrightarrow L\left(x\right)\supset L(y)\] Undominated alternatives on relation \(\delta\) 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\left(x\right)=\left\{y\in A\ \right|yPx\}\] For Uncovered set II we define upper contour set in the majority relation \(\mu\). An alternative \(x\) is said to B-dominate an alternative \(y\), i.e. \(xBy\) if \(x\mu y\) and \(D\left(x\right)\subseteq 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 \(\sigma\) such that: \[x\sigma y\ \leftrightarrow[L\left(x\right)\supseteq L\left(y\right)\land D\left(x\right)\subseteq D\left(y\right)\land\left(\left[L\left(x\right)\supset L\left(y\right)\right]\vee\left[D\left(x\right)\subset D\left(y\right)\right]\right)]\] Undominated alternatives on relation \(\sigma\) 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 \(x\in Q\) exists \(y\mu x\), than either \(y\in Q\) or \(\exists z\ \in Q\ s.t.\ z\mu 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 \(\gamma\) such that: \[x\gamma y\leftrightarrow D(x)\subset D(y)\] Undominated alternatives on relation \(\gamma\) 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\left(x\right)=card\left\{L\left(x\right)\right\}-card\{D\left(x\right)\}\] 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\left(x\right)\).

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\left(x\right)\).

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\left(a,\ b\right)=card\left\{i\in N\ \right|aP_ib\},\ n\left(a,a\right)=+\infty\)
Social choice is defined as \(x\in C(\vec{P})\leftrightarrow x=arg\ \underset{a\epsilon A}{max}\ \underset{b\epsilon A}{min}(n\left(a,b\right))\)

25. MinMax procedure

Define \(n\left(a,\ b\right)=card\left\{i\in N\ \right|aP_ib\},\ n\left(a,a\right)=-\infty\)
Social choice is defined as \(x\in C(\vec{P})\leftrightarrow x=arg\ \underset{b\epsilon A}{min}\ \underset{a\epsilon A}{max}(n(b,a))\)

Q-Paretian Rules

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

Let \(f\left(\vec{P};i,\ q\right)=\{x\in A|card\left(D_i\left(x\right)\right)\le q\}\).
Let \(\tau=\{I\subset N|card\left(i\right)=\left\lceil\frac{n}{2}\right\rceil\}\) be the family of simple majority coalitions.
Define a function \[C\left(A\right)=\bigcup_{I\epsilon\tau}\bigcap_{i\epsilon I}{f(\vec{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.

---