IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2605.01715.html

Strategy-proof and Efficient Job Matching with Participation Constraints

Author

Listed:
  • Sushil Bikhchandani
  • Debasis Mishra

Abstract

We study the design of strategy-proof and efficient mechanisms satisfying participation constraints in the job-matching problem. Each firm can hire multiple workers and each worker can be employed at only one firm. While firm utilities over subsets of workers are common knowledge, worker disutilities for working at each firm are private information. The VCG mechanism is the unique mechanism that is strategy-proof, efficient, and individually rational for workers; however, it may not be individual rational for firms. We show that the VCG mechanism is individually rational for firms if and only if firm utilities satisfy a condition called weak substitutes. We then strengthen participation constraints of firms to {\sl strong individual rationality}, which requires that each firm has no incentive to fire some of the workers assigned to it. The VCG mechanism is strongly individual rational if and only if firm utilities satisfy submodularity.

Suggested Citation

  • Sushil Bikhchandani & Debasis Mishra, 2026. "Strategy-proof and Efficient Job Matching with Participation Constraints," Papers 2605.01715, arXiv.org.
    • Handle: RePEc:arx:papers:2605.01715
    as

    Download full text from publisher

    File URL: https://arxiv.org/pdf/2605.01715
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    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. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    2. Ryuji Sano, 2021. "Dynamic communication mechanism design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 163-180, July.
    3. Mochon, A. & Saez, Y. & Gomez-Barroso, J.L. & Isasi, P., 2012. "Exploring pricing rules in combinatorial sealed-bid auctions," Journal of Economic Behavior & Organization, Elsevier, vol. 82(2), pages 462-478.
    4. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    5. Sébastien Lahaie & Benjamin Lubin, 2025. "Adaptive Pricing in Combinatorial Auctions," Management Science, INFORMS, vol. 71(10), pages 8967-8993, October.
    6. Shirata, Yasuhiro, 2017. "First price package auction with many traders," Journal of Mathematical Economics, Elsevier, vol. 69(C), pages 71-83.
    7. Satoru Fujishige & Zaifu Yang, 2026. "A Universally Efficient Dynamic Auction for All Unimodular Demand Types," Mathematics of Operations Research, INFORMS, vol. 51(1), pages 829-851, January.
    8. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    9. Ingebretsen Carlson, Jim, 2016. "An Auction with Approximated Bidder Preferences - When an Auction has to be Quick," Working Papers 2016:12, Lund University, Department of Economics.
    10. Ozan Candogan & Asuman Ozdaglar & Pablo A. Parrilo, 2015. "Iterative Auction Design for Tree Valuations," Operations Research, INFORMS, vol. 63(4), pages 751-771, August.
    11. Eickhoff, Katharina & Neuwohner, Meike & Peis, Britta & Rieken, Niklas & Vargas Koch, Laura & Végh, Lázló A., 2025. "Faster dynamic auctions via polymatroid sum," LSE Research Online Documents on Economics 127980, London School of Economics and Political Science, LSE Library.
    12. Andersson, Tommy & Erlanson, Albin, 2013. "Multi-item Vickrey–English–Dutch auctions," Games and Economic Behavior, Elsevier, vol. 81(C), pages 116-129.
    13. Jim Ingebretsen Carlson, 2020. "A speedy auction using approximated bidders’ preferences," Annals of Operations Research, Springer, vol. 288(1), pages 65-93, May.
    14. De Liu & Adib Bagh, 2020. "Preserving Bidder Privacy in Assignment Auctions: Design and Measurement," Management Science, INFORMS, vol. 66(7), pages 3162-3182, July.
    15. Lamy, Laurent, 2012. "On minimal ascending auctions with payment discounts," Games and Economic Behavior, Elsevier, vol. 75(2), pages 990-999.
    16. Ioannis Petrakis & Georg Ziegler & Martin Bichler, 2013. "Ascending Combinatorial Auctions with Allocation Constraints: On Game Theoretical and Computational Properties of Generic Pricing Rules," Information Systems Research, INFORMS, vol. 24(3), pages 768-786, September.
    17. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    18. Laurent Lamy, 2007. "The Ausubel-Milgrom Proxy Auction with Final Discounts," Working Papers 2007-25, Center for Research in Economics and Statistics.
    19. Martin Bichler & Pasha Shabalin & Georg Ziegler, 2013. "Efficiency with Linear Prices? A Game-Theoretical and Computational Analysis of the Combinatorial Clock Auction," Information Systems Research, INFORMS, vol. 24(2), pages 394-417, June.
    20. Zaifu Yang & Jingsheng Yu, 2024. "An Efficient and General Ascending Menu Auction under Budget Constraints," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 9(1), pages 105-130, December.

    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:arx:papers:2605.01715. 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: arXiv administrators (email available below). General contact details of provider: https://arxiv.org/ .

    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.