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

    for a different version of it.

    References listed on IDEAS

    as
    1. Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Grossman, Sanford J & Hart, Oliver D, 1983. "An Analysis of the Principal-Agent Problem," Econometrica, Econometric Society, vol. 51(1), pages 7-45, January.
    7. Holmstrom, Bengt & Milgrom, Paul, 1987. "Aggregation and Linearity in the Provision of Intertemporal Incentives," Econometrica, Econometric Society, vol. 55(2), pages 303-328, March.
    8. 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.
    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. 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. Escobar, Juan F. & Pulgar, Carlos, 2017. "Motivating with simple contracts," International Journal of Industrial Organization, Elsevier, vol. 54(C), pages 192-214.
    4. 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.
    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. Raith, Michael, 2012. "Optimal incentives and the time dimension of performance measurement," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2158-2189.
    10. 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.
    11. Bengt Holmström, 2017. "Pay for Performance and Beyond," American Economic Review, American Economic Association, vol. 107(7), pages 1753-1777, July.
    12. Alex Edmans & Xavier Gabaix, 2016. "Executive Compensation: A Modern Primer," Journal of Economic Literature, American Economic Association, vol. 54(4), pages 1232-1287, December.
    13. Li, Zhaolin, 2020. "Robust Moral Hazard with Distributional Ambiguity," Working Papers BAWP-2020-03, University of Sydney Business School, Discipline of Business Analytics.
    14. René Carmona, 2022. "The influence of economic research on financial mathematics: Evidence from the last 25 years," Finance and Stochastics, Springer, vol. 26(1), pages 85-101, January.
    15. Bartsch, Elga, 1996. "Enforcement of environmental liability in the case of uncertain causality and asymmetric information," Kiel Working Papers 755, Kiel Institute for the World Economy (IfW Kiel).
    16. Novak, Jiri & Bilinski, Pawel, 2018. "Social stigma and executive compensation," Journal of Banking & Finance, Elsevier, vol. 96(C), pages 169-184.
    17. Tal Alon & Paul Dutting & Yingkai Li & Inbal Talgam-Cohen, 2022. "Approximate Optimality of Linear Contracts Under Uncertainty," Papers 2211.06850, arXiv.org, revised Mar 2025.
    18. Kissan Joseph & Alex Thevaranjan, 1998. "Monitoring and Incentives in Sales Organizations: An Agency-Theoretic Perspective," Marketing Science, INFORMS, vol. 17(2), pages 107-123.
    19. Kim, Son Ku & Wang, Susheng, 1998. "Linear Contracts and the Double Moral-Hazard," Journal of Economic Theory, Elsevier, vol. 82(2), pages 342-378, October.
    20. Martin Dumav, 2021. "Moral Hazard, Dynamic Incentives, and Ambiguous Perceptions," Papers 2110.15229, arXiv.org.
    21. Felipe Balmaceda, 2020. "Contracting with moral hazard, adverse selection and risk neutrality: when does one size fit all?," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(2), pages 601-637, June.

    More about this item

    Keywords

    ;
    ;
    ;

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