Complexity of Manipulation with Partial Information in Voting

Palash Dey, Neeldhara Misra, Y. NarahariIJCAI 2016

Introduction: The Reality of Partial Information

In computational social choice, the "Coalitional Manipulation" problem explores whether a group of voters can coordinate their ballots to ensure a preferred candidate wins. Traditionally, research assumed manipulators possessed complete information—a perfect understanding of every other voter's preferences. However, in real-world scenarios, privacy and logistical constraints mean that manipulators often only have access to partial information.

The authors address this by modeling voter preferences as partial orders rather than full rankings. For example, a manipulator might know a voter prefers Candidate A over B, but not where Candidate C stands. The core question is: how does this uncertainty affect the computational difficulty of gaming the system?

Modeling Manipulation Frameworks

To capture different manipulative goals under uncertainty, the paper introduces three distinct frameworks:

  1. Weak Manipulation (WM): Can manipulators cast votes such that their candidate wins in at least one possible completion of the partial votes?
  2. Strong Manipulation (SM): Can they ensure their candidate wins in every possible completion?
  3. Opportunistic Manipulation (OM): Can they cast a single vote that guarantees a win in every "viable" scenario (those where a win was possible to begin with)?
Examples of partial orders and their possible linear extensions.

The researchers used complexity theory to analyze these problems, proving hardness by reducing known difficult problems like Exact Cover by 3-Sets (X3C) and the Possible Winner (PW) problem to these frameworks.

Key Results and Complexity Mapping

The most significant finding is that even a small amount of missing information can make voting rules that are traditionally "easy" to manipulate (like Borda or Maximin) computationally intractable (NP-hard).

Complexity results for various voting rules under different manipulation frameworks.

As shown in the table above:

  • Borda, Maximin, and Copeland: These rules become NP-complete for Weak Manipulation and coNP-hard for Strong/Opportunistic Manipulation, even with a single manipulator.
  • Bucklin and Fallback: These are NP-complete for WM but remain in P (polynomial time) for SM.
  • Plurality and Veto: These rules remain easy to manipulate (in P) across all frameworks, suggesting they are fundamentally more vulnerable to manipulation regardless of information levels.

Insights and Future Directions

The research highlights that information acts as a barrier. You don't need total ignorance to deter a manipulator; just a few undetermined pairs in a ballot can turn a simple calculation into an NP-hard problem. The introduction of Opportunistic Manipulation provides a novel middle ground, modeling a manipulator who wants to succeed whenever success is theoretically possible.

While this work focuses on worst-case complexity, future research could explore average-case analysis to see if these barriers hold in typical voting scenarios. Additionally, extending the analysis to other forms of election control, such as adding or deleting candidates under partial information, remains an open area for exploration.

Summary updated

BibTeX
@inproceedings{dey2016complexity,
  author = {Palash Dey and Neeldhara Misra and Y. Narahari},
  title = {{Complexity of Manipulation with Partial Information in Voting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure