投票选举问题是社会选择学中的一个主要研究课题,它在我们的实际生活中有着非常多的应用,在人工智能和社会选择中也起着基础性的作用。制定合理有效的投票规则,预测可能和必要的获胜者,避免可能发生的投票操纵,以及在组合领域问题中的优先级选取、顺序的安排以及偏好的考虑等都与投票选举问题相关联。研究投票选举问题可以为这些情况提供解决方案,建立有效的模型,从而获得更好的、让大家接受的结果。在本文中,我们从计算复杂性的角度研究了多种情况下的投票选举问题。为一些选举问题提供了有效地算法,或从理论上证明了一些选举规则和选举系统的稳定性。我们期望通过研究这几种情况下的选举问题,分析出它们的复杂性结果,从而对其他选举问题的复杂性研究提供一定的分析思路和技术支持,为最终得到选举问题复杂性的一般性规律提供帮助。本文的主要内容和创新点如下:1.我们研究了三种常见的支持投票委员会选举规则:Chamberlin-Courant支持投票（Chamberlin-Courant Approval Votes,CCAV*）1、比例支持投票（Proportional Approval Votes,PAV*）和满意度支持投票（Satisfaction Approval Votes,SAV*）。人们已经对这些规则下的委员会选举问题进行了公理化和算法的研究。已知当输入的投票为二分支持投票时,CCAV*或PAV*规则的委员会选举问题是NP-难的,而SAV*规则的委员会选举问题是多项式时间可解的。此外,人们还研究了这两个NP-难情形的参数复杂性,并考虑了一些比较常见的参数,如候选人数或投票数等。在本文中,我们将上述研究扩展到三分支持投票的委员会选举,并找出三分支持投票导致参数复杂度增加的案例。以投票总满意度界值为参数时,CCAV*规则下二分支持投票委员会选举问题是FPT（Fixed-Parameter Tractable,固定参数可解）的,而三分支持投票时是W[2]-难的。并且,我们还考虑选举的最小值最大化（或平均化）模型,即让选民的最低满意度最大化。我们的结果表明,相较于整体最大化模型（考虑投票总满意度）,最小值最大化模型中的支持投票委员会选举问题更加的复杂。比如:整体最大化模型中,SAV*规则下二分和三分支持投票委员会选举问题都是多项式时间可解的,而在最小值最大化模型中,该问题变为NP-难的,且以投票数、候选人数、委员会大小和满意度界值为参数时,该问题的参数复杂性分别为FPT、FPT、W[2]-难和参数NP-难。2.我们研究了 Borda规则选举控制问题。选举控制是指选举组织者试图通过增加或删除选票或候选人来影响选举结果,目的是使某一特定候选人赢得（创造性控制）或不赢得（破坏性控制）选举的情况。选举控制问题已经从经典复杂性和参数复杂性的角度得到了广泛的研究。在此,我们首先取得了删除投票、添加或删除候选人时Borda选举创造性控制问题的W[2]-难结果,完善了 Borda选举控制问题的参数化复杂性。其中,删除投票时的W[2]-难结果解决了 Liu和Zhu提出的一个开放性问题。根据Menon和Larson的建议,我们还研究了在给定的m个候选人中,每个投票者只给出最多t个候选人的顶部偏好投票对Borda选举控制问题经典复杂性和参数化复杂性的影响。我们的结果显示,即使t是一个很小的常数时,Borda选举创造性控制问题仍然是NP-难的。此外,我们还证明了:在顶部偏好投票下,以添加或删除的投票数和投票序列中最大候选人数t为参数时的选举创造性控制问题是FPT的;而当t ≥ 2,添加或删候候选人的选举创造性控制问题是W[2]-难的。我们的结果表明,相较于删除或添加投票时顶部偏好投票选举控制问题经典复杂性的界值在t=2和t=3之间,删除或添加候选人时顶部偏好投票选举控制问题经典复杂性的界值在t=1和t=2之间,这为选举控制操作类型（候选人操作、投票操作）不同对选举控制问题复杂性产生不同的影响提供了更多的依据。3.我们研究了迭代选举转移贿赂问题。在一个迭代选举中,候选人在连续多个回合中被淘汰,直到剩余候选人集合不变或达到一定的回合数为止。我们考虑了四个基于位置评分规则的迭代选举系统:Hare、Coombs、Baldwin和Nanson。其中,Hare和Coombs分别应用Plurality和Veto得分,而Baldwin和Nanson应用Borda得分。在此,我们从创造性贿赂和破坏性贿赂两个角度,研究了这四种迭代选举系统对贿赂攻击的抵抗情况。已知,这四种迭代选举系统从经典复杂性出发都能抵抗转移贿赂攻击,也就是说,这四种选举系统的创造性或破坏性转移贿赂问题都是NP-难的。我们在此基础上研究了这些迭代选举转移贿赂问题相对于一些参数的参数复杂性,从而进一步证明了迭代选举转移贿赂问题比相应的非迭代情形更难被攻击。同时,我们的结果也体现了不同选举系统或参数之间的参数复杂性差异,具体为:以允许的转移贿赂操作数为参数时,Borda选举创造性转移贿赂问题是FPT的,而Baldwin和Nanson选举创造性转移贿赂问题是W[1]-难的。此外,我们还发现,以候选人数或允许的转移贿赂操作数为参数时,Hare、Coombs、Baldwin和Nanson选举转移贿赂问题表现一致,即都是FPT或W[1]-难的,而以投票数为参数时,Hare选举转移贿赂问题是FPT的,Baldwin和Nanson选举转移贿赂问题是W[1]-难的。这表明,相较于候选人数和允许的转移贿赂操作数为参数时的参数复杂性,以投票数为参数时选举贿赂问题的参数复杂性更加的具有多样性。4.我们还研究了具有候选人属性约束的委员会选举问题。在许多委员会选举中,候选人是与某些属性相关联的,并且所选取的委员会必须满足一些候选人的属性限制。给定一组候选人、一组属性和一组约束,其中,每个候选人都具有一些属性和其获选所能获得的利润,每个约束都是关于属性的命题逻辑表达式。我们的任务是选取出一个具有k个候选人的委员会,使得委员会中候选人的属性满足所有约束条件,且其总利润超过给定的界值。在此,我们取得了一个关于经典复杂性的二分化结果:当满足以下两个条件时,该问题是多项式时间可解的:1)每个候选人最多拥有一个属性;2)每个属性在约束中最多出现一次。而当这两个条件中的任何一个不满足时,该问题就变成NP-难的。此外,我们还研究了该问题的参数复杂性:以约束个数、委员会大小或总利润界值为参数时,我们取得了参数-NP-难或W[1]-难结果;而以属性个数或候选人数为参数时,该问题是FPT的。我们的结果表明,当属性个数很少时,该问题就变为多项式时间可解的。并且即使只有1个约束,仍然可能很难求解出符合要求的委员会,即该问题是NP-难的。这一结果为接下来的研究指明了方向:研究约束的结构限制而非约束的数量限制。