Motivated by the societal need to provide fair accessibility or representation among groups of agents, we study the group-fair facility location problems where agents are divided into groups based on criteria such as race, gender, or age. The agents are located on a real line, modeling agents' private ideal preferences/points for the facility's location (e.g., a public school or representative). 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' private locations truthfully. We first introduce various well-motivated group-fair cost objectives and show that many natural objectives have an unbounded approximation ratio. We then consider the objectives of minimizing the maximum total group cost and minimizing the average group cost. For the first objective, we show that the approximation ratio of the median mechanism depends on the number of groups and provide a new group-based mechanism with an approximation ratio of 3. For the second objective, the median mechanism obtains a ratio of 3, and we propose a randomized mechanism that obtains a better approximation ratio. We also provide lower bounds for both objectives. We then study the notion of intergroup and intragroup fairness that measures fairness between groups and within each group. We consider various objectives and provide mechanisms with tight approximation ratios.


翻译:基于社会需要提供公平的便利,或代表各种代理人群体,我们研究团体公平设施地点问题,这些代理人根据种族、性别或年龄等标准分成不同的群体;这些代理人位于实实在在的一线,是代理人私人理想偏好/点,是设施所在地(例如公立学校或代表)的样板;我们的目的是设计一些机制,将设施定位于(大约)将代理人群体的费用公平降至最低,同时诚实地引出代理人的私人地点;我们首先提出各种动机良好的集团公平成本目标,并表明许多自然目标都具有不受限制的近似比率;然后我们考虑尽量减少最大集团总成本和尽量减少平均集团成本的目标;关于第一个目标,我们表明中位机制的近似比率取决于群体数目,并提供一个新的集团机制,其近似比率为3;关于第二个目标,中位机制获得3的比例,我们提议一个随机化机制,以获得更好的近似比率;我们还提出许多自然目标都具有不受限制的近似率比率;我们随后考虑尽量减少集团总成本和平均费用的目标;关于每个集团内部公平性的概念,我们考虑各集团和集团内部公平性。

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
【开放书】机器意识,236页pdf
专知会员服务
32+阅读 · 2021年7月13日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
125+阅读 · 2020年6月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年9月17日
Arxiv
0+阅读 · 2021年9月16日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:位置感知的长序列会话推荐
LibRec智能推荐
3+阅读 · 2019年5月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
人工智能 | 国际会议截稿信息9条
Call4Papers
4+阅读 · 2018年3月13日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员