An ABC-Problem for Location and Consensus Functions on Graphs

F.R. McMorris, Beth Novick, Martyn Mulder and Robert Powers

No EI 2015-16, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

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.

Keywords: median function; location function; consensus function; voting; consensus; axiom; ABC-problem (search for similar items in EconPapers)
Pages: 26
Date: 2015-06-08
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/78320/EI2015-16.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:78320

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).