A profile = (x1, ..., xk), of length k, in a finite connected graph G is a sequence of vertices of G, with repetitions allowed. A median x of is a vertex for which the sum of the distances from x to the vertices in the profile is minimum. The median function finds the set of all medians of a profile. Medians are important in location theory and consensus theory. A median graph is a graph for which every profile of length 3 has a unique median. Median graphs are well studied. They arise in many arenas, and have many applications. We establish a succinct axiomatic characterization of the median procedure on median graphs. This is a simplification of the characterization given by McMorris, Mulder and Roberts [17] in 1998. We show that the median procedure can be characterized on the class of all median graphs with only three simple and intuitively appealing axioms: anonymity, betweenness and consistency. We also extend a key result of the same paper, characterizing the median function for profiles of even length on median graphs.

, , , , ,
Erasmus School of Economics
Econometric Institute Research Papers
Erasmus School of Economics

Mulder, H.M, & Novick, B. (2011). A simple axiomatization of the median procedure on median graphs (No. EI2011-25). Econometric Institute Research Papers. Erasmus School of Economics. Retrieved from http://hdl.handle.net/1765/25628