Abstract
Many real world tasks involve the need to order alternatives based on specifications of preference over subsets of the alternatives, the problem of preference based alternative ordering. Examples include dancing championship adjudication, Eurovision Song Contest decision-making, collaborative filtering and meta-search engines. One usual solution to this problem consists in allocating scores to the alternatives and aggregating the scores to generate ranks for all alternatives. Examples of this solution include competition adjudication. Another solution involves generating ranks from different sources for all the alternatives and then adding the rank values of each alternative to give the Borda scores for this alternative. The Borda scores are then used to order the alternatives. Examples include elections and meta-search engines. The problem with these two approaches is, the scores or ranks are sometimes hard to determine (e.g., collaborative filtering).
In this paper we take the view that relative preferences over alternatives (e.g., one alternative is preferred to another) are easier to obtain than absolute scores or ranks. We consider an alternative approach to this problem where, instead of using absolute scores or ranks, we use relative preferences over subsets of the alternatives to generate a total ordering that is maximally agreeable with the given preferences.
We consider a set of preference specifications over all or part of the alternatives. For every pair of alternatives we calculate the probability that the two alternatives should be placed in an order. Then the Order-By-Preference algorithm is used to construct a total ordering for all the alternatives, which is guaranteed to be approximately optimal.
The idea presented in this paper was discussed at EU COST Action 274 (TARSKI) Workshop in Belfast, 2005.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Janicki, R., Koczkodaj, W.: A weak order approach to group ranking. Computers and Mathematics with Applications 32(2), 51–59 (1996)
Saari, D.G.: Chaotic Elections! A Mathematician Looks at Voting. American Mathematical Society (2001)
Saari, D.G.: Decisions and Elections: Explaining the Unexpected. Cambridge University Press, Cambridge (2001)
Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. Journal of Artificial Intelligence Research 10, 243–270 (1999)
Ash, R.: Real Analysis and Probability. Academic Press, New York (1972)
Wang, H., Dubitzky, W.: A flexible and robust similarity measure based on contextual probability. In: Proceedings of IJCAI’05, pp. 27–32 (2005)
Wang, H.: Nearest neighbors by neighborhood counting. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(6), 942–953 (2006)
Wang, H.: All common subsequences (Oral presentation). In: Proc. IJCAI-07, pp. 635–640 (2007)
Bouysso, D., Vincke, P.: Ranking alternatives on the basis of preference relations: a progress report with special emphasis on outranking relations. Journal of Multi-Criteria Decision Analysis 6, 77–85 (1997)
Arrow, K.: Social Choice and Individual Values. John Wiley, Philadelphia (1951)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Wang, H., Lin, Z., Gediga, G. (2007). Counting All Common Subsequences to Order Alternatives. In: Yao, J., Lingras, P., Wu, WZ., Szczuka, M., Cercone, N.J., Ślȩzak, D. (eds) Rough Sets and Knowledge Technology. RSKT 2007. Lecture Notes in Computer Science(), vol 4481. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72458-2_70
Download citation
DOI: https://doi.org/10.1007/978-3-540-72458-2_70
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72457-5
Online ISBN: 978-3-540-72458-2
eBook Packages: Computer ScienceComputer Science (R0)