Strategy Proof Mechanisms for Facility Location at Limited Locations
This addresses a practical limitation in facility location for scenarios like highways or bus stops, but it is incremental as it extends existing theory to constrained settings.
The paper tackled the problem of strategy-proof facility location when facilities are constrained to a limited set of locations, showing that this constraint makes all four performance objectives—total distance, maximum distance, utilitarian welfare, and egalitarian welfare—harder to approximate in general.
Facility location problems often permit facilities to be located at any position. But what if this is not the case in practice? What if facilities can only be located at particular locations like a highway exit or close to a bus stop? We consider here the impact of such constraints on the location of facilities on the performance of strategy proof mechanisms for locating facilities.We study four different performance objectives: the total distance agents must travel to their closest facility, the maximum distance any agent must travel to their closest facility, and the utilitarian and egalitarian welfare.We show that constraining facilities to a limited set of locations makes all four objectives harder to approximate in general.