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.

consensus axiom, consensus function, location function, median, median function, median graph
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