Strategy Proof Mechanisms for Facility Location with Capacity Limits
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives
We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, …
Strategy Proof Mechanisms for Facility Location at Limited Locations
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 …
PositionMechanism Design With Predictions for Obnoxious Facility Location
We study mechanism design with predictions for the obnoxious facility location problem. We present deterministic strategyproof mechanisms that display tradeoffs between robustness and consistency on segments, squares, ci…
Proportional Fairness in Obnoxious Facility Location
We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairn…
FairnessStrategy Proof Mechanisms for Facility Location in Euclidean and Manhattan Space
We study the impact on mechanisms for facility location of moving from one dimension to two (or more) dimensions and Euclidean or Manhattan distances. We consider three fundamental axiomatic properties: anonymity which i…
Fairness