Strategy Proof Mechanisms for Facility Location with Capacity Limits

2020/09/17 by Toby Walsh, Walsh, Toby
Economics, Econometrics and Finance · Decision Sciences · Computer Science · #Game Theory and Voting Systems #Auction Theory and Applications #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2009.07986

Abstract

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.

Related

• Facility Location Problem with Capacity Constraints: Algorithmic and\n Mechanism Design Perspectives
• Strategy Proof Mechanisms for Facility Location at Limited Locations
• Facility Location Problems with Capacity Constraints: Two Facilities and Beyond
• Mechanism Design for Facility Location using Predictions
• Constant-Approximate and Constant-Strategyproof Two-Facility Location