{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:25Z","timestamp":1750306465163,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T00:00:00Z","timestamp":1451952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"USA-Israeli BSF"},{"DOI":"10.13039\/501100004350","name":"Studienstiftung des Deutschen Volkes","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004350","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DIAMANT"},{"name":"DFG","award":["NI 369\/10, KR 4286\/1"],"award-info":[{"award-number":["NI 369\/10, KR 4286\/1"]}]},{"name":"ERC","award":["Advanced Grant DMMCA (26718)"],"award-info":[{"award-number":["Advanced Grant DMMCA (26718)"]}]},{"name":"ISF"},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005386","name":"I-Core","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,1,5]]},"abstract":"<jats:p>\n            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\u2014the\n            <jats:italic>favorite ballot<\/jats:italic>\n            of this voter\u2014and 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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/2837467","type":"journal-article","created":{"date-parts":[[2015,12,30]],"date-time":"2015-12-30T13:13:41Z","timestamp":1451481221000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["How to Put Through Your Agenda in Collective Binary Decisions"],"prefix":"10.1145","volume":"4","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"given":"Robert","family":"Bredereck","sequence":"additional","affiliation":[{"name":"TU Berlin"}]},{"given":"Jiehua","family":"Chen","sequence":"additional","affiliation":[{"name":"TU Berlin"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[{"name":"TU Berlin"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"TU Berlin"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[{"name":"TU Eindhoven"}]}],"member":"320","published-online":{"date-parts":[[2016,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90026-9"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 3rd International Conference on Algorithmic Decision Theory (LNCS)","volume":"8176","author":"Alon Noga","unstructured":"Noga Alon , Robert Bredereck , Jiehua Chen , Stefan Kratsch , Rolf Niedermeier , and Gerhard J. Woeginger . 2013a. How to put through your agenda in collective binary decisions . In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (LNCS) , Vol. 8176 . Springer, 30--44. Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, and Gerhard J. Woeginger. 2013a. How to put through your agenda in collective binary decisions. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (LNCS), Vol. 8176. Springer, 30--44."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence. AAAI Press, 39--45","author":"Alon Noga","year":"2013","unstructured":"Noga Alon , Dvir Falik , Reshef Meir , and Moshe Tennenholtz . 2013 b. Bundling attacks in judgment aggregation . In Proceedings of the 27th AAAI Conference on Artificial Intelligence. AAAI Press, 39--45 . Noga Alon, Dvir Falik, Reshef Meir, and Moshe Tennenholtz. 2013b. Bundling attacks in judgment aggregation. In Proceedings of the 27th AAAI Conference on Artificial Intelligence. AAAI Press, 39--45."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2780"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling. 7.","author":"Aziz Haris","year":"2014","unstructured":"Haris Aziz , Serge Gaspers , (Hans) Joachim Gudmundsson , Simon Mackenzie , Nicholas Mattei , and Toby Walsh . 2014 . Computational aspects of multi-winner approval voting . In Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling. 7. Haris Aziz, Serge Gaspers, (Hans) Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. 2014. Computational aspects of multi-winner approval voting. In Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling. 7."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41575-3_6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050843.2050844"},{"volume-title":"The Multivariate Algorithmic Revolution and Beyond (LNCS)","author":"Betzler Nadja","key":"e_1_2_1_8_1","unstructured":"Nadja Betzler , Robert Bredereck , Jiehua Chen , and Rolf Niedermeier . 2012. Studies in computational aspects of voting\u2014A parameterized complexity perspective . In The Multivariate Algorithmic Revolution and Beyond (LNCS) , Vol. 7370 . Springer , 318--363. Nadja Betzler, Robert Bredereck, Jiehua Chen, and Rolf Niedermeier. 2012. Studies in computational aspects of voting\u2014A parameterized complexity perspective. In The Multivariate Algorithmic Revolution and Beyond (LNCS), Vol. 7370. Springer, 318--363."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2566972.2566985"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.10.003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TST.2014.6867518"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2693068.2693079"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/1957270"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10058-007-0028-1"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press","author":"Conitzer Vincent","year":"2009","unstructured":"Vincent Conitzer , J\u00e9r\u00f4me Lang , and Lirong Xia . 2009 . How hard is it to control sequential elections via the agenda? In Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press , San Francisco, CA, 103--108. Vincent Conitzer, J\u00e9r\u00f4me Lang, and Lirong Xia. 2009. How hard is it to control sequential elections via the agenda? In Proceedings of the 21st International Joint Conference on Artificial Intelligence. AAAI Press, San Francisco, CA, 103--108."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-011-9286-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"e_1_2_1_18_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283428"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2444851.2444863"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391495.2391523"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9138-6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.04.008"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_25_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_2_1_27_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. W. H. Freeman and Company . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_28_1","volume-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai","volume":"10","author":"Graver Jack E.","year":"1973","unstructured":"Jack E. Graver . 1973 . A survey of the maximum depth problem for indecomposable exact covers. In Infinite and Finite Sets , Colloquia Mathematica Societatis J\u00e1nos Bolyai , Vol. 10 . North-Holland, 731--743. Jack E. Graver. 1973. A survey of the maximum depth problem for indecomposable exact covers. In Infinite and Finite Sets, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Vol. 10. North-Holland, 731--743."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1309-3"},{"key":"e_1_2_1_31_1","first-page":"240","article-title":"R\u00e9solution d\u2019une question relative aux d\u00e9terminants","volume":"17","author":"Hadamard Jacque","year":"1893","unstructured":"Jacque Hadamard . 1893 . R\u00e9solution d\u2019une question relative aux d\u00e9terminants . Bulletin des Sciences Math\u00e9matiques 17 (1893), 240 -- 246 . Jacque Hadamard. 1893. R\u00e9solution d\u2019une question relative aux d\u00e9terminants. Bulletin des Sciences Math\u00e9matiques 17 (1893), 240--246.","journal-title":"Bulletin des Sciences Math\u00e9matiques"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"volume-title":"Handbook on Approval Voting","author":"Kilgour D. Marc","key":"e_1_2_1_34_1","unstructured":"D. Marc Kilgour . 2010. Approval balloting for multi-winner elections . In Handbook on Approval Voting . Springer , 105--124. D. Marc Kilgour. 2010. Approval balloting for multi-winner elections. In Handbook on Approval Voting. Springer, 105--124."},{"volume-title":"Electoral Systems","author":"Marc Kilgour D.","key":"e_1_2_1_35_1","unstructured":"D. Marc Kilgour and Erica Marshall . 2012. Approval balloting for fixed-size committees . In Electoral Systems . Springer , 305--326. D. Marc Kilgour and Erica Marshall. 2012. Approval balloting for fixed-size committees. In Electoral Systems. Springer, 305--326."},{"key":"e_1_2_1_36_1","first-page":"58","article-title":"Recent developments in kernelization: A survey","volume":"113","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014 . Recent developments in kernelization: A survey . Bulletin of the European Association for Theoretical Computer Science 113 (2014), 58 -- 97 . Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bulletin of the European Association for Theoretical Computer Science 113 (2014), 58--97.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-008-0325-9"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10726-010-9226-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283444"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.2307\/2082518"},{"volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","key":"e_1_2_1_43_1","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910)","volume":"5","author":"Niedermeier Rolf","year":"2010","unstructured":"Rolf Niedermeier . 2010 . Reflections on multivariate algorithmics and problem parameterization . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910) (LIPIcs), Vol. 5 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 17--32. Rolf Niedermeier. 2010. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910) (LIPIcs), Vol. 5. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 17--32."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1177\/0951692898010002001"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0235-2"},{"key":"e_1_2_1_47_1","first-page":"66","article-title":"On approximate solutions of scheduling problems","volume":"32","author":"Sevastyanov S. V.","year":"1978","unstructured":"S. V. Sevastyanov . 1978 . On approximate solutions of scheduling problems . Metody Discretnogo Analiza 32 (1978), 66 -- 75 (in Russian). S. V. Sevastyanov. 1978. On approximate solutions of scheduling problems. Metody Discretnogo Analiza 32 (1978), 66--75 (in Russian).","journal-title":"Metody Discretnogo Analiza"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 2131--2137","author":"Skowron Piotr","year":"2015","unstructured":"Piotr Skowron , Piotr Faliszewski , and J\u00e9r\u00f4me Lang . 2015 . Finding a collective set of items: From proportional multirepresentation to group recommendation . In Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 2131--2137 . Piotr Skowron, Piotr Faliszewski, and J\u00e9r\u00f4me Lang. 2015. Finding a collective set of items: From proportional multirepresentation to group recommendation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI Press, 2131--2137."},{"volume-title":"Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems. 399--406","author":"Skowron Piotr","key":"e_1_2_1_49_1","unstructured":"Piotr Skowron , Piotr Faliszewski , and Arkadii M. Slinko . 2013a. Achieving fully proportional representation is easy in practice . In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems. 399--406 . Piotr Skowron, Piotr Faliszewski, and Arkadii M. Slinko. 2013a. Achieving fully proportional representation is easy in practice. In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems. 399--406."},{"key":"e_1_2_1_50_1","volume-title":"Slinko","author":"Skowron Piotr","year":"2013","unstructured":"Piotr Skowron , Piotr Faliszewski , and Arkadii M . Slinko . 2013 b. Fully proportional representation as resource allocation: Approximability results. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press , 353--359. Piotr Skowron, Piotr Faliszewski, and Arkadii M. Slinko. 2013b. Fully proportional representation as resource allocation: Approximability results. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 353--359."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"volume-title":"Introduction to Graph Theory (2nd. ed.)","author":"West Douglas B.","key":"e_1_2_1_52_1","unstructured":"Douglas B. West . 2001. Introduction to Graph Theory (2nd. ed.) . Prentice Hall . Douglas B. West. 2001. Introduction to Graph Theory (2nd. ed.). Prentice Hall."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2837467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2837467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:36Z","timestamp":1750225416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2837467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,5]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1,5]]}},"alternative-id":["10.1145\/2837467"],"URL":"https:\/\/doi.org\/10.1145\/2837467","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,1,5]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}