Junta distributions and the average-case complexity of manipulating elections Export

@article{Procaccia2006Junta, abstract = {Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used N P-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that N P-hard manipulations may be tractable in the averagecase. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant. 1.}, author = {Procaccia, Ariel D. and Rosenschein, Jeffrey S.}, booktitle = {Journal of Artificial Intelligence Research}, citeulike-article-id = {5373461}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.8377}, citeulike-linkout-1 = {http://www.aaai.org/Papers/JAIR/Vol28/JAIR-2805.pdf}, keywords = {manipulation, voting}, pages = {497--504}, posted-at = {2009-08-05 17:56:49}, priority = {2}, title = {Junta distributions and the average-case complexity of manipulating elections}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.8377}, volume = {28}, year = {2006} }

TY - JOUR ID - Procaccia2006Junta L3 - citeulike-article-id:5373461 N2 - Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used N P-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that N P-hard manipulations may be tractable in the averagecase. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant. 1. EP - 504 TI - Junta distributions and the average-case complexity of manipulating elections VL - 28 T2 - Journal of Artificial Intelligence Research SP - 497 KW - manipulation KW - voting AU - Procaccia, Ariel AU - Rosenschein, Jeffrey PY - 2006/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.8377 ER -