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 O(nlog²n)\mathcal {O}(n\log^{2}n) time algorithm for this problem.