For each of the seven general electoral control type collapses found by Hemaspaandra, Hemaspaandra, and Menton [HHM20] and each of the additional electoral control type collapses of Carleton et al. [CCH+22] for veto and approval (and many other election systems in light of that paper's Theorems 3.6 and 3.9), the collapsing types obviously have the same complexity since as sets they *are* the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [HHM20] and Carleton et al. [CCH+22] we prove that the pair's members' complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. We also, for the concrete systems plurality, veto, and approval completely determine which of those polynomially-related search-problem pairs are polynomial-time computable and which are NP-hard.


翻译:对于Hemaspaandra、Hemaspaandra和Menton[HHM20]所发现的七种大选控制类型的崩溃,以及Carleton等人[CCH+22][CCH+22]为否决和批准(以及根据该文件的Theorems 3.6和3.9,许多其他选举制度)所发现的另外一种选举控制类型的崩溃,这些崩溃类型显然都具有相同的复杂性,因为它们是同一组的。然而,具有同样的复杂性(与组一样)不足以保证与搜索问题同样复杂。在本文中,我们探讨了倒闭配对的搜索版本之间的关系。对于Hemaspaandra、Hmaspaandra、Menton[HHMHM20]和Carleton等人的每对倒闭配对来说,我们证明夫妻成员的复杂性是多式的(如果赢家问题本身不是多式的,那么连锁的,那么赢家问题就是一个或错的问题。此外,我们从一个解决方案到一个彻底的压式的削减,我们决定了这些和多式的系统。

0
下载
关闭预览

相关内容

专知会员服务
39+阅读 · 2020年9月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年8月26日
Neural Architecture Search without Training
Arxiv
10+阅读 · 2021年6月11日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员