|
| 简单规则下Vote Control问题的复杂性分析 |
| The complexity of Vote Control problem under simple rules |
| |
| DOI： |
| 中文关键词: Vote Control问题 复杂性 得分规则 |
| 英文关键词: Vote Control problem complexity scoring rule |
| 基金项目:河南省科技攻关项目(122102310442) |
|
| 摘要点击次数: 2393 |
| 全文下载次数: 137 |
| 中文摘要: |
| 给定候选人集合C,投票集合V=(v1,v2,…,vn)和候选人c∈C,是否存在V的子集V′,|V′|≤k,使得c∈r(V＼V′).该问题在不同的得分规则下复杂性是不同的.在plurality规则的基础上证明了Reto规则下Vote Control问题是多项式时间可解的,并给出了k′-approval规则下该问题是NP-Complete的证明. |
| 英文摘要: |
| Given a set of candidatesC, a profile of partial votesV=(v1,v2,…,vn), and a distinguished candidatec∈C,is there a subset V′,|V′|≤k such that c∈r(V＼V′). The complexity of this problem is different under different scoring rules. The vote control problem was proved under Reto rule can be solved in polynomial time based on plurality rule, the NP-Complete proof of vote control problem underk′-approval rule was also obtained. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
