Dominating Manipulations in Voting with Partial Information

Authors

  • Vincent Conitzer Duke University
  • Toby Walsh NICTA and University of New South Wales
  • Lirong Xia Duke University

Abstract

We consider manipulation problems when the manipulator only has partial information about the votes of the non-manipulators. Such partial information is described by an {\em information set}, which is the set of profiles of the non-manipulators that are indistinguishable to the manipulator. Given such an information set, a {\em dominating manipulation} is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator's information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.

Downloads

Published

2011-08-04

How to Cite

Conitzer, V., Walsh, T., & Xia, L. (2011). Dominating Manipulations in Voting with Partial Information. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 638-643. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7879

Issue

Section

AAAI Technical Track: Multiagent Systems