|Consensus Functions on Graphs: The case of Center and Median Functions|
|Department of Futures Studies, University of Kerala|
|Digital Media Center 1034
December 13, 2018 - 03:30 pm
Consensus is a process of arriving at agreement among a group in which the input of every individual member is carefully considered and a final outcome is obtained based on the needs of the group. So the process of arriving consensus among a group is elaborated in consensus theory. It involves good mathematics that is exciting and has wide applications. A consensus function is a model to describe a rational way to obtain consensus among a group of agents. Input of the function consists of some data about the agents and the output deals with issuing a data about which consensus should be reached. Mathematically, an arbitrary consensus function can be defined on a non-empty set X which returns for every sequence say of elements of X a non-empty subset of X. Rationality of the process of obtaining consensus is guaranteed by certain “rational” rules or “consensus axioms” that are imposed on the consensus function.
A consensus function can be defined on a metric space which returns the suitable consensus outcome for a set of clients using some criteria which depends upon the service facility. Here the clients and the service facilities can be considered as points in the metric space.
The center and median are prime examples of finding an optimal location with respect to certain distance criteria. Given the locations of a set of clients in a graph or network, the center consists of the vertices that minimize the maximum distance to the clients. The median consists of the vertices that minimize the average distance to the clients, which is equivalent to minimizing the distance sum to the clients. Median/center function is a consensus function which returns the median/center of a set of clients. Median function is studied on graphs and semilattices; well-studied on graphs. Median function satisfies the following three basic and natural axioms on any connected graph: anonymity, betweenness and consistency. Anonymity simply says that output does not depend on the ordering of the elements in the profile. In this talk, we give a brief survey on some recent results on the median and center functions on graphs by comparing these two consensus functions.