×

Making choices with a binary relation: relative choice axioms and transitive closures. (English) Zbl 1205.91053

Summary: This article presents an axiomatic analysis of the best choice decision problem from a reflexive crisp binary relation on a finite set (a digraph). With respect to a transitive digraph, optimality and maximality are usually accepted as the best fitted choice axioms to the intuitive notion of best choice. However, beyond transitivity (resp. acyclicity), optimality and maximality can characterise distinct choice sets (resp. empty sets). Accordingly, different and rather unsatisfying concepts have appeared, such as von Neumann-Morgenstern domination, weak transitive closure and kernels. Here, we investigate a new family of eight choice axioms for digraphs: relative choice axioms. Within choice theory, these axioms generalise top-cycle for tournaments, gocha, getcha and rational top-cycle for complete digraphs. We present their main properties such as existence, uniqueness, idempotence, internal structure, and cross comparison. We then show their strong relationship with optimality and maximality when the latter are not empty. Otherwise, these axioms identify a non-empty choice set and underline conflicts between chosen elements in strict preference circuits. Finally, we exploit the close link between this family and transitive closures to compute choice sets in linear time, followed by a relevant practical application.

MSC:

91B06 Decision theory
91B14 Social choice

Software:

VisualUTA; CP-nets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aït Younes, A., Azibi, R., Roy, B., 2000. Electre IS manuel d’utilisation. Tomes 1 & 2, Document du LAMSADE No. 118 & 118 bis, Université Paris-Dauphine.; Aït Younes, A., Azibi, R., Roy, B., 2000. Electre IS manuel d’utilisation. Tomes 1 & 2, Document du LAMSADE No. 118 & 118 bis, Université Paris-Dauphine.
[2] Aizerman, M.; Aleskerov, F., Theory of choice, Studies in Mathematical and Managerial Economics, vol. 38 (1995), Elsevier Science B.V., North-Holland: Elsevier Science B.V., North-Holland Amsterdam · Zbl 0947.91028
[3] Allingham, M., Choice Theory: A Very Short Introduction (2002), Oxford University Press
[4] Bang-Jensen, J.; Gutin, G., Digraphs: Theory Algorithms and Applications. Digraphs: Theory Algorithms and Applications, Springer Monographs in Mathematics (2001), Springer-Verlag: Springer-Verlag London · Zbl 0958.05002
[5] Belmandt, Z., Manuel de prétopologie et ses applications (1993), Éditions Hermès: Éditions Hermès France, Paris, (Chapter 16) · Zbl 0863.54001
[6] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[7] Boutilier, C.; Brafman, R. I.; Domshlak, C.; Hoos, H. H.; Poole, D., CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements, Journal of Artificial Intelligence Research, 21, 135-191 (2004) · Zbl 1080.68685
[8] Bouyssou, D.; Pirlot, M., An axiomatic analysis of concordance-discordance relations, European Journal of Operational Research, 199, 2, 468-477 (2009) · Zbl 1176.90272
[9] Brandt, F.; Fischer, F.; Harrenstein, P., The computational complexity of choice sets, Mathematical Logic Quarterly, 55, 4, 444-459 (2009) · Zbl 1173.91358
[10] Deb, R., On Schwartz’s rule, Journal of Economic Theory, 16, 103-110 (1977) · Zbl 0369.90003
[11] Duggan, J., A systematic approach to the construction of non-empty choice sets, Social Choice and Welfare, 28, 491-506 (2007) · Zbl 1211.91106
[12] Figueira, J.; Greco, S.; Ehrgott, M., Multiple criteria decision analysis: state of the art surveys, International Series in Operations Research and Management Science, vol. 78 (2005), Springer · Zbl 1060.90002
[13] Figueira, J.; Greco, S.; Słowiński, R., Building a set of additive value functions representing a reference preorder and intensities of preference: GRIP method, European Journal of Operational Research, 195, 2, 460-486 (2009) · Zbl 1159.91341
[14] Fishburn, P. C., Intransitive indifference with unequal indifference intervals, Journal of Mathematical Psychology, 7, 144-149 (1970) · Zbl 0191.31501
[15] Fortemps, P.; Greco, S.; Słowiński, R., Multicriteria decision support using rules that represent rough-graded preference relations, European Journal of Operational Research, 188, 1, 185-190 (2008) · Zbl 1135.90019
[16] Ghoshal, J.; Laskar, R.; Pillone, D., Topics on domination in directed graphs, (Haynes, T.; Hedetniemi, S.; Slater, P. J., Domination in Graphs: Advanced Topics. Domination in Graphs: Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, vol. 209 (1998), Marcel Dekker: Marcel Dekker New York), 401-437 · Zbl 0887.05029
[17] Greco, S.; Matarazzo, B.; Słowiński, R., Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules, European Journal of Operational Research, 158, 2, 271-292 (2004) · Zbl 1067.90071
[18] Greco, S.; Mousseau, V.; Słowiński, R., Ordinal regression revisited: multiple criteria ranking using a set of additive value functions, European Journal of Operational Research, 191, 2, 416-436 (2008) · Zbl 1147.90013
[19] Guitouni, A.; Martel, J. M., Tentative guidelines to help choosing an appropriate MCDA method, European Journal of Operational Research, 109, 2, 501-521 (1998) · Zbl 0937.90042
[20] Hudry, O., A survey on the complexity of tournament solutions, Mathematical Social Science, 57, 3, 292-303 (2009) · Zbl 1176.91030
[21] Joseph, R.R., 2003. Systèmes interactifs d’aide à l’Élaboration de plannings de travail de personnel. Ph.D. Thesis, Université Joseph Fourier, Grenoble, France.; Joseph, R.R., 2003. Systèmes interactifs d’aide à l’Élaboration de plannings de travail de personnel. Ph.D. Thesis, Université Joseph Fourier, Grenoble, France.
[22] Joseph, R. R.; Chan, P.; Hiroux, M.; Weil, G., Decision aiding with preference constraints, European Journal of Operational Research, 177, 3, 1469-1494 (2007) · Zbl 1109.90071
[23] Kaymak, B.; Sanver, M. R., Sets of alternatives as condorcet winners, Social Choice and Welfare, 20, 3, 477-494 (2003) · Zbl 1073.91547
[24] Keeney, R. L.; Raïffa, H., Decisions with Multiple Objectives: Preferences and Value Tradeoffs (1976), John Wiley & Sons: John Wiley & Sons New York · Zbl 0488.90001
[25] Lang, J., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T., 2007. Winner determination in sequential majority voting. In: Veloso, M.M. (Ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 1372-1377.; Lang, J., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T., 2007. Winner determination in sequential majority voting. In: Veloso, M.M. (Ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 1372-1377.
[26] Lang, J.; Xia, L., Sequential composition of voting rules in multi-issue domains, Mathematical Social Sciences, 57, 3, 304-324 (2009) · Zbl 1176.91031
[27] Laffond, G.; Laslier, J. F.; Le Breton, M., Condorcet choice correspondences: a set-theoretical comparison, Mathematical Social Sciences, 30, 23-35 (1995) · Zbl 0886.90016
[28] Luce, R. D., Semi-orders and a theory of utility discrimination, Econometrica, 24, 2, 178-191 (1956) · Zbl 0071.14006
[29] Miller, N. R., Graph theoretical approaches to the theory of voting, American Journal of Political Science, 21, 769-803 (1977)
[30] Peris, J. E.; Subiza, B., Condorcet choice correspondences for weak tournaments, Social Choice and Welfare, 16L, 217-231 (1999) · Zbl 1066.91541
[31] Peris, J. E.; Subiza, B., Choosing among maximals, Journal of Mathematical Psychology, 46, 1-11 (2002) · Zbl 1051.91012
[32] Roy, B., A missing link in OR-DA: Robustness analysis, Foundations of Computing and Decision Sciences, 23, 3, 141-160 (1998) · Zbl 0967.90077
[33] Roy, B., Robustness in operational research and decision aiding: a multi-faceted issue, European Journal of Operational Research, 200, 3, 629-638 (2010) · Zbl 1177.90004
[34] Roy, B., Bouyssou, D., 1993. Aide multicritère à la décision: Méthodes et cas collection Gestion, Economica, Paris.; Roy, B., Bouyssou, D., 1993. Aide multicritère à la décision: Méthodes et cas collection Gestion, Economica, Paris. · Zbl 0925.90230
[35] Schwartz, T., Rationality and the myth of the maximum, Noûs, 7, 97-117 (1972)
[36] Schwartz, T., The Logic of Collective Choice (1986), Columbia University Press: Columbia University Press New-York
[37] Sen, A. K., Collective choice and social welfare, Advanced Textbooks in Economics, vol. 11 (1970), Elsevier Science Publishers: Elsevier Science Publishers Netherlands · Zbl 0227.90011
[38] Sen, A. K., Social choice theory, (Arrow, K. J.; Intriligator, M. D., Handbook of Mathematical Economics, vol. 3 (1986), Elsevier Science Publishers B.V., North-Holland), 1073-1181
[39] Sen, A. K., Maximization and the act of choice, Econometrica, 65, 4, 745-779 (1997) · Zbl 0891.90013
[40] Sen, A. K., Rationality and Freedom (2002), Belknap Press, Harvard University Press: Belknap Press, Harvard University Press Cambridge, Massachusetts
[41] Simon, H. A., The New Science of Management Decision (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs
[42] Subiza, B.; Peris, J. E., Choice functions: rationality re-examined, Theory and Decision, 48, 287-304 (2000) · Zbl 0971.91016
[43] Subiza, B.; Peris, J. E., Condorcet choice functions and maximal elements, Social Choice and Welfare, 24, 497-508 (2005) · Zbl 1075.91013
[44] Subiza, B.; Peris, J. E., Strong maximals: elements with maximal score in partial orders, Spanish Economic Review, 7, 157-166 (2005)
[45] Suzumura, K., Rational choice, collective decisions and social welfare (1983), Cambridge University Press: Cambridge University Press Cambridge, Massachusetts
[46] Thomson, W., 1997. On the axiomatic method. Parts I & II. Rochester Center of Economic Research Working Paper 445 & 446.; Thomson, W., 1997. On the axiomatic method. Parts I & II. Rochester Center of Economic Research Working Paper 445 & 446.
[47] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, London · Zbl 0764.05001
[48] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behaviour (1944), Princeton University Press: Princeton University Press Princeton
[49] White, D. J., Kernels of preferences structures, Econometrica, 45, 1, 91-100 (1977) · Zbl 0372.90006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.