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.

L'objet de cette thèse est l'étude des aspects algorithmiques du vote par approbation. Il s'agit principalement d'une étude théorique des enjeux computationnels soulevés par le vote par approbation dans des contextes de décisions variés. Cependant, j'étudie aussi des questions plus proches de la théorie classique du choix social et je conduis de brèves études expérimentales.Dans un premier temps, l'étude se porte sur une famille générale de règles de vote pour les élections de comités et les référendums multiples à l'aide du vote par approbation. Dans un second temps, je porte mon attention sur un contexte plus général, le vote par approbation sur domaines combinatoires en se basant sur des préférences conditionnelles. Finalement, je me place dans le cadre du vote avec préférences incomplètes pour étudier les problèmes de vainqueurs possibles et nécessaires dans le vote par approbation. / The subject of this thesis is the study of computational aspects of approval voting. Most of the works are theoretical results about computational issues raised by approval voting, in many different settings. However, I also study some questions that are more related to classical choice theory, and some problems are investigated through experimental analysis.Firstly, I study a general family of rules for approval voting in the context of committee elections and multiple referenda. Secondly, I focus on a more general setting, approval voting in combinatorial domains, based on conditional preferences. Finally, I consider approval voting in the context of incomplete preferences, to study the possible and necessary winner problems.

In this thesis, a particular class of agent is singled out for examination. In order to provide a guiding metaphor, we speak of control room agents. Our focus is on rational decision- making by such agents, where the circumstances obtaining are such that rationality is bounded. Control room agents, whether human or non-human, need to reason and act in a changing environment with only limited information available to them. Determining the current state of the environment is a central concern for control room agents if they are to reason and act sensibly. A control room agent cannot plan its actions without having an internal representation (epistemic state) of its environment, and cannot make rational decisions unless this representation, to some level of accuracy, reflects the state of its environment. The focus of this thesis is on three aspects regarding the epistemic functioning of a control room agent: 1. How should the epistemic state of a control room agent be represented in order to facilitate logical analysis? 2. How should a control room agent change its epistemic state upon receiving new information? 3. How should a control room agent combine available information from different sources? In describing the class of control room agents as first-order intentional systems hav- ing both informational and motivational attitudes, an agent-oriented view is adopted. The central construct used in the information-theoretic approach, which is qualitative in nature, is the concept of a templated ordering. Representing the epistemic state of a control room agent by a (special form of) tem- plated ordering signals a departure from the many approaches in which only the beliefs of an agent are represented. Templated orderings allow for the representation of both knowledge and belief. A control room agent changes its epistemic state according to a proposed epistemic change algorithm, which allows the agent to select between two well-established forms of belief change operations, namely, belief revision and belief update. The combination of (possibly conflicting) information from different sources has re- ceived a lot of attention in recent years. Using templated orderings for the semantic representation of information, a new family of purely qualitative merging operations is developed. / School of Computing / Ph. D. (Computer Science)

Made available in DSpace on 2016-04-26T20:48:55Z (GMT). No. of bitstreams: 1 Bruno Beltrame.pdf: 550537 bytes, checksum: dd98c2c17868e3f8b2d425a2f8ed1be8 (MD5) Previous issue date: 2009-05-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The aim of this dissertation is to inquire in what sense it is reasonable to locate in Kenneth Arrow s social choice theory and in John Rawls theory of justice the two main theoretical roots of Amartya Sen s capability approach. It will be argued that Arrow s social choice theory had the role of revealing the main deficiencies of the welfare economics theory. Thus, Arrow s analysis points the limitations to be fulfilled in order to arrive at satisfactory theory of social choice indicating, in this sense, the paths to be pursued. In the same manner, it is argued that Ralws theory of justice provided important elements that inspirated certain ethical positions present in Amartya Sen s thought, which appear in his approach to the problem of social choice. To conclude, the main features of the capability approach that can be directly associated with these two theoretical origins are exposed, and it is argued that Sen s theory simultaneously solves the deficiencies pointed by him in the theoretical structure of Arrow s social choice and embodies, even though in a modified way, elements of Rawls thought / O objetivo dessa dissertação é investigar em que sentido é pertinente localizar na teoria da escolha social de Kenneth Arrow e na teoria da justiça de John Rawls as duas principais raízes teóricas da abordagem das capacidades de Amartya Sen. Argumentar-se-á que a teoria da escolha social de Arrow cumpriu o papel de explicitar as deficiências da teoria econômica do bem-estar. Desse modo, as análises de Arrow apontam as limitações a serem superadas para se chegar a uma teoria satisfatória da escolha social indicando em certa medida rumos a serem seguidos. Da mesma maneira argumenta-se que a teoria da justiça de Rawls forneceu elementos importantes que inspiraram certos posicionamentos éticos evidentes no pensamento de Amartya Sen e que se refletem em suas análises da escolha social. Por fim são apresentadas as principais características da abordagem das capacidades que podem ser diretamente associados a estas duas origens teóricas, e será argumentado que a teoria de Sen ao mesmo tempo soluciona as deficiências apontadas por ele na estrutura teórica da escolha social de Arrow e incorpora, ainda que de forma modificada, elementos presentes no pensamento de Rawls

In this thesis, a particular class of agent is singled out for examination. In order to provide a guiding metaphor, we speak of control room agents. Our focus is on rational decision- making by such agents, where the circumstances obtaining are such that rationality is bounded. Control room agents, whether human or non-human, need to reason and act in a changing environment with only limited information available to them. Determining the current state of the environment is a central concern for control room agents if they are to reason and act sensibly. A control room agent cannot plan its actions without having an internal representation (epistemic state) of its environment, and cannot make rational decisions unless this representation, to some level of accuracy, reflects the state of its environment. The focus of this thesis is on three aspects regarding the epistemic functioning of a control room agent: 1. How should the epistemic state of a control room agent be represented in order to facilitate logical analysis? 2. How should a control room agent change its epistemic state upon receiving new information? 3. How should a control room agent combine available information from different sources? In describing the class of control room agents as first-order intentional systems hav- ing both informational and motivational attitudes, an agent-oriented view is adopted. The central construct used in the information-theoretic approach, which is qualitative in nature, is the concept of a templated ordering. Representing the epistemic state of a control room agent by a (special form of) tem- plated ordering signals a departure from the many approaches in which only the beliefs of an agent are represented. Templated orderings allow for the representation of both knowledge and belief. A control room agent changes its epistemic state according to a proposed epistemic change algorithm, which allows the agent to select between two well-established forms of belief change operations, namely, belief revision and belief update. The combination of (possibly conflicting) information from different sources has re- ceived a lot of attention in recent years. Using templated orderings for the semantic representation of information, a new family of purely qualitative merging operations is developed. / School of Computing / Ph. D. (Computer Science)

In this minithesis I conduct a critical discourse analysis to take on a double-pronged task. On the one hand I explore the social phenomenon of the contestation between supporters of then-ANC deputy president Jacob Zuma and supporters of his rape accuser. The trial, which took place in the Johannesburg High Court between mid-February and early May 2006, stirred intense public interest, both locally and internationally. The performance of thousands of Zuma’s supporters and a far smaller number of gender rights lobby groups, both of whom kept a presence outside the court building throughout the trial, received similar attention. Second, I examine how the Sowetan, a national daily tabloid with a black, middle-class readership, mediated the trial through pictures of the theatre outside the court and letters to the editor. The study is informed by post-Marxist and cultural studies perspectives, both approaches that are concerned with issues of power, ideology and the circulation of meaning within specific sociocultural contexts. A rudimentary thematic content analysis draws out some of the main themes from the material, while the critical discourse analysis is located within a theoretical framework based on concepts from Laclau & Mouffe’s theory of meaning, which assumes a power struggle between contesting positions seeking to invalidate one another and to either challenge or support existing hegemonies. This is further informed by, first, Laclau’s theorisation of populism, which assumes that diverse groupings can unite under a demagogue’s banner in shared antagonism towards existing power, and second, by concepts from Mamdani’s theorisation of power and resistance in colonial and post-colonial Africa, which explicates three overarching ideological discourses of human rights, social justice and traditional ethnic practices. The study, then, explores how these three discourses were operationalised by the localised contestations over the trial.