An $ABC$-Problem for location and consensus on graphs

Martyn Mulder
Econometrisch Instituut, Erasmus Universiteit

F.R. McMorris
IIT Chicago, and University of Louisville

Beth Novick
Clemson University

R.C. Powers
University of Louisville



Content: In social choice theory the process of achieving consensus can be modeled by a function $L$ on the set of all finite sequences of vertices of a graph. It returns a nonempty subset of vertices. To guarantee rationality of the process {\em consensus axioms} are imposed on $L$. Three such axioms are Anonymity, Betweenness and Consistency. Functions satisfying these three axioms are called $ABC$-functions. The median function $Med$ on a connected graph returns the set of vertices minimizing the distance sum to the elements of the input sequence. It is a prime example of an $ABC$-function. Recently Mulder \& Novick proved that on median graphs $Med$ is the unique function $ABC$-function. This inspired the {\em $ABC$-Problem} for location and consensus on graphs: $(i)$ On what other classes of graphs is $Med$ the unique $ABC$-function? $(ii)$ If on class $\mathcal{G}$ there are other $ABC$-functions besides $Med$, which additional axioms still characterize $Med$? $(iii)$ Find on $\mathcal{G}$ the other $ABC$-functions, and possibly characterize these. In this talk we present first non-trivial results for this $ABC$-Problem. Moreover we present some interesting voting procedures on $n$ alternatives.

Back to all abstracts