How bad can a voting locating be (Q1082239)

The problem is to locate a single facility on a network. Users, located on the network, wish to have the facility as close as possible to their respective locations. Hence preferences over the set of potential locations are determined by the distances of users. Two solution concepts are discussed. The first one, Weber points, minimizes the average distance from users to the facility. The second one, proposed by Simpson (1969), is based on voting. A Simpson point s minimizes the maximum number of users preferring some alternative location x to s. The maximum percentage of voters \(\rho\) (s) rejecting s is a measure of stability or objectionability. If \(\rho\) (s)\(\leq 1/2\) then s is a Condorcet point. A value close to one indicates a high degree of circular voting. The paper extends to Simpson points the line of research developed by \textit{P. Hansen} and \textit{J.-F. Thisse} [in: Operational Research '81, Proc. 9th IFORS int. Conf., Hamburg 1981, 569-577 (1981; Zbl 0473.90030)], \textit{H. J. Bandelt} [Eur. J. Oper. Res. 20, 314-326 (1985; Zbl 0564.90011)] and \textit{M. Labbé} [ibid. 20, 299-313 (1985; Zbl 0567.90022)] for Condorcet points. A major result is on generalized cacti. It is shown for cacti that the maximal relative rejection of a Simpson point never exceeds 2/3. Furthermore, the average distance of users to a Simpson point is at most twice the optimal value (attained for Weber points). The respective values are extreme unfavourable if general networks are considered. E.g. for badly behaved graphs \(\rho (x)=1-(1/n)\) can be obtained for all locations x. Here, n denotes the number of users. Furthermore, the average distance of users to a Simpson point can reach (n-1) times the optimal value (attained for Weber points). The paper closes with some open problems.