1 Introduction

Artificial intelligence (AI) is the branch of computer science. One of the new areas explored in AI is multi agent system., that analyzes interaction between multi agents. A multi-agent system (MAS) is a computerized system composed of multiple interacting intelligent agents within an environment. Multi-agent systems can be used to solve problems that are complex or impossible for an individual agent Weiss (1999). The branch of mathematics concerned with the analysis of strategies for dealing different situations where the result of one player depends on the result of others. In multi agent systems, it is of essential importance to be able to aggregate the preferences of multiple agents in order to achieve their joint goal even though their individual beliefs may differ over the alternatives (candidates). Other actively growing subareas explored in multi-agent systems is computational social choice theory. It provides in multi-agent domains theoretical foundation for preference aggregation and collective decision-making. Computational social choice is concerned with the application of techniques that developed in computer science, such as complexity analysis or algorithm design, or to the study of social choice mechanisms, such as voting. Social choice theory examines many kinds of multi-person decision-making problems. 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 (Xia and Conitzer 2010). But the important questions that arises in the mind are: How can a group of individuals choose a winner from the given set of candidates? What will be the voting system? How a collective decision can arrive 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 (List 2013). The study of game theory is about decision making where different players make their choices and that affect the preferences of other players. It is based on a set of tools that have been developed to assist with the modelling and analysis of individual, independent decision makers (Omar and Al-Raweshidy 2013).

Voting is a well-studied method of preference aggregation, in terms of its theoretical properties, as well as its computational aspects (Gohar and Goldberg 2013). Voting enables a group of agents from a set of candidates to make a joint choice. Each agent can give report of her preferences to the candidates. To make the result better to them a subset of agent reports their preferences increasingly (Xia et al. 2009). A good social choice function represents the will of the people. One major issue in voting is manipulation. Manipulation in voting is considered to be any situation in which a voter reveals false preferences in order to improve the outcome of the election. When voters hide their true preferences and switch based on their declared preference to support the other candidate or misrepresentation of their true preferences. Most of the previous work focuses on plurality voting, the best-known voting system, and one that is known to be susceptible to manipulation. Naamani-Dery et al. (2015) showed the low impact of manipulation on final outcome in practice. The study of manipulation with iterative behavior is important because it has been proved by Gibbard Satterthwaite theorem that all reasonable voting rules are susceptible to manipulation (Gibbard 1973; Satterthwaite 1975). Duggan and Schwartz (2000) has generalized the Gibbard Satterwaite theorem.

Plurality system electoral process in which the candidate who’s gains more votes than any other candidate is elected. It is distinguished from the majority system, in which to win a candidate must receive more votes than all other candidates combined. In plurality voting the voters will announce some truthful preferences but if they see the result then the voter will switch and change their true preferences. The voters can play a game strategically (Meir et al. 2010). Suppose that voter have a complete knowledge of the reported preferences of other voters. The voters can manipulate based on their true/declared preferences. Voters can change their votes after observing the current state and result. At the same state if the voters can’t affect the result, they simply keep his current reported preference. When no voters has any objections the process ends and the result is set by the final state (Gohar and Goldberg 2013). The score vector for the plurality rule is (1,0…0). Hence, the cumulative score of an alternative equals the number of voters by which it is ranked first. The score vector for the anti-plurality rule which is also called veto is (1…1, 0). As a consequence, it chooses those alternatives that are least-preferred by the lowest number of voters. Let A, B and C are the ranking of candidates, so voter can vote both A and B but not to C. If A, B and C are his true preferences. One possibility is an iterative process in which, after everyone initially votes, participants may change their vote’s one voter at a time. A social choice function contain list of peoples ranked favorites and output a single choice. This technique explored in previous work, converges to Nash equilibrium when Plurality voting is used, along with a tie-breaking rule that chooses a winner according to a linear order of preferences over candidates. Here consider both limitations of the iterative voting method as well as expanding upon it. The significance of tie-breaking rules has been shown in literature that when using a general tie-breaking rule, no scoring rule (nor Maximum) iteratively converge. However, using a restricted tie-breaking rule such as the linear order rule does not by itself ensure convergence. The results show that many scoring rules (such as Borda) do not converge regardless of the tie breaking rule.

Plurality rule means how often each alternative is ranked at first place (Xia and Conitzer 2010). 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.

$$\begin{array}{*{20}c} 5 &\quad 3&\quad 2\\ {\text{A}} &\quad {\text{B}} &\quad {\text{C}} \\ {\text{B}} &\quad {\text{A}} &\quad {\text{A}} \\ {\text{C}} &\quad {\text{C}} &\quad {\text{B}} \\ \end{array}$$

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 (Xia and Conitzer 2010).

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.

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 (Xia and Conitzer 2010). He will not give vote to C because C is his least favorite.

The Borda rule is an appropriate procedure in multi-agent decision making when several alternatives are considered (García-Lapresta and Meneses 2009). 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 (Bhattacharyya et al. 2016).

Example below shows that Borda works like plurality in 2 candidate’s case. 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

Lexicographical rule has been used extensively in literature. We introduced the concept of 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.

In iterative voting the voting rules and voters preferences are fixed. Voters are strategic and are allowed to change their vote one at a time after observing the temporary result. Consider natural dynamics in iterative games. Meir et al. (Meir et al. 2010) used the concept of iterative voting for convergence. All participants vote and one voter at a time can change his vote to change the election outcome in his favor. When equilibrium is reached then this iterative procedure is stopped, when no one player wants to change their vote. Various online websites used to coordinate dates for events, a similar procedures will be seen in action such as www.doodle.com following an initial vote, each participants can change their vote. Clearly, iterative voting rules are more naturally suited to a relatively small number of players, or an especially close election, as players change their choices one at a time. So Meir et al. (Meir et al. 2010) showed that using plurality rule with deterministic tie breaking rule that are using fixed linear order on candidates to break the ties, the iterative vote converges to a Nash equilibrium when voters always give a best response possible to current situation. When using better-reply strategies (in its place of best-replies) convergence is not guaranteed or also when voters are weighted (Lev and Rosenschein 2012).

1.1 Problem statement

According to Gibbard–Satterthwaite theorem manipulation occurs in every voting system (Gibbard 1973). We have used the concept of iterative voting for plurality and borda rule, and for tie breaking the rule is lexicographic that is used in the literature (Gohar 2013, 2017; Gohar and Goldberg 2013) 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 and the voters have knowledge about the scores of candidates only. 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., voters are short sighted and take short term decisions based on incomplete information. By manipulation the scores of the candidates’ changes. 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. By using these tie-breaking rules we select the winner in case of tie. We have categorized Manipulative and Non-manipulative moves.

2 Related work

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 Kenneth J. Arrow in 1951 (Arrow 1951).

The concept of Computational Social Choice theory and the analysis of methods of voting processes are describe in (Brandt et al. 2012). These processes are used to combine the preferences of voters based on number of candidates. The concept of Computational Social choice theory, Game theory, Congestion game, Preference aggregation, Convergence time to Nash equilibrium and multi-agent system dynamics are described in (Gohar 2013, 2017; Gohar and Goldberg 2013; Meir et al. 2010). The notion of strategic voting is highlight in research on social choice to understand the relationship of candidates and the final result. Voters may speculate and counter speculate we must have a formal tool that helps us to understand the final result. Plurality is the most widely used voting rules (Meir et al. 2016). In iterative voting, it is assumed that rather than simply finding the election outcome, voters behave strategically (Farquharson 1969). The convergence to Nash equilibria has been shown in (Turocy 2001) and if the agents restrict their strategies to “best replies” then the convergence is guaranteed.

There have been numerous studies related to game-theoretic solution concepts for voting games, and to Plurality respectively. Feddersen et al. (1990) 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 (Dhillon and Lockwood 2004), which focuses on prevailing strategies in Plurality voting (Feddersen et al. 1990) design a plurality voting game in which the campaigners and the voters play strategically. A second related work to our work is that of (Dhillon and Lockwood 2004) which focuses in plurality strategies on plurality voting (Polborn and Messner 2002), 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. Works in iterative voting can be split into two categories: the convergence to equilibrium point for iterative voting process (e.g. Rabinovich et al. 2015), and finding the restricted conditions that guarantee the convergence of iterative voting dynamics (e.g. Gohar 2017; Annemieke and Endriss 2012; Obraztsova et al. 2015; Grandi et al. 2013; Meir et al. 2014).

The focus of previous work is on convergence of strategic behavior to a decision where no voters want to move away. Consider a scenario that the voters cannot classify their actions, but are allowed to change their votes when they observe the result. The study of plurality voting rules and condition under which this game is guarantee to converge to Nash equilibrium is important. While it is known that no reasonable voting rule is completely protected to strategic behavior. Plurality has been shown to be particularly vulnerable both in theory and in practice. There are many studies that apply game theoretic solution concept to voting games and also to plurality in particular. Recent work on iterative voting is based on uncertainty, truth-biasedness, or voter are non-myopic, or some other restrictions that diverge from the standard notion of better reply in games (Gohar 2013, 2017; Annemieke and Endriss 2012; Obraztsova et al. 2013; Meir 2015; Meir et al. 2014). The outcome of such dynamics are not necessarily be Nash equilibrium as if some restrictions are removed, voters would still have incentive to change his vote at a particular state. Meir et al. (Meir et al. 2017) exclusively focused on myopic better and best reply dynamics that if converge leads to Nash equilibrium. The work by Mao et al. (Mao et al. 2012) compared the performance of voting strategies for aggregating people’s ranking of solutions to optimization problems. They did not study the effect of computer agents using different voting strategies on people’s behavior. Forsythe et al. (Forsythe et al. 1996) studied the effect of different voting rules on people’s voting strategies in three-candidate elections in which a single candidate is elected with full information about voters’ preferences. Convergence of better reply dynamics in iterative voting for particular voting rules has been studied extensively in the computational social choice literature. To investigate the role of knowing other players’ knowledge about preferences of other voters, Chopra et al. (Chopra et al. 2004) examined iterative voting with plurality and showed the effects of limiting a player’s knowledge of the other players’ preferences. Another interesting model, proposed in (Myerson and Weber 1993), has assumed that voters have some knowledge of those candidates who has chances of winning (e.g., based on pre-election polls). They found a Nash equilibrium for scoring rules, this however, does not mean that every election results in an equilibrium. However, one of the limitations of many of the papers mentioned above is that they assume some player knowledge of other players’ preferences. Meir et al. (Meir et al. 2010) assumed that every voter knows the preferences of the others; on the contrary, we assume that each player only knows the scores of candidates at each state, and voters are not aware of other voters’ preferences. Hence, voters are myopic; they only think of changing their vote so as to improve the current outcome of election, they do not take into account future steps by other voters.

2.1 Contribution

We consider scenarios where voters cannot coordinate their actions and have incomplete information about the preferences of other voters, but are allowed to change their vote after observing the current outcome, as is often the case both in offline committees and in online voting. Much attention has been given in the game theory literature to the question of convergence, and several notions of convergence have been defined. Specifically, we are interested in identifying restrictions or types of moves under which such iterative voting process can converge for Plurality and Borda and also what are the properties of the attained outcome. We have analyzed the dynamics for small number of candidates for different types of manipulative and non-manipulative moves. Descendo-graphic tie breaking rule is used in case of tie along with lexicographic rule. We ask is there an impact of manipulation on the final outcome with tie breaking rules?

3 The model

figure a

We build upon the basic notations and definitions of Meir et al. (2010) and Gohar (2017).

There is a set C of m alternatives (or candidates), and a set V of n strategic agents, or voters. let A be the group of all possible preference orders over C. Every voter vi ∈ V has some element in A which is its true, “real” value, let’s suppose we mark it as αi. An election is a formal and planned choice by vote of a person for a political office or other site. A candidate is a person who stood up in a competition in a hope to win. A voter votes or who has a legal right to vote to his favorite candidate in an election. Voter’s vote is in form of ranking of candidates. Vote is the ranking of the candidates according to voter’s preferences. There are two kind of preferences.

3.1 True preferences

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

3.2 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 is the mechanism of making changes in the declared preferences of a voter. The notation used for switching is → . For Example, V1: A > B > C → B > A > C.

  • (>) 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.

By transition we mean changing of a state. Transition is based on switching of vote to a preferred candidate. State is a set of profiles of declared preferences of voters. At a given state a voter has declared preferences according to which candidate is winner by applying a voting rule.

A voting rule is a function f: An → 2C\∅.

There are many known voting systems; one of the category is the family of scoring rules. A scoring rule is a voting rule that uses a vector (α1, α2,…,αm−1,0) ∈ Nm where αi ≥ αi+1. Each voter gives α1 points to its first rank, α2 points to the second, and so on. The candidates with the highest scores are the winners.

  1. 1.

    Plurality: Rule Plurality rule means how often each alternative is ranked at first place with scoring vector (1,0,0, … 0) a point is only given to the most preferred candidate.

  2. 2.

    Borda: It is a ranked based voting rule. The scoring vector is (m − 1, m − 2,…,2, 1, 0) candidate gets score according to the ranked preferences of voters.

The Borda rule is an appropriate procedure in multi-agent decision making when several alternatives are considered (Xia and Conitzer 2010). 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 (Forsythe et al. 1996).

3.3 Types of possible manipulation for plurality

We have divided the moves into two categories i.e. manipulative moves and non-manipulative moves.

3.3.1 Manipulative moves

Manipulative moves are rational moves because it changes the outcome of the election. A voter switches his support to his preferred candidate to make a new winner.

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.

3.3.2 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.

3.4 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.

New 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.

3.5 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.

4 Observations for plurality rule

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

  1. 1.

    V1 prefers A over B.

  2. 2.

    V2 prefers B over A.

  3. 3.

    V3 also prefers A over B.

The true preferences of the voters are given below.

Voters

True Preferences

V1

A > B

V2

B > A

V3

A > B

From the above table 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.

Voter’s v1, v2, v3 cannot switch because they are with their desired preference and changing preferences will lead to their dislike candidate to be the winner.

4.1 Conclusion

We concluded that manipulation is not possible in two candidate case if voters start from truthful state. Switching to dislike candidate is not a rational move. Hence, there is no incentive for voters to switch.

4.2 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:

The voter v1 gives ranking to the candidate A, B and then C, that shows C is disliked by v1. Rest of the voters ranking are given in the table below.

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

True preferences remain the same, voters switch according to their declared preferences. 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 is B. Let us see that after “manipulation” and switching of votes what happens and who will be the winner.

From the above table that the candidate A has 1 vote, candidate B and candidate C has 2 votes. Both candidate B and C are winners and having same votes so we will use tie breaking rule i.e. lexicographic rule. It follows ascending order.

According to lexicographic rule B, is the winner. Let us check the states for each voter and specify some type of moves. At initial state, the scores of candidates are A = 1, B = 2, C = 2. Let’s suppose we allow the following moves.

  1. 1.

    Existing winner to new winner.

  2. 2.

    Loser to loser.

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


So there is a tie between candidate A and candidate B at state S5. Again following the Lexicographic order, 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 descendo-graphic rule then B will become winner and no further switching is possible, all voters switched from their declared preferences towards truthful state.

4.3 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:

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

From the above table 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. A is the winner as per rule. Let us check the states for each voter and specify some type of moves. At initial state, scores are A = 2, B = 2 and C = 1. Moves we consider in this example is

  1. (1)

    Loser to existing winner

  2. (2)

    Existing winner to new winner

  3. (3)

    Loser to loser.

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


So there is a tie between candidate B and C at state S5. Again following the lexicographic order candidate B is considered to be the Winner. Same behavior of moving from declared to truthful state has been observed here.

4.4 Example 4 [three candidate case]

In this example the voters starting from the truthful state and moves are manipulative moves. Let us consider the example of Plurality rule for three candidates A, B, and C 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. 1.

    A prefers B over C

  2. 2.

    B prefers A over C

  3. 3.

    C prefers A over B

  4. 4.

    C prefers B over A

  5. 5.

    A prefers C over B

  6. 6.

    B prefers C over A

  7. 7.

    B prefers A over C

The true and declared preferences of the voters are given below.

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

At initial state the scores are A = 2, B = 3 and C = 2, C is the winner according to lexicographic rule. The Manipulative move consider here is Loser to new winner move.

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

4.5 Conclusion

When voters start from their truthful preferences then in 3 candidate case switching occurs between first and second ranked candidates only. From the truthful state only those voters will make a manipulative move who dislike the current winner and score of winning candidate increases with each move, that is a guarantee of convergence.

5 Observations for Borda rule

5.1 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 six voters V1, V2, V3, V4, V5, V6. The true and declared preferences of the voters for the Candidate A, B, and C are:

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

From the above table 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 and C = 5, B is the winner. Let’s consider the following moves

  1. 1.

    Loser to existing winner

  2. 2.

    Existing winner to loser

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

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

5.2 Example for Descendo-graphic tie breaking (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 are V1, V2, V3, V4. The true preferences of the voters for the Candidate A, B, and C are:

The true and declared preferences of voters are given below.

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

True preferences remain the same voters switch according to their declared preferences. From the above table 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 and C = 5, as C has got highest score so C is the winner. Moves used are

  1. (1)

    Loser to New winner

  2. (2)

    Existing winner to New winner

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

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

5.3 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:

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

Scores of candidates are A = 6, B = 4 and C = 5, A is the winner initially. Moves are

  1. (1)

    Loser to existing winner

  2. (2)

    Existing winner to new winner

  3. (3)

    Loser to new winner.

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

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

6 Conclusion

The analysis is restricted to limited number of candidates and voters. We have analyzed the dynamics on two and three 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 (Forsythe et al. 1996; Saari 1990). In two candidates case manipulation is not possible in all rules if the voters start 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 manipulation 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. When voters start from their truthful preferences then in 3 candidate case switching occurs between first and second ranked candidates only. From the truthful state only those voters will make a manipulative move who dislike the current winner.

To remove the tie a pre-defined rule is commonly used which states that in case of tie, the winning candidate will be the first one in sequence. But it’s not necessary to always follow the linear order to resolve the tie, other than linear orders can also be followed so we have defined our own rule i.e. Descendo-graphic 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.

6.1 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. Iterative voting 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. It can also be used for the development of multi-agent system (http://dspace1.isd.glam.ac.uk) and it can be useful for allocation of resources and negotiation.

Plurality and Borda are most popular voting rules, so the analysis maintains its applicability. Moreover, the common usage of iterative processes in real life may help explain the prevalence of these voting rules.

Let A and B are two candidates and voters’ preferences are

Voters

True Preferences

Declared Preferences

V1

A > B

A > B

V2

B > A

B > A

V3

A > B

B > A

V4

B > A

B > A

V3 switched to change his support from B to A to make A winner. The example shows A is the most deserving winner. So iterative voting can lead to desirable outcome.

Another interesting question raised by Meir is: is the iterative process leading the society to a socially good outcome?

In the real world iterative vetoing is used in various situations, such as elimination decisions in various “reality shows” (e.g., American Idol etc.). As they usually use a single judge’s preferences to break ties, it is indeed linear-order tie-breaking. Iterative process not only happens in smaller groups (e.g., a group of friends choosing a restaurant, or using event coordination sites, such as Doodle), but can also be used to model larger-scale elections, where people’s knowledge of the state of the election comes from polls, according to which they adapt their vote (some simulation-based support for such a view, in a slightly more complex model, was shown in Meir et al. 2014). A voter in a plurality election (e.g., for U.S. Congress or U.K. Parliament) that supports a party that has no chance of winning may switch their vote to the major party that they support the most, in order to influence the election outcome. Looking at the set of states that are reachable from truthful state, using this dynamic, gives us a set of plausible outcomes. These states are far fewer than the number of Nash equilibria, and may give us a better understanding of realistic outcomes. However, a good understanding of how iterative voting shapes the outcome, whether the population of voters consists of humans or artificial agents, is still under way.

Iterative voting may have interesting applications in the development of recommender systems which need to collect information in an iterative way, such as in the work of Dery et al. (2010). Doodle is a popular on-line system and an example of iterative voting, used to select a time slot for a meeting by considering the preferences of the participants. Each participant can approve as many time slots as he/she wants, and the winning time slot is the one with the largest number of approvals. At any point, each participant can modify her vote in order to get a better result, and this can go on for several steps.

6.2 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. descendo-graphic 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.