Algorithm Design And Computational Complexity Analysis Of Voting Problems

Election is a major topic in social choice.It has many practical applications in our real life,and plays a fundamental role in artificial intelligence and social choice.Designing reasonable and effective voting rules,predicting possible and necessary winners,preventing possible election manipulation,the selection of priorities,the arrangement of order and the consideration of preference are all related to election problems.The study of election problems can provide solutions and effective models for these situations.Ultimately,we can obtain a better and more acceptable results for many real-world applications.In this thesis,we study several election problems from the viewpoint of computational complexity.We provide some effective algorithms for some election problems,or prove theoretically the stability of some election rules or election systems towards strategic behaviors.We hope that by studying the election problems in these situations,it is helpful to analyze the complexity of other election problems by applying some ideas and techniques in this thesis.Furthermore,the results and the technical contributions achieved in this thesis might be useful for analyzing the computational complexity of the general election issues.The main contents and innovations of this thesis are as follows:1.We study the winner determination problem for three prevalent committee election rules:Chamberlin-Courant Approval Voting(CCAV*),Proportional Approval Voting(PAV*),and Satisfaction Approval Voting(SAV+).Axiomatic and algorithmic studies of elections under these rules have been conducted recently.It is known that the winner determination problem is NP-hard for CCAV*and PAV*and polynomial-time solvable for SAV*,if the input votes are dichotomous.Moreover,parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes.In this paper,we extend the above studies to committee elections with trichotomous votes and identify cases,where trichotomous votes lead to an increase of parameterized complexity.With the total satisfaction bound as a parameter,committee election problem under CCAV*rule is FPT with dichotomous votes,while this problem turns to be W[2]-hard with trichotomous votes.We also consider the maximin(or egalitarian)variations of the rules,where the minimum satisfaction of the voters is maximized.Our results show that compared with the maxsum model(considering the total satisfaction all votes),the committee election problem is more complex in the maximin model.For example,under the rule of SAV*,committee election problem with dichotomous or trichotomous votes is polynomial time solvable in maxsum model,while in the maximin model,the problem becomes NP-hard.And the parameterized complexity of this problem are FPT,FPT,W[2]-hard and para-NP-hard with respect to the number of votes,the number of candidates,the size of the committee,and the individual satisfaction bound,respectively.2.We consider control problems of a Borda election.The control problems study the condition where the chair of the election attempts to influence the election outcome by adding or deleting either votes or candidates with the intention to make a special candidate win(constructive control)or lose(destructive control)the election.Control problems have been extensively studied for Borda elections from both classical and parameterized complexity viewpoints.We complete the parameterized complexity picture for Borda control problems by showing W[2]-hard results with the number of additions/deletions as parameter for constructive control by deleting votes,adding candidates,or deleting candidates.The hardness result for deleting votes settles an open problem posed by Liu and Zhu.Following the suggestion by Menon and Larson,we also investigate the impact of top-truncated votes,where each voter ranks only t out of the given m candidates,on the classical and parameterized complexity of Borda control problems.Constructive Borda control problems remain NP-hard even with t being a small constant.Moreover,we prove that in the top-truncated case,constructive control by adding/deleting votes problems are FPT with the number of additions/deletions and t as parameters,while for every constant t>2,constructive control by adding/deleting candidates problems are W[2]-hard with respect to the number of additions/deletions.Our results show that the bounds of the classical complexity of voting control problem with top-truncated votes are between t=2 and t=3 for deleting or adding votes operations,while the bounds are between t=1 and t=2 for deleting or adding candidates.This provides more evidence for the observation that the different types of control operation(candidate operation,vote operation)can lead to different effects on the complexity of election control problems.3.We consider the iterative voting shift bribery problem.In an iterative voting system,candidates are eliminated in consecutive rounds until either the set of remaining candidates does not change or a fixed number of rounds is reached.We consider four prominent iterative voting systems,which are all based on positional scoring rules.The Hare and Coombs systems are based on the plurality and veto rules,respectively,while the Baldwin and Nanson systems are based on the Borda rule.We study the resistance of these four systems against shift bribery.Hereby,we consider both constructive and destructive settings.It is known that all four iterative voting systems are resistant to shift bribery from the perspective of classical complexity,that is,both constructive and destructive shift bribery problems are NP-hard for these voting systems.We complement these NP-hard results by examining parameterized complexity of the shift bribery problems with respect to some natural parameters.Our results provide further evidence for the observation that shift bribery problems for iterative voting systems are computationally harder than for the corresponding non-iterative cases.Our results reflects some differences of parameterized complexity between different election systems or parameters:with the number of shift bribery operations as parameter,the parameterized complexity of Borda constructive shift bribery problem is FPT,while the parameterized complexities of Baldwin and Nanson constructive shift bribery problems are W[1]-hard.In addition,we find out that the parameterized complexity of Hare,Coombs,Baldwin and Nanson shift bribery problem are all FPT or W[1]-hard with respect to the number of candidates or the number of shift bribery operations,while with the number of votes as parameter,the parameterized complexity of Hare shift bribery problem is FPT and the parameterized complexities of Baldwin and Nanson shift bribery problem are W[1]-hard.These results indicate the fact that comparing to the parameterized complexities of election bribery problems with the number of candidates or the number of shift bribery operations as parameter,the parameterized complexity of election bribery problem demonstrates more diversity with the number of votes as parameter.4.We consider the committee election with candidate attribute constraints problem.In many real-world applications of committee elections,the candidates are associated with certain attributes and the chosen committee is required to satisfy some constraints posed on the candidate attributes.We study this variant of committee elections from the computational complexity viewpoint.Given a set of candidates,each with some attributes and a profit,and a set of constraints,given as propositional logical expressions of the attributes,the task is to compute a set of k candidates,whose attributes satisfy all constraints and whose total profit exceeds a given bound.We achieve a dichotomy concerning classical complexity:the problem is polynomial-time solvable,if the following two conditions are fulfilled:1)each candidate has only one attribute and 2)each attribute occurs at most once in the constraints.It becomes NP-hard if one of these two conditions is violated.Moreover,we examine its parameterized complexity.The parameterization with the number of constraints,the size of committee,or the total profit bound as parameter leads to para-NP-hard or W[1]-hard,while with the number of attributes or the number of candidates as parameter,the problem turns out to be fixed-parameter tractable.Our results show that when the number of attributes is very small,this problem becomes polynomial-time solvable.Moreover,even if there is only one constraint,it may be difficult to find out a satisfactory committee,that is,the problem is NP-hard.It points out the direction for the following research:study the structural constraints rather than the quantitative constraints.