NDLI: How to Put Through Your Agenda in Collective Binary Decisions

Please wait, while we are loading the content...

How to Put Through Your Agenda in Collective Binary Decisions

Content Provider	ACM Digital Library
Author	Chen, Jiehua Alon, Noga Bredereck, Robert Niedermeier, Rolf Woeginger, Gerhard J. Kratsch, Stefan
Copyright Year	2016
Abstract	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—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 specified number of selected proposals (agenda) such that all voters (or a strict majority of them) accept this ballot. 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.
Starting Page	1
Ending Page	28
Page Count	28
File Format	PDF
ISSN	21678375
e-ISSN	21678383
DOI	10.1145/2837467
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Economics and Computation (TEAC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-05
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Collective binary decision making Approval balloting with majority threshold Control by proposal bundling Voting on multiple issues
Content Type	Text
Resource Type	Article
Subject	Economics and Econometrics Marketing Computational Mathematics Statistics and Probability Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

How to put through your agenda in collective binary decisions.

How to Put Through Your Agenda in Collective Binary Decisions (2013)

How to Put Through Your Agenda in Collective Binary Decisions

Searching for a Compromise in Multiple Referendum

A characterization of Approval Voting without the approval balloting assumption

Minority voting and long-term decisions

Approval voting: three examples

Dealing with incomplete agents ’ preferences and an uncertain agenda in group decision making via sequential majority voting.

Minority Voting and Long-term Decisions

How to Put Through Your Agenda in Collective Binary Decisions

Similar Documents

How to put through your agenda in collective binary decisions.

How to Put Through Your Agenda in Collective Binary Decisions (2013)

How to Put Through Your Agenda in Collective Binary Decisions

Searching for a Compromise in Multiple Referendum

A characterization of Approval Voting without the approval balloting assumption

Minority voting and long-term decisions

Approval voting: three examples

Dealing with incomplete agents ’ preferences and an uncertain agenda in group decision making via sequential majority voting.

Minority Voting and Long-term Decisions

How to Put Through Your Agenda in Collective Binary Decisions