A multivariate complexity analysis of lobbying in multiple referenda

R. Bredereck, J. Chen, S. Hartung, S. Kratsch, R. Niedermeier, O. Suchy, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
154 Downloads (Pure)

Abstract

Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m <5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.
Original languageEnglish
Pages (from-to)409-446
Number of pages38
JournalJournal of Artificial Intelligence Research
Volume50
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'A multivariate complexity analysis of lobbying in multiple referenda'. Together they form a unique fingerprint.

  • Cite this