Manipulative Voting Dynamics (PDF)

One of the most actively growing subareas in multi-agent systems is computational social choice theory, which provides a theoretical foundation for preference aggregation and collective decision-making in multi-agent domains. It is concerned with the application of techniques developed in computer science, including complexity analysis and algorithm design, in the study of social choice mechanisms, such as voting. It seeks to import concepts from social choice theory into Artificial Intelligence and computing. People often have to reach a joint decision despite conflicting preferences over the alternatives. This joint decision can be reached by an informal negotiating process or by a carefully specified protocol. Over the course of the past decade or so, computer scientists have also become deeply involved in this study. Within computer science, there is a number of settings where a decision must be made based on the conflicting preferences of multiple parties. The paradigms of computer science give a different and useful perspective on some of the classic problems in economics and related disciplines. A natural and very general approach for deciding among multiple alternatives is to vote on them. Voting is one of the most popular ways of reaching common decisions. As such, the study of elections is an area where fields such as computer science, economics, business, operations research, and political science can be brought together. Social choice theory deals with voting scenarios, in which a set of individuals must select an outcome from a set of alternatives. This book focuses on convergence to pure strategy Nash equilibria in plurality voting games and a number of other positional and non-positional scoring rules. In such games, the voters strategically choose a candidate to vote for, and the winner is determined by the plurality (or other) voting rules. Voters take turns modifying their votes; these manipulations are classified according to the way in which they affect the outcome of the election. The focus is on achieving a stable outcome, taking strategic behaviour into account. A voting profile is in equilibrium, when no voter can change his vote so that his more preferable candidate gets elected. The book investigates restrictions on the number of iterations that can be made for different voting rules, considering both weighted and equi-weighted voting settings.