2019/11/21 by Haris Aziz, Aziz, Haris, Hau Chan +7 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Voting Systems #Optimization and Search Problems #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.1911.09813
openalex publication_date 2019/11/21 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We consider the facility location problem in the one-dimensional setting\nwhere each facility can serve a limited number of agents from the algorithmic\nand mechanism design perspectives. From the algorithmic perspective, we prove\nthat the corresponding optimization problem, where the goal is to locate\nfacilities to minimize either the total cost to all agents or the maximum cost\nof any agent is NP-hard. However, we show that the problem is fixed-parameter\ntractable, and the optimal solution can be computed in polynomial time whenever\nthe number of facilities is bounded, or when all facilities have identical\ncapacities. We then consider the problem from a mechanism design perspective\nwhere the agents are strategic and need not reveal their true locations. We\nshow that several natural mechanisms studied in the uncapacitated setting\neither lose strategyproofness or a bound on the solution quality for the total\nor maximum cost objective. We then propose new mechanisms that are\nstrategyproof and achieve approximation guarantees that almost match the lower\nbounds.\n