“Untrapped choice procedures” and their computational complexities

Abstract

In this paper, we define two versions of Untrapped set (weak and strong Untrapped sets) over a finite set of alternatives. These versions, considered as choice procedures, extend the notion of Untrapped set in a more general case (i.e. when alternatives are not necessarily comparable). We show that they all coincide with Top cycle choice procedure for tournaments. In case of weak tournaments, the strong Untrapped set is equivalent to Getcha choice procedure and the Weak Untrapped set is exactly the Untrapped set studied in the litterature. We also present a polynomial-time algorithm for computing each set.

Appendix: Proof of Proposition 2

• 1. $WUt(R)\subseteq SUt(R)$. Let R be a pseudo-tournament defined on A. $x \in WUt(R) \Rightarrow \forall y\in A,$ not(yPx) or $xP^*y \Rightarrow \forall y\in A,$ not(yPx) or $xR^*y \Rightarrow x \in SUt(R)$.

• 2. $Gocha(R)\subseteq SUt(R)$. According to proof 4. and 1., we have,, respectively $Gocha(R)\subseteq WUt(R)$ and $WUt(R)\subseteq SUt(R)$.

• 3. $Getcha(R)\subseteq SUt(R)$. Let R be a pseudo tournament defined on A and let $x \in Getcha(R)$. Suppose $x\notin SUt(R)$. Then $\exists y\in A$ such that $y \tilde{T} x$. i.e. yPx and $not(x R^* y)$. A contradiction since $x \in Getcha(R)$ and $Getcha(R) = M(R^*)$.

• 4. $Gocha(R)\subseteq WUt(R)$. Let R be a pseudo-tournament defined on A and let $x \in Gocha(R)$. Suppose $x\notin WUt(R)$. Then $\exists y\in A$ such that yTx, i.e. yPx and $not(x P^* y)$: which is not possible since $x \in Gocha(R)$ and $Gocha(R) = M(P^*)$.

• 5. $WUt(R)\emptyset Getcha(R)$. Let us show that any minimal weak dominant set intersects the weak Untrapped set. Consider a minimal weak dominant set $D'$ and suppose that $WUt(R)\bigcap D'=\emptyset$. Then for $x\in D'$ we have $x \notin WUt(R)$. So $\exists y \in WUt(R)$ such that yPx, which is not possible because $y \notin D'$ and $x\in D'$. The above example shows that none of Getcha and WUt choice procedure is included in the other.

• 6. $Gocha(R)\emptyset Getcha(R)$. Note that every weak dominant set is a weak undominated set. So every minimal weak dominant set contains at least one minimal weak undominated set. We then have $Gocha(R)\bigcap Getcha(R)\ne \emptyset$. The above example shows that none of Getcha and Gocha choice procedure is included in the other.