Complexity of Optimal Lobbying in Threshold Aggregation
AbstractOptimal Lobbying is the problem a lobbyist or a campaign manager faces in a full-information voting scenario of a multi-issue referendum when trying to influence the result. The Lobby is faced with a profile that specifies for each voter and each issue whether the voter approves or rejects the issue, and seeks to find the smallest set of voters it must influence to change their vote, for a desired outcome to be obtained. This computational problem also describes problems arising in other scenarios of aggregating complex opinions, such as principal-agents incentives scheme in a complex combinatorial problem, and bribery and manipulation in Truth-Functional Judgement Aggregation. We study the computational complexity of Optimal Lobbying when the issues are aggregated using an anonymous monotone function and the family of desired outcomes is an upward-closed family. We analyze this problem with regard to two parameters: the minimal number of supporters needed to pass an issue, and the size of the maximal minterm of the desired set. We show that for the extreme values of the parameters, the problem is tractable, and provide algorithms. On the other hand, we prove intractability of the problem for the non-extremal values, which are common values for the parameters.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by The Center for the Study of Rationality, Hebrew University, Jerusalem in its series Discussion Paper Series with number dp642.
Length: 22 pages
Date of creation: Jul 2013
Date of revision:
This paper has been announced in the following NEP Reports:
- NEP-ALL-2013-08-05 (All new papers)
- NEP-CDM-2013-08-05 (Collective Decision-Making)
- NEP-CTA-2013-08-05 (Contract Theory & Applications)
- NEP-POL-2013-08-05 (Positive Political Economics)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Robin Christian & Mike Fellows & Frances Rosamond & Arkadii Slinko, 2007. "On complexity of lobbying in multiple referenda," Review of Economic Design, Springer, vol. 11(3), pages 217-224, November.
- Sebastian Bervoets & Vincent Merlin, 2012. "Gerrymander-proof representative democracies," International Journal of Game Theory, Springer, vol. 41(3), pages 473-488, August.
- Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama).
If references are entirely missing, you can add them using this form.