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: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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. 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)
Title of host publicationAlgorithmic Decision Theory - Third International Conference, ADT 2013, Proceedings
Pages30-44
Number of pages15
DOIs
StatePublished - Dec 16 2013
Externally publishedYes
Event3rd International Conference on Algorithmic Decision Theory, ADT 2013 - Bruxelles, Belgium
Duration: Nov 13 2013Nov 15 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8176 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Algorithmic Decision Theory, ADT 2013
CountryBelgium
CityBruxelles
Period11/13/1311/15/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Alon, N., Bredereck, R., Chen, J., Kratsch, S., Niedermeier, R., & Woeginger, G. J. (2013). How to put through your agenda in collective binary decisions. In Algorithmic Decision Theory - Third International Conference, ADT 2013, Proceedings (pp. 30-44). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8176 LNAI). https://doi.org/10.1007/978-3-642-41575-3-3