We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e.g., median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF) . We consider two IIF objectives and provide mechanisms with tight approximation ratios.
翻译:我们研究的是代理商所在的设施地点问题,即代理商位于实线上,并按族裔或年龄等标准分成若干组。我们的目的是设计一些机制,确定一个设施的位置,以便大致将代理商群体的费用公平降低到设施的成本,同时诚实地了解代理商所在地点。我们首先探讨各种动机良好的集团公平成本目标,并表明许多自然目标具有无限制的近似比率。我们然后考虑尽量减少最大的集团总成本,并尽量减少平均集团成本目标。关于这些目标,我们表明现有的传统机制(例如中位数)和新的集团机制提供了约束性近似比率,使集团机制能够达到更好的比率。我们还为这两个目标提供了较低的界限。为了衡量集团之间和集团内部的公平性,我们研究一个新的集团间和集团内部公平性概念。我们考虑两个综合投资框架目标,并提供具有紧凑近似比率的机制。我们考虑两个目标,并提出了一个比较紧凑近似比率的机制。