How to Put through Your Agenda in Collective Binary Decisions

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

Abstract

We consider the following decision 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 set of selected proposals (agenda) such that all voters (or a strict majority of them) accept this ballot.
BibTeX
@inproceedings{alon2013how,
  author = {Noga Alon and Robert Bredereck and Jiehua Chen and Stefan Kratsch and Rolf Niedermeier and Gerhard J. Woeginger},
  title = {{How to Put through Your Agenda in Collective Binary Decisions}},
  booktitle = {ADT},
  year = {2013},
  doi = {10.1007/978-3-642-41575-3\_3},
}

Loading related content...

Figure