Project topics and materials
Get Complete Project Material File(s) Now! »
An Introduction to Voting Games
Introduction
In the previous chapters we discussed naive manipulation in which just a coalition of manipulators vote strategically and the others vote sincerely. However, a natural question that arises here is that what will happen if all voters behave strategically and all of them know that too. In this case the strategy of each agent depends on the strategy of other agents. Game theory is a useful tool in interactive decision theory. The cooperation and conflict of self-interested and autonomous agents can be modelled mathematically in the game-theoretic study of voting systems. Self-interested agents do not necessarily want to hurt each other, or even that they care only about themselves. Instead, it means that each agent has his own description of which states of the world he likes [76]. This can include good or bad things happening to the other agents and he tries to bring about these states of the world. This analysis can be considered for two different purposes: as a mechanism designer for analyzing the behaviour of people in the system and us ing those information for designing the system, or as a player for finding the best response against the action of the other players. From one perspective, games are either simultaneous or sequential. We are going to discuss simultaneous voting games in which voters act simultaneously. If voters do not play simultaneously, we have a sequential game. Another way of categorizing games is to divide them
to cooperative and non-cooperative. In non-cooperative game theory the basic modelling unit is the individual (including his beliefs, preferences, and possible actions). In cooperative voting games, players are able to form binding commitments. We are going to study the non-cooperative models of voting games.
Voting game
Definition 3.1. A normal or strategic form game consists of:
• N, a finite set of players, • For each player i ∈ N, a finite set of pure strategies Si, • For each player i ∈ N, a payoff function ui that specifies a utility value for each profile of pure strategies (s1,…,si,…,sn). The range of this function is normally the set of real numbers, where the number represents a cardinal utility. However, in our model, the payoff function is the ordinal utilities given by the voters’ preferences of that profile. In voting games, the set of players are voters, states, special interest groups, or politicians. Each player’s action is his vote or decision, and his strategy deter mines his action. One kind of strategy is to select a single action and play it. Such a strategy is called pure strategy. Players could also follow another (less obvious) type of strategy which is called mixed strategy: randomizing over the set of possible strategies according to some probability distribution. Note that pure strategy is a special case of mixed strategy. A dominated strategy is a strategy for which there is some other strategy that is always better whatever the other players are doing . A strategy is strictly dominant when no matter how the other players may play, it is the best strategy. For example, in elections with 3 candidates and approval voting, the dominant strategy is to vote for the most desirable element and voting for the least desirable candidate is dominated [77]. A game is dominance solvable if iterated removal of dominated strategies ends in a unique equilibrium which is a reasonable guess for what will happen if we have rational players and complete information [78].
Definition 3.2 (Nash equilibrium). A Nash equilibrium is a list (profile) of strategies of all players, from which no player is willing to deviate unilaterally. In other words, the profile (s∗ 1,…,s∗ N) is a Nash equilibrium if ∀i ∈ Nand ∀si :ui(s∗ 1,…,s∗ i,…,s∗ N) ≥ ui(s∗ 1,…,si,…,s∗ N)
Theorem 1 (Nash Theorem). At least one (mixed strategy) Nash equilibrium exists in a non-cooperative game with a finite set of actions.Nash equilibrium is a stable situation when there is no voter who has motivation to deviate unilaterally. If a strictly dominant strategy exists for one player , that player will play that strategy in each of the game’s Nash equilibria.
A voting rule is strategy-proof if for all possible profiles of preferences, “everyone votes sincerely” is a Nash equilibrium. In other words, if all voters behave sincerely, no voter benefits by being insincere. However, as we discussed in Chapter 1, the Gibbard-Satterthwaite theorem [7, 8] shows that for each nondictatorial social choice function allowing unrestricted preferences of voters over m alternatives (m ≥ 3) and such that each alternative can win in some profile, there always exists a profile which is unstable. In other words, in the voting game with ordinal utilities given by the voter preferences of that profile, the strategy where all voters express their sincere preferences may not be a Nash equilibrium. Therefore, there exists at least one strategy profile where one voter has incentive to deviate unilaterally by expressing an insincere preference.Strategic voting is clearly a question of game theory. However, it has still been little studied from this viewpoint, perhaps since its main questions go beyond the Nash equilibrium concept (which applies only to individual manipulation). So far most of the studies in the area of computational voting game are dealing with
the cooperative models of coalitional voting games or the complexity analysis of relevant solution concepts (e.g. Nash equilibrium [79]) such as, exploring the voting power of coalitions in weighted voting games (e.g. weighted threshold games) [80, 81, 82], the compact representation of such games or studying the complexity of the core and Banzhaf and Shapley values [83].
A start has been made in filling the gaps between that case and the classical game theory situation of full common knowledge [75]. The game-theoretic study of strategic manipulation is discussed in [84, 85, 86, 87, 88, 89]. The aims and objectives of these papers are to define a proper model for a voting game and to find the equilibrium outcome. Beside Nash equilibrium, other solution concepts are studied in this context such as correlated equilibrium [90] and regret minimization [91].
Correlated equilibrium as a signalling device tells each player about the strategy that he should choose (it gives a joint probability distribution over the set of out comes). However, they are not informed about the outcome of the experiment, and they may choose to follow or not according to their utility function. Regret minimization is a relatively new solution concept. In this solution concept, each voter does not know about the other players’ actions and he just tries to choose a
strategy that ensures that he has done reasonably well compared to the best possible action without paying attention to the other players’ actions. In fact the regret of each action represents the utility difference of the best possible outcome and that action. The quality of solution concepts has been measured in some papers by the price of stability and the price of anarchy e.g. in [92, 93]. The price of stability and anarchy are the best and the worst possible ratio between the cost of an outcome at Nash equilibrium and that of an optimal one.Predicting the result of the game is challenging, as voting games can have many equilibria. Therefore, we are interested in studying how we can omit some of the possible equilibria and reach a unique equilibrium. We concentrate on best reply voting games and study the convergence of dynamic process in Chapter 4. We study the factors that influence this convergence.One important factor which has significant effect on the strategies of players invoting games is the available amount of information. Complete information models where the preferences are common knowledge among the voters are more common in this area. However, recently there are more papers studying partial information models such as [94, 95, 96, 97]. Poisson model for population uncertainty is discussed in [98].
We study the effect of information by introducing a new model of voting games in Chapter 5. In this model voters achieve partial information via a series of pre-election polls, and also each voter has some uncertainty about the announced result of polls. We study the different distributions of uncertainty for plurality voting games.
Best Reply Dynamics for Scoring Rule
Introduction
The strategic misrepresentation of a voter’s true preferences, as a way of obtaining an outcome preferable to that which would be expected by voting sincerely, dates back thousands of years. The amount of information available to voters and their ability to communicate influence voter’s behaviour greatly. Here we consider the case in which all players behave strategically, but coalitions are not formed. The natural setting then is that of a normal form game with ordinal preferences, or more generally a game form. The voting games of this type have enormously many Nash equilibria and are not necessarily dominance solvable [87]. Eliminating dominated strategies is not also helpful because typically far too many equilibria remain for the Nash equilibrium to be a credible prediction. Other refinements such as strong and coalition-proof Nash equilibria may not always exist [99]. One natural direction of enquiry is to consider best-reply dynamics, where players take turns in moving myopically in response to previous moves by other players (these moves are pure strategies of the associated game). For many games this process leads to convergence (neces sarily at a pure Nash equilibrium). It can also be interpreted in the voting context as a method reaching consensus, and is in fact used in this way in some applications such as Doodle (for scheduling). According to Fudenberg and Levine [100], in some cases, most learning models do not converge to any equilibrium and just coincide with the notion of rationalizability, but if best-reply dynamics converges, it necessarily finds a NE. Therefore, the question that arises here is in which cases these best-reply dynamics converge for voting games. To our knowledge, in the voting context the first paper to discuss best-reply dynamics is [101], which concentrated on the plurality rule. The authors considered the effect of initial state, tie-breaking rule, the players’ strategy and weights on convergence. The results show that this definition of best reply, even for such a rule which restricts voter expression severely, is too general to guarantee convergence. Sequential and simultaneous voting games for plurality with abstention have been discussed in [88]. For the sequential case, they provide a complete analysis of the setting with two candidates, and show that for three or more candidates the equilibria of sequential voting may behave in a counterintuitive manner. The strategy of each voter depends strongly on the information he has about the other players’ preference orders.
Contents
I-Strategic Manipulation
1. The Manipulability of Voting Rules
1.1 An introduction to computational social choice
1.2 Basic terminology
1.3 Strategic manipulation
1.4 A new measure of manipulability of voting rules
1.5 Power measures and manipulability measures
1.6 Comparison with existing literature
1.7 Extensions and future work
1.8 Appendix: details from our studies with m = 3
2. The Probability of Safe Manipulation
2.1 Introduction
2.2 Definitions and basic properties
2.3 Algorithms and polytopes
2.4 Numerical results
2.5 Further discussion
II-Voting Games
3. An Introduction to Voting Games
3.1 Introduction
3.2 Voting game
4. Best Reply Dynamics for Scoring Rules
4.1 Introduction
4.2 Problem description
4.3 Best reply dynamics
4.4 Antiplurality
4.5 Plurality
4.6 Counterexamples and interesting phenomena
4.7 Conclusion and future directions
5. Coordination via Polling in Plurality Voting Games under Inertia
5.1 Introduction
5.2 Game model
5.3 Game dynamics
5.4 Equilibrium results for some special cases
5.5 Conclusion and future directions
6. Conclusions
6.1 Summary
6.2 Future directions
GET THE COMPLETE PROJECT
Strategic Manipulation in Voting Systems
