Parameterizedcomputationalcomplexityofcontrolproblemsinvotingsystems资源-CSDN文库

Approval

voting

44 浏览量 2021-02-20 11:42:39 上传评论收藏 494KB PDF 举报

资源推荐

资源详情

资源评论

Theoretical Computer Science 410 (2009) 2746–2753

Contents lists available at ScienceDirect

Theoretical Computer Science

journal homepage: www.elsevier.com/locate/tcs

Parameterized computational complexity of control problems in voting

systems

Hong Liu

∗

, Haodi Feng, Daming Zhu, Junfeng Luan

Algorithms Group, School of Computer Science and Technology, Software Park Campus, Shandong University, Jinan, Shandong Province, China

a r t i c l e i n f o

Article history:

Received 5 November 2008

Received in revised form 12 February 2009

Accepted 9 April 2009

Communicated by X. Deng

Keywords:

Voting systems

Constructive control

Destructive control

Plurality voting

Condorcet voting

Approval voting

Parameterized complexity

a b s t r a c t

Voting systems are common tools in a variety of areas. This paper studies parameterized

computational complexity of control of Plurality, Condorcet and Approval voting systems,

respectively. The types of controls considered include adding or deleting candidates

or voters, under constructive or destructive setting. We obtain the following results:

(1) constructive control by adding candidates in Plurality voting is W[2]-hard with

respect to the parameter ‘‘number of added candidates’’, (2) destructive control by adding

candidates in Plurality voting is W[2]-hard with respect to the parameter ‘‘number of

added candidates’’, (3) constructive control by adding voters in Condorcet voting is

W[1]-hard with respect to the parameter ‘‘number of added voters’’, (4) constructive

control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter

‘‘number of deleted voters’’, (5) constructive control by adding voters in Approval voting is

W[1]-hard with respect to the parameter ‘‘number of added voters’’, and (6) constructive

control by deleting voters in Approval voting is W[2]-hard with respect to the parameter

‘‘number of deleted voters’’.

1. Introduction

Voting systems provide a general framework for preference aggregation, in which each agent expresses a preference

order over a set of candidates, and some voting rule [4] is applied to compute the winner(s). These systems are used not

only in political elections but also in a variety of other areas, for example, meta-search engines [9] and planning in multi-

agent systems [10].

In addition to work that focuses on winner(s) determination, researchers have spent much effort on studying, from the

computational complexity view, the potential dangers that various voting systems would face. The dangers most studied

so far include manipulation [1,7], control [2,13,17,19], and bribery [12,13]. This paper focuses on control of voting systems.

In their seminal paper [2], Bartholdi et al. put forward the following general control problem: Is it computationally hard

or easy for an authority conducting the voting procedure (called chair) to cause a distinguished candidate to be the unique

winner through control of the candidate or voter set? Hemaspaandra et al. [17] called this general problem as constructive

control problem and also put forward a complementary destructive control problem. While in constructive setting the chair

aims to ensure that a specified desirable candidate is the (unique) winner, in destructive setting the chair tries to ensure

that a specified detested candidate is not the (unique) winner.

With respect to different settings (constructive or destructive), different types of control (e.g. adding or deleting

candidates or voters), and different voting systems, different variants of control problem can be formed. Variants of control

Research supported by the National Natural Science Foundation of China (60603007).

∗

Corresponding author. Tel.: +86 13001727985.

E-mail addresses: hong-liu@sdu.edu.cn, hongliu2005@gmail.com (H. Liu), fenghaodi@sdu.edu.cn (H. Feng), dmzhu@sdu.edu.cn (D. Zhu),

jfluan@sdu.edu.cn (J. Luan).

doi:10.1016/j.tcs.2009.04.004

H. Liu et al. / Theoretical Computer Science 410 (2009) 2746–2753 2747

Table 1

Summary of results.

Plurality Condorcet Approval

Control by Con. Des. Con. Des. Con. Des.

AC W[2]-hard W[2]-hard    

DC W[2]-hard[3] W[1]-hard[3]    

AV   W[1]-hard  W[1]-hard 

DV   W[1]-hard  W[2]-hard 

Results new to this paper are in boldface. AC = Adding Candidates, DC = Deleting Candidates,

AV = Adding Voters, DV = Deleting Voters. Con. = Constructive, Des. = Destructive.

problem for Sincere-Strategy Preference-Based Approval voting system was studied in [11]. The computational complexity

of variants of control problems (with respect to ten types of control and constructive and destructive settings) of Plurality,

Condorcet and Approval voting systems obtained so far by researchers were summarized in [17]. We are interested in four

(out of the ten) types of controls: adding or deleting candidates or voters. We can see from the summary that, with respect

to these four types of controls, eight variants of control problem are NP-hard.

Although NP-hardness can in theory be a

barrier to the implementation of certain control, more theoretical analysis is necessary.

More recently, some researchers have started to study the computational complexity of the control problem under

parameterized complexity framework [8,15,20], e.g., [3,14]. A review can be found in [18]. We refer readers to [3] for

a review of the motivations. In practice, it is reasonable to expect that, in some cases, the added/deleted candidates/voters

are in a small amount compared to the main body of already qualified candidates or registered voters, for the chair to

escape detection of his (or her) malicious aim. So, the number of added/deleted candidates/voters are reasonably considered

as ‘‘natural’’ parameters of the problem. Betzler and Uhlmann [3] studied two of the eight variants of control problem,

which are NP-hard as mentioned above. They proved that, with respect to the parameter ‘‘number of deleted candidates’’,

constructive control of Plurality voting by deleting candidates is W [2]-hard and destructive control of Plurality voting by

deleting candidates is W [1]-hard. To the best of our knowledge, parameterized complexity of the other six variants of control

problem are still open. We study them in this paper. For this purpose, with the number of added or deleted candidates or

voters as parameter, we first re-formalize the six variants of control problem in a ‘‘parameterized’’ way. Then, we devise

parameterized reductions to prove the W [1]-hardness or W [2]-hardness of them, respectively. The results obtained are

summarized in Table 1.

The rest of the paper is organized as follows. In the second section, we describe the six variants of control problem and

some notions and concepts used in this paper are introduced. In the following three sections, parameterized complexities

of these six variants of control problem are studied, respectively. Conclusion is given in the last section.

2. Preliminaries

Throughout this work, a voting system (or an election) consists of a set of candidates, a set of voters specified by their

preferences and a voting rule for selecting winner(s). The Plurality, Condorcet, and Approval voting rules are described as

follows:

Plurality: Each candidate receives one vote for each voter that prefers it first. The candidate with the most votes wins.

Condorcet: The candidate who would defeat any other in a pairwise Plurality voting wins. According to the Condorcet

Paradox, whenever there are at least three candidates, a Condorcet winner may not exist due to cycles in preferences [5].

However, whenever one does exist, a Condorcet winner is of course the unique winner.

Approval: Every voter either approves or disapproves of each candidate, and the candidate with the maximum number

of approvals wins.

Suppose there is a candidates set C = {c

, c

, . . . , c

}. In Plurality and Condorcet voting systems, for any two candidates

, c

∈ C , if c

is preferred to c

, it is denoted by c

 c

. We assume that the preferences are transitive, strict (no ties),

and complete (for any two candidates c

and c

, c

 c

or c

 c

). A voter’s preferences are represented as a list like

 c

 · · ·  c

, where {c

, c

, . . . , c

} = C. Often in this paper, we insert one or more candidate subsets into

such preference list, where we assume some arbitrary, fixed order of the candidates within each subset. In Approval voting

system, a voter’s preferences are reflected by a 0/1 vector (1 for approval and 0 for disapproval).

Following a similar fashion in [2,17], we describe the six parameterized variants of control problem:

Constructive Control by Adding Candidates in Plurality Voting (Plurality-CC-AC)

Given: A set C of qualified candidates, a particular candidate c ∈ C, a set B of possible spoiler candidates, and a set P of

voters with preferences over C ∪ B.

Parameter: A positive integer k.

Question: Is there a subset B

, with |B

| 6 k, of B, whose entry into the election would assure that c is the unique winner?

A voting system is said to be immune to a type of control if a non-unique-winner can never be made the unique winner by this type of control, and is

said to be resistant to this type of control if the corresponding control problem is NP-hard, and vulnerable if polynomial-time solvable [17].

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38640985

粉丝: 8
资源: 965

Parameterized computational complexity of control problems in vo...

最新资源

Parameterized computational complexity of control problems in vo...

Parameterized Complexity

voting-system

连通流和多次访问TSP问题的参数化复杂性_On the Parameterized Complexity of the Conn

Parameterized LMIs in control theory

Parameterized Complexity Theory

Distributed model predictive control for constrained linear systems

Parameterized Trigger Plugin 2.25

Parameterized Controller，

Model Free Adaptive Control Theory and Applications

Python库 | parameterized-0.6.3.tar.gz

Parameterized Algorithms

Parameterized Trigger Plugin 2.24 hpi

Parameterized Logarithmic Framework for Image Enhancement

Python库 | nose-parameterized-0.3.3.tar.gz

marine control

Rethinking Style Transfer From Pixels to Parameterized Brush

parameterized-0.7.4 python测试使用

Approximation and Parameterized Runtime Analysis of Evolutionary Algorithms for the Maximum Cut Problem

Lenze GLOBAL DRIVE CONTROL - version 4.14.1

数位板压力测试

parameterized:使用任何Python测试框架进行参数化测试

Pose Partition Network pre-trained model

微软白盒测试例子pex.samples

jpgc-prmctl-0.4.zip

redis注解方式序列化改造

Adaptive Asymptotic Tracking of Nonlinear Systems Using Nonlinearly Parameterized First-Order Sugeno Fuzzy Approximator

rspec-parameterized:规范

c++实验三、四.pdf

最新资源