Author(s)

Mustapha Balewa Sanni^1,2

¹Université Nationale des Sciences, Technologies, Ingénierie et Mathématiques (UNSTIM) d’Abomey, Abomey, Benin.
²Institut National Supérieur de Technologie Industrielle (INSTI) de Lokossa, Lokossa, Benin.

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.

Choice Procedure-Pseudo Tournament-Untrapped Set-Computational Complexity

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