2025/06/12 by Toby Walsh, Walsh, Toby · 1 citation
Business, Management and Accounting · 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 #Facility Location and Emergency Management #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2506.10460
openalex publication_date 2025/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider strategy proof mechanisms for facility location which maximize equitability between agents. As is common in the literature, we measure equitability with the Gini index. We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities for one or more facilities. We propose instead computing approximation ratios of the complemented Gini index of utilities, and consider how well both deterministic and randomized mechanisms approximate this. In addition, as Nash welfare is often put forwards as an equitable compromise between egalitarian and utilitarian outcomes, we consider how well mechanisms approximate the Nash welfare.