Minimal retentive sets in tournaments

Abstract

Tournament solutions, i.e., functions that associate with each complete and asymmetric relation on a set of alternatives a nonempty subset of the alternatives, play an important role in the mathematical social sciences at large. For any given tournament solution $S$, there is another tournament solution  which returns the union of all inclusion-minimal sets that satisfy $S$-retentiveness, a natural stability criterion with respect to $S$. Schwartz’s tournament equilibrium set (${ TEQ }$) is defined recursively as . In this article, we study under which circumstances a number of important and desirable properties are inherited from $S$ to . We thus obtain a hierarchy of attractive and efficiently computable tournament solutions that “approximate” ${ TEQ }$, which itself is computationally intractable. We further prove a weaker version of a recently disproved conjecture surrounding ${ TEQ }$, which establishes —a refinement of the top cycle—as an interesting new tournament solution.

Appendix: Proof of Theorem 3

Theorem 3

Let $S$ be a tournament solution such that $\mathcal R _S$ is pairwise intersecting, and let $\mathsf{{P}}$ be any of the properties $\mathsf{SSP }, \mathsf{WSP }, \mathsf{IUA }, \mathsf{MON } \wedge \mathsf{SSP },$ or ${\widehat{\gamma }}\wedge \mathsf{SSP }$. Then, $\mathsf P$ is satisfied by $S$ if and only if it is satisfied by .

Proof

Assume that $\mathcal R _S$ is pairwise intersecting. We need to show that each of the properties $\mathsf{SSP }, \mathsf{WSP }, \mathsf{IUA }, \mathsf{MON } \wedge \mathsf{SSP }$, and ${\widehat{\gamma }}\wedge \mathsf{SSP }$ is satisfied by $S$ if and only if it is satisfied by . The direction from right to left follows from Theorem 2. We now show that the properties are inherited from $S$ to .

Assume that $S$ satisfies SSP. Let $T=(A,\succ )$ be a tournament, and consider an alternative . We need to show that , where $T^{\prime }={(A\setminus \{x\},\succ )}$. We will show that

(1)

This implies that is a minimal $S$-retentive set in $T^{\prime }$. Since $\mathcal R _S$ is assumed to be pairwise intersecting, is indeed the unique minimal $S$-retentive set in $T^{\prime }$, i.e., .

To show (1), consider an arbitrary . If $x\notin \overline{D}_A(a)$, then obviously $\overline{D}_A(a)=\overline{D}_{A\setminus \{x\}}(a)$ and thus $S(\overline{D}_A(a))=S(\overline{D}_{A\setminus \{x\}}(a))$. Assume on the other hand that $x\in \overline{D}_A(a)$. Since and , it follows that $x\notin {S}(\overline{D}_A(a))$, as otherwise would not be $S$-retentive. Now, since $S$ satisfies $\mathsf{SSP }$, we obtain $S(\overline{D}_A(a))=S(\overline{D}_{A\setminus \{x\}}(a))$ as desired.

Assume that $S$ satisfies WSP. Let $T=(A,\succ )$ be a tournament, and consider an alternative . We need to show that , where $T^{\prime }=(A\setminus \{x\},{\succ })$. Since $\mathcal R _S$ is assumed to be pairwise intersecting, it suffices to show that is also $S$-retentive in $T^{\prime }$. To this end, consider an arbitrary . Since $S$ satisfies WSP, we have that $S(\overline{D}_{A\setminus \{x\}}(a))\subseteq S(\overline{D}_A(a))$. Furthermore, by $S$-retentiveness of , and thus .

Assume that $S$ satisfies IUA. Let $T=(A,\succ )$ and $T^{\prime }=(A,{\succ ^{\prime }})$ be tournaments such that for all $a\in A$. We need to show that . We will show that

(2)

This implies that is a minimal $S$-retentive set in $T^{\prime }$. Since $\mathcal R _S$ is assumed to be pairwise intersecting, we have .

To show (2), consider an arbitrary . $S$-retentiveness of in $T$ implies that . Therefore, it follows from the definition of $T$ and $T^{\prime }$ that $T|_{S(\overline{D}_{\succ }(a),\succ )\cup \{b\}}=T^{\prime }|_{S(\overline{D}_{\succ }(a),\succ )\cup \{b\}}$ for all $b \in \overline{D}(a)$. Now, since $S$ satisfies $\mathsf{IUA }$, we obtain $S(\overline{D}_{\succ }(a),\succ ) = S(\overline{D}_{\succ ^{\prime }}(a),\succ ^{\prime })$ as desired.

Assume that $S$ satisfies $\mathsf{MON }$ and $\mathsf{SSP }$. We have already seen that $\mathsf{SSP }$ is inherited, so it remains to be shown that satisfies $\mathsf{MON }$. The following argument is adapted from the proof of Proposition 3.6 in Laffond et al. (1993). Let $T=(A,{\succ })$ be a tournament, and consider two alternatives $a,b\in A$ such that and $b\succ a$. Let $T^{\prime }=(A,\succ ^{\prime })$ be the tournament with $T|_{A\setminus \{a\}}=T^{\prime }|_{A\setminus \{a\}}$ and $D_{\succ ^{\prime }}(a) = D_{\succ }(a) \cup \{b\}$.

We have to show that . To this end, we claim that for all $c\in A\setminus \{a\}$,

$$\begin{aligned} a \notin S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime }) \quad \text{ implies } \quad S(\overline{D}_{\succ }(c),\succ ) = S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime }). \end{aligned}$$

(3)

Consider the case when $c\ne b$ and assume that $a\notin S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime })$. It follows from monotonicity of $S$ that $a \notin S(\overline{D}_{\succ }(c),\succ )$. To see this, observe that monotonicity of $S$ implies that $a\in S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime })$ whenever $a\in S(\overline{D}_{\succ }(c),\succ )$.

Now, since $S$ satisfies $\mathsf{SSP }$,

$$\begin{aligned} S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime })&= S(\overline{D}_{\succ ^{\prime }}(c) \setminus \{a\},\succ ^{\prime }) \quad \text{ and } \\ S(\overline{D}_{\succ }(c),\succ )&= S(\overline{D}_{\succ }(c) \setminus \{a\},\succ ). \end{aligned}$$

It is easily verified that $(\overline{D}_{\succ ^{\prime }}(c)\setminus \{a\},\succ ^{\prime }) = (\overline{D}_{\succ }(c)\setminus \{a\},\succ )$, thus we have ${S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime })}=S(\overline{D}_{\succ }(c),\succ )$.

If $c=b$, then $a\notin S(\overline{D}_{\succ ^{\prime }}(b),{\succ ^{\prime }})$ together with $\mathsf{SSP }$ of $S$ implies ${S(\overline{D}_{\succ ^{\prime }}(b),\succ ^{\prime })}=S(\overline{D}_{\succ ^{\prime }}(b)\setminus \{a\},\succ ^{\prime })$. Furthermore, by definition of $T$ and $T^{\prime }$, $(\overline{D}_{\succ ^{\prime }}(b)\setminus \{a\},\succ ^{\prime }) = (\overline{D}_{\succ }(b),\succ )$ and thus $S(\overline{D}_{\succ ^{\prime }}(b),\succ ^{\prime })= S(\overline{D}_{\succ }(b),{\succ })$. This proves (3).

We proceed to show that . Assume for contradiction that this is not the case. We claim that this implies that

(4)

To see this, consider . We have to show that . Since, by assumption, , we have that $a \!\notin \! S(\overline{D}_{\succ ^{\prime }}(c),\succ ^{\prime })$. We can thus apply (3) and get

which, together with the $S$-retentiveness of in $T^{\prime }$, implies (4).

Having assumed that $\mathcal R _S$ is pairwise intersecting, it follows from (4) that . Hence, , a contradiction. This shows that satisfies $\mathsf{MON }$.

Finally assume that $S$ satisfies ${\widehat{\gamma }}$ and SSP. We already know from the above that  satisfies SSP, so it remains to be shown that satisfies ${\widehat{\gamma }}$. Let $T=(A,\succ )$ be a tournament, and consider two subsets $B_1, B_2 \subseteq A$ such that . We have to show that . We will show that

$$\begin{aligned} S(\overline{D}_{B_1 \cup B_2}(c))=S(\overline{D}_{B_1}(c)) \quad \text{ for } \text{ all } c\in C. \end{aligned}$$

(5)

This implies that $C$ is a minimal $S$-retentive set in $T|_{B_1 \cup B_2}$. Since $\mathcal R _S$ is assumed to be pairwise intersecting, we have .

To show (5), consider an arbitrary $c \in C$. Since and are $S$-retentive in $T|_{B_1}$ and $T|_{B_2}$, respectively, we have $S(\overline{D}_{B_i}(c))\subseteq C \subseteq B_1 \cap B_2$ for $i \in \{1,2\}$. The fact that $S$ satisfies SSP now implies $S(\overline{D}_{B_1 \cap B_2}(c)) = S(\overline{D}_{B_1}(c))$ and $S(\overline{D}_{B_1 \cap B_2}(c)) = S(\overline{D}_{B_2}(c))$, and thus $S(\overline{D}_{B_1}(c)) = S(\overline{D}_{B_2}(c))$. Since $S$ satisfies ${\widehat{\gamma }}$, we have $S(\overline{D}_{B_1 \cup B_2}(c))=S(\overline{D}_{B_1}(c) \cup \overline{D}_{B_2}(c))=S(\overline{D}_{B_1}(c))$, as desired. $\square$