TITLE:
The Computational Complexity of Untrapped Choice Procedures
AUTHORS:
Mustapha Balewa Sanni
KEYWORDS:
Choice Procedure-Pseudo Tournament-Untrapped Set-Computational Complexity
JOURNAL NAME:
Applied Mathematics,
Vol.10 No.9,
September
24,
2019
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.