IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2502.08412.html
   My bibliography  Save this paper

Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely

Author

Listed:
  • Yan Dai
  • Moise Blanchard
  • Patrick Jaillet

Abstract

We study a repeated resource allocation problem with strategic agents where monetary transfers are disallowed and the central planner has no prior information on agents' utility distributions. In light of Arrow's impossibility theorem, acquiring information about agent preferences through some form of feedback is necessary. We assume that the central planner can request powerful but expensive audits on the winner in any round, revealing the true utility of the winner in that round. We design a mechanism achieving $T$-independent $O(K^2)$ regret in social welfare while requesting $O(K^3 \log T)$ audits in expectation, where $K$ is the number of agents and $T$ is the number of rounds. We also show an $\Omega(K)$ lower bound on the regret and an $\Omega(1)$ lower bound on the number of audits when having low regret. Algorithmically, we show that incentive-compatibility can be mostly enforced with an accurate estimation of the winning probability of each agent under truthful reporting. To do so, we impose future punishments and introduce a *flagging* component, allowing agents to flag any biased estimate (we show that doing so aligns with individual incentives). On the technical side, without monetary transfers and distributional information, the central planner cannot ensure that truthful reporting is exactly an equilibrium. Instead, we characterize the equilibrium via a reduction to a simpler *auxiliary game*, in which agents cannot strategize until late in the $T$ rounds of the allocation problem. The tools developed therein may be of independent interest for other mechanism design problems in which the revelation principle cannot be readily applied.

Suggested Citation

  • Yan Dai & Moise Blanchard & Patrick Jaillet, 2025. "Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely," Papers 2502.08412, arXiv.org.
  • Handle: RePEc:arx:papers:2502.08412
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Canice Prendergast, 2017. "How Food Banks Use Markets to Feed the Poor," Journal of Economic Perspectives, American Economic Association, vol. 31(4), pages 145-162, Fall.
    2. Hervé Moulin, 2002. "The proportional random allocation of indivisible units," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 19(2), pages 381-413.
    3. Heidrun C. Hoppe & Benny Moldovanu & Aner Sela, 2009. "The Theory of Assortative Matching Based on Costly Signals," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 76(1), pages 253-281.
    4. Santiago R. Balseiro & Haihao Lu & Vahab Mirrokni, 2023. "The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems," Operations Research, INFORMS, vol. 71(1), pages 101-119, January.
    5. Miralles, Antonio, 2012. "Cardinal Bayesian allocation mechanisms without transfers," Journal of Economic Theory, Elsevier, vol. 147(1), pages 179-206.
    6. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    7. Kris Johnson & David Simchi-Levi & Peng Sun, 2014. "Analyzing Scrip Systems," Operations Research, INFORMS, vol. 62(3), pages 524-534, June.
    8. Shipra Agrawal & Zizhuo Wang & Yinyu Ye, 2014. "A Dynamic Near-Optimal Algorithm for Online Linear Programming," Operations Research, INFORMS, vol. 62(4), pages 876-890, August.
    9. Satterthwaite, Mark Allen, 1975. "Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions," Journal of Economic Theory, Elsevier, vol. 10(2), pages 187-217, April.
    10. Condorelli, Daniele, 2012. "What money canʼt buy: Efficient mechanism design with costly signals," Games and Economic Behavior, Elsevier, vol. 75(2), pages 613-624.
    11. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    12. Matthew O Jackson & Hugo F Sonnenschein, 2007. "Overcoming Incentive Constraints by Linking Decisions -super-1," Econometrica, Econometric Society, vol. 75(1), pages 241-257, January.
    13. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    14. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    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. Moise Blanchard & Patrick Jaillet, 2024. "Near-Optimal Mechanisms for Resource Allocation Without Monetary Transfers," Papers 2408.10066, arXiv.org.
    2. Ezzat Elokda & Saverio Bolognani & Andrea Censi & Florian Dorfler & Emilio Frazzoli, 2022. "A self-contained karma economy for the dynamic allocation of common resources," Papers 2207.00495, arXiv.org, revised May 2023.
    3. Mizukami, Hideki & Saijo, Tatsuyoshi & Wakayama, Takuma, 2003. "Strategy-Proof Sharing," Working Papers 1170, California Institute of Technology, Division of the Humanities and Social Sciences.
    4. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    5. Maskin, Eric & Sjostrom, Tomas, 2002. "Implementation theory," Handbook of Social Choice and Welfare,in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 5, pages 237-288 Elsevier.
    6. Philippe Jehiel & Laurent Lamy, 2018. "A Mechanism Design Approach to the Tiebout Hypothesis," Journal of Political Economy, University of Chicago Press, vol. 126(2), pages 735-760.
    7. repec:cte:werepe:we081207 is not listed on IDEAS
    8. Debasis Mishra & Abdul Quadir, 2012. "Deterministic single object auctions with private values," Discussion Papers 12-06, Indian Statistical Institute, Delhi.
    9. 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.
    10. Kim, Semin, 2017. "Ordinal versus cardinal voting rules: A mechanism design approach," Games and Economic Behavior, Elsevier, vol. 104(C), pages 350-371.
    11. Philippe Jehiel & Moritz Meyer-ter-Vehn & Benny Moldovanu & William R. Zame, 2006. "The Limits of ex post Implementation," Econometrica, Econometric Society, vol. 74(3), pages 585-610, May.
    12. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    13. Ning Chen & Nick Gravin & Pinyan Lu, 2014. "Truthful Generalized Assignments via Stable Matching," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 722-736, August.
    14. Kwiek, Maksymilian, 2014. "Efficient voting with penalties," Discussion Paper Series In Economics And Econometrics 1419, Economics Division, School of Social Sciences, University of Southampton.
    15. Duygu Yengin, 2017. "No-envy and egalitarian-equivalence under multi-object-demand for heterogeneous objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 81-108, January.
    16. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2023. "Balanced VCG mechanisms for sequencing problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(1), pages 35-46, January.
    17. Jehiel, Philippe & Meyer-ter-Vehn, Moritz & Moldovanu, Benny, 2012. "Locally robust implementation and its limits," Journal of Economic Theory, Elsevier, vol. 147(6), pages 2439-2452.
    18. Ohseto, Shinji, 2005. "Strategy-proof assignment with fair compensation," Mathematical Social Sciences, Elsevier, vol. 50(2), pages 215-226, September.
    19. Thierry Marchant & Debasis Mishra, 2015. "Mechanism design with two alternatives in quasi-linear environments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(2), pages 433-455, February.
    20. Joseph Y. Halpern, 2007. "Computer Science and Game Theory: A Brief Survey," Papers cs/0703148, arXiv.org.
    21. Josheski Dushko & Karamazova Elena, 2021. "Auction theory and a note on game mechanisms," Croatian Review of Economic, Business and Social Statistics, Sciendo, vol. 7(1), pages 43-59, May.

    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:2502.08412. 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: http://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.