Skip to main content

A smooth transition from powerlessness to absolute power

Author(s): Mossel, E; Procaccia, AD; Racz, Miklos Z

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1p28p
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMossel, E-
dc.contributor.authorProcaccia, AD-
dc.contributor.authorRacz, Miklos Z-
dc.date.accessioned2021-10-11T14:17:58Z-
dc.date.available2021-10-11T14:17:58Z-
dc.date.issued2013-01-01en_US
dc.identifier.citationMossel, E, Procaccia, AD, Racz, MZ. (2013). A smooth transition from powerlessness to absolute power. Journal of Artificial Intelligence Research, 48 (923 - 951. doi:10.1613/jair.4125en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1p28p-
dc.description.abstractWe 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(√vn), 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 cn, 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. © 2013 AI Access Foundation. All rights reserved.en_US
dc.format.extent923 - 951en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of Artificial Intelligence Researchen_US
dc.rightsAuthor's manuscripten_US
dc.titleA smooth transition from powerlessness to absolute poweren_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1613/jair.4125-
dc.identifier.eissn1076-9757-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
A smooth transition from powerlessness to absolute power.pdf344.08 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.