Solving hard problems in election systems
Solving hard problems in election systems
复制标题
解决选举制度中的难题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Andrew Lin
中科院分区：
文献类型：
--
作者：
E. Hemaspaandra;Andrew Lin
计算社会选择理论领域中一个有趣的问题是选举问题，其中赢家或获胜者集合将从代理人集合中的偏好中推断出来，以试图最大化代理人的集体福利的方式。除了在政治学中的明显用途外，选举也用于计算，例如在多智能体系统中，不同的智能体可能有不同的信念和偏好，并且必须达成一致的决定。
由于投票的目的是了解实际偏好的集合，因此选举制度中的不诚实往往对整个选民的福利有害。不同形式的不诚实可以由选民（操纵），由影响选民的外部代理人（贿赂），或由选举主席或管理人员（控制）执行。Gibbard-Satterthwaite定理表明，在所有合理的选举制度中，操纵或策略性投票在某些情况下总是不可避免的。Bartholdi、Tovey和Trick反驳说，如果发现这样的操纵是NP困难的，那么计算有限的代理人的操纵不应该构成重大威胁。然而，最近的工作已经利用了这样一个事实，即NP-硬度只是复杂性的最坏情况度量，并表明一些NP-难以操纵的选举系统实际上可能在一些合理的假设下很容易操纵。
我们从理论和经验两方面评估操纵、贿赂和控制选举的复杂性、最坏情况和其他情况。我们特别关注评分协议。在这样做的过程中，我们通过发现是什么让操纵、贿赂和控制变得容易或困难，来了解这些选举系统是如何运作的。这使我们能够发现评分协议的优点和缺点，并了解选举系统的哪些属性是可取的或不可取的。
我们用来做这件事的一种方法是将选举系统中感兴趣的问题与已知复杂性的问题以及已知算法和算法学的问题联系起来，特别是可满足性和划分。这种方法可以帮助我们了解计算社会选择问题，其中对复杂性或潜在算法知之甚少。在其他结果中，我们展示了评分协议的某些参数和属性如何使选举容易或难以操纵。我们发现，操纵的经验复杂性在某些情况下有不寻常的行为，其复杂性类。例如，它被发现的情况下，操纵的Borda选举的未加权选民与一个无界的候选人基数，这个问题的可满足性的编码执行特别好的边界附近的情况下，这个问题和不可满足的情况下，这两个结果相反的正常行为的NP完全问题。
虽然人们曾试图设计具有某些性质的公平选举制度，但由此产生的另一个困境是，存在着难以选出获胜者的选举制度，至少在最坏的情况下是如此。两个著名的选举制度，其中确定赢家是困难的是道奇森和杨。我们评估的问题，找到赢家经验，延长这些复杂性的结果远离最坏的情况下，并确定这些硬赢家问题的最坏情况下的复杂性是否是真正的计算障碍。我们发现，像大多数NP完全问题，如可满足性，在寻找硬选举系统的赢家的兴趣的许多情况下仍然相对简单。我们确认，确实，像可满足性一样，硬最差情况结果仅在极少数情况下发生。我们还发现了一个有趣的复杂性之间的差距，找到一个候选人的道奇森或杨得分的相关问题，并找到一套道奇森或杨赢家。令人惊讶的是，从经验上看，在道奇森或杨的选举中找到所有获胜者的集合似乎比在任何一次选举中为单个候选人打分更容易。
An interesting problem in the field of computational social choice theory is that of elections, in which a winner or set of winners is to be deduced from preferences among a collection of agents, in a way that attempts to maximize the collective well-being of the agents. Besides their obvious use in political science, elections are also used computationally, such as in multiagent systems, in which different agents may have different beliefs and preferences and must reach an agreeable decision.
Because the purpose of voting is to gain an understanding of a collection of actual preferences, dishonesty in an election system is often harmful to the welfare of the voters as a whole. Different forms of dishonesty can be performed by the voters (manipulation), by an outside agent affecting the voters (bribery), or by the chair, or administrator, of an election (control). The Gibbard-Satterthwaite theorem shows that in all reasonable election systems, manipulation, or strategic voting, is always inevitable in some cases. Bartholdi, Tovey, and Trick counter by arguing that if finding such a manipulation is NP-hard, then manipulation by computationally-limited agents should not pose a significant threat. However, more recent work has exploited the fact that NP-hardness is only a worst-case measure of complexity, and has shown that some election systems that are NP-hard to manipulate may in fact be easy to manipulate under some reasonable assumptions.
We evaluate, both theoretically and empirically, the complexity, worst-case and otherwise, of manipulating, bribing, and controlling elections. Our focus is particularly on scoring protocols. In doing so, we gain an understanding of how these election systems work by discovering what makes manipulation, bribery, and control easy or hard. This allows us to discover the strengths and weaknesses of scoring protocols, and gain an understanding of what properties of election systems are desirable or undesirable.
One approach we have used to do this is relating the problems of interest in election systems to problems of known complexity, as well as to problems with known algorithms and heuristics, particularly Satisfiability and Partition. This approach can help us gain an understanding of computational social choice problems in which little is known about the complexity or potential algorithms. Among other results, we show how certain parameters and properties of scoring protocols can make elections easy or hard to manipulate. We find that the empirical complexity of manipulation in some cases have unusual behaviors for its complexity class. For example, it is found that in the case of manipulating the Borda election of unweighted voters with an unbounded candidate cardinality, the encoding of this problem to Satisfiability performs especially well near the boundary cases of this problem and for unsatisfiable instances, both results contrary to the normal behavior of NP-complete problems.
Although attempts have been made to design fair election systems with certain properties, another dilemma that this has given rise to is the existence of election systems in which it is hard to elect the winners, at least in the worst case. Two notable election systems in which determining the winners are hard are Dodgson and Young. We evaluate the problem of finding the winners empirically, to extend these complexity results away from the worst case, and determine whether the worst-case complexity of these hard winner problems is truly a computational barrier. We find that, like most NP-complete problems such as Satisfiability, many instances of interest in finding winners of hard election systems are still relatively simple. We confirm that indeed, like Satisfiability, the hard worst-case results occur only in rare circumstances. We also find an interesting complexity disparity between the related problems of finding the Dodgson or Young score of a candidate, and that of finding the set of Dodgson or Young winners. Surprisingly, it appears empirically easier for one to find the set of all winners in a Dodgson or Young election than to score a single candidate in either election.