# Analysis of Dynamics of Voting System for Small Number of Candidates

^{*}

**Corresponding Author:**Neelam Gohar, Department of Computer Science, Shaheed Benazir Bhutto Women University, Peshawar, Main Campus, Charsadda Road Landay Sarrak, Peshawar KPK, Pakistan, Tel: +923453356998, Email: [email protected]

*
Received Date: Sep 30, 2017 /
Accepted Date: Oct 10, 2017 /
Published Date: Oct 17, 2017 *

### Abstract

A significant research topic in the area of Computational Social Choice is the complication of different kinds of dishonest behavior like manipulation, dominance and bribery. Whereas most of the work on this issue assumes that the opposite party has incomplete knowledge regarding every agent, they did not know the true preferences of other voters. We have analyzed the dynamics of voting rules with the help of some manipulative and non-manipulative moves. Voters have incomplete information. The voters are aware of the winner at every stage and they make short term rational decisions. The number of candidates and voters are small, and the decisions need to be made quickly. We want the better reply as low as possible while keeping the best reply as high as possible. The voting rules we have used are Plurality rule and Borda rule. We have analyzed the dynamics for these two voting rules for small number of voters and candidates.

**Keywords:** Manipulation; Rationality; Preference aggregation; Game theory; Manipulative and non-manipulative moves; Multi-agent systems

#### Introduction

Distributed AI is the study, construction, and application of multiagent systems, that is, systems in which several interacting, intelligent agents pursue some set of goals or perform some set of tasks. An agent is a computational [1] entity such as a software program or robot that can be viewed as perceiving and acting upon its environment and that is autonomous in that its behavior at least partially depends on its own experience. As an intelligent entity, an agent operates flexibly and rationally in a variety of environmental circumstances given its perceptual and effectual equipment. Behavioral flexibility and rationality are achieved by an agent on the basis of key processes such as problem solving, planning, and decision making, and learning. As an interacting entity, an agent can be affected in its activities by other agents and perhaps by humans. A key pattern of interaction in multi-agent systems is goal and task-oriented coordination, both in cooperative and in competitive situations [2].

**Multi-agent systems**

Multi-agent Systems (MAS) is the emerging subfield of AI that aims to provide both principles for construction of complex systems involving multiple agents and mechanisms for coordination of independent agents, behaviors [3]. The characteristics of MASs are that (1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint; (2) there is no system global control; (3) Data are decentralized; and (4) computation is asynchronous. Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. This promise is particularly attractive for creating software that operates in environments that are distributed and open, such as the internet.

• Agents are autonomous, computational entities that can be viewed as perceiving their environment through sensors and acting upon their environment through effectors. To say that agents are computational entities simply means that they physically exist in the form of programs that run on computing devices [2].

• Intelligent indicates that the agents pursue their goals and execute their tasks such that they optimize some given performance measures. Intelligent does not mean that they are well-informed or supreme.

• Interacting indicates that the agents may be affected by other agents or perhaps by humans in pursuing their goals and executing their tasks. Interaction can take place indirectly through the environment in which they are embedded (e.g., by observing one another's actions) [4].

**Preference aggregation**

Social choice theory basically concerns with the collective decisions and procedures. It is not a single theory but a cluster and analysis of combining individual opinions, interests, welfare to reach a collective decision and results concerning the preference aggregation of multiple agents. Example of such method may include voting procedures, which are used for the aggregation of individual inputs (e.g., votes, preferences) into collective output (e.g., collective decisions) over a group of candidates standing for election in order to determine which candidate should be the winner or specifying some set of rules for deciding the fair allocation of resources based on the given preferences [5]. But the important questions that arises in the mind [1] are: How can a group of individuals can choose a winner from the given set of candidates? What will be the voting system? How a collective decision can arrives at consistent preferences on the basis of its member’s individual preferences or judgment? How we can rank different candidates? So social theory is found as one of the most fundamental tools and study the multi-agent system to answer these questions by introducing models [6].

**Plurality rule**

Plurality rule means how often each alternative is ranked at first place [5].

**Example**

Consider an example in which there are ten patient’s three doctors and the patients have to decide which doctor to visit for their treatment on the basis of their experiences and degrees. Doctor A has done MBBS from UK, B from US, and C from China. The patients select doctors as 1) Five patients choose A to B to C. 2) Three patients choose B to A to C, and 3) Two patients choose C to A to B. These preferences can be conveniently represented in a table where each group of agents is represented by one column.

5 3 2

A B C

B A A

C C B

Now, which patient should be visited on the basis of these individual preferences? A could be chosen on the grounds that it has the most agents ranking it first. That is, A is the winner according to the plurality rule, which only considers how often each alternative is ranked in first place [5].

**Rationality**

A player is said to be rational if he pursues to play in a method which maximizes his own payoff. Rationality is about getting what you want. Voters can be rational in a way that they want their true preference to win at any cost, voter wants to see his favorite candidate the winner. Every voter has their own true preferences, but all the voters are not aware of other voter’s true preferences. They know the winner at every stage and they make rational decisions based on that incomplete information.

**Manipulation**

As we have discussed and assumed above that the preferences of all voters are known. In reality, generally the voters need to report their preferences. A significant problem is that a voter may be motivated to give preferences other than their true ones. For example, consider a plurality election between three alternatives, A, B, and C. Consider voter v with preferences A> B> C. Moreover, suppose that voter v believes that almost nobody else will rank A first, but it will be a close race between B and C. Then, v may report his declared preference by casting a vote in which B is ranked first, but still he has little hope of getting A to win, so he may be better off focusing on ensuring that at least B will win [5]. He will not give vote to C because C is his least favorite.

**Computational social choice theory**

Computational social choice theory is a research area dealing with the aggregations of preferences with a group of agents to reach some social objective. It adds an algorithmic perspective to the formal approach of social choice theory. Computational social choice deals with the application of methods usually associated with computer science to problems of social choice [7].

**Game theory**

Game theory is the formal study of battle, conflict and competition. Game theoretic concepts are applied whenever multi agents are independent to select their moves whereas agents may be any individual, group of people or businesses [8]. In other words we can say that Game Theory is a concept in which each individual or group is responsible for his own move [9].

**Nash equilibrium**

A Nash equilibrium, also called strategic equilibrium, is a list of strategies, one for each player, which has the property that no player can unilaterally change his strategy and get a better payoff. Nash equilibrium is used as a solution concept for game theory [10].

**Borda rule**

The Borda rule is an appropriate procedure in multi-agent decision making when several alternatives are considered [11]. In the Borda voting rule each voter gives m-1 points to the candidate he/she ranked first, m-2 points to the candidate she ranked second, or in general m-k points to the candidate she ranked k-th. The winner is the candidate who amasses the highest total number of points. This voting rule is used in the National Assembly of Slovenia, and is similar to that used in the Eurovision song contest [12].

Example below shows that Borda works like plurality in 2 candidate’s case.

**Example**

Consider an example of 2 candidates case A and B, are standing for election to determine which candidate should win the election from a given set of alternatives and three voters v1, v2, v3.

Voters True Preferences

V1 A>B

V2 B>A

V3 A>B

A is the winner. No voter can switch because it would not be a rational move.

**Descendo-graphic rule**

Descendo means to come downwards. Descendo-graphic rule is a tie breaking rule in which the winner is decided by following descending order.

**Our model**

Descendo-graphic rule is represented in **Figure 1**.

**Problem statement**

We have to analyze the switching of voters through manipulative and non-manipulative moves. According to Gibbard-Satterthwaite [13] theorem manipulation occurs in every voting system [14]. We allow the voters to move to make the favorite candidate to be winner of the election. We have used plurality and borda rule, and for tie breaking the is rule lexicographic that is used in the literature [15-17] and we have used new tie breaking rule called descendo-graphic rule for analysis of voting systems. We have defined types of manipulative and non-manipulative moves for plurality and borda. In our model we are defining procedure of election in which we have set of candidates and set of voters. The voters have their true and declared preferences. True preferences are only known to the voters only and the voters have knowledge about the scores of candidates at every state. There are states and transitions in our model from which voters can switch from one candidate to another based on some particular move. The moves are already defined under the heading of preliminaries. The voters make myopic moves i.e., myopic moves are short sighted and the voters take short term decisions based on incomplete information. By manipulation the scores of the candidates changes. Since manipulation is a hazard and it is particularly proven that every voting rule is susceptible to manipulation. Only one voter is allowed to move/switch at a time so there are chances of tie. Through transition there are often chances of tie among the winners and in the state of tie we have two rules of tie breaking called lexicographic and descendo-graphic. Lexicographic [15-17] is already used in literature and we have developed our new tie breaking rule i.e., descendo-graphic rule. By using these tie-breaking rules we select the winner in case of tie.

#### Related Work

Computational Social choice theory is basically concerned with the analysis of different formal methods for finding the aggregate of multiple agent’s preferences. The examples of these methods may include different voting systems based on different rules at which the preferences of multiple agents are aggregated given to the candidates standing in an election. The social choice theory has now found its place in the areas of political science and economics and it is used as a fundamental tool in multiple agent systems. Computational social choice theory is a research area dealing with the aggregations of preferences with a group of agents to reach some social objective. Computational social choice deals with the application of methods usually associated with computer science to problems of social choice. There are large number of old cases that shows the work of social choice have engaged people’s attentions for a very long time. Social choice theory as a scientific discipline with sound mathematical foundations came into existence with the publication of the Ph.D. thesis of Arrow KJ [18]. The concept of computational social choice theory and the analysis of methods of voting processes are described. These processes are used to combine the preferences of voters based on number of candidates [19]. The papers used the concept of Computational Social choice theory, Game theory, Congestion game, Preference aggregation, Convergence time to Nash equilibrium and multi-agent system dynamics [15-17]. Some voting rules are also defined which are: Plurality rule, Borda rule, Veto rule and a tie breaking rule called lexicographic rule. According to these rules each alternate wants to get some outcome for being ranked [20]. It is defined that in multi-agent system dynamics [3] it is common to bound every single agent in the system. The authors defines the convergence to Nash equilibria [10] and if the agents restrict their strategies to “best replies” then the convergence is guaranteed because in the best replies only the most favorite candidate will win. The concept of strategic voting has been emphasized in research on Social Choice as great consequence for understanding the relationship between preferences of the voters, and to understand the final outcome of elections. The most commonly used voting rule is the Plurality rule, in which the winner is the candidate who acknowledged the highest number of votes and each voter has one vote. While it is known that no reasonable voting rule is completely resistant to strategic behavior, Plurality has been shown to be particularly inclined, both in theory and in practice [3,21]. This makes the analysis of any election campaign even one where the simple Plurality rule is used a challenging task. As voters may take a chance and counter-speculate, it would be beneficial to have formal tools that would help us to better understand and predict the final outcome. There have been numerous studies related to game-theoretic solution concepts for voting games, and to Plurality respectively [22] model a Plurality voting game where candidates and voters play deliberately. They illustrate all Nash equilibria in this game under the very restricting supposition that the preference area is single peaked. Another exceedingly related work is that of [23], which focuses on prevailing strategies in Plurality voting. We look at the different extreme, considering that the voters have no know-how about the preferences of the others and the do not coordinate their activities. Voters might still attempt to vote strategically which is established on their present data and this can be incorrect. The observation of such circumstances is of special concern to AI, because it tackles the key troubles of multi-agent decision making. The voting model belonging to us is the Plurality voting model in which voters start from some declaration and also the voters can alter their votes later on by noticing the present declaration and the result. The game continues successfully where an individual voter at every time changes his vote [22] design a plurality voting game in which the campaigners and the voters play strategically. A second related work to our work is that of [23] which focuses in plurality strategies on plurality voting [24], invoke a version of strong equilibria. If we consider natural dynamics in plurality voting we adopt that players begin by declaring some initial voting and then continue and alter their vote till nobody is disagree with the present result. We have specified some examples and from these examples we have concluded some observations and results. The examples are performed on two, three and very few in four candidates and the number of voters can vary. The rules which had used in our research are: Plurality, Borda and when there are more than one winners then we use tie-breaking rule Descendo-graphic rule. These rules helped us to find the best solutions of the problems that occur in our area. We have developed a new tie-breaking rule named as Descendo-graphic rule. This rule is used in the case of tie among the winners. According to Descendo-graphic rule the candidate who is loser will also get a chance to win and we have proved this in the analysis of dynamics of voting system through several examples. In previous literature the voters had both complete and incomplete information regarding the preferences whereas in our work the voters have incomplete information of the preferences of the voters, they only know the scores at every state. We have categorized Manipulative and Non-manipulative moves.

**Preliminaries**

**Election: **A formal and planned choice by vote of a person for a political office or other site. The legal process of electing or the aspect of being elected.

**Candidate: **He/She is a person who stood up in a competition in a hope to win.

**Voter: **A person who votes or who has a legal right to vote to his favorite candidate in an election. Voter’s vote is in form of to ranking of candidates.

**Vote: **Vote is the ranking of the candidates according to voter’s preferences.

**True preferences: **True preferences are the true choices of the voters i.e., the preferences given on the basis of priority.

**Declared preferences: **At a state S, a voter has declared preferences different from his true preferences but that which somehow reflects his/her true preferences.

**Switching: **Switching is the mechanism of making changes in the declared preferences of a voter.

The notation which we will use for switching is - >. For Example V1: A>B>C-> B>A>C.

**Notations for switching: **(>) This symbol is used for defining preferences e.g. A>B>C means A is preferred over B, and B is preferred over C. (->) This symbol is used for the transition of the declared preferences of a voter at a state S e.g. ABC->BAC.

**Transition: **Transition means changes occurring at a state. Transition is based on switching of vote to a preferred candidate.

**Example**

• **State:** State is a set of profiles of declared preferences of voters. At a given state a voter have declared preferences according to which candidate is winner by applying a voting rule.

• **Plurality rule:** Plurality rule means how often each alternative is ranked at first place.

• **Borda:** It is a ranked based voting rule. The Borda rule is an appropriate procedure in multi-agent decision making when several alternatives are considered [5]. In the Borda voting rule each voter gives m-1 points to the candidate he/she ranked first, m-2 points to the candidate she ranked second, or in general m-k points to the candidate she ranked k- th. The winner is the candidate who amasses the highest total number of points. This voting rule is used in the National Assembly of Slovenia, and is similar to that used in the Eurovision song contest [21].

**Types of possible manipulation for plurality: **We have divided the moves into two categories i.e., manipulative moves and non-manipulative moves.

**Manipulative moves**

** Existing winner -> New winner:** When the voter switches his vote from the existing winner to another candidate. He will switch because he/she prefers new winner over existing winner.

* Loser -> New winner: *When the voter switches his vote from loser to new winner. The voter moves because there are no chances of loser to win.

**Non-manipulative moves:** Non-manipulative moves can be rational but they don’t change the election outcome.

** Winner -> Loser:** When the voter switches his vote from the winner to loser. Winner to loser move is helpful in increasing the score of the loser if he/she prefers loser over the winner.

* Loser -> Loser: *When the voter switches his vote from loser to loser. The voter moves because he wants to give his vote to his favorite candidate with the hope that his favorite candidate will win in the future.

*Loser-> Existing winner:* In this move the voter switches because there is no chance for his supported candidate to become the winner. This move increases the score of the existing winner and his chances to win again.

**Manipulative moves for Borda rule**

* Loser-> New winner: *In this move the voter switches from loser in order to make a new winner. Voter exchanges the position of his most favorite candidate with the candidate at the highest rank, in this way the score of the candidate increases to become a winner.

* Existing winner-> *New winner: In this move the position of existing winner is exchanged with the new winner. The voter switches because he prefers new winner over existing winner. It can increase/ decrease the score of the winner. So if he can make his desired candidate to be the winner definitely the voter will take this move.

**Non-manipulative moves for Borda rule**

** Loser -> Existing winner:** In this move the voter switches from losing candidate because he knows the loser has no chance to win. In this move the voters exchange the positions of loser with existing winner.

* Loser-> Loser: *In this move the most favorite candidate of the voter is loser. It is exchanging position of one loser to another and sometimes this move is rational. The reason for using this move is that it increases the score of the expected leading candidate.

* Existing winner-> Loser: *This move only increases the score of the loser and decreases the votes of the existing winner but it does not affect the outcome of the election. However this move is not rational.

#### Observations For Plurality Rule

**Example 1**

Let us consider the example for two candidates A and B, are standing for election to determine which candidate should win the election from a given set of alternatives and three voters v1, v2, v3. The true preferences of the voters for the Candidate A, and B are:

1. V1 prefers A over B.

2. V2 prefers B over A.

3. V3 also prefers A over B.

From the **Table 1** it is clear that the candidate A has 2 votes and candidate B has 1 vote. So obviously the candidate A is the winner according to Plurality Rule.

Voters | True Preferences |
---|---|

V1 | A>B |

V2 | B>A |

V3 | A>B |

**Table 1:** The true preferences of the voters.

Voter’s v1, v2, v3 cannot switch because they are with their desired preference so why would they switch because their switching will lead to their dislike candidate to be the winner.

**Conclusion**

We concluded that manipulation is not possible in two candidate case. For two candidates case voters cannot switch as switching to their least favorite candidate is possible but it is not a rational move. There is no incentive for voters to move.

**Example 2 (three candidate case)**

Let us consider three candidates A, B, C are competing in election to determine which candidate should win the election from a given set of alternatives and five voters v1, v2, v3, v4, v5. The true preferences of the voters for the Candidate A, B, and C are :

1. The voter v1 gives the higher priority to the candidate A then B and candidate C is extremely disliked by v1.

True preferences remains the same, voters can switch according to their declared preferences **(Table 2)**. From the above example it has been seen that from the true and declared preferences the Candidate B is only disliked by the v4 and is liked by most of the voters. So it is clear that the most likely winner should be the Candidate B. Let us see that after “manipulation” and switching of votes what happens and who will be the winner.

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | A>B>C | B>A>C |

V2 | B>A>C | A>B>C |

V3 | C>B>A | B>C>A |

V4 | A>C>B | C>A>B |

V5 | B>C>A | C>B>A |

**Table 2:** Three candidate case.

From the **Table 2** that the candidate A has 1 vote, candidate B and candidate C has 2 votes. The candidate B and C are having same votes so we will use tie breaking rule i.e., lexicographic rule.

**Tie-breaking rule (lexicographic rule):** Tie- breaking rule is the one in which one winner is decided from more than one winners. It follows ascending order.

So according to Lexicographic order B is the winner. Let us check the states for each voter and specify some type of moves.

As

A=1

B=2

C=2

**Moves used:**

1. Existing winner to new winner

2. Loser to loser **(Table 3)**

States | Voters | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V1 | V1: B>A>C-> A>B>C |
Existing winner to new winner | A=2, B=1, C=2 | A is the winner according to tie breaking rule |

S2 | V2 | V2: A>B>C-> B>A>C |
Existing winner to new winner | A=1, B=2, C=2 | B is the winner according to tie breaking rule |

S3 | V3 | V3: B>C>A-> C>B>A |
Existing winner to new winner | A=1, B=1, C=3 | C is the winner with highest votes |

S4 | V4 | V4: C>A>B-> A>C>B |
Existing winner to new winner | A=2, B=1, C=2 | A is again the winner according to tie breaking rule |

S5 | V5 | V5: C>B>A-> B>C>A |
Loser to loser | A=2, B=2, C=1 | A is the winner |

**Table 3:** Lexicographic rule.

So there is a tie between candidate A and candidate B at state S5. Again following the Lexicographic order candidate A is considered to be the Winner. Though according to true preferences of voters B is liked by most voters so manipulation can lead to undesirable results and tie breaking rule is important if we follow descedo-graphic rule then B will become winner and no further switching is possible.

**Example 3 (three candidate case)**

Let us consider three candidates A, B, C are competing in election to determine which candidate should win the election from a given set of alternatives and five voters V1, V2, V3, V4, V5. The true preferences of the voters for the Candidate A, B, and C are represented in **Table 4**. True preferences remains the same voters can switch according to their declared preferences. Let us see that after “manipulation” and switching of votes what happens and who will be the winner. From the **Table 4** that the candidate A and B has 2 votes, and candidate C has 1 vote. The candidate A and B are having same votes so we will use tie breaking rule i.e., lexicographic rule.

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | A>B>C | B>A>C |

V2 | B>A>C | A>B>C |

V3 | C>B>A | B>C>A |

V4 | C>A>B | A>C>B |

V5 | B>C>A | C>B>A |

**Table 4:** The true preferences of the voters for the Candidate A, B, and C.

**Tie-breaking rule (lexicographic rule): **So according to Lexicographic order A is the winner. Let us check the states for each voter and specify some type of moves.

A=2

B=2

C=1

**Moves used:**

1. Loser to existing winner

2. Existing winner to new winner

3. Loser to loser **(Table 5)**.

States | VOTERS | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V1 | V1: B>A>C-> A>B>C |
Loser to existing winner | A=3, B=1, C=1 | A is the winner with highest votes |

S2 | V2 | V2: A>B>C-> B>A>C |
Existing winner to new winner | A=2, B=2, C=1 | A is the winner according to tie breaking rule |

S3 | V3 | V3: B>C>A-> C>B>A |
loser to loser | A=2, B=1, C=2 | A is the winner according to tie breaking rule |

S4 | V4 | V4: A>C>B-> C>A>B |
Existing winner to new winner | A=1, B=1, C=3 | C is the winner with highest votes |

S5 | V5 | V5: C>B>A-> B>C>A |
Existing winner to new winner | A=1, B=2, C=2 | B is the winner |

**Table 5:** Loser to existing winner, existing winner to new winner and loser to loser.

So there is a tie between candidate B and candidate C at state s5. Again following the Lexicographic Order candidate B is considered to be the winner. We used descend-graphic rule with same examples as well.

**Example 4 (three candidate case)**

In this example the voters starting from the truthful state and the move we allowed are manipulative move.

Let us consider the example of Plurality rule for three candidates A, B, and C are standing for election to determine which candidate should win the election from a given set of alternatives and voters V1, V2…….. V7. The true preferences of the voters for the Candidate A, B and C are:

1. A prefers B over C

2. B prefers A over C

3. C prefers A over B

4. C prefers B over A

5. A prefers C over B

6. B prefers C over A

7. B prefers A over C

The true and declared preferences of the voters are given in **Table 6**.

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | A>B>C | A>B>C |

V2 | B>A>C | B>A>C |

V3 | C>A>B | C>A>B |

V4 | C>B>A | C>B>A |

V5 | A>C>B | A>C>B |

V6 | B>C>A | B>C>A |

V7 | B>A>C | B>A>C |

**Table 6:** The true and declared preferences of the voters.

A=2

B=3

C=2

C is the winner according to lexicographic rule.

**Manipulative move used: **Lose to new winner **(Table 7)**.

States | Voters | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V3 | V3: C>A>B-> A>C>B |
loser to new winner | A=3, B=3, C=1 | A is the winner according to tie breaking rule |

S2 | V4 | V4: C>B>A-> B>C>A |
loser to new winner | A=3, B=4, C=0 | B is the winner |

**Table 7:** Loser to new winner.

**Conclusion: **When voters start from their truthful preferences then in 3 candidate case switching occur between first and second ranked candidate only.

#### Observations For Borda Rule

**Example for Borda (three candidate case)**

Let us consider three candidates A, B, C are competing in election to determine which candidate should win the election from a given set of alternatives and five voters V1, V2, V3, V4, V5, V6. The true and declared preferences of the voters for the Candidate A, B, and C are represented in **Table 8**.

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | B>A>C | A>B>C |

V2 | C>A>B | A>C>B |

V3 | A>C>B | B>C>A |

V4 | A>B>C | B>A>C |

V5 | C>B>A | B>C>A |

V6 | B>C>A | C>B>A |

**Table 8:** True preferences remains the same voters.

True preferences remains the same voters can switch according to their declared preferences.

From the **Table 8** that the candidate A has got 5 votes, candidate B has 8 votes and candidate C has 5 votes i.e.,

A=5

B=8

C=5.

As B has got highest number of votes so B is the winner.

**Moves used**

1. Loser to existing winner

2. Existing winner to loser **(Table 9)**

States | Voters | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V1 | V1: A>B>C-> B>A>C |
loser to existing winner | A=4 B=9 C=5 |
B is the winner |

S2 | V4 | V4: B>A>C-> A>B>C |
Existing winner to loser | A=5 B=8 C=5 |
B is the winner |

S3 | V5 | V5: B>C>A-> C>B>A |
Existing winner to loser | A=5 B=7 C=6 |
B is the winner |

S4 | V6 | V6:C>B>A-> B>C>A | Loser to existing winner | A=5 B=8 C=5 |
B is the winner |

**Table 9:** Loser to existing winner and existing winner to loser.

Voters V2 and V3 will not switch because they have no reason to switch the candidates as their least preferred candidate will become the winner.

**Example for descendo-graphic rule (with Borda rule)**

Let us consider three candidates A, B, C are competing in election to determine which candidate should win the election from a given set of alternatives and four voters V1, V2, V3, V4. The true preferences of the voters for the Candidate A, B, and C are:

The true and declared preferences of the voters are given in **Table 10**. True preferences remains the same voters can switch according to their declared preferences.

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | A>B>C | B>A>C |

V2 | B>C>A | C>B>A |

V3 | C>A>B | A>C>B |

V4 | A>C>B | C>A>B |

**Table 10:** Descendo-graphic rule.

**Table 10** represents that the candidate A has got 4 votes, candidate B has 3 votes and candidate C has 5 votes i.e.,

A=4

B=3

C=5

As C has got highest number of votes so C is the winner.

**Moves used**

1. Loser to new winner

2. Existing winner to new winner **(Table 11)**

States | Voters | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V1 | V1: B>A>C-> A>B>C |
Loser to new winner | A=5, B=2, C=5 | C is the winner according to tie breaking rule |

S2 | V3 | V3: A>C>B-> C>A>B |
Existing winner to new winner | A=4, B=2, C=6 | C is the winner with highest votes |

S3 | V4 | V4: C>A>B-> A>C>B |
Existing winner to new winner | A=5, B=2, C=5 | C is the winner according to descendo-graphic rule |

**Table 11: **Loser to new winner and existing winner to new winner.

We have designed such a rule that does not follow the linear order so that the other candidates can have chances to win.

**Example (three candidate case)**

Let us consider three candidates A, B, C are competing in election to determine which candidate should win the election from a given set of alternatives and five voters V1, V2, V3, V4, V5. The true preferences of the voters for the Candidate A, B, and C are represented in **Table 12**:

Voters | True Preferences | Declared Preferences |
---|---|---|

V1 | A>B>C | B>A>C |

V2 | B>A>C | A>B>C |

V3 | C>A>B | A>C>B |

V4 | B>C>A | C>B>A |

V5 | A>C>B | C>A>B |

**Table 12: **Sores of candidates A, B, and C.

Sores of candidates are:

A=6

B=4

C=5

A is the winner initially.

**Moves used**

1. Loser to existing winner

2. Existing winner to new winner

3. Loser to new winner **(Table 13)**.

States | Voters | Switching | Type of Move | Scores | Winner |
---|---|---|---|---|---|

S1 | V1 | V1: B>A>C-> A>B>C |
Loser to existing winner | A=7, B=3, C=5 | A is the winner |

S2 | V2 | V2: A>B>C-> B>A>C |
Existing winner to new winner | A=6, B=4, C=5 | A is the winner |

S3 | V3 | V3: A>C>B-> C>A>B |
Existing winner to new winner | A=5, B=4, C=6 | C is the winner with highest votes |

S4 | V5 | V5: C>A>B-> A>C>B |
Loser to new winner | A=6, B=3, C=5 | A is the winner |

**Table 13:** Loser to existing winner, existing winner to new winner and loser to new winner.

V4 will not switch because he has no incentive to move as his move is not rational because the least preference of voter V4 becomes the winner if he switches.

#### Conclusion

The analysis is restricted to limited number of candidates and voters. We have analyzed the dynamics on 2, 3 and 4 candidates and the number of voters can vary. We consider rational moves of the voters. Voters have incomplete set of information, they only know the score of the candidates at every state. While it is known that no reasonable voting rule is completely immune to strategic behavior. Plurality has been shown to be particularly susceptible, both in theory and in practice [3,21]. In two candidates case manipulation is not possible in all rules if the voters starts from their true preferences because the voters cannot switch to their least favorite candidate and if it is possible then this move will not be a rational move because the voters have no incentive to move and they don’t want to see their least favorite candidate the winner. We have analyzed cases of three candidates, so we can say that in this case manipulation is a hazard because it ends into worst results.

It is not necessary that the most likely candidate will be the winner every time, due to manipulation the results can be undesirable. To remove the tie a pre-defined rule is commonly used which states that the winner between a tie will be the first one. But it’s not necessary to always follow the linear order to remove the tie, other than linear orders can also be followed so we have defined our own rule i.e., Descendographic rule which states that the winner will be selected by following the descending order rather than ascending, so that the other candidates have the chances to win in an election.

#### Applications

Voting is a complete model for making collective decisions. Our model is just a preliminary study of analyzing the dynamics on small number of candidates. Applications includes locating the choices from political elections to faculty employment judgments. Other applications may include singing, dance competitions in which the winner is selected from number of participants where decision wishes to be made hastily on the basis of public choice. Our model also fits in search engine criteria in which the web pages with high number of ratings are superior as compare against each of the other web pages for example page1>page2>page3 and so on, this means that page 1 has higher priority than page 2 and page 2 has higher priority than page 3 i.e., page 1 includes websites with high rated websites than page 2 and so on. Our model can also be used for the development of multiagent system [25] and it can be useful for allocation of resources and negotiation.

#### Future Directions

It would be interesting to take on our assumptions and qualify other kind of moves and voting rules that demonstrates best reply. Similar analytic thinking can be accomplished on voting rules other than plurality, borda and our new tie-breaking rule i.e., descendgraphic rule. New voting rules can be developed from such analysis, for example if tie is occurring among the winners then the candidate who is loser for a long period of time, some kind of strategies should be applied to make him the winner.

#### References

- Copeland BJ (2002) Hypercomputation. Minds and machines 12: 461-502.
- Weiss G (1999) Multiagent systems: A modern approach to distributed artificial intelligence.
- List C (2013) Social choice theory. Stanford Encyclopedia of Philosophy.
- Merlin V, Boutilier C, Dorn B, Maudet N (2015) Computational social choice: Theory and applications. Informatik-Spektrum, Springer Verlag. pp: 423-437.
- Turocy TL, Stengel BV (2001) Game theory. CDAM Research Report.
- Arrow KJ (1951) Social choice and individual values. Wiley, New York.
- García-Lapresta JL, Meneses LC (2009) Modeling rationality in a linguistic framework. Fuzzy Sets and Systems 160: 3211-3223.
- Bhattacharyya A, Dey P, Woodruff DP (2016) An optimal algorithm for l1-heavy hitters in insertion streams and related problems.Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp: 385-400.
- Duggan J, Schwartz T (2000) Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Social Choice and Welfare 17: 85-93.
- Xia L, Conitzer V (2010) Stackelberg voting games: Computational aspects and paradoxes. Proceedings of the National Conference on Artificial Intelligence (AAAI), pp: 921-926.
- Forsythe R, Rietz T, Myerson R, Weber R (1996) An experimental study of voting rules and polls in threecandidate elections. Int J Game Theory 25: 355-383.
- http://whois.domaintools.com/dalel-atareeh.org
- Centre for Discrete and Applicable Mathematics (2001) CDAM research report LSE-CDAM-2001-09.
- Raoof, Omar (2013) Game theory for dynamics spectrum sharing cognitive radio. PhD thesis, Burnel University School of Engineering and Design.
- https://www.yumpu.com/en/dspace1.isd.glam.ac.uk
- Saari DG (1990) Susceptibility to manipulation. Public Choice 64: 21-41.
- Brandt F, Conitzer V,Endriss U (2012) Computational social choice multiagent systems. MIT Press.
- Gohar N (2012) Voting dynamics. Proceedings on the International Conference on Artificial Intelligence (ICAI).
- Gibbard A (1973) Manipulation of voting schemes: A general result. Econometrica 41: 587-601.
- Gohar N, Goldberg PW (2013) Potential functions for voting dynamics. Proceedings on the International Conference on Artificial Intelligence (ICAI). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (World Comp).
- Gohar N (2017) Manipulative voting dynamics. Cambridge Scholars Publishing.
- Meir R, Polukarov M, Rosenschein RJS, Jennings NR (2010) Convergence to equilibria in plurality voting. AAAI 10: 823-828.
- Feddersen TJ, Sened I, Wright SG (1990) Rational voting and candidate entry under plurality rule. A J Pol Sci 34: 1005-1016.
- Dhillon A, Lockwood B (2004) When are plurality rule voting games dominance-solvable. Games and Economic Behavior 46:55-75.
- Polborn M, Messner M (2002) Voting on majority rules. Review of Economic Studies 71:115-132.

Citation: Gohar N, Aslam S, Khan M, Qadeer A (2017) Analysis of Dynamics of Voting System for Small Number of Candidates. J Inform Tech Softw Eng 7:210. Doi: 10.4172/2165-7866.1000210

Copyright: © 2017 Gohar N, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.