Complexity of manipulation with partial information in Voting

Show simple item record

dc.contributor.author Dey, Palash
dc.contributor.author Misra, Neeldhara
dc.date.accessioned 2016-06-09T09:26:24Z
dc.date.available 2016-06-09T09:26:24Z
dc.date.issued 2016-04
dc.identifier.citation Dey, Palash and Misra, Neeldhara, "Complexity of manipulation with partial information in Voting”, arXiv, Cornell University Library, DOI: arXiv:1604.04359, Apr. 2016. en_US
dc.identifier.other arXiv:1604.04359
dc.identifier.uri http://repository.iitgn.ac.in/handle/123456789/2299
dc.description.abstract The Coalitional Manipulation problem has been studied extensively in the literature for many voting rules. However, most studies have focused on the complete information setting, wherein the manipulators know the votes of the non-manipulators. While this assumption is reasonable for purposes of showing intractability, it is unrealistic for algorithmic considerations. In most real-world scenarios, it is impractical for the manipulators to have accurate knowledge of all the other votes. In this paper, we investigate manipulation with incomplete information. In our framework, the manipulators know a partial order for each voter that is consistent with the true preference of that voter. In this setting, we formulate three natural computational notions of manipulation, namely weak, opportunistic, and strong manipulation. We say that an extension of a partial order is if there exists a manipulative vote for that extension. 1. Weak Manipulation (WM): the manipulators seek to vote in a way that makes their preferred candidate win in at least one extension of the partial votes of the non-manipulators. 2. Opportunistic Manipulation (OM): the manipulators seek to vote in a way that makes their preferred candidate win in every viable extension of the partial votes of the non-manipulators. 3. Strong Manipulation (SM): the manipulators seek to vote in a way that makes their preferred candidate win in every extension of the partial votes of the non-manipulators. We consider several scenarios for which the traditional manipulation problems are easy (for instance, Borda with a single manipulator). For many of them, the corresponding manipulative questions that we propose turn out to be computationally intractable. Our hardness results often hold even when very little information is missing, or in other words, even when the instances are quite close to the complete information setting. en_US
dc.description.statementofresponsibility by Palash Dey and Neeldhara Misra
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Complexity of manipulation with partial information in Voting en_US
dc.type Preprint en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account