An ABC-Problem for Location and Consensus Functions on Graphs

__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.