IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v175y2010i1p107-15810.1007-s10479-009-0648-7.html
   My bibliography  Save this article

An updated survey on the linear ordering problem for weighted or unweighted tournaments

Author

Listed:
  • Irène Charon
  • Olivier Hudry

Abstract

In this paper, we survey some results, conjectures and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem. This problem consists in finding a linear order which is at minimum distance from a (weighted or not) tournament. We show how it can be used to model an aggregation problem consisting of going from individual preferences defined on a set of candidates to a collective ranking of these candidates. Copyright Springer Science+Business Media, LLC 2010

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:175:y:2010:i:1:p:107-158:10.1007/s10479-009-0648-7
    DOI: 10.1007/s10479-009-0648-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-009-0648-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-009-0648-7?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Thomas C. Ratliff, 2001. "A comparison of Dodgson's method and Kemeny's rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(1), pages 79-89.
    2. Righini, Giovanni, 2008. "A branch-and-bound algorithm for the linear ordering problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 186(3), pages 965-971, May.
    3. Nathalie Caspard & Bruno Leclerc & Bernard Monjardet, 2007. "Ensembles ordonnés finis : concepts, résultats, usages," Post-Print halshs-00197128, HAL.
    4. Mendonca, D. & Raghavachari, M., 2000. "Comparing the efficacy of ranking methods for multiple round-robin tournaments," European Journal of Operational Research, Elsevier, vol. 123(3), pages 593-605, June.
    5. Kaas, R., 1981. "A branch and bound algorithm for the acyclic subgraph problem," European Journal of Operational Research, Elsevier, vol. 8(4), pages 355-362, December.
    6. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    7. Barthelemy, J. P. & Guenoche, A. & Hudry, O., 1989. "Median linear orders: Heuristics and a branch and bound algorithm," European Journal of Operational Research, Elsevier, vol. 42(3), pages 313-325, October.
    8. Bernard Monjardet & Jean-Pierre Barthélemy & Olivier Hudry & Bruno Leclerc, 2009. "Metric and latticial medians," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-00408174, HAL.
    9. Leung, J. & Lee, J., 1994. "More facets from fences for linear ordering and acyclic subgraph polytopes," LIDAM Reprints CORE 1087, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
    11. 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.
    12. Olivier Hudry, 2004. "A note on “Banks winners in tournaments are difficult to recognize” by G. J. Woeginger," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(1), pages 113-114, August.
    13. Pierre Barthelemy, Jean & Monjardet, Bernard, 1981. "The median procedure in cluster analysis and social choice theory," Mathematical Social Sciences, Elsevier, vol. 1(3), pages 235-267, May.
    14. Monsuur, Herman & Storcken, Ton, 1997. "Measuring intransitivity," Mathematical Social Sciences, Elsevier, vol. 34(2), pages 125-152, October.
    15. Laffond G. & Laslier J. F. & Le Breton M., 1993. "The Bipartisan Set of a Tournament Game," Games and Economic Behavior, Elsevier, vol. 5(1), pages 182-201, January.
    16. J. M. Blin & A. B. Whinston, 1974. "Note--A Note on Majority Rule under Transitivity Constraints," Management Science, INFORMS, vol. 20(11), pages 1439-1440, July.
    17. Irène Charon & Olivier Hudry, 1998. "Lamarckian genetic algorithmsapplied to the aggregation of preferences," Annals of Operations Research, Springer, vol. 80(0), pages 281-297, January.
    18. Deepak K. Merchant & M. R. Rao, 1976. "Majority Decisions and Transitivity: Some Special Cases," Management Science, INFORMS, vol. 23(2), pages 125-130, October.
    19. Fishburn, Peter C., 1992. "Induced binary probabilities and the linear ordering polytope: a status report," Mathematical Social Sciences, Elsevier, vol. 23(1), pages 67-80, February.
    20. Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 523-528, June.
    21. Olivier Hudry, 2008. "NP-hardness results for the aggregation of linear orders into median orders," Annals of Operations Research, Springer, vol. 163(1), pages 63-88, October.
    22. Bertacco, Livio & Brunetta, Lorenzo & Fischetti, Matteo, 2008. "The Linear Ordering Problem with cumulative costs," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1345-1357, September.
    23. Young, H. P., 1988. "Condorcet's Theory of Voting," American Political Science Review, Cambridge University Press, vol. 82(4), pages 1231-1244, December.
    24. V. J. Bowman & C. S. Colantoni, 1973. "Majority Rule Under Transitivity Constraints," Management Science, INFORMS, vol. 19(9), pages 1029-1041, May.
    25. Christian Klamler, 2004. "The Dodgson ranking and its relation to Kemeny’s method and Slater’s rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(1), pages 91-102, August.
    26. Fred Glover & T. Klastorin & D. Kongman, 1974. "Optimal Weighted Ancestry Relationships," Management Science, INFORMS, vol. 20(8), pages 1190-1193, April.
    27. Christian Klamler, 2003. "Kemeny's rule and Slater''s rule: A binary comparison," Economics Bulletin, AccessEcon, vol. 4(35), pages 1-7.
    28. T. Christof & G. Reinelt, 1996. "Combinatorial optimization and small polytopes," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(1), pages 1-53, June.
    29. J. M. Blin & Andrew B. Whinston, 1975. "Discriminant Functions and Majority Voting," Management Science, INFORMS, vol. 21(5), pages 557-566, January.
    30. Hudry, Olivier, 2010. "On the complexity of Slater's problems," European Journal of Operational Research, Elsevier, vol. 203(1), pages 216-221, May.
    31. Martin Grötschel & Michael Jünger & Gerhard Reinelt, 1984. "A Cutting Plane Algorithm for the Linear Ordering Problem," Operations Research, INFORMS, vol. 32(6), pages 1195-1220, December.
    32. Banks, J.S. & Bordes, G., 1991. "Covering Relations, Closest Ordering and Hamiltonian Bypaths in Tournaments," G.R.E.Q.A.M. 91a05, Universite Aix-Marseille III.
    33. Charon, Irene & Hudry, Olivier, 2001. "The noising methods: A generalization of some metaheuristics," European Journal of Operational Research, Elsevier, vol. 135(1), pages 86-101, November.
    34. Vicente Campos & Manuel Laguna & Rafael Martí, 2005. "Context-Independent Scatter and Tabu Search for Permutation Problems," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 111-122, February.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Gregorio Curello & Ludvig Sinander, 2020. "Agenda-manipulation in ranking," Papers 2001.11341, arXiv.org, revised Sep 2022.
    2. Haruki Kono & Kota Saito & Alec Sandroni, 2023. "Axiomatization of Random Utility Model with Unobservable Alternatives," Papers 2302.03913, arXiv.org, revised Aug 2023.
    3. Olivier Hudry & Bernard Monjardet, 2010. "Consensus theories: An oriented survey," Documents de travail du Centre d'Economie de la Sorbonne 10057, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    4. Hudry, Olivier, 2012. "On the computation of median linear orders, of median complete preorders and of median weak orders," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 2-10.
    5. 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.
    6. Thierry Denœux & Marie-Hélène Masson, 2012. "Evidential reasoning in large partially ordered sets," Annals of Operations Research, Springer, vol. 195(1), pages 135-161, May.
    7. Olivier Hudry, 2015. "Complexity results for extensions of median orders to different types of remoteness," Annals of Operations Research, Springer, vol. 225(1), pages 111-123, February.
    8. Rajeev Kohli & Khaled Boughanmi & Vikram Kohli, 2019. "Randomized Algorithms for Lexicographic Inference," Operations Research, INFORMS, vol. 67(2), pages 357-375, March.
    9. Jean-Paul Doignon & Kota Saito, 2022. "Adjacencies on random ordering polytopes and flow polytopes," Papers 2207.06925, arXiv.org.
    10. Tiwisina, Johannes & Külpmann, Philipp, 2016. "Probabilistic Transitivity in Sports," Center for Mathematical Economics Working Papers 520, Center for Mathematical Economics, Bielefeld University.
    11. Juan Aparicio & Mercedes Landete & Juan F. Monge, 2020. "A linear ordering problem of sets," Annals of Operations Research, Springer, vol. 288(1), pages 45-64, May.
    12. Gregorio Curello & Ludvig Sinander, 2023. "Agenda-Manipulation in Ranking," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 90(4), pages 1865-1892.
    13. Labbé, Martine & Landete, Mercedes & Monge, Juan F., 2023. "Bilevel integer linear models for ranking items and sets," Operations Research Perspectives, Elsevier, vol. 10(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Olivier Hudry & Bernard Monjardet, 2010. "Consensus theories: An oriented survey," Documents de travail du Centre d'Economie de la Sorbonne 10057, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    2. Olivier Hudry, 2015. "Complexity results for extensions of median orders to different types of remoteness," Annals of Operations Research, Springer, vol. 225(1), pages 111-123, February.
    3. De Donder, Philippe & Le Breton, Michel & Truchon, Michel, 2000. "Choosing from a weighted tournament1," Mathematical Social Sciences, Elsevier, vol. 40(1), pages 85-109, July.
    4. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    5. Scott Moser, 2015. "Majority rule and tournament solutions," Chapters, in: Jac C. Heckelman & Nicholas R. Miller (ed.), Handbook of Social Choice and Voting, chapter 6, pages 83-101, Edward Elgar Publishing.
    6. Hudry, Olivier, 2010. "On the complexity of Slater's problems," European Journal of Operational Research, Elsevier, vol. 203(1), pages 216-221, May.
    7. Hudry, Olivier, 2012. "On the computation of median linear orders, of median complete preorders and of median weak orders," Mathematical Social Sciences, Elsevier, vol. 64(1), pages 2-10.
    8. Brandt, Felix & Harrenstein, Paul & Seedig, Hans Georg, 2017. "Minimal extending sets in tournaments," Mathematical Social Sciences, Elsevier, vol. 87(C), pages 55-63.
    9. Vincent Anesi, 2012. "A new old solution for weak tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(4), pages 919-930, October.
    10. 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.
    11. Laffond G. & Laslier, J. F. & Le Breton, M., 1996. "Condorcet choice correspondences: A set-theoretical comparison," Mathematical Social Sciences, Elsevier, vol. 31(1), pages 59-59, February.
    12. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
    13. Felix Brandt & Markus Brill & Hans Georg Seedig & Warut Suksompong, 2018. "On the structure of stable tournament solutions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(2), pages 483-507, March.
    14. Aleksei Y. Kondratev & Vladimir V. Mazalov, 2020. "Tournament solutions based on cooperative game theory," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 119-145, March.
    15. Burak Can & Mohsen Pourpouneh & Ton Storcken, 2021. "An axiomatic characterization of the Slater rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 56(4), pages 835-853, May.
    16. Vincent Anesi, 2012. "A new old solution for weak tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(4), pages 919-930, October.
    17. Bernard Monjardet & Jean-Pierre Barthélemy & Olivier Hudry & Bruno Leclerc, 2009. "Metric and latticial medians," Post-Print halshs-00408174, HAL.
    18. Michael J. Brusco & Douglas Steinley & Ashley L. Watts, 2022. "Disentangling relationships in symptom networks using matrix permutation methods," Psychometrika, Springer;The Psychometric Society, vol. 87(1), pages 133-155, March.
    19. W. Art Chaovalitwongse & Carlos A. S. Oliveira & Bruno Chiarini & Panos M. Pardalos & Mauricio G. C. Resende, 2011. "Revised GRASP with path-relinking for the linear ordering problem," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 572-593, November.
    20. Brandt, Felix, 2011. "Minimal stable sets in tournaments," Journal of Economic Theory, Elsevier, vol. 146(4), pages 1481-1499, July.

    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:spr:annopr:v:175:y:2010:i:1:p:107-158:10.1007/s10479-009-0648-7. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.