In liquid democracy, each voter either votes herself or delegates her vote to some other voter. This gives rise to what is called a delegation graph. To decide the voters who eventually votes along with the subset of voters whose votes they give, we need to resolve the cycles in the delegation graph. This gives rise to the Resolve Delegation problem where we need to find an acyclic sub-graph of the delegation graph such that the number of voters whose votes they give is bounded above by some integer {\lambda}. Putting a cap on the number of voters whose votes a voter gives enable the system designer restrict the power of any individual voter. The Resolve Delegation problem is already known to be NP-hard. In this paper we study the parameterized complexity of this problem. We show that Resolve Delegation is para-NP-hard with respect to parameters {\lambda}, number of sink nodes and the maximum degree of the delegation graph. We also show that Resolve Delegation is W[1]-hard even with respect to the treewidth of the delegation graph. We complement our negative results by exhibiting FPT algorithms with respect to some other parameters. We finally show that a related problem, which we call Resolve Fractional Delegation, is polynomial time solvable.


翻译:在液态民主中,每个选民要么自己投票,要么将自己的选票委托给其他选民。这产生了一个称为代表团图的图表。为了决定最终投票的选民以及他们投票的一组选民,我们需要在代表团图中解决周期问题。这产生了解决代表团问题,我们需要在代表团图中找到一个循环的子图,这样,他们投票的选民人数就受到某种整数的 lambda 的制约。对选民投票使系统设计者能够限制任何个人选民权力的选民人数设定一个上限。解决代表团的问题已经众所周知是NP-硬的。我们在这份文件中研究这一问题的参数复杂性。我们表明,解决代表团对于参数 lambda 、 汇点数和代表团图的最大程度来说,是PNP 硬的。我们还表明,即使代表团的票数与代表团图的树枝节有关,但解代表团的票数也是W[1]硬的。我们用其他参数来补充我们的负面结果,我们用FPT算法来显示其他参数。我们最后展示了一个相关的代表团。我们决心是巨大的问题。

0
下载
关闭预览

相关内容

专知会员服务
107+阅读 · 2020年12月21日
专知会员服务
19+阅读 · 2020年12月11日
【ECCV2020】OCRNet化解语义分割上下文信息缺失难题
专知会员服务
16+阅读 · 2020年8月24日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
已删除
将门创投
12+阅读 · 2018年6月25日
Arxiv
0+阅读 · 2021年1月17日
Arxiv
0+阅读 · 2021年1月15日
VIP会员
相关VIP内容
专知会员服务
107+阅读 · 2020年12月21日
专知会员服务
19+阅读 · 2020年12月11日
【ECCV2020】OCRNet化解语义分割上下文信息缺失难题
专知会员服务
16+阅读 · 2020年8月24日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
已删除
将门创投
12+阅读 · 2018年6月25日
Top
微信扫码咨询专知VIP会员