How to Put Through Your Agenda in Collective Binary Decisions
Dipl.-Inf. Robert Bredereck (TU Berlin)
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.
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.
Back to the research colloquium site.