On the complexity of bribery and manipulation in tournaments with uncertain information
On the complexity of bribery and manipulation in tournaments with uncertain information
复制标题
论信息不确定的锦标赛中贿赂和操纵的复杂性
DOI：
10.1016/j.jal.2015.03.004
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Mundhenk
中科院分区：
文献类型：
--
作者：
Nicholas Mattei;J. Goldsmith;A. Klapper;M. Mundhenk
研究了具有不确定信息的体育赛事贿赂和操纵方案的计算复杂度。我们引入了多轮比赛的一般概率模型，并考虑了几种特殊类型的比赛：挑战（或履带式）；杯;还有循环赛。在某些方面，锦标赛类似于连续的双人比赛，杯赛和Copeland的投票规则。贿赂和操纵的复杂性在选举中得到了很好的研究，通常假设有关投票和结果的信息是确定的。我们假设对于锦标赛参与者i和j， i击败j的概率和以固定增量降低每个概率的成本是操纵者已知的。我们对各种类型的比赛中与操纵和贿赂相关的几个问题进行了复杂性分析。复杂性的范围从概率对数空间到NP PP。这表明，在某些情况下，在推理过程中引入不确定性大大增加了贿赂问题的复杂性。
We study the computational complexity of bribery and manipulation schemes for sports tournaments with uncertain information. We introduce a general probabilistic model for multi-round tournaments and consider several special types of tournament: challenge (or caterpillar); cup; and round robin. In some ways, tournaments are similar to the sequential pair-wise, cup and Copeland voting rules. The complexity of bribery and manipulation are well studied for elections, usually assuming deterministic information about votes and results. We assume that for tournament entrants i and j, the probability that i beats j and the costs of lowering each probability by fixed increments are known to the manipulators. We provide complexity analyses for several problems related to manipulation and bribery for the various types of tournaments. Complexities range from probabilistic log space to NP PP. This shows that the introduction of uncertainty into the reasoning process drastically increases the complexity of bribery problems in some instances.