Strategy-proof location on a network (Q697960)

A problem of location on a graph is considered. The preferences of agents are supposed single-peaked and inversely related to distances from a most prefered point on the graph. A social choice rule is a function mapping the lists of agents' peaks into points on the graph. The strategy proof rules are considered, i.e. it is assumed that an agent can not manipulate the choice by misreporting his preferences to it. If the graph is a tree, then the class of strategy-proof, onto rules are proved to be extended medium voter schemes. If however the graph contains at least one cycle, the class of strategy proof, onto rules grant some agent an amount of decision power. The results for cyclic graphs are partially negative and partially positive: one agent acts as a dictator on or between all cycles on the graph, but excercises more limited power on the other parts of the graph.