New Approximations for Coalitional Manipulation in Scoring Rules

Orgad Keller, Avinatan Hassidim, Noam HazonJAIR 2019 · OpenReview

TL;DR

This paper tackles the challenge of "coalitional manipulation" in elections, where a group of voters (manipulators) collude to ensure their preferred candidate wins. Instead of focusing on the minimum number of manipulators needed, the authors propose novel algorithms that approximate the score margin—the difference between the winner's score and their preferred candidate's score. Their approach uses advanced linear programming techniques, offering better approximations for certain scenarios, especially in the Borda protocol.

What Problem Does This Paper Address?

In democratic societies and multi-agent systems, elections are crucial for decision-making. However, most voting systems are susceptible to manipulation, where voters can strategically cast their ballots to achieve a desired outcome. A specific concern is "coalitional manipulation," where a group of voters (the coalition) coordinates their votes. Previous research often focused on finding the minimum number of manipulators required to make a candidate win. This paper shifts the focus to a more nuanced metric: the score margin. Minimizing this margin means ensuring the preferred candidate wins by the smallest possible lead over their closest competitor. This is important because it provides a finer-grained understanding of how "close" a candidate is to winning and how effective manipulation can be, especially when the number of manipulators is fixed. The authors explore this problem for "scoring rules," a broad class of voting systems that includes popular methods like Borda, Plurality, and Veto.

Methods

The core of the paper's contribution lies in its novel algorithmic approach. The authors introduce "configuration linear programs" (C-LPs), a technique adapted from multiprocessor scheduling. These LPs involve an exponential number of variables, which they overcome by using the ellipsoid method with a "separation oracle." This allows them to solve the LP without explicitly enumerating all constraints.

For the unweighted case (UCM), they develop a randomized rounding algorithm on the C-LP solution to find a strategy that approximates the optimal score margin. For the weighted case (WCM), they extend this by defining configurations that account for individual manipulator weights and employing a "k-sequence knapsack" variant for the separation oracle.

Key technical innovations include:

  • Configuration Linear Programs (C-LPs): A novel formulation for manipulation problems, moving beyond traditional LP formulations.
  • Ellipsoid Method with Separation Oracle: An efficient way to solve LPs with an exponential number of variables, crucial for C-LPs.
  • Randomized Rounding: A technique to convert fractional LP solutions into valid manipulation strategies.
  • k-Sequence Knapsack: A new variant of the knapsack problem tailored for the weighted manipulation scenario.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their analysis, with experimental validation on simulated data.

Key Insights and Ideas

  • Score Margin as a Better Metric: Focusing on the score margin, rather than just the number of manipulators, provides a more granular and informative measure of manipulation effectiveness. This allows for better approximations, especially when the number of manipulators is fixed.
  • Configuration LPs are Powerful: The introduction of C-LPs is a significant technical contribution, enabling the modeling of complex manipulation scenarios that were difficult to capture with traditional LP formulations.
  • Bridging Scheduling and Voting: The paper successfully adapts techniques from multiprocessor scheduling (like C-LPs) to solve problems in computational social choice, demonstrating the cross-disciplinary applicability of these methods.
  • Approximation Guarantees for Any Scoring Rule: The algorithms are designed to work for any scoring rule, not just specific ones like Borda, making them broadly applicable.

Key Results

The paper presents theoretical results providing additive approximation guarantees for the score margin in both unweighted (Ra-UCM) and weighted (Ra-WCM) coalitional manipulation for any scoring rule Ra.

  • Ra-UCM: An additive $kg(a)$-approximation to the optimal score margin is achieved with high probability, where $g(a)$ depends on the scoring rule's coefficients. For Borda-UCM, this translates to an $O(k\sqrt{m \log m})$-approximation.
  • Ra-WCM (Polynomial Weights): An additive $Wg(a)$-approximation is achieved, where $W$ is the sum of manipulator weights. For Borda-WCM, this is $O(W\sqrt{m \log N})$.
  • Ra-WCM (General Weights): A slightly weaker but still valuable result provides a bound of $T < (1 + \epsilon)T_{OPT} + Wg(a)$ for any $\epsilon > 0$. For Borda-WCM, this can be an FPTAS under certain assumptions.

The paper also demonstrates that simpler greedy algorithms (like REVERSE) can provide only an $\Omega(m)$ approximation for the score margin in certain Borda-UCM cases, highlighting the superiority of their LP-based approach.

Limitations and Future Work

Limitations: * Runtime: The LP-based approach, while theoretically polynomial, can be computationally intensive in practice due to the simulation of the ellipsoid method with a separation oracle. The authors note that a dedicated LP solver for this purpose would improve performance. * Assumptions for FPTAS: Achieving an FPTAS for Borda-WCM with general weights relies on assumptions like $Wg(a) = o(T_{OPT})$ or $k = 2^{\Omega(m)}$.

Future Work: * Tighter Approximations: Investigating whether tighter approximations are possible or if NP-hardness results can be proven for finding strategies with small score margins. * Approximation Factor Trade-offs: Exploring other trade-offs between the number of manipulators ($k$), candidates ($m$), and approximation factors. * Dichotomies for Scoring Rules: Defining clear boundaries for when Ra-UCM and Ra-WCM are NP-hard. * Instance Taxonomy: Developing a classification of instances where different manipulation strategies perform best. * Broader Applications of C-LPs: Exploring the use of configuration linear programs in other voting methods and computational social choice problems, such as fair division.

Summary updated

Abstract

We study the problem of coalitional manipulation---where k manipulators try to manipulate an election on m candidates---for any scoring rule, with focus on the Borda protocol. We do so in both the weighted and unweighted settings. For these problems, recent approximation approaches have tried to minimize k, the number of manipulators needed to make some preferred candidate p win (thus assuming that the number of manipulators is not limited in advance). In contrast, we focus on minimizing the score margin of p which is the difference between the maximum score of a candidate and the score of p.&nbsp;We provide algorithms that approximate the optimum score margin, which are applicable to any scoring rule. For the specific case of the Borda protocol in the unweighted setting, our algorithm provides a superior approximation factor for lower values of k.Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle. We believe that such methods could be beneficial in other social choice settings as well.
BibTeX
@article{keller2019new,
  author = {Orgad Keller and Avinatan Hassidim and Noam Hazon},
  title = {{New Approximations for Coalitional Manipulation in Scoring Rules}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=LLKuu2agroc},
}
Figure