Approximate Mechanism Design for Facility Location with Multiple Objectives

Author:
Open Access
Publisher website
Google Scholar
Abstract
We identify strategy proof mechanisms for facility location that simultaneously approximate well both the maximum distance from the nearest facility and the minimum utility of any agent. Somewhat surprisingly, while the deterministic MEDIAN and the randomized ENDORAV mechanisms perform optimally with respect to approximating the maximum distance, neither perform optimally with respect to approximating the minimum utility. With deterministic mechanisms for locating a single facility, we prove that the MIDORNEAREST mechanism is optimal with respect to approximating both the maximum distance and the minimum utility. By comparison, the MEDIAN mechanism has an unbounded approximation ratio for approximating the minimum utility. With randomized mechanisms for locating a single facility, we construct the first mechanism that is optimal with respect to approximating the minimum utility. For deterministic and randomized mechanisms locating two or more facilities, we identify strategy proof mechanisms that are within a constant factor of optimal with respect to both objectives.

This publication has 11 references indexed in Scilit: