A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric.

This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading 1-median problem in the plane with Manhattan metric and implies an $\mathcal {O}(n\log^{2}n)$ time algorithm for this problem. [ABSTRACT FROM AUTHOR]