TY - GEN
T1 - How to put through your agenda in collective binary decisions
AU - Alon, Noga
AU - Bredereck, Robert
AU - Chen, Jiehua
AU - Kratsch, Stefan
AU - Niedermeier, Rolf
AU - Woeginger, Gerhard J.
N1 - Funding Information:
NA is supported in part by an ERC advanced grant, by a USA-Israeli BSF grant, by an ISF grant and by the Israeli I-Core program. RB is supported by the DFG, research project PAWS, NI 369/10. JC is supported by the Studienstiftung des Deutschen Volkes. SK is supported by the DFG, research project PREMOD, KR 4286/1. GW is supported by DIAMANT (a mathematics cluster of the Netherlands Organization for Scientific Research NWO) and, while staying at TU Berlin (October 2012 - June 2013), by the Alexander von Humboldt Foundation, Bonn, Germany.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84890048633&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890048633&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-41575-3_3
DO - 10.1007/978-3-642-41575-3_3
M3 - Conference contribution
AN - SCOPUS:84890048633
SN - 9783642415746
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 30
EP - 44
BT - Algorithmic Decision Theory - Third International Conference, ADT 2013, Proceedings
PB - Springer Verlag
T2 - 3rd International Conference on Algorithmic Decision Theory, ADT 2013
Y2 - 13 November 2013 through 15 November 2013
ER -