Location Functions on Trees and Beyond: A Short Survey and Some Recent Results

Let G =(V,E) be a finite connected graph and π a k-tuple in V. Think of k customers, each one reporting a most preferred vertex. Location and consensus theory often involves finding the set of vertices x, for which D(x,π) is minimum, where D(x,π) is some measure of the "remoteness" of x to π. Finding these vertices is thus an optimization problem, and the OR folks have produced many nice algorithmic approaches. But what properties does an exact algorithm have when considered abstractly as a function? Perhaps some counterintuitive things are going on—or perhaps not, and the function can be shown to satisfy a list of desired axioms. A function that returns, for any π, the set of vertices minimizing D is called a (distance-based) location function and the problem of characterizing various functions of this type has been a challenge for more than 25 years. In this talk a survey of some old and new results is presented, while focusing on the case where G is a tree or, more generally, a median graph. I will discuss functions based on three examples of D that are popular in the location theory literature. If time and interest permits, I will also discuss some recent results on the notion of "strategy-proof" location functions, which are those for which it is impossible for any customer "j" to favorably manipulate the results by reporting vertices that are sub-optimal from "j's" point-of-view.

Event Topic

Discrete Applied Math Seminar