挑战冠军比赛中行贿的参数化分析
原文中文，约1400字，阅读约需4分钟。
📝
内容提要
本文研究了投票系统中贿赂问题的计算复杂度，特别是Shift Bribery和Swap Bribery。研究表明，贿赂问题的复杂度与选民和候选人数量、成本函数等因素密切相关，某些情况下可用多项式时间解决，而更一般化的情况则为NP困难。不同投票规则下的贿赂复杂性也有所不同。
❓
Q&A
Shift Bribery问题的计算复杂度如何？
Shift Bribery问题的复杂度与选民和候选人数量、成本函数等因素密切相关，某些情况下可用多项式时间解决，而更一般化的情况则为NP困难。
在不同投票规则下，贿选的复杂性有什么不同？
不同投票规则下的贿选复杂性有所不同，例如在Borda、Maximin和Copeland算法下，贿选问题的复杂度表现各异。
以预算为参数时，Shift Bribery问题的解决情况如何？
以预算为参数时，Shift Bribery问题的解决情况依赖于价格函数，通常在选民数量为参数时可解，但候选人数量为参数时则更复杂。
Swap Bribery的k-approval情况有什么特点？
在Swap Bribery的k-approval情况下，某些特定情况可以用多项式时间解决，而更一般化的情况则为NP困难。
贿选复杂度与选举方式有什么关系？
贿选复杂度与具体的选举方式密切相关，同一类选举方式中，贿选复杂度可能是NP完全的，而设定个人贿选门槛的选民则为P。
如何研究选票操作模型对贿选问题的影响？
通过提出统一框架研究选票操作模型，发现选票规则的复杂性对贿选问题的难度有显著影响。
🏷️
