# query_complexity_of_tournament_solutions__dd531107.pdf

Query Complexity of Tournament Solutions

Palash Dey Indian Institute of Science, Bangalore

A directed graph where there is exactly one edge between every pair of vertices is called a tournament. Finding the best set of vertices of a tournament is a well studied problem in social choice theory. A tournament solution takes a tournament as input and outputs a subset of vertices of the input tournament. However, in many applications, for example, choosing the best set of drugs from a given set of drugs, the edges of the tournament are given only implicitly and knowing the orientation of an edge is costly. In such scenarios, we would like to know the best set of vertices (according to some tournament solution) by querying as few edges as possible. We, in this paper, precisely study this problem for commonly used tournament solutions: given an oracle access to the edges of a tournament T , find f(T ) by querying as few edges as possible, for a tournament solution f. We first show that the set of Condorcet non-losers in a tournament can be found by querying 2n log n 2 edges only and this is tight in the sense that every algorithm for finding the set of Condorcet non-losers needs to query at least 2n log n 2 edges in the worst case, where n is the number of vertices in the input tournament. We then move on to study other popular tournament solutions and show that any algorithm for finding the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and the top cycle must query Ω(n2) edges in the worst case. On the positive side, we are able to circumvent our strong query complexity lower bound results by proving that, if the size of the top cycle of the input tournament is at most k, then we can find all the tournament solutions mentioned above by querying O(nk + n log n/log(1 1/k)) edges only.

Introduction

Many scenarios in multiagent systems can often be modeled and analyzed using tournaments (Mou86; BBFH14). An important example of such scenarios is voting where we have a set of alternatives and a set of votes which are linear orders over the set of alternatives. A important tournament to consider in this context is defined by the majority relation induced by the set of votes. In the majority relation, an alternative x is preferred over another alternative y if x is preferred over y in a majority of the votes. Indeed, many

Copyright 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

important voting rules, like Copeland for example, are defined using the tournament induced by the majority relation of the input set of votes. Other than voting, tournaments have found many applications in multi-criteria decision analysis (AR+86; BMP+06), zero-sum games (FR95; DLB96), coalitional games (BH10), argumentation theory (Dun95; Dun07), biology (CH07), etc.

Formally, a tournament is defined as a set of alternatives along with an irreflexive, antisymmetric, and total relation, called dominance relation, on the set alternatives. An equivalent and often more convenient view of a tournament is as a directed graph on the alternatives where, between every pair of vertices (which corresponds to the alternatives), there is exactly one edge. A tournament solution takes a tournament as input and outputs a subset of the vertices. Tournament and tournament solutions are important mathematical tools in any general situation where we have to make a choice from a set of alternatives solely based on pairwise comparisons. Motivation. We often have situations where the input tournament is given implicitly the vertices of the tournament are given explicitly and we have to query for an edge to know its orientation. Moreover, knowing the orientation of an edge of the tournament can often be costly. For example, we can think of an application where we have a set of drugs for a particular disease and we want to know the best (according to some tournament solution) set of drugs. A natural dominance relation in this context would be to define a drug x to dominate another drug y if the probability that the drug x cures the disease is more than the corresponding probability for the drug y. Since these probabilities are often not known a priori, estimating them often requires extensive lab experiments as well as clinical trials. Hence, we would like to make as few queries as possible to know the best set of drugs. More generally, we can think of any tournament based voting rules like Copeland in an election scenario. A tournament based voting rule chooses winners solely based on the tournament induced by the pairwise majority relation between the alternatives. However, in many applications of voting in multiagent systems, recommender systems (PHG00) for example, the number of voters is huge and consequently, learning the majority relation is costly. Hence, we would like to learn the set of most popular items (according to the tournament solution under consideration)

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

with the smallest number of queries possible. Motivated by these applications, we study, for a tournament solution f, the problem of finding f(T ) of an input tournament T by querying smallest number of edges possible. A query for an edge, in our model, reveals the orientation of the edge in the input tournament. Finding the query complexity of various graph properties has drawn significant attention in literature. In the most general setting, the input is a directed graph on n vertices and one has to find whether the input graph satisfies some property we are concerned with, by asking a minimum number of queries. A query is a question of the form: Is there an edge from a vertex x to another vertex y? The query complexity of a property is the worst case number of queries that must be made to know whether the input graph has that property. A graph property, in this context, is called evasive if its query complexity is n(n 1), that is, one has to query all possible edges of the input digraph to test the property in the worst case. Karp conjectured that every monotone and nontrivial graph property is evasive. A graph property is monotone if it continues to hold even after adding more edges and nontrivial if it holds for some but not all graphs. A substantial amount of research effort has provided increasingly better query complexity lower bounds for monotone and nontrivial properties, although Karp s conjecture remained open (KSS84; Kin88; RV76; Ros73; CKS01; Kul13; KT10). In the case of tournaments (where there is exactly one edge between every pair of vertices), Balasubramanian et al. (BRS97) showed (rediscovered by Procaccia (Pro08)) that a Condorcet winner a vertex with n 1 outgoing edges can be found, if it exists, with 2n logn 2 queries and this query complexity upper bound is tight in the worst case. This further motivates us to study the query complexity of other commonly used tournament solutions. Our Contribution. In this paper, we prove tight bounds on the query complexity of commonly used tournament solutions. Our specific contributions in this paper are as follows.

We show that the query complexity of the problem of finding the set of Condorcet non-losers is 2n logn 2 [Observation 1].

We show that any algorithm for finding the Copeland set, the Slater set, and the Markov set in a tournament has query complexity (n 2) [Theorem 1]. We remark that Goyal et al. (GJR17) also discovered this result independently (and in parallel) around same time.

We prove that any algorithm for finding the bipartisan set [Theorem 2], the uncovered set [Theorem 3], the Banks set [Theorem 4], and the top cycle [Theorem 5] has query complexity Ω(n2).

We complement the our strong query complexity lower bounds above by showing that, if the tournament T has a top cycle of size at most k, then the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and the top cycle of a tournament T can be found using O(nk + n log n/log(1 1/k)) queries [Theorem 6 and 7].

Related Work. The work of Balasubramanian et

al. (BRS97) (rediscovered by Procaccia (Pro08)) is the closest predecessor of our work where he shows that the query complexity of Condorcet winner in tournaments is 2n logn 2. There have been several other works in the literature which study the query complexity of various problems in tournaments. For example, Noy and Naor use comparison-based sorting algorithms to find feedback sets and Hamiltonian paths in tournaments (BNN90). There have been works in computational social choice theory on communication complexity of different voting rules (CS02) and query complexity of preference elicitation in various domains (Con09; DM16a; DM16b; Dey16b). However, the querying model in the above works is completely different from ours and consequently, neither the results nor the techniques involved in these works are directly applicable to our work; a query in the works above asks: Does a voter v prefer an alternative x over another alternative y?

Preliminaries

For a positive integer ℓ, we denote the set {1,2,...,ℓ} by [ℓ]. For a finite set X and a positive integer ℓ, we denote the set of all subsets of X of size ℓby Pℓ(X) and the set of all probability distributions on X by Δ(X). Tournaments. A tournament T = (V,E) is a directed graph on a set V of n vertices such that, for any two vertices u,v V, either (u,v) E or (v,u) E but not both. If not mentioned otherwise, we denote the number of voters by n. We call any subgraph of a tournament a partial tournament. We call a tournament balanced if the in-degree and out-degree of every vertex are the same. A tournament T defines a relation T on the set of vertices V: u T v if (u,v) T . Alternatively, any irreflexive, antisymmetric, and total relation on a set V defines a tournament T = (V,E) where (u,v) E if u v. When there is no possibility of confusion, we drop T from the subscript of . We call the relation T associated with a tournament T the dominance relation of T . We say a vertex u dominates or defeats another vertex v if u T v. Let us define the dominion D(v) of a vertex v as D(v) = {u V v u} and D(v) is called the dominators of v. Given a tournament T , let A(T ) be its adjacency matrix. We call the matrix G(T ) = A(T ) A(T )t the skew-adjacency matrix of T , where A(T )t is the transpose of A(T ). A vertex v is called the Condorcet winner of a tournament if the out-degree of v is n 1; alternatively, a vertex v is the Condorcet winner if v u for every u V {v}. Given a set V, we denote the set of all tournaments over V by T(V). A tournament solution f V >0T(V) 2V { } is a function that takes a tournament as input and selects a nonempty set of vertices as output. Examples of commonly used tournament solutions are as follows (MBC+16, Chapter 3). Condorcet non-loser: The Condorcet non-loser set of a tournament is the set of all vertices which has at least one outgoing edge. Copeland set: The Copeland set of a tournament is the set of vertices with maximum out-degree. Slater set: Given a tournament T = (V, ), let us denote the maximal element of V according to a strict linear order

> on V by max(>). The Slater score of a strict linear order > over V with respect to tournament T = (V, ) is > where > = {(x,y) V V x > y,x y}. A strict linear order is a Slater order if it has maximum Slater score. Then the Slater set is defined as SL(T ) = {max(>) : > is a Slater order for T }. Markov set: Given a tournament T = (V,E), we define a Markov chain M(T ) as follows. The states of the Markov chain M(T ) are the vertices of T and the transition probabilities are determined by the dominance relation: in every step, stay in the current state v with probability D(v) / T 1, and move to state u with probability 1/ T 1 for all u D(v). The Markov set is the the set of vertices that have maximum probability in the unique stationary distribution of M(T ). Formally, the transition matrix of the Markov chain is defined as.

Q = 1 T 1 (A(T )t + diag(CO))

where diag(CO) is the diagonal matrix of the Copeland scores. Markov set MA(T ) of a tournament T is then given by MA(T ) = argmaxa V{p(a) p Δ(V),Qp = p}. Bipartisan set: Bipartisan set generalizes the notion of Condorcet winner to lotteries over the vertices of the tournament. Interestingly, for every tournament T = (V,E), there exists a unique maximal lottery (MBC+16). That is, there exists a probability distribution p Δ(V) such that, for the skew-adjacency matrix G(T ) = (gab)a,b V of T , a,b V p(a)q(b)gab 0 for all q Δ(V) which is, by convexity, equivalent to the following condition.

a V p(a)gab 0 for all b V (1)

Let p T denote the unique maximal lottery of T . Then the bipartisan set BP(T ) of T is defined as the support of p T . That is, BP(T ) = {a V p T (a) > 0} Uncovered set: Given a tournament T =(V, ), we say a vertex v V covers another vertex u V if D(u) D(v) and is denoted by v Cu. We observe that v Cu implies v u and is equivalent to D(v) D(u). The uncovered set UC(T ) of a tournament T is given by the set of maximal elements of the covering relation C. That is,

UC(T ) = {v V u Cv for no u V}

Banks set: A sub-tournament of a tournament T = (V,E) is an induced subgraph of T . The Banks set BA(T ) is the set of maximal elements of all the maximal transitive subtournaments of T . Top cycle: A non-empty subset of vertices B V is called dominant in a tournament T = (V, ) if x y for every x B and y V B. Dominant sets are linearly ordered via set inclusion and the top cycle returns the unique smallest dominant set. A tournament solution is called neutral if the output does not depend on the names of the input set of vertices. All the tournament solutions discussed above are neutral. Essential States in a Markov Chain. A state i in a finite Markov chain is called essential if for every state j that is

reachable from i, the state i is also reachable from j. A state is called inessential if it is not essential. A well known fact from probability theory is that, π(i) = 0 for every inessential state i, where π is a stationary distribution of the Markov chain. Hence, every vertex whose corresponding state in the Markov chain is inessential, does not belong to the Markov set of that tournament. We refer the reader to (Br e13) for a more detailed discussion on Markov chains. Query Model. Given a tournament T = (V,E) on n vertices, a query for a pair of vertices {x,y} P2{V} reveals whether (x,y) E or (y,x) E. The query complexity of an algorithm is the maximum number of queries the algorithm makes in the worst case. The query complexity of a tournament solution f is the minimum query complexity of any algorithm for computing f.

Query Complexity Lower Bounds of Tournament Solutions

We begin with the following observation which gives us the query complexity of the Condorcet non-loser set of tournaments.

Observation 1 The query complexity of the Condorcet nonloser set in tournaments is equal to the query complexity of the Condorcet winner in tournaments. Hence, the query complexity of the Condorcet non-loser set in tournaments is 2n logn 2.

Proof: Given a tournament T = (V,E), let us define another tournament T = {V,E}, where E = {(x,y) (y,x) E}. Now the result follows from the observation that a vertex v is a Condorcet non-loser in T if and only if v is not the Condorcet winner in T . Now the 2n logn 2 query complexity of the Condorcet non-loser set follows from the 2n logn 2 query complexity of the Condorcet winner in tournaments (BRS97).

We next consider the query complexity of the Slater set of tournaments. The following result provides a necessary condition for a vertex to belong to the Slater set of a tournament. We will use it to prove query complexity lower bound of the Slater set. In the interest of space, we defer the proof of Lemma 1 to the full version of the paper (Dey16a).

Lemma 1 Suppose the out-degree of a vertex v V in a tournament T = (V,E) on n vertices is strictly less than (n 1)/2. Then v does not belong to the Slater set of T .

Let us consider the tournament Treg = (V,E) on n vertices V = {ai i [n]}. We assume n to be an odd integer. In Treg, vertex ai defeats ai+j (mod n) for every i [n] and j [(n 1)/2]. We will use the tournament Treg crucially in our proofs of the query complexity lower bounds of the Copeland set, the Slater set, and the Markov set. The following result is immediate from the definition of neutral tournament solutions.

Lemma 2 Given the tournament Treg as input, every neutral tournament solution outputs the set of all vertices in Treg.

Suppose there exists an edge from a vertex u to another vertex v in Treg. Let T u,v reg be the tournament which is the same as Treg except the edge from u to v is reversed, that is, T u,v reg = Treg {(v,u)} {(u,v)}. The following lemma will be used crucially in our proofs of the query complexity lower bounds of the Copeland set, the Slater set, and the Markov set.

Lemma 3 The Copeland set, the Slater set, and the Markov set of T u,v reg do not contain u.

Proof: Copeland set: For the Copeland set, the result follows from the observation that u is no longer a vertex with highest out-degree in T u,v reg. Slater set: For the Slater set, the result follows immediately from Lemma 1 since the out-degree of u is strictly smaller than (n 1)/2 in T u,v reg. Markov set: If possible, let us assume that the stationary distribution of the Markov chain M(T u,v reg) associated with the tournament T u,v reg be π such that π(a) = p for every a [n] {u,v}. Then we have the following.

p + π(u) 2 n + 1 = π(v) (2)

n 1 = π(u) (3)

π(u) + (n 2)p + π(v) = 1 (4)

We first observe that, since the Markov chain M(T u,v reg) is ergodic, it has a unique stationary distribution. Now, since there exists an unique solution to the equations above, the stationary distribution π of M(T u,v reg) is indeed of the form we assumed (that is, π(a) = p for every a [n] {u,v}). We observe that equation 3 shows that π(u) < p and equation 2 shows that p < π(v). Hence, the Markov set of T u,v reg is {v}.

We now prove that any algorithm for finding the Copeland set, the Slater set, and the Markov set must query every edge in the input tournament in the worst case.

Theorem 1 Any algorithm for finding the Copeland set, the Slater set, and the Markov set of tournaments has query complexity (n 2).

Proof: Let us consider the tournament Treg. We observe that, due to Lemma 2, the Copeland set, the Slater set, and the Markov set of Treg is the set of all vertices. Let us now consider the oracle which answers the queries according to Treg. We claim that any algorithm for finding the Copeland set, the Slater set, and the Markov set of tournaments must query all the (n 2) edges of Treg. Suppose not, then there exists an edge from u to v in Treg for some vertices u and v that the algorithm does not query. Let ˆT be the partial tournament of Treg containing the edges that the algorithm queries. If the output of the algorithm does not contain u, then the oracle completes ˆT to Treg and thus the algorithm does not output correctly since the output should contain all the vertices. On the other hand, if the output of the algorithm contains u then the oracle completes ˆT by directing the edge between u and v from v to u and directing the rest of

the edges as in Treg. Again the algorithm outputs wrongly due to Lemma 3.

We now present our query complexity lower bound for the bipartisan set of tournaments. Before embarking on the query complexity lower bound of the bipartisan set, let us prove a few structural results for the bipartisan set which we will use crucially later. The following result for the bipartisan set is well known (GLM93; FR95).

Lemma 4 In a tournament T = (V, ), suppose a vertex u covers another vertex v, that is, u w whenever v w for every w V. Then v does not belong to the bipartisan set of T .

The following result shows that, in the tournaments where every vertex has the same number of incoming edges as the number of outgoing edges, the bipartisan set is the set of all vertices.

Lemma 5 Let T be a tournament on n vertices where the in-degree and out-degree of every vertex is (n 1)/2. Then the only maximal lottery of T is the uniform distribution over the set of all vertices of T and thus the bipartisan set of T is the set of all vertices.

Proof: We observe that the uniform distribution over all the vertices satisfy Equation (1) for the tournament T , since the average of the entries in every column of the skew-symmetric matrix G of the tournament T is 0. Now the result follows from the fact that the maximal lottery in every tournament is unique (MBC+16).

In the next lemma, we formalize the intuition that, if a (A,V A) cut in a tournament has a majority of its edges from V A to A and A is balanced, then the bipartisan set of the tournament must include at least one vertex from V A.

Lemma 6 Let T = (V1 V2,E) be a tournament such that there exist at most V1 V2 /2 1 edges from V1 to V2 and the in-degrees and out-degrees of all the vertices in the subtournament T [V1] of T induced on V1 are exactly V1 1/2. Then the bipartisan set of T must include at least one vertex from V2.

Proof: Let p Δ(V1 V2) be the maximal lottery of T and V = V1 V2. If possible, let us assume that p (v) = 0 for every v V2. Let q Δ(V2) be the uniform distribution on V2 and G = (gab)a,b V the skew-adjacency matrix of T . We first claim that p cannot be the uniform distribution on V1. Indeed, otherwise we have a,b V p (a)q(b)gab < 0 (since a strict majority of the edges between V1 and V2 are from V2 to V1) which contradicts the fact that p is the maximal lottery of T . We now consider the sub-tournament T [V1] of T induced on V1. Due to Lemma 5, the only maximal lottery of T [V1] is the uniform distribution on V1. Hence, since p is not the uniform distribution over V1, there exists a distribution q Δ(V1) such that a,b V1 p (a)q (b)gab < 0. However, this contradicts our assumption that p is the maximal lottery of T . Hence, the bipartisan set of T must include at least one vertex from V2.

We now have all the ingredients to present our query complexity lower bound result for the bipartisan set.

Theorem 2 The query complexity of the bipartisan set of a tournament is Ω(n2).

Proof: Let n be an odd integer. We consider a partial tournament T = (A B,E) where A = {ai i [n]},B = {bi i [n]}, and E = {(ai,ai+j (mod n)),(bi,bi+j (mod n)) i [n],1 j (n 1)/2}. The oracle answers the queries of the algorithm as follows. If a query comes for an edge between vertices ai and aj or bi and bj for any i,j [n], then the oracle answers according to T . If a query comes for an edge between ai and bj for any i,j [n], then the oracle says that the edge is oriented from ai to bj. We now claim that the algorithm must query at least n2/2 edges between A and B. Suppose not, then, if the output of the algorithm contains any vertex from B, then the oracle orients every edge between A and B, from A to B, thereby ensuring that the output of the algorithm is wrong due to Lemma 4. On the other hand, if the output of the algorithm does not contain any vertex from B, then the oracle orients all the edges between A and B that are not queried, from B to A, thereby ensuring that the output of the algorithm is again wrong due to Lemma 6. Hence, the algorithm must query at least n2/2 edges between A and B and thus the query complexity of the bipartisan set is Ω(n2).

We now show that the query complexity of the uncovered set is Ω(n2).

Theorem 3 The query complexity of the uncovered set of a tournament is Ω(n2).

Proof: Consider a partial tournament T = (A B {x},E) where A = {ai i [n]},B = {bi i [n]} and E = {(ai,x),(x,bi) i [n]}. Let us consider the following oracle. Let us define the partial tournament T to be the graph on A B {x} consisting of all the answers of the oracle till now. Hence, to begin with, T does not have any edge. The oracle answers the queries for any edge in T according to T . For any query of the form {ai,aj} or {bi,bj}, the oracle answers arbitrarily but consistently. For a query {ai,bj} for some i,j [n], if ai defeats bk for every k [n] {j} in T , then the oracle answers that bj defeats ai; otherwise oracle answers that ai defeats bj. We claim that any algorithm for finding the uncovered set of tournaments must query for the pair {ai,bj} for every i,j [n]. Suppose not, then there exists a pair {ai,bj} which the algorithm does not query. Notice that, by the design of the oracle, ai defeats bk in T for every k [n] such that {ai,bk} has been queried by the algorithm. For every pair {ak,bℓ} with k,ℓ [n],k i and {ak,bℓ} has not been queried, the oracle orients the edge from bℓto ak. The oracle also orients all the edges from ai to bk for every k [n] {j}. Now, if the output of the algorithm contains x, then the oracle orients the edge {ai,bj} from ai to bj. Notice that, in this case, x is covered by ai and thus x should not be in the uncovered set and hence the output of the algorithm is wrong. On the other hand, if the output of the algorithm does not contain x, then the oracle orients the

edge {ai,bj} from bj to ai. In this case, x is not covered by any other vertex and thus x belongs to the uncovered set. Hence, the algorithm outputs incorrectly in both the cases thereby proving the result.

Next we consider the Banks set and show its query complexity to be Ω(n2). Theorem 4 The query complexity of the Banks set of a tournament is Ω(n2). Proof: Consider a partial tournament T = (A B {x},E), where A = {ai i [n]},B = {bi i [n]}, and E = {(ai,x),(x,bi),(bi,bj) i,j [n],i > j}. Let us consider the following oracle. Let us define the partial tournament T to be the graph on A B {x} consisting of all the answers of the oracle till now. Hence, to begin with, T does not have any edge. The oracle answers the queries for any edge in T according to T . For any query of the form {ai,aj} or {bi,bj}, the oracle answers arbitrarily but consistently. For a query {ai,bj} for some i,j [n], if ai defeats bk for every k [n] {j} in T , then the oracle answers that bj defeats ai; otherwise oracle answers that ai defeats bj. We claim that the algorithm must query for the pair {ai,bj} for every i,j [n]. Suppose not, then there exists a pair {ai,bj} which the algorithm does not query. Notice that, by the design of the oracle, ai defeats bk in T for every k [n] such that {ai,bk} has been queried by the algorithm. For every pair {ak,bℓ} with k,ℓ [n],k i and {ak,bℓ} has not been queried, the oracle orients the edge from ak to bℓ. The oracle also orients all the edges not in T between ai and bk from ai to bk for every k [n] {j}. Now if the output of the algorithm contains x, then the oracle orients the edge between ai and bj from ai to bj. We claim that x can not be the maximum vertex of any maximal transitive sub-tournament T of T . To see this, we first observe that the sub-tournament T must have all the vertices in B and no vertex from A. Indeed, otherwise either x is not the maximum vertex of T (if any vertex from A is there in T ) or T is not a maximal transitive sub-tournament (if any vertex from B is not there in T ). However, such a sub-tournament is not a maximal transitive sub-tournament since ai can be added to T without violating transitivity. Hence x does not belong to the Banks set of the resulting tournament and thus the algorithm s output is wrong. On the other hand, suppose the output of the algorithm does not contain x. Then the oracle orients the edge between ai and bj from bj to ai. In this case, the sub-tournament of T induced on B {x} is a maximal sub-tournament where x is the maximum vertex and thus x belongs to the Banks set of the resulting tournament. Hence, the algorithm outputs incorrectly in both the cases thereby proving the result.

We now show that the query complexity of the top cycle of tournaments is Ω(n2). Theorem 5 The query complexity of the top cycle of a tournament is Ω(n2). Proof: We consider a partial tournament T = (A B,E) where A = {ai i [n]},B = {bi i [n]}, and

E = {(ai,ai+1 (mod n)),(bi,bi+1 (mod n)) i [n]}. The oracle answers the queries of the algorithm as follows. If a query comes for the edge between vertices ai and aj or bi and bj for any i,j [n], then the oracle answers according to T if the edge is present in T , and arbitrarily but consistently otherwise. If a query comes for an edge between ai and bj for any i,j [n], then the oracle says that the edge is oriented from ai to bj. Now we claim that the algorithm must query all the n2 edges between A and B. Suppose not, then there exist ai and bj for some i,j [n] such that the algorithm has not queried for the edge between ai and bj. Now if the output of the algorithm does not contain any vertex from B, then the oracle orients the edge between ai and bj from bj to ai. Notice that, in this case the top cycle of the resulting tournament T contains at least one vertex bj B and thus the algorithm does not output correctly in this case. On the other hand, if the output of the algorithm contains any vertex from B, then the oracle orients all the edges between A and B from A to B. In this case, the top cycle of the resulting tournament is A and thus the algorithm again fails to output correctly. Hence, the algorithm must make Ω(n2) queries.

Results for Tournaments with Small Top Cycle It turns out that, if we a priori know that the size of the top cycle in the input tournament is at most k, then there is an algorithm for finding the top cycle with much less number of queries. Theorem 6 Suppose we know that the top cycle of the input tournament T is of size at most k. Then there exists an algorithm for finding the top cycle of T with query complexity O(nk + n log n/log(1 1/k)). Proof: We first partition the set of vertices V into n/2k subsets Vi,i n/2k , each of size at most 2k. For each partition, we query all pair of vertices. We notice that, in each set Vi of the partition, there must exist at least one vertex vi with in-degree at least k (for every k larger than some small constant) and consequently vi does not belong to the top cycle of T for every i n/2k . We delete the vertex vi from Vi for every i n/2k , thereby deleting n/2k vertices in total. The now iterate the same process on the remaining set of vertices. The first iteration takes O((n/k)k2) = O(nk) queries. From the next iteration onwards, we can manage with only n queries per iteration by partitioning the vertices cleverly: since we have deleted exactly one vertex from each set of the partition we can add one vertex to each set of the partition by breaking some of the sets from the partition. We now observe that, in every set, we now need to compare the new vertex with the rest of the vertices thereby requiring at most n k queries in total. Since, each iteration decreases the size of the tournament by a factor of Ω(1 1/k), after O(log n/log(1 1/k)) iterations, we have O(k) vertices in the tournament where we can find the top cycle using O(k2) = O(nk) queries. Hence, the query complexity of our algorithm is O(nk + n log n/log(1 1/k)). The correctness of the algorithm follows from the fact that whenever we remove a vertex v from the tournament, v does

not belong to the top cycle of T .

The following result gives relationship between the top cycle of a tournament and other tournament solutions like the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, and the Banks set. Lemma 7 Let T be a tournament whose top cycle is C. Then the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, and the Banks set of T are the same as the corresponding solutions for the tournament T (C). Proof: Copeland set, bipartisan set, uncovered set: Follows from the observation that every vertex in C covers every vertex in V C and Lemma 4. Markov set: All the states corresponding to the vertices in V C are inessential and thus do not belong to the Markov set of T . Slater set: We observe that, in the Slater order of the tournament T , every vertex in C must be preferred over every vertex in V C. If not, then let there be a vertex a C and b V C such that a immediately follows b in . Then by swapping the positions of the vertices a and b in , we can strictly decrease the disagreement of with T thereby contradicting that is a Slater order of T . Banks set: Follows from the fact that every maximal element of every maximal sub-tournament of T belongs to C.

Lemma 7 and Theorem 6 immediately give the the following query complexity upper bound for the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, and the Banks set when we a priori know that the size of the top cycle of the input tournament is at most k. Theorem 7 Suppose we know that the top cycle of the input tournament T is of size at most k. Then there exists an algorithm for finding the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, and the Banks set of T with query complexity O(nk + n log n/log(1 1/k)). Proof: We first find the top cycle C of T using Theorem 6. This step requires O(nk + n log n/log(1 1/k)) queries. Next, we query for all the pair of vertices in C and output the corresponding solution of T (C). The correctness of the algorithm follows immediately from Lemma 7. Since the second step requires O(k2) = O(nk) queries, the query complexity of our algorithm is O(nk + n log n/log(1 1/k)).

Conclusion and Future Directions We have shown that, for finding many common tournament solutions, one has to query, in the worst case, almost entire set of edges in the tournament. On the positive side, we have exhibited an important structural property, in terms of the top cycle of the tournament being small, which substantially reduces the query complexity of common tournament solutions. An immediate future direction of research is to study query complexity for other tournament solutions like the minimal covering set, the minimal extending set, the minimal TC-retentive set, the tournament equilibrium set, etc.

Kenneth J Arrow, Herv e Raynaud, et al. Social choice and multicriterion decision-making. MIT Press Books, 1, 1986. Felix Brandt, Markus Brill, Felix Fischer, and Paul Harrenstein. Minimal retentive sets in tournaments. Soc. Choice Welf., 42(3):551 574, 2014. Felix Brandt and Paul Harrenstein. Characterization of dominance relations in finite coalitional games. Theor. Decis., 69(2):233 256, 2010. Denis Bouyssou, Thierry Marchant, Marc Pirlot, Alexis Tsouki as, and Philippe Vincke. Evaluation and decision models with multiple criteria: Stepping stones for the analyst, volume 86. Springer Science & Business Media, 2006. Amotz Bar-Noy and Joseph Naor. Sorting, minimal feedback sets, and hamilton paths in tournaments. SIAM J. Discrete Math., 3(1):7 20, 1990. Pierre Br emaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 2013. R. Balasubramanian, Venkatesh Raman, and G. Srinivasaragavan. Finding scores in tournaments. J. Algorithms, 24(2):380 394, 1997. Ir ene Charon and Olivier Hudry. A survey on the linear ordering problem for weighted or unweighted tournaments. 4OR, 5(1):5 60, 2007. Amit Chakrabarti, Subhash Khot, and Yaoyun Shi. Evasiveness of subgraph containment and related properties. SIAM J. Comput., 31(3):866 875, 2001. Vincent Conitzer. Eliciting single-peaked preferences using comparison queries. J. Artif. Intell. Res., 35:161 191, 2009. Vincent Conitzer and Tuomas Sandholm. Vote elicitation: Complexity and strategy-proofness. In Eighteenth National Conference on Artificial Intelligence (AAAI), pages 392 397, 2002. Palash Dey. Query complexity of tournament solutions. Co RR, abs/1611.06189, 2016. Palash Dey. Recognizing and eliciting weakly single crossing profiles on trees. Co RR, abs/1611.04175, 2016. John Duggan and Michel Le Breton. Dutta s minimal covering set and shapley s saddles. J. Econ. Theory, 70(1):257 265, 1996. Palash Dey and Neeldhara Misra. Elicitation for preferences single peaked on trees. In Proc. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 215 221, 2016. Palash Dey and Neeldhara Misra. Preference elicitation for single crossing domain. In Proc. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 222 228, 2016. Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif Intel, 77(2):321 357, 1995.

Paul E Dunne. Computational properties of argument systems satisfying graph-theoretic constraints. Artif Intel, 171(10):701 729, 2007. David C Fisher and Jennifer Ryan. Tournament games and positive tournaments. J. Graph Theory, 19(2):217 236, 1995. Dishant Goyal, Varunkumar Jayapaul, and Venkatesh Raman. Elusiveness of finding degrees. To appear in Proc. Third International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), February 13 - 18, 2017, Goa, India., 2017. Laffond G., Jean-Franois Laslier, and Le Breton M. The bipartisan set of a tournament game. GEB, 5(1):182 201, 1993. Valerie King. Lower bounds on the complexity of graph properties. In Proc. twentieth annual ACM symposium on Theory of computing, pages 468 476. ACM, 1988. Jeff Kahn, Michael Saks, and Dean Sturtevant. A topological approach to evasiveness. Combinatorica, 4(4):297 306, 1984. Torsten Korneffel and Eberhard Triesch. An asymptotic bound for the complexity of monotone graph properties. Combinatorica, 30(6):735 743, 2010. Raghav Kulkarni. Evasiveness through a circuit lens. In Proc. 4th Conference on Innovations in Theoretical Computer Science, ITCS 13, pages 139 144, New York, NY, USA, 2013. ACM. Herv e Moulin, Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel D Procaccia. Handbook of Computational Social Choice. Cambridge University Press, 2016. H Moulin. Choosing from a tournament. Soc. Choice Welf., 3:271 291, 1986. David M. Pennock, Eric Horvitz, and C. Lee Giles. Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering. In Proc. Seventeenth AAAI, July 30 - August 3, 2000, Austin, Texas, USA., pages 729 734, 2000. Ariel D Procaccia. A note on the query complexity of the condorcet winner problem. Inform. Process. Lett., 108(6):390 393, 2008. Arnold L Rosenberg. On the time required to recognize properties of graphs: A problem. ACM SIGACT News, 5(4):15 16, 1973. Ronald L Rivest and Jean Vuillemin. On recognizing graph properties from adjacency matrices. Theor Comput Sci, 3(3):371 384, 1976.