_{1}

^{*}

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.

A common way to model a decision maker’s preferences is to consider a binary relation R over a set A of alternatives (teams, projects, candidates, goods, etc. …). In many different contexts (Sports league, Social Choice Theory, Economics, Operational Research, etc …), the binary relation R is used to make a choice between alternatives of A. Very often this relation is assumed to be complete and asymmetric (we say that R is a tournament) or sometimes complete (R is said to be a weak tournament). The general case concerning incomplete binary relations has received less attention (see [

From the binary relation defined on A, many mechanisms (procedures) are defined in order to choose the set of ‘‘best alternatives’’ also called choice sets. Some familiar choice procedures studied in the literature are the Top cycle choice procedure [

Recent work has addressed the computational complexity of many choice procedures (see for example: [

In this article, we consider the Untrapped choice procedure (UT) defined by Duggan [

We particularly focus, in this paper, on pseudo tournaments and we deduce another notion of the Untrapped (Strong Untrapped: SUt) choice procedure directely dependent on the pseudo tournament R studied. We also discuss the computational complexity of identifying the choice set for each of the choice procedures studied.

The rest of this article is structured as follows. Concepts that are used throughout this paper are given in Preliminaries (Section 2). Section 3 introduces the two extensions of the Untrapped choice procedures which are compared with two extensions of the Top cycle choice procedure. Computational complexity of Untrapped choice procedures is then explored in Section 4. Section 5 ends with an overview of the results.

A represents a finite set of alternatives and R a binary relation defined on A (i.e. R is a subset of A × A ). If ( x , y ) ∈ R we write x R y . If B is a non empty subset of A, R / B represents the restriction of R on B, i.e. R / B = { ( x , y ) ∈ B × B / x R y } . The binary relation R is said to be reflexive if x R x , ∀ x ∈ A . It is symmetric if x R y ⇒ y R x , ∀ x , y ∈ A . Relation R is asymmetric if x R y ⇒ n o t ( y R x ) , ∀ x , y ∈ A with x ≠ y . It is antisymmetric if x R y and y R x ⇒ x = y , ∀ x , y ∈ A . It is transitive if ( x R y and y R z ) ⇒ x R z , ∀ x , y , z ∈ A . It is complete if x R y or y R x , ∀ x , y ∈ A . A tournament is a complete and antisymmetric relation^{1}. A weak tournament is a complete relation. A pseudo tournament is any reflexive binary relation (the relation may be complete or not)^{2}.

Three other binary relations (I: indifference relation, P: strict preference relation and J: incomparability relation) are defined from R as follow: ∀ x , y ∈ A , x I y ⇔ ( x I y and y R x ), x P y ⇔ ( x R y and n o t ( y R x ) ) and x J y ⇔ n o t ( x R y ) and n o t ( y R x ) . It can be noticed that I is reflexive and symmetric, P is asymmetric (P is also called the asymmetric part of R) and J is symmetric. x P y (resp. x I y ) can be interpreted as x beats or is better than (resp. x is indifferent to) y.

A circuit is any subset { x 1 , x 2 , ⋯ , x k } of A (with k ≥ 2 ) such that x 1 R x 2 R ⋯ R x k and x k R x 1 . The subset { x 1 , x 2 , ⋯ , x k } is a P-circuit if x 1 P x 2 P ⋯ P x k and x k P x 1 . A is acyclic (resp. P-acyclic) if it contains no circuit (resp. no P-circuit).

The transitive closure R * of R is defined as follows: ∀ x , y ∈ A , x R * y if and only if ∃ k ∈ ℕ with k ≥ 1 , ∃ x 1 , x 2 , ⋯ , x k ∈ A , such that ∀ i ∈ { 1,2, ⋯ , k − 1 } , x i R x i + 1 , x 1 = x et x k = y . In other words x R * y if and only if there exists at least a path of length k from x to y (we also say that y is reachable from x). The transitive closure P * of P can also be defined in the same way (we then say that y is P-reachable from x).

The predecessor with respect to R (resp. with respect to P) of an alternative x ∈ A is the set P r e d ( x ) = { y ∈ A / y R x } (resp. P r e d P ( x ) = { y ∈ A / y P x } ). We also define the set C l ( x ) (resp. C l P ( x ) ) as C l ( x ) = { y ∈ A / y R * x } (resp. C l P ( x ) = { y ∈ A / y P * x } ). So y ∈ C l P ( x ) ) if y is P-reachable from x.

A choice procedure is a function C that maps each pseudo tournament R to a nonempty subset C ( R ) of A called the choice set.

If R is a tournament (resp. a weak tournament) the choice procedure is called a tournament solution (resp. a generalized or weak tournament solution) (see [

We say that a choice procedure C is contained in a choice procedure C ′ if C ( R ) ⊆ C ′ ( R ) for every pseudo tournament R defined on A (we write C ⊆ C ′ ).

^{1}Tournaments are always supposed to be asymmetric. We suppose without lost of generality that tournament may be reflexive.

^{2}Pseudo tournaments should not be confound with partial tournaments for which binary relations are asymmetric and not necessarily reflexive.

Many tournament or generalized tournament solutions have been studied in the litterature. A well known one is the Top Cycle choice procedure [

Definition 1. A non empty subset D of A is said to be a dominant set for a tournament R in A if x R y , ∀ x ∈ D , ∀ y ∈ A \ D .

D is a minimal dominant set if D is dominant and if no subset of D is dominant.

The Top Cycle choice procedure of a tournament R on A is defined as T C ( R ) = D , where D is the unique minimal dominant set for the tournament R. It is easy to show that T C ( R ) = { x ∈ A / x R ∗ y , ∀ y ∈ A } . It is also obvious that the asymmetric part of the transitive closure R * is without circuit and because R * is complete we have T C ( R ) = M ( R * ) . An attractive property of TC is that any alternative that beats another alternative in the Top Cycle is indirectly beaten by the latter.

The notion of (minimal) dominant set has been extended to the case of weak tournaments in two directions.

Definition 2. Let R be a weak tournament on A. A non empty subset D of A is a dominant (resp. undominated) set for R in A if n o t ( y R x ) (resp. n o t ( y P x ) ), ∀ x ∈ D , ∀ y ∈ A \ D .

D is a minimal dominant (resp. minimal undominated) set if D is dominant (resp. undominated) and if no subset of D is dominant (resp. undominated).

Contrary to the minimal undominated set, the minimal dominant set is unique. Schwartz [^{3} choice procedures] as follow:

Definition 3. Let R be a weak tournament defined on A.

The Getcha choice procedure of R is defined as G e t c h a ( R ) = D , where D is the (unique) minimal dominant set for R in A.

The Gocha choice procedure is defined by: G o c h a ( R ) = ∪ D i , where D i is a minimal undominated set.

Both Gocha and Getcha choice procedures coincide with the Top Cycle (TC) when the binary relation R is a tournament. It is easy to show that G o c h a ( R ) ⊆ G e t c h a ( R ) . Moreover we have [

For pseudo tournaments, we adopt the same definition for dominant and undominated sets. It is then easy to see that the dominant set is no more unique, so we have the following definition.

Definition 4. Let R be a pseudo-tournament on A^{4}.

The Gocha choice procedure is defined as the union of all minimal undominated sets for R in A.

The Getcha choice procedure is defined as the union of all minimal dominant sets for R in A.

Lemma 1. Let D be a minimal dominant (resp. minimal undominated) set for R in A. For all x , y ∈ D , we have x R * y (resp. x P * y ).

^{3}Getcha set (resp. Gocha set) is also called Smith set (resp. Schwartz set) in the litterature.

^{4}Sanni (2010) has defined two extensions of the Gocha procedure and two extensions of the Getcha procedure.

Proof. We give the proof for the case of the minimal dominant set. The proof for minimal undominated set is similar.

Consider D a minimal dominant set for R in A. Suppose there exists x , y ∈ D , such that n o t ( x R * y ) . Since y ∈ D , there exists y 1 ∈ D such that y 1 R y . We also have n o t ( x R y 1 ) [otherwise x R * y , a contradiction to n o t ( x R * y ) ]. So there exists y 2 ∈ D such that y 2 R y 1 . We have n o t ( x R y 2 ) . Similarly, there exist y 3 , y 4 , ⋯ , y n ∈ D such that y i + 1 R y i and n o t ( x R y i + 1 ) for all i ∈ { 1,2, ⋯ , n − 1 } . Now consider the set U = { z ∈ D , z R * y } . For all z ∈ U and z 0 ∉ U , we have n o t ( z 0 R z ) . So U is a dominant set for R in A. This contradicts the minimality of D because x ∈ D but x ∉ U .

The result of Deb [

Proposition 1. For a pseudo tournament R defined on A, we have:

1) G e t c h a ( R ) = M (R*)

2) G o c h a ( R ) = M ( P * ) .

Proof. Consider x ∈ M ( R * ) and suppose x ∉ G e t c h a ( R ) . There exists y 1 ∈ A such that y 1 R x . If y 1 ∈ G e t c h a ( R ) , then y 1 R x ⇒ y 1 R * x and since x ∈ M ( R * ) , we have x R * y (which is not possible). So y 1 ∉ G e t c h a ( R ) . There exists y 2 ∈ A such that y 2 R y 1 .

For the same reasons y 2 ∉ W G e ( R ) . Consider the set U = { z ∈ A , z R * y 1 } , we have U ∩ W G e ( R ) = ϕ . Moreover for all z ∈ U and for all z ′ ∈ A \ U , we have n o t ( z ′ R z ) . So the set U contains a dominant set for R in A which contains a minimal weak dominant set (which is not possible).

Now let x ∈ G e t c h a ( R ) and suppose there exists y ∈ A such that y R * x . x ∈ G e t c h a ( R ) implies that there exists a minima dominant set D such that x ∈ D . Then we have y ∈ D [otherwise ∃ x 1 , x 2 , ⋯ , x n ∈ A such that y = x 1 R x 2 R ⋯ R x n = x (which is not possible)]. so x , y ∈ D and according to the previous lemma, we also have x R * y .

Example. Let R be the pseudo tournament defined on A = { a , b , c , d , e , f , g } by a P b , a I c , b P c , c P d , c P e , d P e , e I f , e P g and g P d . We also have x R x , ∀ x ∈ A . The graph of R is represented by:

We have G o c h a ( R ) = { a , f } , G e t c h a ( R ) = { a , b , c } , S U t ( R ) = { a , b , c , f , g } and W U t ( R ) = { a , f , g } .

We study in this section two choice procedures (strong and weak Untrapped choice procedures) for pseudo tournaments. These choice procedures generalize the concept of Untrapped choice procedure defined by Duggan [

Definition 5. Let R be a pseudo tournament on A. We say that x weakly (resp. strongly) traps y with respsect to R and we write x T y (resp x T ˜ y ) if x P y and if n o t ( y P * x ) (resp. if x R y and if n o t ( y R * x ) ).

Relation T (resp T ˜ ) is not necessary transitive but is P-acyclic (resp. acyclic) [because if x 1 T x 2 ⋯ T x n and x n T x 1 , we get x 1 P x 2 P ⋯ P x n and x n P x 1 , which implies x 2 P * x 1 : this is not possible since x 1 T x 2 ]. So, we can define the set of its maximal elements. This leads to two choice procedures called weak Untrapped (resp. strong Untrapped) choice procedure, denoted by W U t (resp. S U t ) and defined as follow: W U t ( R ) = { x ∈ A / n o t ( y T x ) , ∀ y ∈ A } (resp. S U t ( R ) = { x ∈ A / n o t ( y T ˜ x ) , ∀ y ∈ A } ).

It is easy to see that an element x of A is in W U t ( R ) ^{5} if and only if n o t ( y P x ) or x P * y , ∀ y ∈ A .

So any alternative x which is not directly beaten or which beats indirectly some other alternatives (specially alternatives that beat directly x) is in the weak Untrapped set.

It is also easy to see that an element x of A is in S U t if and only if n o t ( y R x ) or x R * y , ∀ y ∈ A .

We can say that an alternative x strongly traps another alternative y ( x T ˜ y ) if x P y and if n o t ( y R * x ) ). So x ∈ S U t ( R ) if and only if n o t ( y P x ) or x R * y , ∀ y ∈ A .

When relation R is a tournament (resp. weak tournament) Duggan [

The following proposition gives inclusion relations between the different choice procedures mentionned above.

Proposition 2. For a pseudo tournament R defined on A, we have the following relations (

Legend: The symbol ⊇ (resp.=, ∅ ) indicates that the choice set in column is always contained in (resp. is equaled to, intersects) the choice set in row.

Proof. See Appendix.

The previous proposition can be summarized by the following Hasse diagram.

We can then notice that W U t is nested between Gocha and Getcha ( G o c h a ⊆ W U t ⊆ G e t c h a ) and that G e t c h a ⊆ S U t . Missing arrows between two choice sets indicates that the two always intersect and none is included in the other.

^{5}Duggan [

Lemma 2.

1) x ∈ S U t ⇔ P r e d ( x ) ⊆ C l (x)

2) x ∈ W U t ⇔ P r e d P ( x ) ⊆ C l P (x)

S U t ( R ) | W U t ( R ) | G o c h a ( R ) | G e t c h a ( R ) | |
---|---|---|---|---|

S U t ( R ) | = | ⊇ 1. | ⊇ 2. | ⊇ 3. |

W U t ( R ) | = | ⊇ 4. | ∅ 5. | |

G o c h a ( R ) | = | ∅ 6. | ||

G e t c h a ( R ) | = |

Proof.

1) ( ⇒ ): Let x ∈ S U t ( R ) .

· If P r e d ( x ) = ∅ then P r e d ( x ) ⊆ C l ( x ) .

· If P r e d ( x ) ≠ ∅ then for y ∈ P r e d ( x ) , y R x . And since x ∈ S U t ( R ) , we then have x R * y ; which implies that y ∈ C l ( x ) .

( ⇐ ): Let x ∈ A such that P r e d ( x ) ⊆ C l ( x ) and suppose that x ∉ S U t ( R ) ; then ∃ y ∈ A such that y T ˜ x . i.e. ∃ y ∈ A such that y R x and n o t ( x R * y ) . But y R x ⇒ y ∈ P r e d ( x ) ( ⊆ C l ( x ) ); which means y ∈ C l ( x ) , i.e. x R * y : a contradiction.

2) Similar to the previous one.

In this section we analyze the computational complexity of the weak (resp. strong) Untrapped set. The following algorithm (based on the previous lemma) describes how to get W U t ( R ) for a given pseudo tournament R defined on a finite set A. This algorithm can be considered for S U t ( R ) if P r e d P ( x ) (resp. C l P ( x ) )) is replaced by P r e d ( x ) (resp. C l ( x ) )).

Let us mention that deciding whether an alternative is contained in a choice set is computationally equivalent to finding the set [

It has been shown that the transitive closure of each x ∈ A is computable in polynomial time. The same holds for the computation of predecessors of x (see [

Duggan [

We have shown that each of the new choice procedures coincides with the familiar 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 by Duggan [

In terms of computational complexity, we present an algorithm to compute both the strong and the weak Untrapped choice procedure. This algorithm allows us to show that deciding whether an alternative is contained in the strong (or in the weak) Untrapped set is in P (class of problems that can be solved in polynomial time).

The author declares no conflicts of interest regarding the publication of this paper.

Sanni, M.B. (2019) The Computational Complexity of Untrapped Choice Procedures. Applied Mathematics, 10, 743-752. https://doi.org/10.4236/am.2019.109053

1) W U t ( R ) ⊆ S U t ( R ) .

Let R be a pseudo tournament defined on A. x ∈ W U t ( R ) ⇒ ∀ y ∈ A , n o t ( y P x ) or x P * y ⇒ ∀ y ∈ A , n o t ( y P x ) or x R * y ⇒ x ∈ S U t ( R ) .

2) G o c h a ( R ) ⊆ S U t ( R ) .

According to proof 4. and 1., we have respectively G o c h a ( R ) ⊆ W U t ( R ) and W U t ( R ) ⊆ S U t ( R ) .

3) G e t c h a ( R ) ⊆ S U t ( R ) .

Let R be a pseudo tournament defined on A and let x ∈ G e t c h a ( R ) .

Suppose x ∉ S U t ( R ) . Then ∃ y ∈ A such that y T ˜ x i.e. y P x and n o t ( x R * y ) . A contradiction since x ∈ G e t c h a ( R ) and G e t c h a ( R ) = M ( R * ) .

4) G o c h a ( R ) ⊆ W U t ( R ) .

Let R be a pseudo tournament defined on A and let x ∈ G o c h a ( R ) .

Suppose x ∉ W U t ( R ) . Then ∃ y ∈ A such that y T x . i.e. y P x and n o t ( x P * y ) : which is not possible since x ∈ G o c h a ( R ) and G o c h a ( R ) = M ( P * ) .

5) W U t ( R ) ∅ G e t c h a ( R ) .

Let’s show that any minimal weak dominant set intersects the weaak Untrapped set.

Consider a minimal weak dominant set D ′ and suppose that W U t ( R ) ∩ D ′ = ∅ . Then for x ∈ D ′ we have x ∉ W U t ( R ) . So ∃ y ∈ W U t ( R ) such that y P x . Which is not possible because y ∉ D ′ and x ∈ D ′ .

The above example shows that none of Getcha and WUt choice procedure is included in the other.

6) G o c h a ( R ) ∅ G e t c h a ( 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 G o c h a ( R ) ∩ G e t c h a ( R ) ≠ ∅ .

The above example shows that none of Getcha and Gocha choice procedure is included in the other.