Complexity of Optimal Lobbying in Threshold Aggregation

Ilan Nehama

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

Abstract: Optimal 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.

Pages: 22 pages
Date: 2013-07
New Economics Papers: this item is included in nep-cdm, nep-cta and nep-pol
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Proceedings of the 4th International Conference, ADT 2015, p. 379-395

Downloads: (external link)
http://www.ratio.huji.ac.il/sites/default/files/pu ... ld%20Aggregation.pdf (application/pdf)
http://link.springer.com/chapter/10.1007%2F978-3-319-23114-3_23 (text/html)
http://ratio.huji.ac.il/sites/default/files/publications/dp642.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp642.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp642.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp642

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().