IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v32y1986i6p660-672.html
   My bibliography  Save this article

On the Minimum Violations Ranking of a Tournament

Author

Listed:
  • Iqbal Ali

    (Department of General Business, University of Texas, Austin, Texas 78712)

  • Wade D. Cook

    (Faculty of Administrative Studies, York University, Toronto, Ontario, Canada M3J 2R6)

  • Moshe Kress

    (CEMA, P.O. Box 2250, Haifa, Israel)

Abstract

This paper examines the problem of rank ordering a set of players or objects on the basis of a set of pairwise comparisons arising from a tournament. The criterion for deriving this ranking is to have as few cases as possible where player i is ranked above j while i was actually defeated by j in the tournament. Such a situation is referred to as a violation. The objective, therefore, is to determine the Minimum Violations Ranking (MVR). While there are situations where this ranking would be allowed to contain ties among subsets of objects, we will concern ourselves herein with linear ordering (no ties). A series of examples are given where this requirement would seem to be appropriate. In order to put the MVR problem into proper perspective we introduce the concept of a distance on the set of tournaments. A set of natural axioms is presented which any such distance measure should obey, and it is proven that in the presence of these axioms a unique such measure exists. It is then shown that the MVR problem is equivalent to the minimum distance problem, which can be represented in several forms---in particular as a problem of determining the minimum feedback edge set in a graph and as a mixed integer generalized network problem. This opens up a wide scope of possible solution procedures for the MVR problem. An optimal algorithm is presented along with computational results. In addition, various heuristics are discussed including an improved heuristic referred to as the Iterated Kendall method.

Suggested Citation

  • Iqbal Ali & Wade D. Cook & Moshe Kress, 1986. "On the Minimum Violations Ranking of a Tournament," Management Science, INFORMS, vol. 32(6), pages 660-672, June.
  • Handle: RePEc:inm:ormnsc:v:32:y:1986:i:6:p:660-672
    DOI: 10.1287/mnsc.32.6.660
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.32.6.660
    Download Restriction: no

    File URL: https://libkey.io/10.1287/mnsc.32.6.660?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wade D. Cook & Tal Raviv & Alan J. Richardson, 2010. "Aggregating Incomplete Lists of Journal Rankings: An Application to Academic Accounting Journals," Accounting Perspectives, John Wiley & Sons, vol. 9(3), pages 217-235, September.
    2. Zhang, L.P. & Zhou, P., 2018. "A non-compensatory composite indicator approach to assessing low-carbon performance," European Journal of Operational Research, Elsevier, vol. 270(1), pages 352-361.
    3. Csató, László, 2013. "Rangsorolás páros összehasonlításokkal. Kiegészítések a felvételizői preferencia-sorrendek módszertanához [Paired comparisons ranking. A supplement to the methodology of application-based preferenc," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(12), pages 1333-1353.
    4. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    5. B. Jay Coleman, 2005. "Minimizing Game Score Violations in College Football Rankings," Interfaces, INFORMS, vol. 35(6), pages 483-496, December.
    6. Jonathan Levin & Barry Nalebuff, 1995. "An Introduction to Vote-Counting Schemes," Journal of Economic Perspectives, American Economic Association, vol. 9(1), pages 3-26, Winter.
    7. Michel Truchon, 2005. "Aggregation of Rankings: a Brief Review of Distance-Based Rules," Cahiers de recherche 0534, CIRPEE.
    8. Siraj, Sajid & Mikhailov, Ludmil & Keane, John, 2012. "A heuristic method to rectify intransitive judgments in pairwise comparison matrices," European Journal of Operational Research, Elsevier, vol. 216(2), pages 420-428.
    9. Kou, Gang & Ergu, Daji & Shang, Jennifer, 2014. "Enhancing data consistency in decision matrix: Adapting Hadamard model to mitigate judgment contradiction," European Journal of Operational Research, Elsevier, vol. 236(1), pages 261-271.
    10. Dong, Zhi-Long & Ribeiro, Celso C. & Xu, Fengmin & Zamora, Ailec & Ma, Yujie & Jing, Kui, 2023. "Dynamic scheduling of e-sports tournaments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    11. Kelin Luo & Yinfeng Xu & Bowen Zhang & Huili Zhang, 2018. "Creating an acceptable consensus ranking for group decision making," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 307-328, July.
    12. Ahmed Ghoniem & Agha Iqbal Ali & Mohammed Al-Salem & Wael Khallouli, 2017. "Prescriptive analytics for FIFA World Cup lodging capacity planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(10), pages 1183-1194, October.
    13. Wenfeng Zhu & Hengjie Zhang & Jing Xiao, 2023. "Coming to Consensus on Classification in Flexible Linguistic Preference Relations: The Role of Personalized Individual Semantics," Group Decision and Negotiation, Springer, vol. 32(5), pages 1237-1271, October.
    14. Yu Xiao & Ye Deng & Jun Wu & Hong‐Zhong Deng & Xin Lu, 2017. "Comparison of rank aggregation methods based on inherent ability," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(7), pages 556-565, October.
    15. Mass A. & Bezembinder, T. & Wakker, P., 1996. "On solving intansitivities in repeated pairwise choices," Mathematical Social Sciences, Elsevier, vol. 31(1), pages 53-53, February.
    16. Monsuur, Herman & Storcken, Ton, 1997. "Measuring intransitivity," Mathematical Social Sciences, Elsevier, vol. 34(2), pages 125-152, October.
    17. S. S. Dabadghao & B. Vaziri, 2022. "The predictive power of popular sports ranking methods in the NFL, NBA, and NHL," Operational Research, Springer, vol. 22(3), pages 2767-2783, July.
    18. Cook, Wade D., 2006. "Distance-based and ad hoc consensus models in ordinal preference ranking," European Journal of Operational Research, Elsevier, vol. 172(2), pages 369-385, July.
    19. Cooper, Orrin & Yavuz, Idil, 2016. "Linking validation: A search for coherency within the Supermatrix," European Journal of Operational Research, Elsevier, vol. 252(1), pages 232-245.
    20. C. Richard Cassady & Lisa M. Maillart & Sinan Salman, 2005. "Ranking Sports Teams: A Customizable Quadratic Assignment Approach," Interfaces, INFORMS, vol. 35(6), pages 497-510, December.
    21. Siraj, Sajid & Mikhailov, Ludmil & Keane, John A., 2015. "Contribution of individual judgments toward inconsistency in pairwise comparisons," European Journal of Operational Research, Elsevier, vol. 242(2), pages 557-567.
    22. Monsuur, Herman, 2005. "Characterizations of the 3-cycle count and backward length of a tournament," European Journal of Operational Research, Elsevier, vol. 164(3), pages 778-784, August.
    23. Brozos-Vázquez, Miguel & Campo-Cabana, Marco Antonio & Díaz-Ramos, José Carlos & González-Díaz, Julio, 2008. "Ranking participants in tournaments by means of rating functions," Journal of Mathematical Economics, Elsevier, vol. 44(11), pages 1246-1256, December.
    24. Siraj, S. & Mikhailov, L. & Keane, J.A., 2012. "Preference elicitation from inconsistent judgments using multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 220(2), pages 461-471.

    More about this item

    Keywords

    group decisions; voting/committees;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:32:y:1986:i:6:p:660-672. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.