The Majority Strategy for finding medians of a set of clients on a graph can be relaxed in the following way: if we are at v, then we move to a neighbor w if there are at least as many clients closer to w than to v (thus ignoring the clients at equal distance from v and w). The graphs on which this Plurality Strategy always finds the set of all medians are precisely those for which the set of medians induces always a connected subgraph.

, , , ,
Econometric Institute Research Papers
Report / Econometric Institute, Erasmus University Rotterdam
Erasmus School of Economics

Balakrishnan, K., Changat, M., & Mulder, M. (2006). The plurality strategy on graphs (No. EI 2006-35). Report / Econometric Institute, Erasmus University Rotterdam. Retrieved from