How to put through your agenda in collective binary decisions

Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We consider the following decision-making scenario: a society of voters has to find an agreement on a set of proposals, and every single proposal is to be accepted or rejected. Each voter supports a certain subset of the proposals-the favorite ballot of this voter-and opposes the remaining ones. He accepts a ballot if he supports more than half of the proposals in this ballot. The task is to decide whether there exists a ballot approving a specified number of selected proposals (agenda) such that all voters (or a strict majority of them) accept this ballot. We show that, on the negative side, both problems are NP-complete, and on the positive side, they are fixed-parameter tractable with respect to the total number of proposals or with respect to the total number of voters. We look into further natural parameters and study their influence on the computational complexity of both problems, thereby providing both tractability and intractability results. Furthermore, we provide tight combinatorial bounds on the worst-case size of an accepted ballot in terms of the number of voters.

Original languageEnglish (US)
Article number2837467
JournalACM Transactions on Economics and Computation
Issue number1
StatePublished - Dec 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Computational Mathematics
  • Economics and Econometrics
  • Marketing
  • Statistics and Probability


  • Approval balloting with majority threshold
  • Collective binary decision making
  • Control by proposal bundling
  • Voting on multiple issues


Dive into the research topics of 'How to put through your agenda in collective binary decisions'. Together they form a unique fingerprint.

Cite this