In multiwinner approval voting, the goal is to select $k$-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding 'good' committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.


翻译:在多赢的核准投票中,目标是根据选民的核准选票选择以美元为成员的委员会。在这方面,一个经过充分研究的相称性概念是合理的代表制(JR)xiom,它要求没有大批具有凝聚力的选民群体仍然无人任职。然而,JRxiom可能与其他偏差发生冲突,如覆盖范围(使至少一名委员会成员获得核准的选民人数最大化)或社会福利(使委员会成员获得的核准数目最大化)。在这项工作中,我们调查了将JRxiom(以及要求更高的EJRxiom)强加于社会福利和覆盖的影响。我们的方法有三重:我们从最坏的案例中找出因强制实施JR而造成的福利/覆盖损失,研究找到提供JR的“良好”委员会的计算复杂性(取得硬性结果、近似算法和一维偏好的确切算法),并研究这一对若干合成数据集的经验设定。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
Google最新《机器学习对偶性》报告,48页ppt
专知会员服务
35+阅读 · 2020年11月29日
专知会员服务
60+阅读 · 2020年3月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
专知会员服务
53+阅读 · 2019年12月22日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2022年2月15日
Arxiv
0+阅读 · 2022年2月14日
Arxiv
0+阅读 · 2022年2月11日
VIP会员
相关VIP内容
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
Google最新《机器学习对偶性》报告,48页ppt
专知会员服务
35+阅读 · 2020年11月29日
专知会员服务
60+阅读 · 2020年3月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
专知会员服务
53+阅读 · 2019年12月22日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员