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 𝒪(n log²n) time algorithm for this problem.