Strategy Proof Mechanisms for Facility Location with Capacity Limits
This addresses facility location problems with capacity limits, which are common in real-world applications, and provides incremental insights into mechanism design under constraints.
The paper tackles the problem of designing strategy-proof mechanisms for facility location with capacity constraints, showing that while capacity limits make strategy-proof design harder, they can paradoxically improve approximation guarantees for the optimal solution.
An important feature of many real world facility location problems are capacity limits on the facilities. We show here how capacity constraints make it harder to design strategy proof mechanisms for facility location, but counter-intuitively can improve the guarantees on how well we can approximate the optimal solution.