A Smooth Transition from Powerlessness to Absolute Power
A Smooth Transition from Powerlessness to Absolute Power
复制标题
从无权到绝对权力的平稳过渡
DOI：
10.1613/jair.4125
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Miklós Z. Rácz
中科院分区：
文献类型：
--
作者：
Elchanan Mossel;Ariel D. Procaccia;Miklós Z. Rácz
我们研究了广义评分规则的联合操纵问题的相变。先前已经证明，在选票分布的某些条件下，如果操纵者的数量为 o (√n)，其中 n 是选民的数量，那么随着选民数量趋于无穷大，随机配置文件可被联盟操纵的概率将趋于零，而如果操纵者的数量为 ω(√n)，则随机配置文件可操纵的概率将变为 1。在这里，我们考虑临界窗口，其中联盟的大小为 c√n，并且我们表明，当 c 从零到无穷大时，可操纵的随机分布的极限概率以平滑的方式从零到一，即两个状态之间存在平滑的相变。这一结果在分析上验证了最近的实证结果，并表明在实践中确定联合操纵问题的计算难度可能有限。
We study the phase transition of the coalitional manipulation problem for generalized scoring rules. Previously it has been shown that, under some conditions on the distribution of votes, if the number of manipulators is o (√n), where n is the number of voters, then the probability that a random profile is manipulable by the coalition goes to zero as the number of voters goes to infinity, whereas if the number of manipulators is ω(√n), then the probability that a random profile is manipulable goes to one. Here we consider the critical window, where a coalition has size c√n, and we show that as c goes from zero to infinity, the limiting probability that a random profile is manipulable goes from zero to one in a smooth fashion, i.e., there is a smooth phase transition between the two regimes. This result analytically validates recent empirical results, and suggests that deciding the coalitional manipulation problem may be of limited computational hardness in practice.