A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrej Suchý, Gerhard J. WoegingerJAIR 2014 · OpenReview

Lobbying in multiple referenda is a complex challenge where an external agent attempts to influence the outcome of several simultaneous votes by persuading a limited number of voters. While the general problem is known to be NP-hard, recent research published in the Journal of Artificial Intelligence Research provides a comprehensive multivariate complexity analysis, identifying the specific conditions that make this problem tractable.

Understanding the Lobbying Problem

In a typical scenario, $n$ voters cast "yes" or "no" votes on $m$ different issues. A "lobby" aims to ensure all $m$ issues pass by influencing up to $k$ voters. When a voter is influenced, their entire row of votes is flipped to "yes."

The computational difficulty arises because the problem is W[2]-complete with respect to the number of voters $k$. This classification suggests that as the number of voters to be influenced grows, the problem becomes exponentially harder to solve, likely precluding an efficient general-purpose algorithm. To navigate this, the authors sought "islands of tractability"—specific parameter constraints that allow for efficient solutions.

Mapping the Complexity Landscape

The researchers employed Multivariate Complexity Analysis to examine how various parameters—such as the number of issues ($m$), the number of voters ($n$), the "gap" to a majority ($g$), and the maximum number of "yes" or "no" votes per voter ($s$ and $t$)—interact to determine the problem's difficulty.

Figure 1: A map of parameter relationships and their corresponding complexity classes.

As shown in the "map" above, the interplay between these parameters reveals a nuanced landscape. For instance, while the problem is hard when parameterized solely by $k$, it becomes Fixed-Parameter Tractable (FPT) when combining $m$ and $g$. One of the most significant theoretical findings is that the problem is LOGSNP-complete even when the "gap value" $g$ is as small as 1. This identifies Lobbying as a rare natural example of a problem in the LOGSNP class.

Algorithmic Breakthroughs and Results

The study utilized several sophisticated techniques to tackle different facets of the problem:

  • Integer Linear Programming (ILP): Used to prove FPT for the number of issues ($m$).
  • Greedy Approximation: The authors developed the MaxGapZeros algorithm, which selects voters based on their potential to close the largest vote gaps.
  • Graph Matching: Applied to solve cases where voters approve at most two issues ($s \le 2$).
Figure 2: Summary of complexity results for various parameter combinations.

The results summarized in the table above highlight several key findings. Notably, the problem is FPT for the number of issues $m$, which is highly relevant in practice as most referenda involve a manageable number of issues (typically under 20). Furthermore, the MaxGapZeros greedy algorithm was proven to be provably optimal for instances with 4 or fewer issues ($m \le 4$).

Real-World Performance and Empirical Success

Beyond theoretical proofs, the authors evaluated their algorithms using voting records from the German Bundestag (2012–2013). The dataset, comprising 620 politicians and 67 issues, revealed that real-world voting patterns often exhibit high redundancy due to party-line voting.

This structure significantly reduces the search space, allowing both ILP and greedy algorithms to perform exceptionally well. In fact, the MaxGapZeros algorithm solved 100% of the real-world instances optimally, often outperforming the more complex ILP solver in terms of speed.

Conclusion

This multivariate analysis provides a clear guide for when the Lobbying problem can be solved efficiently. By identifying the number of issues ($m$) and the gap value ($g$) as key drivers of tractability, the research offers practical tools for analyzing influence in democratic processes. Future work may extend these models to account for partial influence or dynamic voter pools, further bridging the gap between theoretical complexity and real-world political strategy.

Summary updated

BibTeX
@article{bredereck2014multivariate,
  author = {Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondrej Suchý and Gerhard J. Woeginger},
  title = {{A Multivariate Complexity Analysis of Lobbying in Multiple Referenda}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=u0Ng3YN3Ze},
}
Figure