Voting theory is plagued by seemingly contradictory results, called voting paradoxes. For example, different methods of tallying votes can result in different election results; these voting paradoxes give contradictory answers to the question of what the voting population “really” wants. This paper studies voting paradoxes brought about by considering the effect of dropping one or more candidates in an election after the voting data has already been collected. Dropping a candidate may change the election results for the remaining candidates. This paper adopts an algebraic framework to approach this voting theoretic problem.

Mathematical concepts have aided the progression of many different fields of study. Math is not only helpful in science and engineering, but also in the humanities and social sciences. Therefore, it seemed quite natural to apply my preliminary work with set intersections to voting theory, and that application has helped to focus my thesis. Rather than studying set intersections in general, I am attempting to study set intersections and what they mean in a voting situation. This can lead to better ways to model preferences and to predict which campaign platforms will be most popular. Because I feel that allowing people to only vote for one candidate results in a loss of too much information, I consider approval voting, where people can vote for as many platforms as they like.

In voting theory, simple questions can lead to convoluted and sometimes paradoxical results. Recently, mathematician Donald Saari used geometric insights to study various voting methods. He argued that a particular positional voting method (namely that proposed by Borda) minimizes the frequency of paradoxes. We present an approach to similar ideas which draw from group theory and algebra. In particular, we employ tools from representation theory on the symmetric group to elicit some of the natural behaviors of voting profiles. We also make generalizations to similar results for partially ranked data.

<p>For at least two thousand years, voting has been used as one of the most effective ways to aggregate people's ordinal preferences. In the last 50 years, the rapid development of Computer Science has revolutionize every aspect of the world, including voting. This motivates us to study (1) <bold>conceptually, how computational thinking changes the traditional voting theory</bold>, and (2) <bold>methodologically, how to better use voting for preference/information aggregation with the help of Computer</p><p>Science</bold>.</p><p>My Ph.D. work seeks to investigate and foster the interplay between Computer Science and Voting Theory. In this thesis, I will discuss two specific research directions pursued in my Ph.D. work, one for each question asked above. The first focuses on investigating how computational thinking affects the game-theoretic aspects of voting. More precisely, I will discuss the rationale and possibility of using computational complexity to protect voting from a type of strategic behavior of the voters, called <italic>manipulation</italic>. The second studies a voting setting called <italic>Combinatorial Voting</italic>, where the set of alternative is exponentially large and has a combinatorial structure. I will focus on the design and analysis of novel voting rules for combinatorial voting that balance computational efficiency and the expressivity of the voting language, in light of some recent developments in Artificial Intelligence.</p> / Dissertation

Approval voting is an election method in which voters may cast votes for as many candidates as they desire. This can be modeled mathematically by associating to each voter an approval region: a set of potential candidates they approve. In this thesis we add another level of approval somewhere in between complete approval and complete disapproval. More than one level of approval may be a better model for a real-life voter's complex decision making. We provide a new definition for intersection that supports multiple levels of approval. The case of pairwise intersection is studied, and the level of agreement among voters is studied under restrictions on the relative size of each voter's preferences. We derive upper and lower bounds for the percentage of agreement based on the percentage of intersection.

A k-majority tournament is a directed graph that models a k-majority voting scenario, which is realized by 2k - 1 rankings, called linear orderings, of the vertices in the tournament. Every k-majority voting scenario can be modeled by a tournament, but not every tournament is a model for a k-majority voting scenario. In this thesis we show that all acyclic tournaments can be realized as 2-majority tournaments. Further, we develop methods to realize certain quadratic residue tournaments as k-majority tournaments. Thus, each tournament within these classes of tournaments is a model for a k-majority voting scenario. We also explore important structures specifically pertaining to 2- and 3-majority tournaments and introduce the idea of pseudo-3-majority tournaments and inherited 2-majority tournaments.

A well-known fact about positional election procedures is that its ranking of m alternatives can change when some of the alternatives are removed from consideration—given a positional procedure on each of 2, 3, …, m alternatives and a collective preference order for each distinct subset of the m alternatives. Saari has established that with few exceptions, we can find a voter profile for which the collective preference order for each subset under the according positional procedure is the one given. However, Saari's results do not quantify the likelihood of finding such voter profiles. For small numbers of alternatives, William Gehrlein developed a statistical model to explore the probabilities that particular collective preference orders on subsets of alternatives can occur for large electorates. One goal of this research is to determine whether changes in the collective preference order as alternatives are removed can be considered to be the norm or an outlier for positional procedures. This dissertation extends the research headed by Gehrlein in two directions. One, I generalize his statistical model to explore probabilities for iterated election procedures. Gehrlein's model previously produced results only for three alternatives and in limited cases for four alternatives. I have extended this model to produce results for up to five alternatives, including analysis of instant-runoff voting and runoff elections. Two, Gehrlein's model required specific conditions on the probability distribution of individual voter preferences across the population. I relax this assumption so that for any probability distribution of individual voter preferences across the population, I can explore the probability that a collective preference order is inconsistent with the outcomes when alternatives are removed. These results provide a foundation for discussing the impact of removing alternatives on elections across all large electorates. I also apply these results to two recent United States elections wherein a third-party candidate received a significant share of the votes: the 1992 U.S. Presidential election and the 1998 Minnesota Gubernatorial election. Overall, my research will suggest that as the number of alternatives increases, the likelihood of finding changes in the collective preference order as alternatives are removed will approach one.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.

203 12 Dissertation Summary Dissertation title: Democracy in the Lack of Interest: the Effects of Remote Internet Voting Implementation in the Electoral Process of Selected Countries Name and Surname: Karel Sál Field of Study: Political Science Place of Work: Institute of Political Studies, Faculty of Social Sciences, Charles University in Prague Dissertation Supervisor: PhDr. Petr Jüptner, Ph.D. No. of Pages: 203 No. of Appendixes: 30 Year of Defense: 2016 Keywords: internet voting; remote internet voting; electoral turnout; crisis of democracy; theory of participation; rational choice theory; Estonia; Switzerland; France; Norway; Spain. Abstract: The dissertation thesis named Democracy in the Lack of Interest: the Effects of Remote Internet Voting Implementation in the Electoral Process of Selected States reflects the phenomenon of the last decade - incorporation of new media into the political process. Internet voting is one of the discussed and suggested solutions of the so-called crisis of democracy, which could possibly stop the negative trend of diminishing voter turnout in advanced western democracies. The entire academic debate can be summarized into one question: It is possible, that the way of ballot casting can affect the voter turnout in that scale, that we can recognize a significant-positive...