When Does Schwartz Conjecture Hold?

1 Introduction

Tournaments play a significant role in multiagent systems [Brandt et al., 2013a]. For instance, a group of autonomous agents may jointly decide on a course of action based on the relation of majority preference, which prescribes that an alternative dominates another alternative if a majority of agents prefer the former to the later. If there is no tie, the relation of majority preference gives rise to a tournament-a complete and antisymmetric binary relation over the alternatives. A tournament can be represented by a directed graph where between each pair of vertices (alternatives) there is exactly one arc. Moreover, an arc from a vertex a to another vertex b means that a is preferred to b by a majority of agents (or a dominates b).

When tournaments are used for joint decision making, the problem of determining which vertices should be selected as the winners is of particular importance. If there is a vertex that dominates every other vertex, then this vertex is widely recognized as the winner. This winner is called the Condorcet winner (many tournaments solutions select only the Condorcet winner when it exists, see [Hudry, 2009] for further discussions). However, the relation of majority preference may result in tournaments where no Condorcet winner exists. For instance, given three alternatives a, b, c and three agents, if the preferences of the agents are a ≻ b ≻

∗This research was supported by ERC Starting Grant 306465.

Yongjie Yang

Universit¨at des Saarlandes Saarbr¨ucken, Germany

c, b ≻ c ≻ a, c ≻ a ≻ b, then, there will be a triangle in the tournament (a dominates b, b dominates c, and c dominates a); and thus, no alternative dominates all other alternatives. This is called a Condorcet paradox in the literature. In this case there is no straightforward notion of a "best" alternative. To address the problem, researchers proposed several prominent tournament solutions. A tournament solution is a function that maps a tournament to a nonempty set of vertices, the winners. In many literature, the tournament solutions are required to include the Condorcet winner in the winning set whenever the Condorcet winner exists. In particular, Thomas Schwartz proposed to select the tournament equilibrium set (τ for short) as the winners. For a given tournament solution S, Schwartz calls a set of vertices S-retentive if it satisfies a natural stability criterion with respect to S (see Section 2 for further details). He then recursively defines τ as the union of all minimal τ-retentive sets. Moreover, Schwartz conjectured that every tournament has a unique minimal τ-retentive set. This conjecture is of particular importance since it is equivalent that τ having any one of a set of desirable fairness properties. Fairness properties play a significant role in evaluating tournament solutions. In general, the more the fairness properties a tournament solution satisfies, the better it is. We refer to [Brandt et al., 2013a; Brandt, 2011; Brandt et al., 2014]

fairness properties of tournaments solutions. In particular, if τ satisfied monotonicity, it would be a very attractive solution concept refining both the Banks set and the minimal covering set [Brandt et al., 2010].

Unfortunately, Schwartz's Conjecture has been disproved very recently by Brandt et al., who firstly proposed a counterexample with around 10136 vertices using the probabilistic method [Brandt et al., 2013b], and then devised a counterexample with only 24 vertices [Brandt and Seedig, 2013]. Their negative results imply that τ does not satisfy the following properties: monotonicity, independent of unchosen alternatives, weak superset and strong superset (see [Brandt, 2011] for the definitions).

In this paper, we provide some positive results. In particular, we prove sufficient conditions for infinite classes of tournaments that satisfy Schwartz's Conjecture. Our results reveal some structures that are forbidden in every counterexample to Schwartz's Conjecture. This might be helpful in finding further smaller counterexamples to Schwartz's Conjecture.

In addition, we prove that τ can be calculated in polynomial time for serval special classes of tournaments. Recall that in general, even determining whether a given vertex is in τ is NP-hard [Brandt et al., 2010].

Finally, we study a weak variant of Schwartz's Conjecture proposed by Brandt et al. [2013b]. In [Brandt et al., 2013b], the authors actually disproved Schwartz's Conjecture by disproving this weak variant.

2 Preliminaries

Tournament. A tournament T is a pair (V (T),≻), where V (T ) is a set of alternatives and ≻ is an asymmetric and complete (and thus irreflexive) binary relation on V (T ), called the dominance relation. Intuitively, a ≻ b (reads a dominates b) signifies that alternative a is socially preferable to alternative b. For two sets X and Y of alternatives, X ≻ Y means that x ≻ y for every x ∈ X and every y ∈ Y . Tournaments can be represented by directed graphs where between every pair of vertices there is exactly one arc. Precisely, a tournament T = (V (T ), ≻) can be represented by a directed graph where alternatives one-to-one correspond to vertices, and there is an arc from a to b if a ≻ b. For simplicity, we still use a ≻ b to denote the arc from a to b. Throughout this paper, we exchangeably use the terms "vertex" and "alternative".

A source of a tournament T = (V (T),≻) is a vertex a so that a ≻ b for every other vertex b ∈ V (T) \ {a}. From social choice point of view, the source is called the Condorcet winner of the tournament. Clearly, every tournament has at most one source. A tournament is transitive if there is an order (v1, v2, ..., vk) of the vertices such that for every vi, vj with i < j there is an arc from vi to vj. Clearly, v1 is the source of the transitive tournament.

For a vertex v ∈ V (T), let N - T (v) denote the set of inneighbors of v in T and N + T (v) the set of out-neighbors of v, that is N - T (v) = {u ∈ V (T) | u ≻ v} and N + T (v) = {u ∈ V (T) | v ≻ u}. For a subset B ⊆ V (T), T[B] is the subtournament induced by B, that is, T[B] = (B,≻′ ) where for every a, b ∈ B, a ≻′ b if and only if a ≻ b. A triangle is a tournament with three vertices so that each vertex has exactly one in-neighbor. Two triangles are vertex-disjoint if they do not share a common vertex. For a tournament T, its triangle packing number is the maximum number of vertex-disjoint copies of triangles, and its triangle covering number is the minimum number of vertices intersecting all triangles of T .

A tournament T = (V (T),≻) is isomorphic to another tournament T ′ = (V (T ′ ),≻′ ) if there is a bijection f : V (T) → V (T ′ ) such that v ≻ u if and only if f(v) ≻′ f(u). We say that T is H-free for some tournament H if no subtournament of T is isomorphic to H; otherwise, we say T contains H.

Tournament Equilibrium Set (τ) A tournament solution S is a function that maps every tournament T to a nonempty set S(T) ⊆ V (T). For a tournament solution S and a tournament T, a nonempty subset A ⊆ V (T) is an S-retentive set in T if for all v ∈ A with N - T (v) ̸= ∅, we have that S(N - T (v)) ⊆ A. An S-retentive set A in T is said to be minimal if there is no other S-retentive set B in T with B ⊂ A.

Since the set V (T) of all alternatives is trivially S-retentive in T, S-retentive sets are guaranteed to exist. Schwartz defined the tournament equilibrium set (τ for short) recursively as the union of all minimal τ-retentive sets. This recursion is well-defined since |N - T (v)| is strictly smaller than |V (T)|, for every v. Particularly, the τ-retentive set of a triangle is the set of all three vertices.

Composition-Consistent. The terminologies here mainly follow from [Brandt et al., 2011]. A homogeneous set (component) of T is a subset X ⊆ V (T) such that for all v ∈ V (T ) \ X, either {v} ≻ X or X ≻ {v}. A homogeneous set X ⊆ V (T) is non-trivial if 1 < |X| < |V (T)|; otherwise it is trivial. A tournament is prime if all its homogeneous sets are trivial. A prime tournament T on at least two vertices is critical if T - v is not prime for all v ∈ V (T). Here, T - v is the tournament obtained from T by deleting the vertex v.

A decomposition of T is a set of pairwise disjoint homogeneous sets {B1, B2, ..., Bk} of T such that V (T) = ∪ki=1Bi. The null decomposition of a tournament T is V (T). Given a particular decomposition of a tournament, the summary of the tournament is defined as follows.

Definition 1. Let T = (V (T),≻) be a tournament and ˜ B = {B1,B2, ...,Bk} a decomposition of T. The summary of T with respect to ˜ B is defined as ˜ T = ({1, 2, ..., k}, ˜≻), where for every i ̸= j, i˜≻j if and only if Bi ≻ Bj.

A tournament is called reducible if it admits a decomposition into two homogeneous sets. Otherwise, it is irreducible. Laslier [1997] has shown that there exists a natural unique way to decompose any irreducible tournament (in fact, Laslier [1997] proved this for all tournaments. See [Brandt et al., 2011] for discussion). Call a decomposition ˜ B finer than another decomposition ˜ B′ if ˜ B ̸= ˜ B′ and for each B ∈ ˜ B there exists B′ ∈ ˜ B′ such that B ⊆ B′ . ˜ B′ is said to be coarser than ˜ B. A decomposition is minimal if its only coarser decomposition is the null decomposition.

Lemma 1. [Laslier, 1997] Every irreducible tournament T with more than one alternative admits a unique minimal decomposition. Moreover the summary of T with respect to the decomposition is prime.

A tournament solution is composition-consistent if it chooses the "best" alternatives from the "best" components [Laffond et al., 1996].

Definition 2. A tournament solution S is compositionconsistent if for all tournaments T and ˜ T such that ˜ T is the summary of T with respect to some decomposition {B1, B2, ..., Bk},

Brandt et al. [2013a] proved that among all tournament solutions that are defined as the union of all minimal retentive sets with respect to some tournament solution, τ is the only one that is composition-consistent (see [Brandt et al., 2013a] for further details). Notice that this holds regardless of whether Schwartz's Conjecture holds.

2.1 Our Contribution

In 1990, Schwartz proposed the following conjecture.

Conjecture 1 (Schwartz's Conjecture). Every nonempty tournament has a unique minimal τ -retentive set.

Over the years, Schwartz's Conjecture has been extensively studied from the social choice perspective [Dutta, 1990; Laffond et al., 1993; Laslier, 1997; Houy, 2009; Brandt, 2011; Brandt et al., 2010]. In particular, it is known that Schwartz's Conjecture is equivalent to τ having any one of several desirable properties of tournament solutions, including monotonicity, independent of unchosen alternatives, weak superset and strong superset. Unfortunately, Schwartz's Conjecture was disproved very recently [Brandt and Seedig, 2013; Brandt et al., 2013b].

In this paper, we develop structural conditions that a tournament must satisfy in order for Schwartz's Conjecture to hold. Our first result is summarized in the following theorem.

Theorem1. Schwartz's Conjecture holds for all tournaments whose triangle packing number and triangle covering number are equal. Moreover, τ can be calculated in polynomial time for these tournaments.

A proper subclass of the tournaments who have equal number of triangle packing and triangle covering are the ones where triangles are pairwise vertex-disjoint. In this case, each triangle is a homogenous set and the tournaments are transitive over the triangles. This could happen in real-world applications where the alternatives can be divided into groups, each containing at most three alternatives that are "similar" to each other. The similarity implies that every agent ranks the alternatives in the same group together. Moreover, all agents have a consensus ranking over the groups. The term "similarity" has been studied in the literature. For example, Elkind et al. [2012] studied the clone structure, where cloning an alternative means to replace this alternative with a group of alternatives that are ranked together by all agents. Another example are elections with bounded single-peaked width or bounded single-crossing width (see e.g., [Cornaz et al., 2013] for further information on single-peaked width and singlecrossing width). The second condition stating that all agents have a common consensus ranking over the alternatives could arise in the applications where there exists a correct ranking over the alternatives, and each agent's preference corresponds to a noisy perception of this correct ranking [Conitzer and Sandholm, 2005] (in the case we are discussing, the noise is due to the similarity of the alternatives in each group). We remark that for tournaments with equal triangle packing number and triangle covering number, it is not necessary that all triangles are pairwise vertex-disjoint.

To prove Theorem 1, we use some properties of tournaments whose triangle packing number and triangle covering number are equal. In particular, it is easy to see that such tournaments must exclude certain 5-vertex tournaments as subtournaments. We give such tournaments in Fig. 1, where the undrawn arcs can take either orientation.

Curiously, Brandt and Seedig's counterexample [2013] to Schwartz's Conjecture on 24 vertices contains both F1 and F2 as subtournaments: two disjoint copies of F1 are formed by

{x1, x2, x3, x4, x9} and {y1, y2, y3, y4, y9}, and two disjoint copies of F2 are formed by {x1, x7, x5, x10} ∪ {v ∈ Y1} and {y1, y7, y5, y10} ∪ {v ∈ X2} in their figure.

Now we come to our second result. In particular, we prove Schwartz's Conjecture for tournaments defined by a forbidden subtournament called U5. Let U5 be the tournament with vertices v1, . . . , v5 such that v2 ≻ v1, and vi ≻ vj if j-i ≡ 1, 2 (mod 5) and i, j ̸= 1, 2. Various subclasses and generalizations of U5-free tournaments are well-studied [Ehrenfeucht and Rozenberg, 1990; Schmerl and Trotter, 1993; Liu, 2015; Belkhechine and Boudabbous, 2013].

Theorem 2. Schwartz's Conjecture holds in U5-free tournaments.

We remark that the 24-vertex counterexample to Schwartz's Conjecture by Brandt and Seedig [2013] contains two disjoint copies of U5; the first copy is induced by x1, x3, x5, x12 and any vertex of Y1; the second copy is induced by y1, y3, y5, y12 and any vertex of X2. Our third result is as follows.

Theorem3. Schwartz's Conjecture holds for critical tournaments. Moreover, τ can be calculated in polynomial time for critical tournaments.

Now we discuss some extensions of the above results. It is well known that τ contains exactly the Condorcet winner whenever the Condorcet winner exists. As a consequence, Schwartz's Conjecture holds in all tournaments where Condorcet winner exists. Since τ is composition-consistent, we then have the following corollary.

Corollary 1. Schwartz's Conjecture holds in all tournaments T who have a summary ˜ T = ({1, 2, ..., k}, ≻) with respect to a decomposition {B1, B2, ..., Bk} of T such that ˜ T admits the Condorcet winner i, and at least one of the following holds for each i = 1, 2, ..., k:

(1) the triangle packing number and the triangle covering number of T [Bi] are equal; or

(2) T[Bi] is U5-free; or

(3) T[Bi] is critical.

Our fourth result concerns a weakening of Schwartz's Conjecture, which claims the existence of an "undominated" vertex set A in any tournament T, where A is undominated if there is a vertex v ∈ V (T) \ A and a vertex u ∈ A so that u ≻ v.

Conjecture 2 ([Brandt et al., 2013b]). Let (A,B) be a partition of the vertex set of a tournament T. Then one of A,B contains a transitive subset which is undominated in T .

It is known that Conjecture 1 implies Conjecture 2 [Brandt et al., 2013b]. Therefore, all the above results for Schwartz's Conjecture apply to Conjecture 2. In addition, we prove Conjecture 2 for all tournaments in which every triangle shares at most one of its arcs with other triangles.

Theorem 4. Conjecture 2 holds for all tournament T where every triangle shares at most one arc with other triangles.

In the remainder of the paper, we prove the theorems shown above.

3 Triangle Packing-Covering

In this section we prove Theorem 1. Before proceeding further, we introduce an interesting property on minimal τretentive set.

Lemma 2. Any minimal τ-retentive set either induces an irreducible subtournament, or contains only one vertex.

Proof. Let T be a tournament. Assume, for the sake of contradiction, that the statement is false. Then there exists a minimal τ -retentive set X with |X| ≥ 2 which induces a reducible subtournament. Let A ⊆ X and B ⊆ X be the two homogenous sets such that A ≻ B in T [X]. We argue that A is also a τ -retentive set of T . Let x be any vertex in A. If N - T (x) = ∅, we are done. Assume now that N - T (x) ̸= ∅. Since A ≻ B, we know that X∩N - T (x) ⊆ A. Since X is a τ -retentive set of T and x ∈ X, we know that τ (N - T (x)) ⊆ (X∩N - T (x)) ⊆ A. Therefore, A is also a τ-retentive set, contradicting that X is a minimal τ -retentive set.

The above lemma implies that no minimal τ-retentive set contains exactly two vertices. Moreover, a minimal τretentive set contains exactly one vertex if and only if the vertex is the Condorcet winner of the tournament.

Lemma 3. If a tournament does not have a source, then any minimal τ-retentive set of T contains at least 3 vertices. Moreover, every minimal τ-retentive set contains at least one triangle.

Now we discuss a property on tournaments whose triangle packing number equals its triangle covering number. Let T be a tournament not containing any of the five tournaments represented by F1, F2 in Fig. 1 as subtournament; we call such a tournament clean.

Proposition 1 ([Cai et al., 2001]). For clean tournaments T = (V (T), ≻) with |V (T)| ≥ 5, V (T) can be partitioned into sets V1, . . . , Vt for some t ≥ 3 such that

(1) for i = 1, . . . , t, the induced tournament T[Vi] is transitive and thus admits a linear order ▷ such that x▷y whenever x ≻ y;

(2) for i = 1, . . . , t there is a map f : Vi+1 → Vi such that

• for any v ∈ Vi+1, x ≻ v for each x in Vi with x ▷ f(v); and v ≻ x for each x in Vi with f(v) ⊵x;
• for any u, v ∈ Vi+1 with u ▷ v, it holds f(u) ⊵ f(v);

(3) for any i, j with 1 ≤ i ≤ j - 2 ≤ t - 2, each arc between Vi and Vj is directed from Vi to Vj.

Proof of Theorem 1. Cai et al. [2001] showed that if a tournament T (of size at least 5) has its triangle packing number and triangle covering number equal, T is neat; and thus, there exists a partition V1, . . . , Vt of its vertices satisfying Proposition 1. Recall that t ≥ 3. For each i = 1, 2, 3, let si be the source of T [Vi]. We distinguish between the following cases.

Case 1. s1 ▷ f(s2). In this case, it is easy to check that s1 is the source of T , and thus, Theorem 1 holds.

Case 2. f(s2) ⊵ s1 (equivalently, f(s2) = s1) and s2 ▷ f(s3). According to the condition (2) in Proposition 1 and f(s2) ⊵ s1, we have that {s2} ≻ V1. Moreover, since s2 ▷ f(s3), we know that {s2} ≻ V3. Further, {s2} ≻ Vi for each i ≥ 4. With s2 being the source of T[V2], we conclude that s2 is the source of T , and thus, Theorem 1 holds.

Case 3. f(s2) ⊵ s1 and f(s3) ⊵ s2 (equivalently, f(s3) = s2). Then {s1, s2, s3} forms a triangle in T. We claim that X = {s1, s2, s3} is a τ-retentive set of T. To see this, notice that f(s2) ⊵ s1, s2 ≻ s1 and N - T (s1) ⊆ V2. As s2 is the source of T[V2], τ(N - T (s1)) = {s2} ⊂ X. Similarly, f(s3) ⊵ s2, s3 ≻ s2 and N - T (s2) ⊆ V3. With s3 being the source of T[V3], τ(N - T (s2)) = {s3} ⊂ X. Finally, N - T (s3) ⊆ V1 ∪V4. Now, since T [V1 ∪V4] is transitive and s1 is its source, τ(N - T (s3)) = {s1} ⊂ X. This implies that X = {s1, s2, s3} is a τ -retentive set of T , and completes the proof of the claim. Due to Lemma 3, X is a minimal τ-retentive set.

Next, we show that X is the unique minimal τ -retentive set of T. Suppose that there exists another minimal τ-retentive set Y of T. Due to Lemma 3, |Y | ≥ 3. Due to the above analysis, if Y contains any of {s1, s2, s3}, Y contains all of them. Therefore, we know that Y ∩ X = ∅. Let x be any vertex in Y . We consider all possibilities of x, and prove that each possibility contradicts with the fact that Y ∩ X = ∅. (1) x ∈ V1. In this case, τ(N - T (x)) = {s2}. (2) x ∈ V2 and s1 ̸∈ N - T (x). In this case, τ(N - T (x)) = {s3}. (3) x ∈ V2 and s1 ∈ N - T (x). In this case, {s1, s2, s3} ⊆ N - T (x). According to the above analysis, it is easy to see that {s1, s2, s3} is also a minimal τ-retentive set of T[N - T (x)]; and thus, {s1, s2, s3} ⊆ τ(N - T (x)). (4) x ∈ V3 and s2 ̸∈ N - T (x). In this case, τ(N - T (x)) = {s1}. (5) x ∈ V3 and s2 ∈ N - T (x). In this case, {s1, s2, s3} ⊆ N - T (x) (then, the same as (2)). (6) x ∈ V4 and s3 ̸∈ N - T (x). In this case, τ(N - T (x)) = {s2}. (7) x ∈ V4 and s3 ∈ N - T (x). In this case, {s1, s2, s3} ⊆ N - T (x) (then, the same as (2)). (8) x ∈ Vi for each i ≥ 5. Then it is easy to see that {s1, s2, s3} ⊆ N - T (x) (then, the same as (2)). In each of the above cases, τ(N - T (x)) contains some vertices from {s1, s2, s3}, implying that Y ∩ {s1, s2, s3} ̸= ∅, a contradiction. Therefore, we conclude that X = {s1, s2, s3} is indeed the unique minimal τ -retentive set of T .

Cai et al. [2001] proved that for tournaments where the triangle packing number equals the triangle covering number, a partition stated in Proposition 1 can be found in polynomial time. Then, according to the above proof, the τ of these tournaments can be calculated in polynomial time.

4 Tournaments Excluding U5

In this section we prove Schwartz's Conjecture for tournaments that do not contain U5. That is, we give a proof of Theorem 2.

Definition 3. For odd n ∈ N≥5, define tournaments

• Hn is the tournament with vertices v1, . . . , vn such that vi ≻ vj if j - i ≡ 1, 2, . . . , (n - 1)/2 (mod n).
• Un is the tournament obtained fromHn by reversing all arcs which have both ends in {v1, . . . , v(n-1)/2}.

We first prove Schwartz's Conjecture for Hn with odd n.

Lemma 4. Schwartz's Conjecture holds for tournaments Hn, for all odd n ∈ H≥5.

Proof. For any tournament Hn, we show that V (Hn) is the unique minimal τ-retentive set. For the sake of contradiction, assume that there is a minimal τ-retentive set R ⊂ V (Hn). Let vi be a vertex such that vi ∈ V (Hn) \ R. Due to the definition of Hn, there is some vertex vj ∈ V (Hn) with τ (N - Hn (vj)) = vi, where j ≡ i + n-1 2 (mod n). As R is τ-retentive and vi /∈ R, we have vj ̸∈ R. Again, there is some vertex vk ∈ V (Hn) with τ(N - Hn (vk)) = vj, where k ≡ j + n-1 2 ≡ i + n-1 2 + n-1 2 ≡ i - 1 (mod n). Hence, vi-1 ̸∈ R. Similarly, we can show that vj-1, vi-2, vj-2, vi-3 and so on are not in R, contradicting that R ̸= ∅.

Now we prove Schwartz's Conjecture for U5-free tournaments. We start with U5-free tournaments that are prime.

Proposition 2 ([Liu, 2015]). Let T be a prime tournament. Then T is U5-free if and only if T is isomorphic to Hn for some odd n ≥ 1, or V (T ) can be partitioned into sets X, Y, Z such that each of T [X ∪Y ], T [Y ∪Z], T [Z ∪X] is transitive.

Lemma 5. Schwartz's Conjecture holds for all U5-free tournaments that are prime.

Proof. Let T be a U5-free tournament that is prime. Due to Proposition 2 and Lemma 4, we can assume that V (T) can be partitioned into sets X, Y,Z such that each of X ∪ Y, Y ∪Z, Z ∪X induces a transitive subtournament. If T has a source, then the source is the unique minimal τ -retentive set of T . Assume from now on that T does not have a source.

Let sxy, syz and sxz be the source vertices of T[X ∪ Y ], T[Y ∪Z] and T[Z ∪X], respectively. Observe that sxy, syz and sxz are distinct, as T does not have a source. Moreover, sxy, syz, sxz all belong to distinct partition classes of the partition (that is, each X, Y, Z contains exactly one from {sxz, sxy, syz}). Assume, without loss of generality, that syz ≻ sxy; otherwise, we can exchange x with z.

We claim that {sxy, syz, sxz} is a minimal τ-retentive set. As sxy dominates all vertices in X∪Y , all in-neighbors of sxy belong to Z. Since syz ≻ sxy, it must be that syz ∈ Z. Then, since sxz is the source of T [X ∪Z], it must be that sxz ∈ X. This implies that sxy ∈ Y . Moreover, {sxz, syz, sxy} forms a triangle with sxz ≻ syz, syz ≻ sxy, sxy ≻ sxz. Since sxz is the source of T[X ∪ Z], N - T (sxz) ⊆ Y . Since sxy is the source of T[X ∪ Y ] and sxz ∈ X, we have that sxy ∈ N - T (sxz) and sxy dominates every other vertex in N - T (sxz).

Therefore, τ(N - T (sxz)) = {sxy}. Analogously, we can show that τ(N - T (sxy)) = {syz} and τ(N - T (syz)) = {sxz}. Therefore, {sxy, syz, sxz} is a τ-retentive set. By Lemma 3, every minimal τ-retentive set of T contains at least 3 vertices. This implies that {sxy, syz, sxz} is a minimal τ-retentive set.

Finally, we prove that R is the unique minimal τ-retentive set. For the sake of contradiction, assume that there exists another minimal τ-retentive set R′ of T. By Lemma 3, R′ contains at least one triangle. Hence, R′ must contain at least one vertex from Y . Let that vertex be d ∈ R′ ∩Y . If d = sxy, then, as discussed above, sxz and syz must also be in R′ . Thus, R′ ⊇ R, the desired contradiction. Next we assume that d ̸= sxy. Since d ∈ Y , we have that sxy ≻ d and syz ≻ d. If sxz ≻ d, we have {sxz, syz, sxy} ⊆ N - T (d). Then due to the above analysis, it is easy to check that {sxy , syz , sxz} is also a minimal τ -retentive set of T [N - T (d)]; thus, {sxy, syz, sxz} ⊆ R′ , a contradiction. On the other hand, if d ≻ sxz, then due to that T[X ∪ Y ] is transitive and sxz is the source of T[X], we have that N - T (d) ∩ X = ∅. Therefore, all in-neighbors of sxz are in Y ∪Z. Since syz is the source of T [Y ∪Z], τ (N - T (d)) = {syz}. Due to the above analysis, if one of {sxy, syz, sxz} is in a τ-retentive set, then all of them are in the τ-retentive set. Therefore, we have that {sxy, syz, sxz} ⊆ R′ , also a contradiction.

Now it remains to prove Schwartz's Conjecture for nonprime U5-free tournaments. The following lemma is useful.

Lemma 6. Let T be a tournament with a decomposition ˜ B = {B1,B2, ...,Bk}. Let ˜ T = ({1, 2, ..., k}, ˜≻) be the summary of T with respect to ˜ B. If Schwartz's Conjecture holds in ˜ T and in every T[Bi] for i = 1, 2, ..., k, then Schwartz's Conjecture holds in T .

Proof. (Sketch.) If ˜ T has a source, then it is easy to check that the lemma is true (due to that τ is composition-consistent). In the following, we assume that ˜ T does not have a source. Let ˜R be the unique minimal τ-retentive set of ˜ T, and let Ri be the unique minimal τ-retentive set of T[Bi] for every i ∈ ˜R. We claim that ∪i∈˜RRi is the unique minimal τ-retentive set of T. Let R be any minimal τ-retentive set of T. Since τ is composition-consistent, we know that R ⊆ (∪i∈˜RRi). Let x ∈ R be a vertex in some Ri with i ∈ ˜R. The in-neighbors N - T (x) of x can be divided into two sets: N - T[Bi] (x) and ∪j˜≻iBj. Since Bi is a homogeneous set of T, we know that (∪j˜≻iBj) ≻ N - T[Bi] (x). Therefore, τ (N - T (x)) = τ(∪j˜≻iBj). Since τ is composition-consistent, we know that

Therefore, (∪j∈˜R,j˜≻iRj) ⊆ R. Analogously, from any vertex y ∈ Rj with j ∈ ˜R and j ˜≻i, we can conclude that all vertices ∪l∈ ˜R,l ˜≻j Rl must be in R. Due to Lemma 2, ˜ T [ ˜R] is irreducible, which implies that after at most | ˜R| steps, all vertices in ∪i∈ ˜RRi must be in R (see Theorem 2 in [Moon, 2013] for a property of irreducible tournaments). Since R ⊆ (∪i∈ ˜RRi), we conclude that R = ∪i∈ ˜RRi, and R is the unique minimal τ -retentive set of T .

Let T be a non-prime U5-free tournament. Let A be the minimum set of vertices such that there is an arc from every vertex in A to every vertex not in A (in the literature, A is called the Smith set of T [Smith, 1973]). Clearly, T [A] is irreducible; and moreover, {A, V (T ) \ A} is a decomposition of T. Let ˜ T be the summary of T with respect to {A, V (T )\A}. Then, the vertex corresponding to A in the summary ˜ T is the Condorcet winner (source) of ˜ T. Since τ is compositionconsistent, every minimal τ-retentive set of T must be in A. Let {A1,A2, ...,Ak} be the unique decomposition of T[A] according to Lemma 1, and let˜ T [A] be the summary of T [A] with respect to {A1,A2, ...,Ak}. Due to Lemma 1, ˜ T[A] is a U5-free prime tournament. Due to Lemma 5, Schwartz's Conjecture holds in˜ T[A]. Then, according to Lemma 6, we need only to prove that Schwartz's Conjecture holds in each T[Ai]: we recursively decompose each T[Ai]. In each recursion, we have a U5-free summary of the original tournament. Then, again, due to Lemma 5, Schwartz's Conjecture holds in this summary. We recursively use this scheme until the summary contains only one vertex. Then, due to Lemma 6, we can finally prove that Schwartz's Conjecture holds in every T [Ai].

5 Critical Tournaments

In this section we prove Schwartz's Conjecture for critical tournaments, that is, we prove Theorem 3.

For odd n ∈ N≥5, let Wn be the tournament with vertices v, w1, . . . , wn-1 such that wi ≻ wj for i < j, and {wi | i ≡ 0 (mod 2)} ≻ {v} ≻ {wi | i ≡ 1 (mod 2)}. We employ a structural result of critical tournaments:

Proposition 3 ([Schmerl and Trotter, 1993]). Any critical tournament on at least five vertices is isomorphic to either Hn, or Un, or Wn, for any odd n ∈ N≥5.

By Lemma 4, it remains to prove Schwartz's Conjecture for Un and Wn in order to prove it for critical tournaments.

Lemma 7. Schwartz's Conjecture holds for tournaments Un, for any odd n ∈ N≥5.

Proof. Observe that Un does not have a source, hence by Lemma 3 every minimal τ-retentive set of Un must contain at least three vertices. We show that the set R = {v n-1 2 , v n+1 2 , vn} is a minimal τ-retentive set of Un. By definition of Un, it is evident that vn is the only in-neighbor of vn-1 2 , hence τ(N - Un (v n-1 2 )) = {vn}. With {vn-1 2 } ≻ {v1, . . . , vn-3 2 } and N - Un (v n+1 2 ) = {v1, . . . , vn-1 2 }, we observe that τ (N - Un (v n+1 2 )) = {v n-1 2 }. Finally, {vn+1 2 } ≻ {vn+3 2 , . . . , vn} and N - Un (vn) = {vn+1 2 , . . . , vn-1}, so τ (N - Un (vn)) = {v n+1 2 }. Therefore, R = {vn-1 2 , v n+1 2 , vn} is a minimal τ-retentive set of T. Next, we show that R is the unique minimal τ-retentive set of T . For the sake of contradiction, suppose there exists another minimal τ-retentive set R′ of Un other than R. Let vi ∈ R′ \ R. Since vn is the only in-neighbor of vn-1 2 , the set τ(N - Un (vi)) contains at least one vertex from {vn, vn-1 2 }. Now, as shown above, any τ-retentive set of Un which contains any vertex from {v n-1 2 , v n+1 2 , vn} must contain all vertices in R. As R′ contains at least one vertex from {vn, vn-1 2 }, it holds R ⊂ R′ , a contradiction.

Lemma 8. Schwartz's Conjecture holds for tournaments Wn, for any odd n ∈ N≥5.

Proof. We claim that {v,w1,w2} is the unique minimal τretentive set of Wn. This follows from the facts that (i) w1 is the unique in-neighbor of w2; and (ii) v is the unique inneighbor of w1; and (iii) w2 is the source of the subtournament induced by w2 and all in-neighbors of v.

Due to the above proofs, and the fact that whether a tournament is isomorphic to Hn, Un or Wn for any odd n can be determined in polynomial time, τ can be calculated in polynomial time for critical tournaments.

As corollary we obtain Schwartz's Conjecture for further well-studied classes of tournaments. Latka [2003] showed that any prime tournament T of size at least 12 does not contain W5 (Theorem 1.2 in [Latka, 2003]. The authors in [Latka, 2003] use N5 to denote the graph W5 defined in this paper) if and only if T is isomorphic to an element of {H2n+1 | n ≥ 2} ∪ {U2n+1 | n ≥ 2}. Recall that Schwartz's Conjecture holds in all tournaments with at most 12 vertices [Brandt and Seedig, 2013]. By recursively use Lemma 6, as discussed in the last in Section 4, we have the following lemma.

Corollary 2. Schwartz's Conjecture holds for all W5-free tournaments.

6 Undominated Sets in Tournaments with Triangles Sharing at Most One Arc

In this section, we prove Theorem 4. Due to space limitations, we give only the sketch of the proof.

A feedback vertex set S of a tournament T is a subset of the vertices such that T [V (T )\S] is transitive. A feedback vertex set S is minimal if there is no other feedback vertex set S′ with S′ ⊂ S. Let (A, B) be a partition of T . Let fvs(A) be a minimal feedback vertex set of T [A], and let X = A\fvs(A). Then for each vertex v ∈ fvs(A) there is a triangle formed by v and two vertices in X. Hence, X is undominated in T [A]. If no vertex from B dominates X in T , then X is undominated in T, and is the desired set. Suppose now that some nonempty set R ⊆ B of vertices dominates X in T . Consider the following cases:

Case 1: Some r ∈ R dominates A in T .

In this case, we find a minimal feedback vertex set fvs(B) of T[B] such that r /∈ fvs(B). Then, one can check that B \ fvs(B) is undominated in T .

Case 2: No vertex of R dominates all vertices in A.

Now, for each vertex r ∈ R we can find a vertex gr ∈ fvs(A), called the guard of r, such that gr ≻ r. Let G be the set of all guard vertices of R. Then, we can find a desired set S (that is, a set S which induces a transitive subtournament and is undominated in T) such that S is formed from X by replacing some vertices in X with vertices in G. Due to space limitations, we defer further details to a full version of the paper.

7 Discussion

τ (Tournament equilibrium set) is a prominent tournament solution that has been extensively studied. Recently, Schwartz's Conjecture (Conjecture 1) and a weak variant proposed by Brandt [2013b] (Conjecture 2) were disproved, implying that τ does not satisfy many desirable properties. It is believed that tournaments where Schwartz's Conjecture does not hold are rare. However, less theoretical evidence is known. In this paper, we take the first step towards this line of research. In particular, we devised several sufficient conditions for infinite classes of tournaments that satisfy Schwartz's Conjecture and Brandt's Conjecture (see Theorems 1-4). Moreover, we explored several interesting properties on τ-retentive sets (Lemmas 2, 3 and 6). These properties might be useful in further study on τ and Schwartz's Conjecture.

Our results imply that every counterexample to Schwartz's Conjecture must contain at least one copy of W5, one copy of U5, and at least any one copy of graphs depicted in Fig. 1 ({F1, F2}). Notice that this does not mean that every counterexample includes at least 15 vertices, since these copies of W5,U5, F1, F2 could be overlapped. We believe that extending our method can yield the smallest counterexample to Schwartz's Conjecture, which is currently only known to lie in the range between 12 and 24 [Brandt and Seedig, 2013].

An intriguing direction for further research would be to extend our results to further tournaments.