A location function on a finite graph takes a set of most preferred locations (vertices of the graph) for a set of users, and returns a set of locations satisfying conditions meant to please the entire user set as much as possible. A strategy-proof location function is one for which it never benefits a user to report a suboptimal preferred location. We introduce four versions of strategy-proof and prove some preliminary results focusing on two well-known location functions, the median and the center.

Additional Metadata
Keywords Center, Location function, Median, Strategy-proof
Persistent URL dx.doi.org/10.1007/978-1-4939-0742-7_4, hdl.handle.net/1765/104248
Note This paper is dedicated to our friend and colleague Boris Mirkin on the occasion of his 70th birthday
McMorris, F.R, Mulder, H.M, & Roberts, F.S. (Fred S.). (2014). Strategy-proof location functions on finite graphs. In Alekserov, Goldengorin, Pardalos (eds.) Clusters, Orders, and Trees: Methods and Application (Springer Optimization and Its Applications ; 92) (pp. 63–75). doi:10.1007/978-1-4939-0742-7_4