设计公平的设施选址机制，平衡个体利益与整体效率。
Equitable Mechanism Design for Facility Location
- 用互补吉尼指数衡量公平性，避免策略性操纵
- 证明任何公平机制都无法保证最优公平性的近似比
- 对比确定性和随机机制在纳什福利上的表现
我们研究策略无关的设施选址机制，以最大化代理间的公平性。如文献常见做法，采用吉尼指数衡量公平性。首先证明一个基础不可能性结果：任何策略无关机制都无法对一个或多个设施的最优效用吉尼指数近似比进行上界约束。因此，我们转而计算效用互补吉尼指数的近似比，并分析确定性和随机机制在此指标上的表现。此外，由于纳什福利常被视为平等与功利之间的公平折衷，我们进一步考察机制在近似纳什福利方面的表现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。