IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v49y2025i5d10.1007_s10878-025-01307-1.html
   My bibliography  Save this article

Approximating combinatorial contracts with a cardinality constraint

Author

Listed:
  • Qinqin Gong

    (Beijing University of Technology)

  • Ling Gai

    (University of Shanghai for Science and Technology)

  • Yanjun Jiang

    (Ludong University)

  • Yang Lv

    (Beijing University of Technology)

  • Ruiqi Yang

    (Beijing University of Technology)

Abstract

We explore the problem of combinatorial contract design, a subject introduced and studied by Dütting et al. (2023). Previous research has focused on the challenge of selecting an unconstrained subset of agents, particularly when the principal’s utility function exhibits XOS or submodular characteristics related to the subset of agents that exert effort. Our study extends this existing line of research by examining scenarios in which the principal aims to select a subset of agents with a specific k-cardinality constraint. In these scenarios, the actions that each agent can take are binary values: effort or no effort. We focus on linear contracts, where the expected reward function is XOS or submodular. Our contribution is an approximation of 0.0197 for the problem of designing multi-agent hidden-action principal-agent contracts with the k-cardinality constraint. This result stands in contrast to the unconstrained setting, where Dütting et al. (2023) achieved an approximation of nearly 0.0039.

Suggested Citation

  • Qinqin Gong & Ling Gai & Yanjun Jiang & Yang Lv & Ruiqi Yang, 2025. "Approximating combinatorial contracts with a cardinality constraint," Journal of Combinatorial Optimization, Springer, vol. 49(5), pages 1-16, July.
  • Handle: RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01307-1
    DOI: 10.1007/s10878-025-01307-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01307-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-025-01307-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lin William Cong & Zhiguo He, 2019. "Blockchain Disruption and Smart Contracts," The Review of Financial Studies, Society for Financial Studies, vol. 32(5), pages 1754-1797.
    2. Holmstrom, Bengt & Milgrom, Paul, 1987. "Aggregation and Linearity in the Provision of Intertemporal Incentives," Econometrica, Econometric Society, vol. 55(2), pages 303-328, March.
    3. Wanyi Dai Li & Itai Ashlagi & Irene Lo, 2023. "Simple and Approximately Optimal Contracts for Payment for Ecosystem Services," Management Science, INFORMS, vol. 69(12), pages 7821-7837, December.
    4. Grossman, Sanford J & Hart, Oliver D, 1983. "An Analysis of the Principal-Agent Problem," Econometrica, Econometric Society, vol. 51(1), pages 7-45, January.
    5. Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
    6. Holmstrom, Bengt & Milgrom, Paul, 1991. "Multitask Principal-Agent Analyses: Incentive Contracts, Asset Ownership, and Job Design," The Journal of Law, Economics, and Organization, Oxford University Press, vol. 7(0), pages 24-52, Special I.
    7. Ross, Stephen A, 1973. "The Economic Theory of Agency: The Principal's Problem," American Economic Review, American Economic Association, vol. 63(2), pages 134-139, May.
    8. Lehmann, Benny & Lehmann, Daniel & Nisan, Noam, 2006. "Combinatorial auctions with decreasing marginal utilities," Games and Economic Behavior, Elsevier, vol. 55(2), pages 270-296, May.
    9. Gabriel Carroll, 2015. "Robustness and Linear Contracts," American Economic Review, American Economic Association, vol. 105(2), pages 536-563, February.
    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. Paul Duetting & Michal Feldman & Inbal Talgam-Cohen, 2024. "Algorithmic Contract Theory: A Survey," Papers 2412.16384, arXiv.org.
    2. Inés Macho-Stadler & David Pérez-Castrillo, 2018. "Moral hazard: Base models and two extensions," Chapters, in: Luis C. Corchón & Marco A. Marini (ed.), Handbook of Game Theory and Industrial Organization, Volume I, chapter 16, pages 453-485, Edward Elgar Publishing.
    3. 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.
    4. Escobar, Juan F. & Pulgar, Carlos, 2017. "Motivating with simple contracts," International Journal of Industrial Organization, Elsevier, vol. 54(C), pages 192-214.
    5. repec:eee:labchp:v:3:y:1999:i:pb:p:2485-2563 is not listed on IDEAS
    6. Asunur Cezar & Huseyin Cavusoglu & Srinivasan Raghunathan, 2014. "Outsourcing Information Security: Contracting Issues and Security Implications," Management Science, INFORMS, vol. 60(3), pages 638-657, March.
    7. Kyota Eguchi, 2017. "Guilty Conscience And Incentives With Performance Assessment Errors," Economic Inquiry, Western Economic Association International, vol. 55(1), pages 434-450, January.
    8. Oindrila Dey & Swapnendu Banerjee, 2022. "Incentives, Status and Thereafter: A Critical Survey," South Asian Journal of Macroeconomics and Public Finance, , vol. 11(1), pages 95-115, June.
    9. Emre M. Demirezen & Subodha Kumar & Bala Shetty, 2020. "Two Is Better Than One: A Dynamic Analysis of Value Co‐Creation," Production and Operations Management, Production and Operations Management Society, vol. 29(9), pages 2057-2076, September.
    10. Raith, Michael, 2012. "Optimal incentives and the time dimension of performance measurement," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2158-2189.
    11. Siqueira, Kevin Jay, 1998. "Issues of collective action: common agency, partial cooperation, and clubs," ISU General Staff Papers 1998010108000013526, Iowa State University, Department of Economics.
    12. Kadan, Ohad & Swinkels, Jeroen M., 2013. "On the moral hazard problem without the first-order approach," Journal of Economic Theory, Elsevier, vol. 148(6), pages 2313-2343.
    13. Emmanuel Jimenez & Yasuyuki Sawada, 2003. "Does Community Management Help Keep Kids in Schools? Evidence Using Panel Data from El Salvador's EDUCO Program," CIRJE F-Series CIRJE-F-236, CIRJE, Faculty of Economics, University of Tokyo.
    14. Barlo, Mehmet & Ayca, Ozdogan, 2012. "Team beats collusion," MPRA Paper 37449, University Library of Munich, Germany.
    15. Bengt Holmström, 2017. "Pay for Performance and Beyond," American Economic Review, American Economic Association, vol. 107(7), pages 1753-1777, July.
    16. Qi Liu & Lei Lu & Bo Sun, 2017. "Incentive Contracting Under Ambiguity Aversion," International Finance Discussion Papers 1195, Board of Governors of the Federal Reserve System (U.S.).
    17. Guillaume Roger, 2016. "A Revelation Mechanism for Soft Information under Moral Hazard," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 18(5), pages 752-763, October.
    18. Brigitte Godbillon-Camus, 2003. "Subjective evaluation, ambiguity and relational contracts," Working Papers of LaRGE Research Center 2003-03, Laboratoire de Recherche en Gestion et Economie (LaRGE), Université de Strasbourg.
    19. Dey, Oindrila & Banerjee, Swapnendu, 2014. "Status and incentives: A critical survey," MPRA Paper 57658, University Library of Munich, Germany.
    20. Alex Edmans & Xavier Gabaix, 2016. "Executive Compensation: A Modern Primer," Journal of Economic Literature, American Economic Association, vol. 54(4), pages 1232-1287, December.
    21. Li, Zhaolin, 2020. "Robust Moral Hazard with Distributional Ambiguity," Working Papers BAWP-2020-03, University of Sydney Business School, Discipline of Business Analytics.

    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:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01307-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.