Approval Voting with Intransitive Preferences
Yongjie Yang




1



Approval Voting with Intransitive Preferences
    
Yongjie Yang

Chair of Economic Theory

Saarland University, Saarbrücken, Germany

yyongjiecs@gmail.com

    December 30, 2023
=============================================================================================================




We extend Approval voting to the settings where voters may have intransitive preferences. The major obstacle to applying Approval voting in these settings is that voters are not able to clearly determine who they should approve or disapprove, due to the intransitivity of their preferences. An approach to address this issue is to apply tournament solutions to help voters make the decision. We study a class of voting systems where first each voter casts a vote defined as a tournament, then a well-defined tournament solution is applied to select the candidates who are assumed to be approved by the voter. Winners are the ones receiving the most approvals. We study axiomatic properties of this class of voting systems and complexity of control and bribery problems for these voting systems.



 



§ INTRODUCTION


Voting is a common method for preference aggregation and collective decision-making, and has significant applications in
multi-agent systems, political elections, web spam reduction, pattern recognition, etc. <cit.>. For instance, in multiagent systems, it is often necessary for a group of agents to make a collective decision by means of voting in order to reach a joint goal.
Approval-based voting systems are among the most important voting systems and have been extensively studied in the literature <cit.>. In an approval-based voting, each voter has a preference over the candidates, and based on the preference, the voter determines a subset of candidates that  approves. The winners are the candidates that get the most approvals. In most of the approval-based voting systems, voters are assumed to have transitive preferences. That is, if a voter prefers a candidate a to another candidate b, and prefers b to a third candidate c, then the voter prefers a to c. Among the most well-studied approval-based voting systems are Approval, r-Approval and Plurality. In Approval voting, each voter has a dichotomous preference which can be represented by a partition (C_1,C_2) of the candidates, meaning that the voter prefers every candidate in C_1 to every candidate in C_2, and are indifferent between candidates in each C_i where i=1,2. Moreover, a voter with a dichotomous preference (C_1,C_2) approves all candidates in C_1 and disapproves  all candidates in C_2. In r-Approval voting, each voter has a preference which is defined as a linear order over the candidates, and approves exactly the top-r ordered candidates. Plurality is exactly 1-Approval.

-5pt


 §.§ Motivation

There is no doubt that transitive preferences occur naturally in many real-world applications. The question is whether intransitive preferences make sense either. The answer is “Yes!”. In fact, there exist many real-world applications where voters may have intransitive preferences (see, e.g., <cit.>). For instance, when voters compare candidates based on, not one, but multiple quality parameters <cit.>. Another natural scenario where intransitive preferences arise is that when the number of candidates is considerably large <cit.>. In this case, it is more efficient to utilize vote elicitation techniques where voters iteratively cast parts of their preference such as pairwise comparisons. In addition, intransitive preferences may also arise in the settings of sport prediction, where an agency (e.g., a gambling company) desires to predict the sport result for some special purpose. In order to gain a result as precise as possible, the agency might resort to several experts, who based on their expertise suggest the winning player in each pending match between two players. Then, based on the suggestions, the agency applies a voting to predict the winning player(s). In this case, each suggestion by an expert may be considered as a preference which is not necessarily transitive, since it is commonplace to see that a player a who beats another player b is beaten by a third player c who is beaten by b. We refer to <cit.> for further discussion with several concrete examples.


Finally, we would like to point out that intransitive preferences may also occur in district-based voting or group-based voting (a group may be a political party, a department in a university, an affiliate of a company, a set of robots, etc.), where each group consists of their own group members and is only allowed to submit one single group vote. In such a situation, group leaders may need to first apply a voting to derive their group vote before the whole voting. If there are three group members whose preferences over three candidates a,b,c are a≻ b≻ c, b≻ c≻ a, c≻ a≻ b, respectively, then the group vote would probably be a≻ b, b≻ c but c≻ a, an intransitive preference. A significant difference between this case and the cases mentioned above is that each intransitive preference (group vote) in this case is drawn from the votes cast by the group members.   However, each previous mentioned intransitive preference is cast by a single voter.

We extend the framework of approval-based voting to the settings where voters may hold intransitive preferences over the candidates. The major difficulty of imposing the framework in these settings is that voters with intransitive preferences are not able to determine who they should approve. In order to address this issue, we utilize tournament solutions. It should be noted that an intransitive preference can be represented by a tournament (we consider only complete preferences, i.e., for every two candidates a and b either a is preferred to b or the other way around)—a complete and asymmetric binary relation. From the graph theory point of view, a tournament is a directed graph where there is exactly one arc between every pair of vertices (candidates). A tournament solution is a function that maps each tournament to a nonempty subset of candidates.
Tournament solutions as a powerful decision making model have been extensively-studied in the literature <cit.>. For instance, tournament solutions have significant applications in voting. In particular, given a set of votes, we can create a tournament based on the majority relations between the candidates (assume that the number of votes is odd): create an arc from a to b if there are more voters preferring a to b. Then, a tournament solution is applied to the tournament to select the winners. 

Each approval-based voting system studied in this paper is a natural combination of the classic Approval voting and a well-studied tournament solution. Precisely, fixing a tournament solution, each voter in this setting submits a vote which is defined as a tournament. Then, every candidate selected by the tournament solution is approved by the voter, and every candidate not selected is disapproved. We remark that in practice, voters need only to cast their votes, but leave the duty of calculating the winning candidates with respect to the tournament solution to a second agency (e.g., a computer, the voting designer, etc.), since it is unnatural to assume or require that every voter knows how the tournament solution works. In other words, we assume that the voters implicitly approve the winning candidates in their cast tournaments, with respect to the associated tournament solution.
In this paper, we mainly consider three tournament solutions, namely, the top cycle, Copeland set and uncovered set. One reason that we choose them to study is that they are among the most prevalent tournament solutions which have been extensively studied in the literature. 
It also makes sense to consider other tournament solutions such as minimal covering set and tournament equilibrium set (see <cit.> for further tournament solutions).

As we pointed out earlier in the example on group-based voting, tournaments in our model are not necessarily to be cast directly by voters, but can be also drawn from the majority relations between the candidates according to the votes cast by some group members. In this scenario, it makes much sense to first apply a tournament solution to the group votes (tournaments) to determine the winning candidates in each subvoting.

We would like to point out that apart from the model we proposed in this paper, there are several other prominent approaches to aggregate tournaments. For instance, we could apply different tournament solutions to the given tournaments to determine the candidates implicitly approved by the voters. An explanation is that in a group-based voting, each group (leader) is allowed to freely choose a tournament solution to use. Another approach to select winners from a set of tournaments would be as follows: First, we create a tournament based on the majority relations between the candidates, i.e., there is an arc from a to b if there is an arc from a to b in a majority of the given tournaments. Then, we apply a tournament solution to the tournament to select the winners. In addition, researchers have studied the model of deriving a ranking of the candidates based on a give set of tournaments, see, e.g., <cit.> and references therein.

-2pt


 §.§ Our Contribution

The major contribution of this work is the initialization of the study of a class of voting systems for the scenarios where voters may have intransitive preferences. To give a comprehensive understanding of the new voting systems, we study some axiomatic properties of these voting systems. Axiomatic properties of voting systems are primary factors used to evaluate voting systems and important guidance for voting organizers to select a proper voting system for their specific purpose in practice <cit.>. In particular, we prove that these voting systems satisfy several axiomatic properties for many common tournament solutions. As a byproduct, we introduce two concepts of monotonicity for tournament solutions, and show that the top cycle satisfies both monotonicity criteria, while both the Copeland set and the uncovered set averse to the monotonicity criteria. Our results concerning axiomatic properties are summarized in Theorems <ref>-<ref>.

In addition, we study the complexity of strategic behavior under these voting systems. In particular, we study control and bribery problems. We achieve polynomial-time solvability results,  results as well as  results. See Table <ref> for a summary of these results. A general conclusion is that these voting systems resist more types of strategic behavior than other approval-based voting systems such as Plurality and Approval. Studying complexity of strategic voting problems has been the main focus of many research papers. First, complexity is widely considered as a prominent theoretical barrier against strategic behavior in voting systems. Second, complexity helps practitioners decide what
kind of solution method is appropriate. For polynomial-time solvability results, we directly provide efficient algorithms with low time complexity. On the other hand, hardness results (e.g.,  results and  results) suggest that finding an exact solution is apt to be costly or impractical, and resorting to approximation  algorithms or heuristic algorithms may be a necessary choice.
Finally, it should be pointed out that complexity of strategic behavior for voting systems has also been considered as an important factor to evaluate voting systems, see, e.g.,  <cit.>.

-8pt


§ PRELIMINARIES



Tournament. 
In this paper, we use the terms “candidate” and “vertex” interchangeably.
A tournament T is a pair (V(T), ) where V(T) is a set of candidates and  is an asymmetric and complete binary relation on V(T).
For X,Y⊆ V(T) such that X∩ Y=∅, X  Y means that x y for every x∈ X and every y∈ Y.
For ease of exposition, we use directed graphs to represent tournaments. Precisely, in this paper a tournament T=(V(T), ) is considered as a directed graph where V(T) is considered as the vertex set and  is considered as the arc set. We refer to the textbook by West <cit.> for readers who are not familiar with graph theory.

For a candidate a∈ V(T), let N^-_T(a) denote the set of inneighbors of a in T and N^+_T(a) the set of outneighbors of a, i.e., N^-_T(a)={b∈ V(T)| b a} and N^+_T(a)={b∈ V(T)| a b}. The indegree (resp. outdegree) of a is defined as |N^-_T(a)| (resp. |N^+_T(a)|). A tournament T is regular if for every candidate a in T it holds that ||N_T^+(a)|-|N_T^-(a)||≤ 1. A directed triangle is a regular tournament with three vertices.

A directed path from a candidate a to another candidate b is a vertex sequence (a=v_1,v_2,...,v_t=b) such that v_i v_i+1, for every i∈{1,2,...,t-1}. A tournament T is strongly connected if there is a directed path from every candidate to every other candidate.
A maximal strongly connected component of T is a strongly connected subtournament of T with maximal vertices.

The source of a tournament T=(V(T),) is the candidate a so that a b for every candidate b∈ V(T)∖{a}.
The source is also called the Condorcet winner of the tournament from the social choice point of view. Clearly, not every tournament has a source. 

For a subset B⊆ V(T), T[B] is the subtournament induced by B, i.e., T[B]=(B,') where for every a,b∈ B, a' b if and only if a b.


Tournament Solution. A tournament solution  is a function that maps every tournament T to a nonempty subset (T)⊆ V(T). In this paper, we mainly study the following three tournament solutions <cit.>. We refer to <cit.> for a comprehensive introduction to further well-studied tournament solutions.

-6pt
=-2pt


  Copeland Set. The Copeland score of a candidate c in a tournament T

is defined as the outdegree of c in T. 
The Copeland set of T, denoted by T, consists of all candidates with the highest Copeland score.


  Top Cycle.  The top cycle T of a tournament T is the unique minimal subset of candidates such that there is an arc from every candidate in the subset to every candidate not in the subset.


  Uncovered Set. A king in a tournament is a candidate a such that for every other candidate b, either a b or there is another candidate c such that a c and c b. It is folklore that every tournament has at least one king <cit.>. The uncovered set of a tournament T, denoted by T, is the set of all kings of T.



It is known that for every tournament T it holds T,T⊆T (see, e.g., <cit.>).


Election. An election is a tuple ℰ=(𝒞,𝒯),
where 𝒞 is a set of candidates, and 𝒯 is a list of votes
(for convenience, the terminologies “vote” and “voter” are used interchangeably throughout this paper).
In this paper, we consider only the election where each vote is defined as a tournament T=(𝒞,). For two candidates a,b∈𝒞
and a vote T(𝒞,), a b means that the vote prefers a to b.
A voting correspondence 
 is a function that maps an election ℰ=(𝒞,𝒯) to a
nonempty subset (ℰ) of 𝒞. We call the elements in (ℰ)
the winners of ℰ with respect to . If (ℰ) consists of only one winner, we call
it the unique winner; otherwise, we call them co-winners. For two non-overlapping lists of tournaments
𝒯=(T_1,T_2,...,T_x) and
𝒯'=(T_1',T_2',...,T_y'), we denote by 𝒯+𝒯' the list (T_1,...,T_x,T_1',...,T_y'). For two elections
ℰ=(𝒞,𝒯) and ℰ'=(𝒞,𝒯') with the same candidate set 𝒞,
 ℰℰ'=(𝒞,𝒯+𝒯').


Implicit Approval Voting.
Now we introduce the core concept in this paper—-Approval. Each -Approval is a combination of the prevalent Approval voting and a tournament solution . To the best of our knowledge, such voting correspondences have not been studied in the literature.
Let ℰ=(𝒞,𝒯) be an election.

-8pt



-Approval 

Each candidate c∈𝒞 is assigned a score defined as cℰ=|{T∈𝒯| c∈(T)}|.
The candidates with the highest score are the winners.
 


-2pt

In Approval, each voter explicitly determines  whom  wants to approve.
In -Approval, each voter with preference T is assumed to implicitly approve
all candidates in (T) and disapprove all the remaining candidates.






Properties of Voting Correspondences.

-5pt
=-2pt

  Anonymity. A voting correspondence  is anonymous if reordering the votes does not affect the winning set. That is, for every two elections ℰ=(𝒞,𝒯=(T_1,...,T_n)) and ℰ'=(𝒞,𝒯'=(T_σ(1), T_σ(2),...,T_σ(n))) where (σ(1), σ(2),...,σ(n)) is a permutation of (1,2,...,n), it holds that (ℰ)=(ℰ').


  Neutrality. An election (𝒞,𝒯=(T_1,...,T_n)) is isomorphic to
another election (𝒞',𝒯'=(T_1',...,T_n')) where T_i=(𝒞,_i) and T_i'=(𝒞',_i') for every i∈{1,...,n},
 if there is an one-to-one mapping
f: 𝒞↦𝒞' such that
for every two distinct candidates a,b∈𝒞 and every i∈{1,2,....,n}, it holds that a_i b if and only if f(a)_i' f(b).
A voting correspondence  is neutral if for every two isomorphic elections
ℰ=(𝒞,𝒯) and ℰ'=(𝒞',𝒯'), and every c∈𝒞,
it holds that c∈(ℰ) if and only if f(c)∈(ℰ'), where f is the mapping as discussed above for
ℰ and ℰ'.


  Monotonicity. A voting correspondence  is monotonic if for every two elections
ℰ=(𝒞,𝒯=(T_1,...,T_n)), ℰ'=(𝒞,𝒯'=(T_1',...,T_n')),
and every c∈(ℰ) such that for every i∈{1,2,...,n}
    (1) T_i[𝒞∖{c}]=T_i'[𝒞∖{c}]; and
    (2) N^+_T_i(c)⊆ N^+_T_i'(c),
    it holds that c∈(ℰ').








  Majority. A voting correspondence  satisfies the majority criterion if for every
election ℰ=(𝒞,𝒯) where there is a candidate c∈𝒞 which is the source
in a majority of the tournaments in 𝒯, it holds that c∈(ℰ).


  Consistency. A voting correspondence  is consistent if for every two elections
ℰ=(𝒞,𝒯) and ℰ'=(𝒞,𝒯'), it holds that
(ℰ)∩(ℰ')⊆(ℰℰ').


  Pareto optimal. A voting correspondence  is Pareto optimal if for every election ℰ=(𝒞,𝒯) and every two candidates a,b∈𝒞 such that a≻ b in every tournament T=(𝒞,≻)∈𝒯, a∉(ℰ) implies b∉(ℰ).




Properties of Tournament Solutions.

To the names of the following properties of tournament solutions, we append a prefix “TS”, standing for “tournament solution”, to avoid confusion with the definitions of the axiomatic properties of voting correspondences.

-5pt
=-2pt

  Neutrality. Two tournaments T=(𝒞,)
and T'=(𝒞',') where |𝒞|=|𝒞'| are isomorphic if there is an one-to-one
mapping f: 𝒞↦𝒞' such that for every two a,b∈𝒞,
it holds that a b if and only if f(a)' f(b). Here, f is called an isomorphic mapping of T and T'.
A tournament solution  satisfies the neutrality criterion if for every two isomorphic tournaments
T=(𝒞,) and T'=(𝒞','), it holds that
(T')={f(a)∈𝒞'| a∈(T)}, where f is an isomorphic mapping of T and T'.


  Monotonicity. A tournament solution  is monotonic if for every two tournaments T=(𝒞,≻), T'=(𝒞,≻'),
and every candidate c∈(T) such that
T[𝒞∖{c}]=T'[𝒞∖{c}] and N^+_T(c)⊆ N^+_T'(c),
it holds that c∈(T').


  Condorcet consistency. A tournament solution 
is Condorcet consistent if for every
tournament T which admits the Condorcet winner w, (T)={w}.








Now we introduce two concepts of monotonicity of tournament solutions. To the best of our knowledge, they have not been studied in the literature. Generally speaking, a tournament solution is exclusive monotonic if a winning candidate c remains as a winning candidate when
c is preferred to more candidates, without changing the preferences between other candidates. Moreover,
no nonwinning candidate benefits from this, i.e., no nonwinning candidate becomes a winning candidate. So, if a tournament solution is exclusive monotonic, then making a winning candidate stronger never makes a nonwinning candidate better off. The formal definition is as follows.




  Exclusive monotonicity. A tournament solution  is
exclusive monotonic if for every two tournaments
T=(𝒞,≻), T'=(𝒞,≻'), and every  c∈(T) such that
    (1) T[𝒞∖{c}]=T'[𝒞∖{c}]; and
    (2) N^+_T(c)⊆ N^+_T'(c),
    it holds that c∈(T') and (T')⊆(T).



A tournament solution is exclusive negative monotonic if when
a nonwinning candidate c is preferred to more candidates, and some other nonwinning candidate becomes a winning candidate, then c must become a winning candidate as well. 
In other words, if extending the outneighborhood of c benefits some nonwinning candidates, then c must benefit from this operation. The formal definition is as follows.




  Exclusive negative monotonicity (ENM).
A tournament solution 
satisfies the ENM criterion,
if for every two tournaments T=(𝒞,≻) and T'=(𝒞,≻'),
and every candidate c∉(T) such that
    (1) T[𝒞∖{c}]=T'[𝒞∖{c}]; and
    (2) N^+_T(c)⊆ N^+_T'(c),
    it holds that (T')⊈(T) implies c∈(T').




Parameterized Complexity.
A parameterized problem is a language L ⊆Σ^*×ℕ, where Σ is a finite alphabet.
The first  ∈Σ^* is called the main part, and the second component ∈ℕ is called the parameter. Downey and Fellows <cit.> established the parameterized complexity theory and developed the following parameterized complexity hierarchy:

    ⊆⊆⊆...⊆.

In particular,  (stands for fixed-parameter tractable) includes all parameterized problems which admit O(f()·||^O(1))-time algorithms. Here f() is a computable function of k and |I| is the size of the main part.
Given two parameterized problems Q and Q', an -reduction from Q to Q' is an
algorithm that takes as input an instance (,) of Q and outputs an instance (',') of Q' such that 

(1) the algorithm runs in f()· ||^O(1) time, where f is a computable function in ;

(2) (,)∈ Q if and only if (',')∈ Q'; and

(3) '≤ g(), where g is a computable function in .

A problem is  for a positive integer i if all problems in  can be -reducible to the problem.
 problems are unlikely to admit -algorithms, unless the parameterized complexity hierarchy
collapses at some level <cit.>.




-5pt


§ AXIOMATIC PROPERTIES

In this section, we study axiomatic properties for -Approval for different tournament solutions .

It is fairly easy to check that -Approval is anonymous for all tournament solutions .
Moreover, -Approval is neutral for all tournament solutions
 which satisfy the neutrality criterion.
Furthermore, -Approval satisfies the majority criteria for all  that are Condorcet consistent. We now study some other properties for -Approval. Consider first the consistency criterion.




-Approval is consistent for all tournament solutions .


Let ℰ_1=(𝒞,𝒯_1) and ℰ_2=(𝒞,𝒯_2)
be two elections such that (ℰ_1)∩(ℰ_1)≠∅.
For a candidate c∈𝒞, it holds that

    cℰ_1+ℰ_2=cℰ_1+cℰ_2.

This directly implies that if a candidate c∈𝒞 has the highest score in both ℰ_1 and ℰ_2, then c has the highest score in the combined election ℰ_1+ℰ_2. It then follows that (ℰ_1ℰ_2)=(ℰ_1)∩(ℰ_2). 


Now we study the monotonicity of -Approval for all Condorcet consistent tournament solutions . It should be noted that almost all commonly used tournament solutions, including all tournament solutions studied in this paper, are Condorcet consistent. We derive both sufficient and necessary conditions for such -Approval to be monotonic.

-4pt


Let  be a Condorcet consistent tournament solution.
Then, -Approval is monotonic if and only if  satisfies the
exclusive monotonicity and ENM criteria.





Let  be a Condorcet consistent tournament solution as stated in the theorem and φ=-Approval.
Assume that  satisfies the exclusive monotonicity
and the ENM criteria.
Let  ℰ=(𝒞,𝒯=(T_1,...,T_n)) and
ℰ'=(𝒞,𝒯'=(T_1',...,T_n')) be two
elections with the same candidate set 𝒞.
Moreover, let c∈(ℰ) be a candidate such that
(1) T_i[𝒞∖{c}]=T_i'[𝒞∖{c}]; and
(2) N^+_T_i(c)⊆ N^+_T_i'(c) for every i∈{1,2,...,n}.
We shall show that c∈(ℰ'). Let's first study the scores of
the candidates in ℰ'.
Apparently, cℰ≥c'ℰ for every c'∈𝒞∖{c}.
Since  is exclusive monotonic, if c∈(T_i)
for some T_i∈𝒯, then c∈(T_i'). 
For each a∈𝒞, let 𝒲_a={i∈{1,2,...,n}| a∉(T_i), a∈(T_i')}.
The following claim is useful.

Claim. 𝒲_c'⊆𝒲_c for every c'∈𝒞∖{c}.

Let c' be a candidate in 𝒞∖{c}, and T_i and T_i' be two tournaments in 𝒯 and 𝒯', respectively, such that c'∉(T_i) and c'∈(T_i').
Clearly, (T')⊈(T).
Since  is exclusive monotonic, it must be that c∉(T_i); since otherwise,
(T')⊆(T), a contradiction. Then, since  satisfies
the ENM criterion, we know that c∈(T'). The claim follows.

Due to the above claim and discussions, for every c'∈𝒞∖{c}, 
-10pt


    cℰ'    =cℰ+|𝒲_c| 
       ≥c'ℰ+|𝒲_c| 
       ≥c'ℰ+|𝒲_c'|
       ≥c'ℰ'.

-10pt

Thus, c∈(ℰ'). 

It remains to prove the other direction. Assume that  is not exclusive monotonic. Then, there exist two tournaments T and T' over the same candidate set 𝒞 and a c∈(T) such that
(1) T[𝒞∖{c}]=T'[𝒞∖{c}];
(2)  N^+_T(c)⊆ N^+_T'(c); and
(3) c∉(T'), or c∈(T') but (T')⊈(T).
If c∉(T') in Condition (3), then, the election consisting of only one
vote defined as T obviously shows that -Approval is not monotonic. Otherwise,
we construct an election as follows. Let b be any arbitrary candidate in (T')∖(T).
The election consists of the following votes: 1 vote defined as T; 2 votes each defined as a tournament where
b is the source; 1 vote defined as a tournament where c is the source. Apparently, both b and c are winners in
the election, with each having two approvals. However, by replacing the vote defined as T by T', b gets one more approval from T',
implying c is no longer a winner. Therefore, in this case -Approval is not monotonic.

Assume that  does not satisfy the ENM
criterion. Then, there exist two tournaments T and T' and a c∉(T) such that
(1) T[𝒞∖{c}]=T'[𝒞∖{c}];
(2)  N^+_T(c)⊆ N^+_T'(c); and
(3) (T')⊈(T) and c∉(T').
We construct an election as follows. Let b be any arbitrary candidate in (T')∖(T).
The election consists of the following votes: 1 vote defined as T; 1 vote defined as a tournament where
b is the source; 1 vote defined as a tournament where c is the source. It is clear that both b and c are winners.
However, by replacing the vote defined as T by T', b gets one more approval from T',
implying c is no longer a winner. Therefore, in this case -Approval is not monotonic.



Due to Theorem <ref>, to check whether -Approval is monotonic for each ∈{TC,UC,CO}, we need only to investigate if  satisfies the exclusive monotonicity and ENM criteria. Though that the monotonicity of  for each ∈{CO,UC,TC} is apparent and has been studied in the literature <cit.>, whether  satisfies the two variants of the monotonicity criterion is not equally easy to see. In fact, we prove that among the three tournament solutions, only the top cycle satisfies the both the exclusive monotonicity and the ENM criteria. It then follows from this fact and Theorem <ref> that TC-Approval is monotonic, but CO-Approval and UC-Approval are not. Our results concerning the above discussion are summarized in Lemma <ref> and Theorem <ref> shown below.



 satisfies the exclusive monotonicity
and ENM criteria.



We first show that the  is exclusive monotonic.
Let T=(𝒞,≻) and T'=(𝒞,≻') be two tournaments, and c∈ TC(T) be a candidate such that
(1) T[𝒞∖{c}]=T'[𝒞∖{c}] and
(2) N^+_T(c)⊆ N^+_T'(c).
Since the  is monotonic <cit.>,
it holds that c∈T'.
It remains to show that T'⊆T. 
Due to the definition of the , it holds that T𝒞∖T. Then, it holds that T' 𝒞∖T. It directly follows that T'⊆T.


Now we prove that the  satisfies the ENM criterion.
Let T=(𝒞,) and T'=(𝒞,') be two tournaments, and c∈𝒞 be a candidate such that c∉TC(T), T[𝒞∖{c}]=T'[𝒞∖{c}], and N^+_T(c)⊆ N^+_T'(c).
Let CC_1,CC_2,...,CC_t be the maximal
strongly connected components of T.
It is known that for every two distinct CC_i and CC_j where
{i,j}⊆{1,2,...,t}, it holds that either
V(CC_i) V(CC_j) or V(CC_j) V(CC_i),
where V(CC_i) denotes the vertices of CC_i. 
Moreover, there is a unique ordering (CC_ρ(1),CC_ρ(2),...,CC_ρ(t)) where
{ρ(1),ρ(2),...,ρ(t)}={1,2,...,t} such that CC_ρ(i) CC_ρ(j)
for every 1≤ i< j≤ t <cit.>. 
Furthermore, T=CC_ρ(1).
Without loss of generality, assume that c∈ CC_ρ(i) for some 1< i≤ t.
We shall show that either T'=T, or T'⊈T and c∈T'.
Due to the above discussion, if CC_ρ(1)' {c} in T', then T'=T=CC_ρ(1). Assume now that there exists some candidate b in CC_ρ(1) such that c' b. We distinguish between the following cases to proceed the proof.

Case 1. CC_ρ(i)={c}, or |CC_ρ(i)|>1 and c is the source of T'[CC_ρ(i)].

Let j be the minimum integer such that i>j≥ 0 and {c}' ⋃_i> j'>jCC_ρ(j').
If j=0, then {c} is the top cycle of T'. Otherwise, (⋃_1≤ j'≤ jCC_ρ(j'))∪{c} is the top cycle of T'.

Case 2. |CC_ρ(i)|>1 and c is not the source of T'[CC_ρ(i)].

In this case, ⋃_1≤ j≤ iCC_ρ(j) is the top cycle of T'.

In summary, we can conclude that either T'=T, or T'⊈T and c∈T'. Thus, the  satisfies the ENM criterion.








Both the  and the  do not satisfy ENM.
Counter-examples can be found in fig:counterexamplecopucENM.
Due to Theorem <ref>, both CO-Approval and UC-Approval are not monotonic.
Due to Theorem <ref>, Lemma <ref>, and the above discussion, we have the following theorem.








TC-Approval is monotonic, and UC-Approval and CO-Approval are not monotonic.



Finally, we study the Pareto optimal criterion.
-5pt


TC-Approval is Pareto optimal, and CO-Approval and UC-Approval are not Pareto optimal.



We first show that TC-Approval is Pareto optimal.
Let =TC-Approval. Let ℰ=(𝒞,𝒯)
be an election and a,b∈𝒞 be two candidates such that a b in every T=(𝒞,)∈𝒯 and a∉(ℰ).
We need to prove that b∉(ℰ). It is clear that if a∉T for some T∈𝒯, then b∉T.
Therefore, aℰTC≥bℰTC.
Since a∉(ℰ), there is a candidate d∈𝒞∖{a} such that
dℰTC>aℰTC. As a result,
dℰTC>bℰTC, implying
that b∉(ℰ).

To prove that CO-Approval and UC-Approval are not Pareto optimal,
one only needs to check the election with four candidates a,b,c,d
and one vote with preference
a b, {b}{d,c}, {c}{a,d}
and d a. It is easy to see that {b, c} is the winning set
in CO-Approval, but all votes (in this case only one vote) prefer a to b.
On the other hand, {a,b,c} is the winning set in UC-Approval, but all votes prefer d to a.

















§ COMPLEXITY OF STRATEGIC BEHAVIOR


A voting system is immune to a constructive (resp. destructive) strategic voting problem if it is impossible to change a nonwinning (resp. winning) candidate to a winning (resp. nonwinning) candidate by performing the operations imposed in the definition of the problem.


An obstacle to the fairness of voting systems is strategic behavior, potentially carried out by strategic individuals. 
For instance, a strategic individual wants to change the election
result by adding/deleting some voters/candidates, or by bribing some voters.
We refer to <cit.>
for comprehensive surveys on this topic. In this section, we study the
complexity of strategic behavior in -Approval.
Complexity has been widely recognized as a barrier against strategic behavior <cit.>.
The point is that if it is  for the strategic individual to find out
how to successfully change the result, he might give up attacking the election.
Due to this, complexity of strategic behavior of voting systems can be also considered as a property to evaluate the voting systems <cit.>.
In this paper, wWe assume the familiarity of complexity theory.
For readers who are not familiar with complexity theory, we refer to <cit.>.

We particularly study the control and the bribery problems.
In each problem, there is a strategic individual
who has an incentive to influence the election result by modifying the registered election (see later for explanation of registered election).

Depending on the situations, the strategic individual may have the goal to
make a given distinguished candidate p win the registered election,
or have the goal to make p not win the registered election.
The former case is indicated by the word “constructive”, and
the latter case by the word  “destructive”.
Following the convention in the literature <cit.>,
for each problem studied in this paper,
we distinguish between the unique-winner model and the nonunique-winner model.
In the unique-winner model, winning an election means to be the unique winner, while
in the nonunique-winner model, winning an election means to be the unique winner
or to be a co-winner. 

Now we explain what modification operations the strategic individual
may perform. 




Control. In the control problems studied in this paper, the strategic individual may perform 
one of the following four modification operations:  
adding/deleting at most k votes/candidates, where k>0 is a given integer.
Therefore, the combination of the two goals and the four modification operations gives us
in total eight control problems denoted by CCAV, CCDV, CCAC, CCDC, DCAV, DCDV, DCAC and DCDC.
The first two characters “CC”/“DC” in the notations stand for “constructive control”/“destructive control”,
and the last two characters “AV”/“DV”/“AC”/“DC” stand for
“adding votes”/“deleting votes”/“adding candidates”/“deleting candidates”. 

In the inputs of all control problems, we have a set 𝒞 of candidates,
a list 𝒯 of votes over 𝒞,
a distinguished candidate p∈𝒞, and an integer k>0. A registered election consists of all registered candidates and registered votes.
In CCDV/DCDV, all candidates and votes are registered.
The question is whether the strategic individual can achieve
 goal by deleting at most k votes from 𝒯.
In CCAV/DCAV, all candidates are registered, but not all votes.
In particular, a sublist 𝒰⊆𝒯 of unregistered votes is given in the input.
The question is whether the strategic individual can achieve
 goal by adding (registering) at most k votes in 𝒰.
In CCDC/DCDC, all candidates and votes are registered.
The question is whether the strategic individual can achieve
 goal by deleting at most k candidates from 𝒞∖{p}.
It should be pointed out that the deletion of a candidate does not
affect the preference of a vote over the remaining candidates.
In CCAC/DCAC, all votes are registered but not all candidates.
In particular, a subset 𝒟⊆𝒞∖{p} of unregistered
candidates is given in the input.
The question is whether the strategic individual can achieve
his goal by adding (registering) at most k candidates in 𝒟.

The above defined control problems for many voting systems have been extensively studied in the literature. Due to the work of many researchers, the complexity of these control problems for almost all commonly used voting systems is known. A motivation of the study of control problems is that the issues of adding/deleting votes/candidates occur in many electoral settings, see, e.g., <cit.> for some concrete examples. In addition, as argued in <cit.>, adding voters pertains to simply encouraging some agents to vote, multiplying the existing
agents, or performing false-name attacks.
We refer to <cit.> for further discussions on control problems.

Bribery. We study two bribery problems: Constructive Bribery by Reversing Arcs (CBRA)
and Destructive Bribery by Reversing Arcs (DBRA).
In both problems we are given an election ℰ=(𝒞,𝒯), a distinguished candidate p∈𝒞, and an integer k>0.
The question is whether the strategic individual can achieve  goal
by reversing at most k arcs in total in tournaments in 𝒯.

We remark that CBRA and DBRA have already been studied under the name microbribery <cit.>. However, the complexity of CBRA/DBRA for -Approval has not been studied yet.

The study of bribery problems was initiated by Faliszewski, Hemaspaandra and Hemaspaandra FaliszewskiHH06, and since then many bribery problems have been proposed and studied <cit.>.
A major motivation of such studies is that bribery behavior in voting happens in many real-world situations, such as in political elections. 
Our results concerning the complexity of control and
bribery problems are summarized in Table <ref>. We achieve polynomial-time solvability results,  results, as well as  results for the control and bribery problems for -Approval for different tournament solutions .
We compare our complexity results for -Approval with the previous known results for the two most relevant voting systems Plurality and Approval.
Our results reveal that -Approval resists more types of strategic behavior than both Plurality and Approval.
 We need the following two problems to establish our hardness results.


Exact 3 Set Cover (X3C)

Input: A universal set U={c_1,c_2,...,c_3}
and a collection S of 3-subsets of U.

Question: Is there an S'⊆S
such that |S'|= and each c_i∈ U
appears in exactly one set of S'?




We assume that each element c_i∈ U occurs in
exactly three different 3-subsets of S. Thus,
we have that |S|=3. This assumption does not change the
 of the problem <cit.>.

A dominating set of a tournament T=(V,) is a vertex subset D of the tournament
such that for every vertex v not in D, there is a vertex u in D such that
u v.



Tournament Dominating Set (TDS)

Input: A tournament T=(V,) and an integer k>0.

Parameter: k.

Question: Does T have a dominating set of size at most k?




It is known that TDS is  <cit.>.

-3pt


 §.§ Complexity of Election Control

In this section, we study the complexity of control by adding/deleting votes/candidates for -Approval for difference tournament solutions . 
We first study CCAV and CCDV. We show that both problems for -Approval for  being several natural tournament solutions are , as summarized in the following theorem. Recall that both problems are polynomial-time solvable for Plurality but  for Approval <cit.>.



CCAV and CCDV are   for -Approval for every ∈{TC, UC, CO},
for both the unique-winner model and the nonunique-winner model.





We first consider  the unique-winner model of CCAV.
The following reduction applies to every ∈{TC, UC, CO}.
Let I=(U={c_1,c_2,...,c_3κ},S={s_1,s_2,...,s_3κ}) be
an instance of the X3C problem. We create an instance (𝒞,𝒯,p∈𝒞,𝒰⊆𝒯,k) for the CCAV problem as follows.

Candidates 𝒞. We create in total 3κ+2 candidates.
In particular, for each c_i∈ U, we create a candidate a(c_i).
In addition, we have a distinguished candidate p and a dummy candidate q.

Registered votes 𝒯∖𝒰. For each c_i∈ U, we create κ-1 votes,
each represented by a tournament where a(c_i) is the source. The arcs between candidates in 𝒞∖{a(c_i)}
are set arbitrarily. In addition, we create 1 vote defined as a tournament where p is the source. The arcs between candidates in
𝒞∖{p} can be set arbitrarily.

Unregistered votes 𝒰. For each s_i={c_x,c_y,c_z}∈ S where {x,y,z}⊆{1,2,...,3κ}, we create a vote  represented by a tournament T_s_i such that
a(c_x),a(c_y),a(c_z),p,q induce a regular subtournament

and, moreover there is an arc from every candidate in the set {a(c_x),a(c_y),a(c_z),p,q} to every candidate not in the set.
The arcs between candidates in 𝒞∖{a(c_x),a(c_y),a(c_z),p,q} are set arbitrarily.
Observe that for every ∈{TC, UC, CO},
it holds that (T_s_i)={c_x,c_y,c_z,p,q}. 

Finally, we set k=κ. It is easy to see that with the registered votes, each candidate
a(c_i) where i∈{1,...,3κ} has -Approval score κ-1,
the distinguished candidate p has -Approval score 1, and the
dummy candidate q has -Approval score 0.
Observe that q cannot have an equal or higher -Approval score than
that of p no matter which unregistered votes are added, since all
unregistered votes approve both p and q.
Observe further that adding any one unregistered vote increases the -Approval score
of some candidate a(c_i) where i∈{1,...,3κ} to κ.
Hence, in order to make p the unique winner, we need add exactly k
unregistered votes. As a result, p has -Approval score κ+1 in the final election.
Moreover, for every a(c_i) where i∈{1,...,3κ}, we can add only one unregistered vote that
approves a(c_i). This happens if and only if there is an exact 3-set cover.

The  reduction for the nonunique-winner model is similar to the
above reduction with the difference that 
we create one more registered vote for each c_i∈ U. 

Now we consider the CCDV problem for the unique-winner model.
We construct an instance (𝒞,𝒯,p∈𝒞,k) as follows.

Candidates 𝒞. We create in total 3κ+1 candidates in 𝒞.
In particular, for each c_i∈ U, we create a candidate a(c_i).
In addition, we have a distinguished candidate p.

Votes 𝒯. For each s_i={c_x,c_y,x_z}∈ S where {x,y,z}⊆{1,2,...,3κ},
we create a vote represented by a tournament T_s_i where a(c_x),a(c_y),a(c_z)
form a directed triangle and, moreover, there is an arc from every candidate
in {a(c_x),a(c_y),a(c_z)} to every candidate in 𝒞∖{a(c_x),a(c_y),a(c_z)}.
It is easy to check that (T_s_i)={a(c_x),a(c_y),a(c_z)} for
every ∈{TC, UC, CO}.
In addition, we create 3 votes,
each represented by a tournament where p is the source.

Since each c_i occurs in exactly three sets in S,
each a(c_i) where i∈{1,2,...,3κ} as well as p has -Approval score 3.
In order to make p the unique winner, for each a(c_i) where
i∈{1,...,3κ}, we need to delete one vote that approves a(c_i).
This happens if and only if there is an exact 3-set cover.

The  reduction for the CCDV problem for the nonunique-winner model is
similar to the above reduction,
with only the difference that we create one less vote corresponding to p,
so that the -Approval score of p in the original election is 2.



Now we consider DCAV and DCDV.
It is known that both problems are polynomial-time solvable for Plurality and Approval <cit.>.
We prove that both problems are polynomial-time solvable for every -Approval where  is a polynomial-time computable tournament solution.
A tournament solution  is polynomial-time computable if
for every tournament T, the set (T) can be calculated in
polynomial time in the size of T. It is well known that the
top cycle, the uncovered set and the Copeland set are
all polynomial-time computable <cit.>.
It is worth mentioning that there exist numerous tournament solutions such as the tournament equilibrium set which are not polynomial-time computable.
See <cit.> for further discussions.

-4pt

DCAV and DCDV are polynomial-time solvable for -Approval
such that  is polynomial-time computable,
for both the unique-winner model and the nonunique-winner model.


To prove the theorem, we reduce DCAV (resp. DCDV) for -Approval
where  is a polynomial-time computable tournament solution
to the same problem for Approval in polynomial time.
In particular, given an instance of
 DCAV (resp. DCDV)  for -Approval,
we calculate (T) for every vote T in the instance
(for both registered and unregistered votes if applicable). Since 
is polynomial-time computable, this can be done in polynomial time.
Then, we can get an instance of DCAV (resp. DCDV)  for
Approval by taking the same candidate set, and changing
each vote originally defined as a tournament T to a vote
defined as the dichotomous preference ((T),𝒞∖(T)),
where 𝒞 is the candidate set.
The theorem then follows from the fact that  DCAV (resp. DCDV) 
for Approval is polynomial-time solvable, for both the unique-winner
model and the nonunique-winner model <cit.>.




Theorem <ref> implies that
DCAV and DCDV are polynomial-time solvable for
TC-Approval, CO-Approval and UC-Approval.

Now we turn our attention to control by adding/deleting candidates.
In Plurality, each vote is defined as a linear order over the
candidates and the top ordered candidate is approved.
A linear order can be considered as a transitive tournament,
where there is an arc from a candidate a to another candidate b
if a is ordered before b. Thus, the top ordered candidate
in the linear order is the source of the transitive tournament.
It is clear that the top cycle,
Copeland set and uncovered set of a transitive tournament consist of exactly the source
of the tournament. Hence, CCAC/CCDC/DCAC/DCDC for Plurality is
a special case of the same problem for -Approval for every
∈{TC, UC, CO}.
Since CCAC/CCDC/DCAC/DCDC for Plurality is  <cit.>,
for both the unique-winner model
and the nonunique-winner model, the same problem for -Approval for each
∈{TC, UC, CO} is  as well[From a parameterized complexity point of view, Yang and Guo Yangaamas14b proved that the CCDC problem for Plurality is  with respect to the number of deleted candidates even in 3-peaked elections.
], as summarized in the following theorem.

-4pt

CCAC/CCDC/DCAC/DCDC is  for -Approval for every
∈{TC, UC, CO}, for both the unique-winner model
and the nonunique-winner model.





 §.§ Complexity of Bribery

Now we study CBRA and DBRA for -Approval for different tournament solutions .  
Since reversing an arc may make a transitive tournament intransitive, it does not make sense to study CBRA and DBRA for Plurality and Approval.





CBRA is  for UC-Approval,  for CO-Approval, and polynomial-time solvable for TC-Approval,

for both the unique-winner model and the nonunique-winner model.



Yang and Guo DBLP:conf/aldt/YangG13 studied a problem where
the given are a tournament and a distinguished vertex p in the tournament,
and the question is whether p can be made a king by reversing at most k
arcs. In particular, they proved that this problem is W[2]-hard with respect to k, by a reduction from the TDS  problem (See <cit.> for further details). This problem can be considered as a special case of the
nonunique-winner model of the CBRA problem for UC-Approval, where the instances consist of only one vote.
To prove the  of CBRA for
UC-Approval for the unique-winner model, we need only to create one more vote defined as a tournament
where the distinguished candidate p is the source (the arcs between other
candidates can be set arbitrarily) in the reduction in <cit.>.

Now we prove the  of CBRA for CO-Approval by a reduction from the X3C problem.
We first study the nonunique-winner model.
Let (U={c_1,c_2,...,c_3κ},S={s_1,s_2,...,s_3κ}) be
an instance of the X3C problem. We create an instance
(𝒞,𝒯,p∈𝒞,k=κ)
of CBRA as follows. Without loss of generality,
assume that k≥ 4.

Candidates 𝒞. We create in total 6κ+1 candidates in 𝒞. 
For each c_x∈ U, we create a candidate a(c_x). For each s_i∈ S, we create a candidate a(s_i). In addition, we have a distinguished candidate p.

Votes 𝒯. We create in total 3k^2+4k+2 votes. For ease of exposition, we divide the votes into three sublists A,B,C. The sublist A consists of the following votes. For each s_i={c_x,c_y,c_z}∈ S, we create a vote defined as a tournament H_s_i=(𝒞,_s_i) such that
(1) a(c_x) _s_i a(c_y), a(c_y)_s_i a(c_z), a(c_z)_s_i a(c_x);
(2) there is an arc from a(s_i) to every of {a(c_x),a(c_y),a(c_z)};
(3) there is an arc from every {a(c_x),a(c_y),a(c_z)} to every
candidate in 𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z)};
(4) there is an arc from a(s_i) to every candidate in
𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z),a(c_u),a(c_v)},
and an arc from each of {a(c_u), a(c_v)} to a(s_i), where a(c_u)
and a(c_v) are any two arbitrary candidates in
𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z),p}; and
(5) H_s_i[𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z)}] is regular.
It is easy to verify that in H_s_i, the Copeland score of
each a(s_i),a(c_x),a(c_y),a(c_z) is 6k-2, and of each other candidate
is at most ⌈6k-3/2⌉+2. Thus, the Copeland
set of H_s_i is {a(s_i),a(c_x),a(c_y),a(c_z)}. Moreover, due to the large
score gap between candidates in the Copeland set and candidates not in the
Copeland set (and due to k≥ 4), no candidate in
𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z)} can be included in the
Copeland set of H_s_i by reversing at most k arcs.
The sublist B consists of k+2 votes, each of which is defined as a tournament
such that p is the source, and the subtournament induced by
𝒞∖{p} is regular. Finally, the sublist C
consists of the following 3k^2 votes. For each c_x∈ U, we
create k votes, each of which is defined as a tournament such that a(c_x)
is the source and the subtournament induced by 𝒞∖{a(c_x)}
is regular. Notice that due to the regularity of the subtournaments
induced by all candidates except the sources in all tournaments constructed
in sublists B and C, it is impossible to change the Copeland set of
every tournament in B∪ C by reversing at most k arcs.
It is easy to verify that the CO-Approval score of p is k+2,
of each a(c_x) where c_x∈ U is k+3, and of each a(s_i) where s_i∈ S is 1.


Now we prove the correctness of the reduction.

(⇒:) Suppose that S'⊂ S is an exact 3-set cover, i.e.
|S'|=κ=k and for every c_x∈ U there is exactly one s∈ S' such
that c_x∈ s.
We shall show that we can make p a winner by reversing at most k arcs.
In particular, for each s_i={a_x,a_y,a_z}∈ S', we reverse the arc from a(s_i) to a(c_u), where a(c_u)
is one candidate in 𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z),p} such that
a(c_u)_s_i a(s_i), as defined above. After reversing this arc,
the Copeland set of H_s_i consists of only the candidate a(s_i).
As a result, the CO-Approval score of each {a(c_x),a(c_y),a(c_z)} decreases by one.
Since S' is an exact 3-set cover, due to the construction, after reversing
all these k arcs, the CO-Approval score of each a(c_x) where c_x∈ U
is k+2 and of each
a(s_i) where s_i∈ S is 1. Moreover, the CO-Approval score of p is k+2, implying that p is a winner.

(:⇐) Observe that due to the score gap between every a(s_i) where s_i∈ S and p, none of a(s_i) has a chance to have a CO-Approval score that is equal to or higher than that of p by reversing at most k arcs. Moreover, as discussed above, we cannot include p in the Copeland set of each tournament in A∪ C by reversing at most k arcs. Therefore, in order to make p a winner, for each a(c_x) where c_x∈ U, we need to decrease the number of tournaments whose Copeland sets include a(c_x) by at least one. Due to the above discussion, we cannot change the Copeland set of each tournament in B∪ C by reversing at most k arcs. Thus, the optimal solution is to reverse  arcs in tournaments in A. Moreover, if we attempt to reverse arcs in some tournament H_s_i in A, the optimal choice is to only reverse an arc from a(s_i) to a candidate a(c_u)∈𝒞∖{a(s_i),a(c_x),a(c_y),a(c_z),p} such that a(s_i)_s_i a(u) in H_s_i (such a candidate a(c_u) exists due to the construction of the votes), so that the CO-Approval score of each a(c_x),a(c_y),a(c_z) decreases by one. Let A' be the set of tournaments in A where an arc is reversed. Let S'={s_i| H_s_i∈ A'}. Due to the above discussion, for every c_x∈ U, there is at least one H_s_i∈ A' such that c_x∈ s_i. Since we can reverse at most k arcs, it holds that |A'|≤ k, implying that S' is an exact 3-set cover.

To prove the unique-winner model of the problem,
we need only to create one more vote in B in the above reduction.


Now we study destructive bribery by reversing arcs.



DBRA is  for UC-Approval, and polynomial-time solvable for TC-Approval and CO-Approval.
The results hold for both the unique-winner model and the nonunique-winner model.




We first prove the  of DBRA for UC-Approval for the nonunique-winner model.
We develop an -reduction from the TDS problem to the DBRA problem.

Let (T=(V,≻),k) be an instance of the TDS problem. Let n=|V|. We assume that n≥ (k+1)(2k+4). This assumption does not affect the W[2]-hardness of the TDS problem[If n≤ (k+1)(2k+3), we can add (k+1)(2k+4)-n additional vertices to the tournament such that there is an arc from every vertex in the original tournament to every newly added vertex.

].
We create an instance ℐ=(𝒞,𝒯,p∈𝒞,k) for DBRA as follows.

Candidates 𝒞. For each v∈ V, we create a candidate a(v). Let the distinguished candidate p be any arbitrary candidate a(w) such that w is not a king in T (in the W[2]-hardness reduction of the TDS problem in <cit.>, there exist vertices w which are not kings. Thus, such a candidate a(w) is well definedwe need to ensure that there is an isolated clique, say a triangle, in the graph G in the proof of Theorem 4.1 in <cit.>. In this case, each vertex in the isolated clique will not be a king.). In addition, we create an additional candidate q. Thus, 𝒞={a(v)| v∈ V}∪{q}.

Votes 𝒯. The list 𝒯 of votes consists of three sublists 𝒯_1,𝒯_2,𝒯_3 of votes. The list 𝒯_1 consists of only one vote T_1=(𝒞,_1), which is created first with a copy of T, i.e., a(v)_1 a(u) in T_1 if and only if v u in T. Then, we create an arc from every candidate in 𝒞∖{q} to q.

The list 𝒯_2 consists of 2k+3 votes, each of which is defined as a tournament such that q is the source. The arcs between every two candidates in 𝒞∖{q} are set arbitrarily. The construction of the votes in 𝒯_3 is a little involved. Let A be any arbitrary (k+1)(2k+3)-subset of 𝒞∖{p,q}, and B=𝒞∖ (A∪{p,q}). Let (A_0,A_1,...,A_2k+2) be any arbitrary partition of A such that |A_i|=k+1 for every i∈{0,1,...,2k+2}. Let f_i be any arbitrary one-to-one mapping from A_i to A_(i+1) (2k+3) for every i∈{0,1,...,2k+2}. We create in total 2k+3 votes in 𝒯_3. In particular, for each i∈{0,1,...,2k+2}, we create a vote defined as a tournament H_i such that

(1) there is an arc from p to every candidate in 𝒞∖ (A_i∪{p});

(2) there is an arc from a candidate a(v)∈ A_(i+1) (2k+3) to a candidate a(u)∈ A_i if and only if f_i(a(u))=a(v);

(3) there is an arc from every candidate in A_i to every candidate in 𝒞∖ (A_i∪ A_(i+1) (2k+3));

(4) there is an arc from every candidate in 𝒞∖{q} to q;

(5) H_i[A_i] is isomorphic to H_i[A_(i+1) (2k+3)]; and

(6) there is no source in H_i[A_i].

The arcs that are not specified above are set arbitrarily.
It is clear that such a tournament can be constructed in polynomial time. Observe that {p}∪{A_i} is the uncovered set of H_i. every candidate in B cannot reach p. since there is no source in H_i, for every candidate a(v)∈ A_(i+1) 2k+3 cannot reach at least one candidate in H_i.
Moreover, by constructing the votes this way, it is impossible to make q a king in each tournament H_i in 𝒯_3 by reversing at most k arcs. since to the cost of making q reach each candidate in A_i is at least one arc reversal.

Now we show the correctness of the reduction. It is easy to calculate that in the election, both p and q have the same UC-Approval score 2k+3, and every other candidate has UC-Approval score at most 2. Thus, {p,q} is the UC-Approval winning set of the election.

(⇒:) Let D⊆ V(T) be a dominating set of size at most k of T. After reversing all arcs a(v)q where v∈ D in T_1, q becomes a king in T_1. As a result, q has UC-Approval score 2k+4 and p still has UC-Approval score 2k+3, implying that p is no longer a winner.

(:⇐) Suppose that ℐ is a .

Observe that due to the large UC-Approval score gap between p and every candidate in 𝒞∖{p,q}, none of 𝒞∖{p,q} has a chance to have a higher score than that of p by reversing at most k arcs. Therefore, q is the only candidate which can prevent p from being a winner.

Moreover, due to the above discussion, it is impossible to make q a king in each vote in 𝒯_3 by reversing at most k arcs. Given that q is the unique king in each tournament in 𝒯_2, in order to prevent p from being a winner, q has to become a king in the first vote T_1 by reversing at most k arcs. This happens only if there is a dominating set of T of size at most k

.


To prove the unique-winner model, we need only to create one less tournament in 𝒯_2. 

Now we develop a polynomial-time algorithms for DBRA for TC-Approval for the nonunique-winner model and CO-Approval. 

TC-Approval. Let (𝒞,𝒯,p∈𝒞, k) be an instance where p is a TC-Approval winner. Let m=|𝒞|. We assume that m≥ 3 (otherwise, we can easily solve the problem). To prevent p from being a winner, we need to make a candidate q have a higher TC-Approval score than that of p by reversing at most k arcs. Based on this observation, the algorithm breaks down the given instance into m-1 subinstances, each of which takes a candidate q≠ p together with (𝒞,𝒯,p∈𝒞, k) as the input, and asks whether q can have a higher TC-Approval score than that of p by reversing at most k arcs. Obviously, the original instance is a  if and only if at least one of the subinstances is a . It remains to develop a polynomial-time algorithm to solve each subinstance. The following claim is useful.

Claim. Let H=(V,) be a tournament and c∈ V a candidate not in the top cycle of H.
Then, we can make c be included in the top cycle of H by reversing only one arc.

Proof of the claim. Let



CC_ρ(1),CC_ρ(2),...,CC_ρ(t) be the unique ordering of the maximal strongly connected components of H

such that CC_ρ(i) CC_ρ(j)
for every 1≤ i< j≤ t.

The top cycle
of H is exactly CC_ρ(1). Assume that
c∈ CC_ρ(i) for some 1< i≤ t. Then,

by reversing any one arbitrary arc between c and a candidate in CC_ρ(1),



⋃_1≤ j≤ i V(CC_j) becomes the
top cycle of the tournament (see the proof of Lemma <ref> for some additional details). This completes the proof of the above claim.


Since m≥ 3, it is impossible to decrease the score gap between p and q by 2 by reversing 1 arc.

Then, due to the above claim,

to prevent p from being a winner, an optimal choice is to reverse

arcs in the tournaments whose top cycles do not include q in advance.

Precisely, the algorithm finds all tournaments in the subinstance where q is not in the top cycle. Let k' be the number of such tournaments. Then, due to the above discussion, we can increase the TC-Approval score of q by min{k,k'} without changing the TC-Approval score of p, by reversing min{k,k'} arcs.

As a result, if qℰTC+min{k,k'}≥pℰTC where ℰ=(𝒞,𝒯), the subinstance is a ; otherwise, it is a .


It should be noted that Papadimitriou and Yannakakis <cit.> devised an O(n^O(logn))-time algorithm for the TDS problem, which implies that the TDS problem is probably not , unless ⊆ Dtime(n^logn). In fact, Downey and Fellows proved the  of the TDS problem by a reduction from the Dominating Set problem which is both  and  <cit.>. However, the reduction is an -reduction but not a polynomial-time reduction—it takes O(2^O(k)· poly(n)) time where n is the number vertices of the given tournament and k is the solution size. Hence, our reductions in the proofs of Theorems <ref> and <ref> do not imply that DBRA and CBRA for UC-Approval are . Whether DBRA and CBRA for UC-Approval are  remain open.




§ CONCLUDING REMARKS

-4pt
We have studied a class of approval-based voting correspondences for
the scenario where voters may have intransitive preferences.

Each newly introduced voting correspondence -Approval is a natural combination of the classic Approval correspondence and a well-studied tournament solution .
In particular, each voter with preference T is assumed to approve all
candidates in (T) and disapprove all the remaining candidates. The
winners are the ones receiving the most approvals. This class of new
voting correspondences extends the classic Approval voting to the settings where
voters have intransitive preferences. Note taht an intransitive preference is not necessarily to be cast by a single voter, but can be drawn from the preferences of voters in a subvoting, as we illustrated in the introduction. As far as we know, such -Approval voting correspondence has not been studied in the literature.

In this paper, we first showed that -Approval satisfies
several axiomatic properties for ∈{CO,TC,UC}. As a byproduct, we proposed two new concepts of monotonicity criteria of tournament
solutions, namely, the exclusive monotonicity and the ENM, and proved that the top cycle satisfies both monotonicity criteria, while the Copeland set and the uncovered set fail to satisfy  ENM.
Then, we investigated the complexity of
constructive/destructive control by adding/deleting voters/candidates and
constructive/destructive bribery by reversing arcs for -Approval for ∈{CO,UC,TC}.
Our results reveal that -Approval
resists more types of strategic behavior than both Plurality and Approval.
See Table <ref> for a summary of our complexity results.



There remain several open questions for future research. For instance, is top cycle the minimal tournament solution that satisfies neutrality, exclusive monotonicity and ENM? In addition, it is interesting to explore whether CBRA and DBRA for UC-Approval are .


plain
10

AAAI2015AzizBCEFW
H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh.
Justified representation in approval-based committee voting.
In AAAI, pages 784–790, 2015.

Bartholdi92howhard
J. J. Bartholdi III, C. A. Tovey, and M. A. Trick.
How hard is it to control an election?
Math. Comput. Model., 16(8-9):27–40, 1992.

baumeisterapproval09
D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. A. Hemaspaandra, and
  J. Rothe.
Computational Aspects of Approval Voting, chapter 10, pages
  199–251.
Handbook on Approval Voting. Springer Berlin Heidelberg, 2010.

DBLP:conf/birthday/BetzlerBCN12
N. Betzler, R. Bredereck, J. Chen, and R. Niedermeier.
Studies in computational aspects of voting – A parameterized
  complexity perspective.
In The Multivariate Algorithmic Revolution and Beyond, pages
  318–363, 2012.

handbookofcomsoc2015Cha3Brandt
F. Brandt, M. Brill, and P. Harrenstein.
Tournament solutions.
In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia,
  editors, Handbook of Computational Social Choice, chapter 3. Cambridge
  University Press, 2016.

handbookofcomsocBrandt2016
F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors.
Handbook of Computational Social Choice.
Cambridge University Press, 2016.

Brandt2010
F. Brandt, F. Fischer, P. Harrenstein, and M. Mair.
A computational analysis of the tournament equilibrium set.
Soc. Choice. Welf., 34(4):597–609, 2010.

BrandtS2014ORDiscrimitiveTournament
F. Brandt and H. G. Seedig.
On the discriminative power of tournament solutions.
In GOR, pages 53–58, 2014.

DBLP:conf/aaai/BredereckFNT16
R. Bredereck, P. Faliszewski, R. Niedermeier, and N. Talmon.
Complexity of shift bribery in committee elections.
In AAAI, pages 2452–2458, 2016.

DBLP:journals/jair/BredereckFNT16
R. Bredereck, P. Faliszewski, R. Niedermeier, and N. Talmon.
Large-scale election campaigns: Combinatorial shift bribery.
J. Artif. Intell. Res. (JAIR), 55:603–652, 2016.

Douglas2000
D. B.West.
Introduction to Graph Theory.
Prentice-Hall, 2000.

DBLP:conf/sofsem/ChevaleyreELM07
Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet.
A short introduction to computational social choice.
In SOFSEM (1), pages 51–69, 2007.

DBLP:conf/aaai/DeyMN16
P. Dey, N. Misra, and Y. Narahari.
Frugal bribery in voting.
In AAAI, pages 2466–2472, 2016.

fellowsfeasibility92
R. G. Downey and M. R. Fellows.
Parameterized computational feasibility.
In Feasible Mathematics II, pages 219–244, 1995.

fellows99
R. G. Downey and M. R. Fellows.
Parameterized Complexity.
Springer, 1999.

DBLP:series/txcs/DowneyF13
R. G. Downey and M. R. Fellows.
Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013.

DBLP:conf/www/DworkKNS01
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar.
Rank aggregation methods for the web.
In WWW, pages 613–622, 2001.

Egan2014
P. J. Egan.
Do something politics and double-peaked policy preferences.
J. Polit., 76(2):333–349, 2014.

DBLP:conf/atal/ElkindFSS14
E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko.
Properties of multiwinner voting rules.
In AAMAS, pages 53–60, 2014.

DBLP:conf/uai/Elkind014
E. Elkind and N. Shah.
Electing the most probable without eliminating the irrational: Voting
  over intransitive domains.
In UAI, pages 182–191, 2014.

FaliszewskiHH06
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra.
The complexity of bribery in elections.
In AAAI, pages 641–646, 2006.

DBLP:journals/jair/FaliszewskiHH09
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra.
How hard is bribery in elections?
J. Artif. Intell. Res. (JAIR), 35:485–532, 2009.

DBLP:journals/jair/FaliszewskiHH15
P. Faliszewski, E. Hemaspaandra, and L. A. Hemaspaandra.
Weighted electoral control.
J. Artif. Intell. Res., 52:507–542, 2015.

DBLP:journals/jair/FaliszewskiHHR09
P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe.
Llull and Copeland voting computationally resist bribery and
  constructive control.
J. Artif. Intell. Res., 35:275–341, 2009.

DBLP:conf/atal/FaliszewskiHS10
P. Faliszewski, E. Hemaspaandra, and H. Schnoor.
Manipulation of Copeland elections.
In AAMAS, pages 367–374, 2010.

Fishburm81
P. C. Fishburn and S. J. Brams.
Approval voting, Condorcet's principle, and runoff elections.
Public. Choice., 36(1):89–114, 1981.

DBLP:conf/aaai/FreemanBC14
R. Freeman, M. Brill, and V. Conitzer.
On the axiomatic characterization of runoff voting rules.
In AAAI, pages 675–681, 2014.

garey
M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of
  NP-Completeness.
W. H. Freeman, New York, 1979.

DBLP:journals/tcs/Gonzalez85
T. F. Gonzalez.
Clustering to minimize the maximum intercluster distance.
Theoret. Comput. Sci., 38:293–306, 1985.

DBLP:journals/ai/HemaspaandraHR07
E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe.
Anyone but him: The complexity of precluding an alternative.
Artif. Intell., 171(5-6):255–285, 2007.

DBLP:conf/atal/KaczmarczykF16
A. Kaczmarczyk and P. Faliszewski.
Algorithms for destructive shift bribery.
In AAMAS, pages 305–313, 2016.

Kalech2011
M. Kalech, S. Kraus, G. A. Kaminka, and C. V. Goldman.
Practical voting rules with partial information.
Auton. Agent. Multi-AG., 22:151–182, 2011.

Kilgour2014Marshall
D. M. Kilgour and E. Marshall.
Approval balloting for fixed-size committees.
In D. S. Felsenthal and M. Machover, editors, Electoral
  Systems, Studies in Choice and Welfare, pages 305–326. Springer Berlin
  Heidelberg, 2012.

KirchsteigerP1996Intransitive
G. Kirchsteiger and C. Puppe.
Intransitive choices based on transitive preferences: The case of
  menu-dependent information.
Theor. Decis., 41:37–58, 1996.

Landau1953tournamentking
H. Landau.
On dominance relations and the structure of animal societies III.
  the condition for score structure.
B. Math. Biophys., 15(2):143–148, 1953.

DBLP:conf/icaart/Lin11
A. P. Lin.
The complexity of manipulating k-Approval elections.
In ICAART (2), pages 212–218, 2011.
http://arxiv.org/abs/1005.4159.

DBLP:journals/prl/LuminiN06
A. Lumini and L. Nanni.
Detector of image orientation based on Borda count.
Pattern. Recongn. Lett., 27(3):180–186, 2006.

MSYangIJCAI2015
M. Mnich, Y. R. Shrestha, and Y. Yang.
When does Schwartz Conjecture hold?
In IJCAI, pages 603–609, 2015.

Monjardet1978
B. Monjardet.
An axiomatic theory of tournament aggregation.
Math. Oper. Res., 3(4):334–351, 1978.

Moon2013
J. M. Moon.
Topics on tournaments.
http://www.gutenberg.org/ebooks/42833, 1968.

DBLP:journals/jcss/PapadimitriouY96
C. H. Papadimitriou and M. Yannakakis.
On limited nondeterminism and the complexity of the V-C dimension.
J. Comput. Syst. Sci., 53(2):161–170, 1996.

DBLP:conf/aaai/PiniRV13
M. S. Pini, F. Rossi, and K. B. Venable.
Bribery in voting with soft constraints.
In AAAI, pages 803–809, 2013.

SaarinenTG2014AAAIworkshopIntransitivePreference
C. A. Tovey S. Saarinen and J. Goldsmith.
A model for intransitive preferences.
In MPREF@AAAI2014, pages 85–89, 2014.

DBLP:journals/scw/Schulze11
M. Schulze.
A new monotonic, clone-independent, reversal symmetric, and
  Condorcet-consistent single-winner election method.
Soc. Choice. Welfare., 36(2):267–303, 2011.
.

DBLP:conf/aaai/SkowronF15
P. K. Skowron and P. Faliszewski.
Fully proportional representation with Approval ballots:
  Approximating the MaxCover problem with bounded frequencies in FPT
  time.
In AAAI, pages 2124–2130, 2015.



DBLP:journals/interfaces/Tovey02
C. A. Tovey.
Tutorial on computational complexity.
Interfaces., 32(3):30–61, 2002.



Tversky1969intranstivepreferences
A. Tversky.
Intransitivity of preferences.
Psychol. Review., 76:31–48, 1969.

DBLP:conf/sigecom/Xia15
L. Xia.
Generalized decision scoring rules: Statistical, computational, and
  axiomatic properties.
In EC, pages 661–678, 2015.

DBLP:conf/atal/XiaCL10
L. Xia, V. Conitzer, and J. Lang.
Aggregating preferences in multi-issue domains by using maximum
  likelihood estimators.
In AAMAS, pages 399–408, 2010.

Yang2016FurtherstepTES
Y. Yang.
A Further Step Towards an Understanding of the Tournament Equilibrium Set,
http://arxiv.org/abs/1611.03991, 2016.


DBLP:conf/aldt/YangG13
Y. Yang and J. Guo.
Possible winner problems on partial tournaments: A parameterized
  study.
In ADT, pages 425–439, 2013.

Yangaamas14b
Y. Yang and J. Guo.
The control complexity of r-Approval: from the single-peaked
  case to the general case.
In AAMAS, pages 621–628, 2014.

Yangaamas14a
Y. Yang and J. Guo.
Controlling elections with bounded single-peaked width.
In AAMAS, pages 629–636, 2014.

AAMAS15YangSG
Y. Yang, Y. R. Shrestha, and J. Guo.
How credible is the prediction of a party-based election?
In AAMAS, pages 1431–1439, 2015.

AAMAS15YangSGpartybribery
Y. Yang, Y. R. Shrestha, and J. Guo.
How hard is bribery in party based elections?
In AAMAS, pages 1725–1726, 2015.
extended abstract.

ECAI2016YangSGDistanceRestrictedBribery
Y. Yang, Y. R. Shrestha, and J. Guo.
How hard is bribery with distance restrictions?
In ECAI, pages 363–371, 2016.


