IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/78320.html
   My bibliography  Save this paper

An ABC-Problem for Location and Consensus Functions on Graphs

Author

Listed:
  • McMorris, F.R.
  • Novick, B.
  • Mulder, H.M.
  • Powers, R.C.

Abstract

__Abstract__ A location problem can often be phrased as a consensus problem or a voting problem. We use these three perspectives, namely location, consensus and voting to initiate the study of several questions. The median function Med is a location/consensus function on a connected graph G that has the finite sequences of vertices of G as input. For each such sequence, Med returns the set of vertices that minimize the distance sum to the elements of the sequence. The median function satisfies three intuitively clear axioms: (A) Anonymity, (B) Betweenness and (C) Consistency. In [13] it was shown that on median graphs these three axioms actually characterize Med. This result raises a number of questions: (i) On what other classes of graphs is Med characterized by (A), (B) and (C)? (ii) If some class of graphs has other ABC-functions besides Med, then determine additional axioms that are needed to characterize Med. (iii) In the latter case, can we find characterizations of other functions that satisfy (A), (B) and (C)? We call these questions, and related questions, the ABC-Problem for location/consensus functions on graphs. In this paper we present first results. For the first question we use consensus terminology. We construct a non-trivial class different from the median graphs, on which the median function is the unique “ABC function”. For the second and third question voting terminology is most apt for our approach. On K_n with n > 2 we construct various non-trivial ABC-voting procedures. For some nice families, we present a full axiomatic characterization. We also construct an infinite family of ABC-functions on K_3.

Suggested Citation

  • McMorris, F.R. & Novick, B. & Mulder, H.M. & Powers, R.C., 2015. "An ABC-Problem for Location and Consensus Functions on Graphs," Econometric Institute Research Papers EI 2015-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
  • Handle: RePEc:ems:eureir:78320
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/78320/EI2015-16.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ron Holzman, 1990. "An Axiomatic Approach to Location on Networks," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 553-563, August.
    2. Roberts, Fred S., 1991. "Characterizations of the plurality function," Mathematical Social Sciences, Elsevier, vol. 21(2), pages 101-127, April.
    3. Vohra, Rakesh, 1996. "An axiomatic characterization of some locations in trees," European Journal of Operational Research, Elsevier, vol. 90(1), pages 78-84, April.
    4. McMorris, F.R. & Mulder, H.M. & Ortega, O., 2010. "Axiomatic Characterization of the Mean Function on Trees," Econometric Institute Research Papers EI 2010-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    6. McMorris, F.R. & Mulder, H.M. & Novick, B. & Powers, R.C., 2014. "Five axioms for location functions on median graphs," Econometric Institute Research Papers EI 2014-10, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. 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.
    Full references (including those not matched with items on IDEAS)

    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. McMorris, F.R. & Mulder, H.M. & Novick, B. & Powers, R.C., 2014. "Five axioms for location functions on median graphs," Econometric Institute Research Papers EI 2014-10, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. McMorris, F.R. & Mulder, H.M. & Ortega, O., 2010. "Axiomatic Characterization of the Mean Function on Trees," Econometric Institute Research Papers EI 2010-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Changat, M. & Lekha, D.S. & Mulder, H.M. & Subhamathi, A.R., 2014. "Axiomatic Characterization of the Median and Antimedian Functions on Cocktail-Party Graphs and Complete Graphs," Econometric Institute Research Papers EI 2014-31, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Changat, M. & Lekha, D.S. & Mohandas, S. & Mulder, H.M. & Subhamathi, A.R., 2015. "Axiomatic Characterization of the Median and Antimedian Function on a Complete Graph minus a Matching," Econometric Institute Research Papers EI2015-17, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    5. Mulder, H.M. & Novick, B., 2011. "A simple axiomatization of the median procedure on median graphs," Econometric Institute Research Papers EI2011-25, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    6. McMorris, F.R. & Mulder, Henry Martyn & Novick, Beth & Powers, Robert C., 2021. "Majority rule for profiles of arbitrary length, with an emphasis on the consistency axiom," Mathematical Social Sciences, Elsevier, vol. 109(C), pages 164-174.
    7. Balakrishnan, K. & Changat, M. & Mulder, H.M. & Subhamathi, A.R., 2011. "Axiomatic Characterization of the Antimedian Function on Paths and Hypercubes," Econometric Institute Research Papers EI 2011-08, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Dean P. Foster & Rakesh V. Vohra, 1998. "An Axiomatic Characterization of a Class of Locations in Tree Networks," Operations Research, INFORMS, vol. 46(3), pages 347-354, June.
    9. Mulder, H.M. & Vohra, R.V., 2006. "Axiomatic characterization of the absolute median on cube-free median networks," Econometric Institute Research Papers EI 2006-26, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Masashi Umezawa, 2012. "The replacement principle for the provision of multiple public goods on tree networks," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(2), pages 211-235, February.
    11. Herman Monsuur & Ton Storcken, 2004. "Centers in Connected Undirected Graphs: An Axiomatic Approach," Operations Research, INFORMS, vol. 52(1), pages 54-64, February.
    12. Lombardi, Michele & Yoshihara, Naoki, 2016. "Partially-honest Nash Implementation with Non-connected Honesty Standards," Discussion Paper Series 633, Institute of Economic Research, Hitotsubashi University.
    13. Bock, Hans-Hermann & Day, William H. E. & McMorris, F. R., 1998. "Consensus rules for committee elections," Mathematical Social Sciences, Elsevier, vol. 35(3), pages 219-232, May.
    14. Leo Katz & Alvaro Sandroni, 2020. "Limits on power and rationality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(2), pages 507-521, March.
    15. Thibault Gajdos & John Weymark, 2005. "Multidimensional generalized Gini indices," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(3), pages 471-496, October.
    16. List, Christian & Polak, Ben, 2010. "Introduction to judgment aggregation," Journal of Economic Theory, Elsevier, vol. 145(2), pages 441-466, March.
    17. Guido Bonatti & Enrico Ivaldi, 2016. "Un indicatore per la misurazione della partecipazione culturale e sociale nelle regioni italiane," ECONOMIA E DIRITTO DEL TERZIARIO, FrancoAngeli Editore, vol. 2016(2), pages 283-302.
    18. Reiko Gotoh & Naoki Yoshihara, 2018. "Securing basic well-being for all," Review of Social Economy, Taylor & Francis Journals, vol. 76(4), pages 422-452, October.
    19. Erik Ansink & Hans-Peter Weikard, 2012. "Sequential sharing rules for river sharing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(2), pages 187-210, February.
    20. Hitoshi Matsushima, 2003. "Implementation and Preference for Honesty," CIRJE F-Series CIRJE-F-244, CIRJE, Faculty of Economics, University of Tokyo.

    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:ems:eureir:78320. 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: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.