We consider a social choice setting with agents that are partitioned into disjoint groups, and have metric preferences over a set of alternatives. Our goal is to choose a single alternative aiming to optimize various objectives that are functions of the distances between agents and alternatives in the metric space, under the constraint that this choice must be made in a distributed way: The preferences of the agents within each group are first aggregated into a representative alternative for the group, and then these group representatives are aggregated into the final winner. Deciding the winner in such a way naturally leads to loss of efficiency, even when complete information about the metric space is available. We provide a series of (mostly tight) bounds on the distortion of distributed mechanisms for variations of well-known objectives, such as the (average) total cost and the maximum cost, and also for new objectives that are particularly appropriate for this distributed setting and have not been studied before.


翻译:我们考虑一种社会选择环境,由被分割成不相连的团体的代理商组成,并且对一套替代物享有基本偏好。我们的目标是选择一种单一的替代物,目的是优化各种目标,这些目标是代理人与替代物在计量空间的距离功能,但这种选择必须以分配方式作出:每个集团内的代理商的偏好首先归为集团的有代表性的替代物,然后将这些集团代表合并为最后的赢家。决定胜者的方式自然会导致效率的丧失,即使有关于计量空间的完整信息。我们提供一系列(最紧凑的)界限,说明如何扭曲分配的机制,以改变众所周知的目标,例如(平均)总成本和最大成本,以及对于特别适合这一分布环境而且以前未曾研究过的新目标。

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
专知会员服务
17+阅读 · 2020年9月6日
【机器学习术语宝典】机器学习中英文术语表
专知会员服务
59+阅读 · 2020年7月12日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年9月9日
Arxiv
45+阅读 · 2019年12月20日
A Graph Auto-Encoder for Attributed Network Embedding
Arxiv
4+阅读 · 2019年1月14日
Arxiv
5+阅读 · 2018年5月31日
Arxiv
4+阅读 · 2018年1月15日
Arxiv
3+阅读 · 2017年5月14日
VIP会员
相关VIP内容
专知会员服务
17+阅读 · 2020年9月6日
【机器学习术语宝典】机器学习中英文术语表
专知会员服务
59+阅读 · 2020年7月12日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年9月9日
Arxiv
45+阅读 · 2019年12月20日
A Graph Auto-Encoder for Attributed Network Embedding
Arxiv
4+阅读 · 2019年1月14日
Arxiv
5+阅读 · 2018年5月31日
Arxiv
4+阅读 · 2018年1月15日
Arxiv
3+阅读 · 2017年5月14日
Top
微信扫码咨询专知VIP会员