[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/hal/cesptp/halshs-00408174.html
   My bibliography  Save this paper

Metric and latticial medians

Author

Listed:
  • Bernard Monjardet

    (CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique)

  • Jean-Pierre Barthélemy

    (LUSSI - Département Logique des Usages, Sciences sociales et Sciences de l'Information - UEB - Université européenne de Bretagne - European University of Brittany - Télécom Bretagne - IMT - Institut Mines-Télécom [Paris])

  • Olivier Hudry

    (TSP - INF - Département Informatique - IMT - Institut Mines-Télécom [Paris] - TSP - Télécom SudParis)

  • Bruno Leclerc

    (CAMS - Centre d'Analyse et de Mathématique sociales - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique)

Abstract
This paper presents the -linked- notions of metric and latticial medians and it explains what is the median procedure for the consensus problems, in particular in the case of the aggregation of linear orders. First we consider the medians of a v-tuple of arbitrary or particular binary relations.. Then we study in depth the difficult (in fact NP-difficult) problem of finding the median orders of a profile of linear orders. More generally, we consider the medians of v-tuples of elements of a semilattice and we describe the median semilattices, i.e. the semilattices were medians are easily computable.

Suggested Citation

  • 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.
    • Handle: RePEc:hal:cesptp:halshs-00408174
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00408174v1
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-00408174v1/document
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. 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.
    2. Barnett,William A. & Moulin,Hervé & Salles,Maurice & Schofield,Norman J. (ed.), 1995. "Social Choice, Welfare, and Ethics," Cambridge Books, Cambridge University Press, number 9780521443401, September.
    3. 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.
    4. Fuad Aleskerov & Denis Bouyssou & Bernard Monjardet, 2007. "Utility Maximization, Choice and Preference," Springer Books, Springer, edition 0, number 978-3-540-34183-3, January.
    5. Bernard Monjardet & Vololonirina Raderanirina, 2004. "Lattices of choice functions and consensus problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(3), pages 349-382, December.
    6. 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.
    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. Daniel Eckert & Bernard Monjardet, 2009. "Guilbaud's Theorem : An early contribution to judgment aggregation," Post-Print halshs-00404185, HAL.
    2. Ernesto Savaglio & Stefano Vannucci, 2022. "Strategy-proof aggregation rules in median semilattices with applications to preference aggregation," Papers 2208.12732, arXiv.org.
    3. 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.
    4. 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.

    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 & Bruno Leclerc & Bernard Monjardet & Jean-Pierre Barthélemy, 2004. "Médianes métriques et latticielles," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-03322636, HAL.
    2. 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.
    3. Bernard Monjardet & Vololonirina Raderanirina, 2004. "Lattices of choice functions and consensus problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(3), pages 349-382, December.
    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. Ernesto Savaglio & Stefano Vannucci, 2021. "Strategy-Proof Aggregation Rules in Median Semilattices with Applications to Preference Aggregation," Department of Economics University of Siena 867, Department of Economics, University of Siena.
    6. 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.
    7. Ernesto Savaglio & Stefano Vannucci, 2022. "Strategy-proof aggregation rules in median semilattices with applications to preference aggregation," Papers 2208.12732, arXiv.org.
    8. Monjardet, Bernard, 2003. "The presence of lattice theory in discrete problems of mathematical social sciences. Why," Mathematical Social Sciences, Elsevier, vol. 46(2), pages 103-144, October.
    9. Dirk Van de gaer & Michel Martinez & Erik Schokkaert, 1998. "Measuring Intergenerational Mobility and Equality of Opportunity," Working Papers of Department of Economics, Leuven ces9810, KU Leuven, Faculty of Economics and Business (FEB), Department of Economics, Leuven.
    10. Stefan Ambec & Yann Kervinio, 2016. "Cooperative decision-making for the provision of a locally undesirable facility," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(1), pages 119-155, January.
    11. Barnett, William A. & Serletis, Apostolos, 2008. "Consumer preferences and demand systems," Journal of Econometrics, Elsevier, vol. 147(2), pages 210-224, December.
    12. 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.
    13. Effrosyni Diamantoudi, 2003. "Equilibrium binding agreements under diverse behavioral assumptions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 22(2), pages 431-446, September.
    14. Boniface Mbih & Issofa Moyouwou & Jérémy Picot, 2008. "Pareto violations of parliamentary voting systems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 34(2), pages 331-358, February.
    15. Truchon, Michel, 1998. "Figure Skating and the Theory of Social Choice," Cahiers de recherche 9814, Université Laval - Département d'économique.
    16. Schwartz, Thomas, 2014. "Choice functions and bounded rationality," Mathematical Social Sciences, Elsevier, vol. 68(C), pages 14-18.
    17. Bernard Monjardet, 2005. "Modèles ordinaux de préférences," Cahiers de la Maison des Sciences Economiques b05097, Université Panthéon-Sorbonne (Paris 1).
    18. Ngo Long & Vincent Martinet, 2018. "Combining rights and welfarism: a new approach to intertemporal evaluation of social alternatives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 35-64, January.
    19. Ehlers, Lars & Klaus, Bettina, 2016. "Object allocation via deferred-acceptance: Strategy-proofness and comparative statics," Games and Economic Behavior, Elsevier, vol. 97(C), pages 128-146.
    20. Juan P. Aguilera & Levent Ülkü, 2017. "On the maximization of menu-dependent interval orders," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 357-366, February.

    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:hal:cesptp:halshs-00408174. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.