Research ArticleOpen AccessGoogle Scholar indexed
The Computational Complexity of Untrapped Choice Procedures
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
- 1 Université Nationale des Sciences, Technologies, Ingénierie et Mathématiques (UNSTIM) d’Abomey, Abomey, Benin
- 2 Institut National Supérieur de Technologie Industrielle (INSTI) de Lokossa, Lokossa, Benin
Applied Mathematics·Volume 10 (2019)·Pages 743–752·Published 6 September 2019·DOI10.4236/am.2019.109053
Copy link · social · email
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.
KeywordsChoice Procedure-Pseudo Tournament-Untrapped Set-Computational Complexity
- Eliaz, K. and Ok, E.A. (2006) Indifference or Indecisiveness? Choice-Theoretic Foundations of Incomplete Preferences. Games and Economic Behavior, 56, 61-86. https://doi.org/10.1016/j.geb.2005.06.007
- Tapk, I.G. (2007) Revealed Incomplete Preferences under Status-Quo Bias. Mathematical Social Sciences, 53, 274-283. https://doi.org/10.1016/j.mathsocsci.2006.12.003
- Gorno, L. (2018) The Structure of Incomplete Preferences. Economic Theory, 66, 159-185. https://doi.org/10.1007/s00199-017-1057-9
- Urena, R., Chiclana, F., Morente-Molinera, J.A. and Herrera-Viedma, E. (2015) Managing Incomplete Preference Relations in Decision Making: A Review and Future Trends. Information Sciences, 302, 14-32. https://doi.org/10.1016/j.ins.2014.12.061
- Zhi, H. and Chao, H. (2018) Three-Way Concept Analysis for Incomplete Formal Contexts. Mathematical Problems in Engineering, 2018, Article ID: 9546846. https://doi.org/10.1155/2018/9546846
- Hill, B. (2016) Incomplete Preferences and Confidence. Journal of Mathematical Economics, 65, 83-103. https://doi.org/10.1016/j.jmateco.2016.05.007
- Albers, S., Bichler, M., Brandt, F., Gritzmann, P. and Kolisch, R. (2017) Algorithmic Economics und Operations Research. Informatik-Spektrum, 40, 165-171. https://doi.org/10.1007/s00287-017-1023-8
- Schwartz, T. (1972) Rationality and the Myth of the Maximum. Nous, 7, 97-117. https://doi.org/10.2307/2216143
- Copeland, A. (1951) A Reasonable Social Welfare Function. Seminar on Applications of Mathematics to Social Sciences, University of Michigan, Ann Arbor (Mimeographed Notes).
- Miller, N.R. (1980) A New Solution Set for Tournaments and Majority Voting: Further Graph-Theoretical Approaches to the Theory of Voting. American Journal of Political Science, 24, 68-96. https://doi.org/10.2307/2110925
- Laslier, J.-F. (1997) Tournament Solutions and Majority Voting. No. 7, Springer Verlag, Berlin. https://doi.org/10.1007/978-3-642-60805-6
- Peris, J.E. and Subiza, B. (1999) Condorcet Choice Correspondences for Weak Tournaments. Social Choice and Welfare, 16, 217-231. https://doi.org/10.1007/s003550050141
- Sanni, M. (2010) Etude des procedures de choix fondees sur des relations binaires. PhD Thesis, Universite de Paris Dauphine, Paris.
- Aziz, H., Brandt, F., Elkind, E. and Skowron, P. Computational Social Choice: The First Ten Years and Beyond. In: Steffen, B. and Woeginger, G., Eds., Computing and Software Science, Vol. 10000 of Lecture Notes in Computer Science (LNCS), Springer, Berlin, forthcoming.