Manipulative Elicitation - A New Attack on Elections with Incomplete Preferences

Palash DeyAAAI 2018 · DOI

Introduction

In modern multi-agent systems and collaborative filtering applications, agents often provide incomplete rankings of alternatives. To determine a winner from these partial orders, the minimax regret (MR) framework is frequently employed. This robust approach identifies a candidate who minimizes the maximum potential "regret"—the score difference compared to any other candidate—across all possible completions of the partial preferences. While MR is valued for its computational efficiency, this paper identifies a significant security vulnerability: manipulative elicitation.

The Manipulative Elicitation Problem

Manipulative elicitation occurs when an elicitor, possessing knowledge of the agents' true underlying preferences, strategically chooses which comparisons to reveal to the voting rule. Unlike traditional manipulation where a voter lies about their preferences, this attack relies on selective omission. By strategically withholding specific information, the elicitor can artificially manipulate the regret calculations to ensure a preferred candidate wins, even if that candidate would not have won under full disclosure.

The author formalizes this as the s-manipulative elicitation problem. The investigation reveals a stark contrast between the basic attack and a proposed defense mechanism based on computational complexity.

Computational Vulnerability vs. Defense

The research first establishes that for a broad class of "monotone, neutral, and worst-efficient" voting rules—including Borda, Plurality, and Maximin—the basic manipulative elicitation attack is solvable in polynomial time (P). This implies that if a system can efficiently compute a winner, it is inherently vulnerable to an elicitor who can find an optimal partial profile to favor their candidate.

To mitigate this, the author introduces a novel defense: Candidate Pair Limits. This constraint mandates that for every pair of candidates, a minimum number of voters must have a revealed preference between them. This ensures a baseline level of information density, preventing the elicitor from being overly selective in their omissions.

Complexity Results and Proof Construction

The core contribution of the paper is proving that adding Candidate Pair Limits elevates the complexity of the manipulator's task to NP-complete. This provides a computational barrier, making it unlikely that an elicitor can find a successful manipulation in a reasonable timeframe for large-scale elections.

The author employs mathematical reductions from hard problems like Set Cover Frequency Two and Exact Cover by 3-Sets (X3C). The proofs involve constructing specific partial profiles where the minimax regret scores of various alternatives are carefully balanced to map to the underlying hard problem.

Minimax regret scores for a general scoring rule $r$ in the hardness proof construction.

The hardness results extend across several categories of voting rules:

  • Scoring Rules: Including Plurality, k-approval, veto, and Borda.
  • Tournament-based Rules: Including Maximin and Copeland.
  • Elimination Rules: Including simplified Bucklin voting.
Minimax regret scores for the Maximin rule, illustrating the NP-completeness of the constrained attack.

As shown in the tables above, the construction of the "MR-score" is central to the reduction. By strategically setting these values based on the parameters of the hard problem instance, the author demonstrates that finding a winning partial profile is equivalent to solving an NP-hard combinatorial problem.

Conclusion and Future Work

This research highlights a critical trade-off in social choice: the efficiency of a voting rule can be a double-edged sword that facilitates manipulation. By introducing Candidate Pair Limits, system designers can leverage computational complexity as a shield to protect the integrity of preference elicitation processes.

While NP-completeness offers a strong worst-case guarantee, the author acknowledges that this is a "weak barrier." Future work should investigate the "average-case" hardness to ensure these defenses remain robust in practical scenarios like recommender systems. Additionally, exploring whether uniform limits across all candidate pairs maintain this hardness remains an open question for future theoretical research.

Summary updated

BibTeX
@inproceedings{dey2018manipulative,
  author = {Palash Dey},
  title = {{Manipulative Elicitation - A New Attack on Elections with Incomplete Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11578},
}
Figure