IDEAS home Printed from https://ideas.repec.org/p/mnh/wpaper/37417.html
   My bibliography  Save this paper

Ex-post optimal knapsack procurement

Author

Listed:
  • Jarman, Felix
  • Meisner, Vincent

Abstract

We consider a budget-constrained mechanism designer who wants to select an optimal subset of projects to maximize her utility. Project costs are private information and the value the designer derives from their provision may vary. In this allocation problem the choice of projects - both which and how many - is endogenously determined by the mechanism. The designer faces hard ex-post constraints: The participation and budget constraint must hold for each possible outcome while the mechanism must be implementable in dominant strategies. We derive the class of optimal mechanisms that are characterized by cutoff functions. These cutoff functions exhibit properties that allow an implementation through a descending clock auction. Only in the case of symmetric projects price clocks descend synchronously such that always the cheapest projects are executed. However, the asymmetric case, where values or costs are asymmetrically distributed, features a novel tradeoff between quantity and quality. Interestingly, this tradeoff mitigates the distortion due to the informational asymmetry compared to environments where quantity is exogenous.

Suggested Citation

  • Jarman, Felix & Meisner, Vincent, 2015. "Ex-post optimal knapsack procurement," Working Papers 15-02, University of Mannheim, Department of Economics.
    • Handle: RePEc:mnh:wpaper:37417
    as

    Download full text from publisher

    File URL: https://madoc.bib.uni-mannheim.de/37417/4/expostoptimalknapsack-wp_15-02.pdf
    Download Restriction: no
    File URL: https://madoc.bib.uni-mannheim.de/38873/1/Jarman_und_Meisner_15-02.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Baron, David P & Myerson, Roger B, 1982. "Regulating a Monopolist with Unknown Costs," Econometrica, Econometric Society, vol. 50(4), pages 911-930, July.
    3. Tilman Börgers & Peter Norman, 2009. "A note on budget balance under interim participation constraints: the case of independent types," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 39(3), pages 477-489, June.
    4. Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071.
    5. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    6. Yeon-Koo Che & Ian Gale, 1998. "Standard Auctions with Financially Constrained Bidders," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 65(1), pages 1-21.
    7. de Castro, Luciano I. & de Frutos, María-Angeles, 2010. "How to translate results from auctions to procurements," Economics Letters, Elsevier, vol. 106(2), pages 115-118, February.
    8. Strausz, Roland, 2003. "Deterministic mechanisms and the revelation principle," Economics Letters, Elsevier, vol. 79(3), pages 333-337, June.
    9. Mookherjee, Dilip & Reichelstein, Stefan, 1992. "Dominant strategy implementation of Bayesian incentive compatible allocation rules," Journal of Economic Theory, Elsevier, vol. 56(2), pages 378-399, April.
    10. John Ledyard & David Porter & Randii Wessen, 2000. "A Market-Based Mechanism for Allocating Space Shuttle Secondary Payload Priority," Experimental Economics, Springer;Economic Science Association, vol. 2(3), pages 173-195, March.
    11. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    12. Luton, Richard & McAfee, R. Preston, 1986. "Sequential procurement auctions," Journal of Public Economics, Elsevier, vol. 31(2), pages 181-195, November.
    13. Alexey Kushnir, 2013. "On the equivalence between Bayesian and dominant strategy implementation: the case of correlated types," ECON - Working Papers 129, Department of Economics - University of Zurich.
    14. , & , & ,, 2011. "Revenue maximization in the dynamic knapsack problem," Theoretical Economics, Econometric Society, vol. 6(2), May.
    15. Ensthaler, Ludwig & Giebe, Thomas, 2014. "A dynamic auction for multi-object procurement under a hard budget constraint," Research Policy, Elsevier, vol. 43(1), pages 179-189.
    16. Jeffrey C. Ely & Kim-Sau Chung, 2002. "Ex-Post Incentive Compatible Mechanism Design," Discussion Papers 1339, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    17. Mu'alem, Ahuva & Nisan, Noam, 2008. "Truthful approximation mechanisms for restricted combinatorial auctions," Games and Economic Behavior, Elsevier, vol. 64(2), pages 612-631, November.
    18. Bernard Caillaud & Jacques Robert, 2005. "Implementation of the revenue-maximizing auction by an ignorant seller," Review of Economic Design, Springer;Society for Economic Design, vol. 9(2), pages 127-143, April.
    19. John William Hatfield & Fuhito Kojima, 2008. "Matching with Contracts: Comment," American Economic Review, American Economic Association, vol. 98(3), pages 1189-1194, June.
    20. Alex Gershkov & Jacob K. Goeree & Alexey Kushnir & Benny Moldovanu & Xianwen Shi, 2013. "On the Equivalence of Bayesian and Dominant Strategy Implementation," Econometrica, Econometric Society, vol. 81(1), pages 197-220, January.
    21. Ensthaler, Ludwig & Giebe, Thomas, 2014. "Bayesian optimal knapsack procurement," European Journal of Operational Research, Elsevier, vol. 234(3), pages 774-779.
    22. Alejandro M. Manelli & Daniel R. Vincent, 2010. "Bayesian and Dominant‐Strategy Implementation in the Independent Private‐Values Model," Econometrica, Econometric Society, vol. 78(6), pages 1905-1938, November.
    23. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    24. Pai, Mallesh M. & Vohra, Rakesh, 2014. "Optimal auctions with financially constrained buyers," Journal of Economic Theory, Elsevier, vol. 150(C), pages 383-425.
    25. HervÊ Moulin, 1999. "Incremental cost sharing: Characterization by coalition strategy-proofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(2), pages 279-320.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Haoran He & Yefeng Chen, 2021. "Auction mechanisms for allocating subsidies for carbon emissions reduction: an experimental investigation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(2), pages 387-430, August.
    2. Jarman, Felix & Meisner, Vincent, 2017. "Deterministic mechanisms, the revelation principle, and ex-post constraints," Economics Letters, Elsevier, vol. 161(C), pages 96-98.
    3. Saurab Chhachhi & Fei Teng, 2024. "Wasserstein Markets for Differentially-Private Data," Papers 2412.02609, arXiv.org.
    4. Paul Dütting & Vasilis Gkatzelis & Tim Roughgarden, 2017. "The Performance of Deferred-Acceptance Auctions," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 897-914, November.

    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. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    2. Arigapudi, Srinivas, 2018. "On the equivalence of Bayesian and deterministic dominant strategy implementation," Economics Letters, Elsevier, vol. 162(C), pages 37-40.
    3. Laura Doval & Vasiliki Skreta, 2022. "Mechanism Design With Limited Commitment," Econometrica, Econometric Society, vol. 90(4), pages 1463-1500, July.
    4. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    5. Erlanson, Albin & Kleiner, Andreas, 2019. "A note on optimal allocation with costly verification," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 56-62.
    6. Manea, Mihai & Maskin, Eric, 2023. "Withholding and damage in Bayesian trade mechanisms," Games and Economic Behavior, Elsevier, vol. 142(C), pages 243-265.
    7. Ensthaler, Ludwig & Giebe, Thomas, 2014. "Bayesian optimal knapsack procurement," European Journal of Operational Research, Elsevier, vol. 234(3), pages 774-779.
    8. Kushnir, Alexey, 2015. "On sufficiency of dominant strategy implementation in environments with correlated types," Economics Letters, Elsevier, vol. 133(C), pages 4-6.
    9. Goeree, Jacob K. & Kushnir, Alexey, 2016. "Reduced form implementation for environments with value interdependencies," Games and Economic Behavior, Elsevier, vol. 99(C), pages 250-256.
    10. Arve, Malin, 2014. "Procurement and predation: Dynamic sourcing from financially constrained suppliers," Journal of Public Economics, Elsevier, vol. 120(C), pages 157-168.
    11. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    12. Drexl, Moritz & Kleiner, Andreas, 2015. "Optimal private good allocation: The case for a balanced budget," Games and Economic Behavior, Elsevier, vol. 94(C), pages 169-181.
    13. Csapó, Gergely & Müller, Rudolf, 2013. "Optimal mechanism design for the private supply of a public good," Games and Economic Behavior, Elsevier, vol. 80(C), pages 229-242.
    14. Xu Lang & Zaifu Yang, 2021. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints: A Revision," Discussion Papers 21/05, Department of Economics, University of York.
    15. Long, Yan & Mishra, Debasis & Sharma, Tridib, 2017. "Balanced ranking mechanisms," Games and Economic Behavior, Elsevier, vol. 105(C), pages 9-39.
    16. Deniz Kattwinkel & Axel Niemeyer & Justus Preusser & Alexander Winter, 2023. "Mechanisms without transfers for fully biased agents," CRC TR 224 Discussion Paper Series crctr224_2023_485, University of Bonn and University of Mannheim, Germany.
    17. Xu Lang & Zaifu Yang, 2023. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints," Discussion Papers 23/02, Department of Economics, University of York.
    18. Kaplan, Todd R. & Zamir, Shmuel, 2015. "Advances in Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. Tilman Börgers, 2017. "(No) Foundations of dominant-strategy mechanisms: a comment on Chung and Ely (2007)," Review of Economic Design, Springer;Society for Economic Design, vol. 21(2), pages 73-82, June.
    20. Baisa, Brian, 2017. "Auction design without quasilinear preferences," Theoretical Economics, Econometric Society, vol. 12(1), January.

    More about this item

    Keywords

    Mechanism Design ; Knapsack ; Budget; Procurement ; Auction;
    All these keywords.

    JEL classification:

    • D02 - Microeconomics - - General - - - Institutions: Design, Formation, Operations, and Impact
    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions
    • D45 - Microeconomics - - Market Structure, Pricing, and Design - - - Rationing; Licensing
    • D87 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Neuroeconomics
    • H57 - Public Economics - - National Government Expenditures and Related Policies - - - Procurement

    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:mnh:wpaper:37417. 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: Katharina Rautenberg (email available below). General contact details of provider: https://edirc.repec.org/data/fvmande.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.