IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp642.html

Complexity of Optimal Lobbying in Threshold Aggregation

Author

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.

Suggested Citation

  • Ilan Nehama, 2013. "Complexity of Optimal Lobbying in Threshold Aggregation," Discussion Paper Series dp642, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    • Handle: RePEc:huj:dispap:dp642
    as

    Download full text from publisher

    File URL: http://www.ratio.huji.ac.il/sites/default/files/publications/Ilan%20Nehama%20-%20ADT%20-%20Complexity%20of%20Optimal%20Lobbying%20in%20Threshold%20Aggregation.pdf
    Download Restriction: no
    File URL: http://link.springer.com/chapter/10.1007%2F978-3-319-23114-3_23
    Download Restriction: no
    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp642.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Sebastian Bervoets & Vincent Merlin, 2012. "Gerrymander-proof representative democracies," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(3), pages 473-488, August.
    2. Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
    3. Robin Christian & Mike Fellows & Frances Rosamond & Arkadii Slinko, 2007. "On complexity of lobbying in multiple referenda," Review of Economic Design, Springer;Society for Economic Design, vol. 11(3), pages 217-224, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shahar Dobzinski & Noam Nisan & Michael Schapira, 2005. "Truthful Randomized Mechanisms for Combinatorial Auctions," Discussion Paper Series dp408, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    2. Balmaceda, Felipe & Balseiro, Santiago R. & Correa, José R. & Stier-Moses, Nicolás E., 2016. "Bounds on the welfare loss from moral hazard with limited liability," Games and Economic Behavior, Elsevier, vol. 95(C), pages 137-155.
    3. Paul Milgrom, 2009. "Assignment Messages and Exchanges," American Economic Journal: Microeconomics, American Economic Association, vol. 1(2), pages 95-113, August.
    4. Yigal Gerchak & Christian Schmid, 2022. "Principal–agent models where a principal is only affected by extreme performances," Managerial and Decision Economics, John Wiley & Sons, Ltd., vol. 43(2), pages 468-477, March.
    5. Ariane Lambert‐Mogiliansky & Konstantin Sonin, 2006. "Collusive Market Sharing and Corruption in Procurement," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 15(4), pages 883-908, December.
    6. repec:dau:papers:123456789/5665 is not listed on IDEAS
    7. Yuval Emek & Michal Feldman, 2007. "Computing an Optimal Contract in Simple Technologies," Discussion Paper Series dp452, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    8. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    9. Rica Gonen & Anat Lerner, 2013. "The Incompatibility of Pareto Optimality and Dominant-Strategy Incentive Compatibility in Sufficiently-Anonymous Budget-Constrained Quasilinear Settings," Games, MDPI, vol. 4(4), pages 1-21, November.
    10. Liad Blumrosen & Noam Nisan, 2005. "On the Computational Power of Iterative Auctions I: Demand Queries," Discussion Paper Series dp381, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    11. Ramchurn, Sarvapali D. & Dash, Rajdeep K. & Jennings, Nicholas R. & Giovannucci, Andrea & Rodriguez-Aguilar, Juan A. & Mezzetti, Claudio, 2008. "Trust-Based Mechanisms for Robust and Efficient Task Allocation in the Presence of Execution Uncertainty," Economic Research Papers 269891, University of Warwick - Department of Economics.
    12. Müller, R.J. & Perea ý Monsuwé, A. & Wolf, S., 2007. "Combinatorial scoring auctions," Research Memorandum 020, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. Müller, R.J., 2001. "Auctions : the big winner among trading mechanisms for the Internet economy," Research Memorandum 016, Maastricht University, Maastricht Economic Research Institute on Innovation and Technology (MERIT).
    14. Balmaceda, Felipe, 2018. "Optimal task assignments with loss-averse agents," European Economic Review, Elsevier, vol. 105(C), pages 1-26.
    15. Mark Bykowsky & Jonathan Levy & William Sharkey & Tracy Waldon & Simon Wilkie, 2003. "Economic Analysis at the Federal Communications Commission," Review of Industrial Organization, Springer;The Industrial Organization Society, vol. 23(2), pages 157-174, September.
    16. Song, Jiongjiong & Regan, Amelia C. & Nandiraju, Srinivas, 2008. "A Bid Analysis Model with Business Constraints for Transportation Procurement Auctions," University of California Transportation Center, Working Papers qt24817929, University of California Transportation Center.
    17. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    18. Regan, A C & Song, Jiongjiong, 2003. "Combinatorial Auctions for Transportation Service Procurement: The Carrier Perspective," University of California Transportation Center, Working Papers qt7sq003mj, University of California Transportation Center.
    19. Song, Jiongjiong & Regan, Amelia C & Nandiraju, Srinivas, 2008. "A Bid Analysis Model with Business Constraints for Transportation Procurement Auctions," University of California Transportation Center, Working Papers qt5766c7r1, University of California Transportation Center.
    20. Yuval Emek & Michal Feldman, 2007. "Computing an Optimal Contract in Simple Technologies," Levine's Bibliography 843644000000000184, UCLA Department of Economics.
    21. Blumrosen, Liad & Feldman, Michal, 2013. "Mechanism design with a restricted action space," Games and Economic Behavior, Elsevier, vol. 82(C), pages 424-443.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp642. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.