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

Strategyproofness and Monotone Allocation of Auction in Social Networks

Author

Listed:
  • Yuhang Guo
  • Dong Hao
  • Bin Li
  • Mingyu Xiao
  • Bakh Khoussainov

Abstract

Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand present unexpected difficulties, and all pioneering researches fail to be strategyproof. For the first time in this field, we identify two categories of monotone allocation rules on networks: Invitation-Depressed Monotonicity (ID-MON) and Invitation-Promoted Monotonicity (IP-MON). They encompass all existing allocation rules of network auctions as specific instances. For any given ID-MON or IP-MON allocation rule, we characterize the existence and sufficient conditions for the strategyproof payment rules, and show that among all such payment rules, the revenue-maximizing one exists and is computationally feasible. With these results, the obstacle of combinatorial network auction with single-minded bidders is now resolved.

Suggested Citation

  • Yuhang Guo & Dong Hao & Bin Li & Mingyu Xiao & Bakh Khoussainov, 2025. "Strategyproofness and Monotone Allocation of Auction in Social Networks," Papers 2507.14472, arXiv.org.
    • Handle: RePEc:arx:papers:2507.14472
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    2. Jeong, Seungwon (Eugene) & Lee, Joosung, 2024. "The groupwise-pivotal referral auction: Core-selecting referral strategy-proof mechanism," Games and Economic Behavior, Elsevier, vol. 143(C), pages 191-203.
    3. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    4. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    5. Rochet, Jean-Charles, 1987. "A necessary and sufficient condition for rationalizability in a quasi-linear context," Journal of Mathematical Economics, Elsevier, vol. 16(2), pages 191-200, April.
    6. Qi Shi & Dong Hao, 2021. "Social Sourcing: Incorporating Social Networks Into Crowdsourcing Contest Design," Papers 2112.02884, arXiv.org, revised Nov 2022.
    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. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    2. Carbajal, Juan Carlos & Ely, Jeffrey C., 2013. "Mechanism design without revenue equivalence," Journal of Economic Theory, Elsevier, vol. 148(1), pages 104-133.
    3. Heydenreich, B. & Mishra, D. & Müller, R.J. & Uetz, M.J., 2008. "Optimal mechanisms for single machine scheduling," Research Memorandum 033, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    4. Georgiou, Konstantinos & Swamy, Chaitanya, 2019. "Black-box reductions for cost-sharing mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 17-37.
    5. Vijay Krishna & Motty Perry, 1997. "Efficient Mechanism Design," Game Theory and Information 9703010, University Library of Munich, Germany, revised 28 Apr 1998.
    6. Hartline, Jason D. & Kleinberg, Robert & Malekian, Azarakhsh, 2015. "Bayesian incentive compatibility via matchings," Games and Economic Behavior, Elsevier, vol. 92(C), pages 401-429.
    7. Bin Li & Dong Hao & Dengji Zhao, 2020. "Incentive-Compatible Diffusion Auctions," Papers 2001.06975, arXiv.org, revised Apr 2020.
    8. Tim Roughgarden & Inbal Talgam-Cohen, 2018. "Approximately Optimal Mechanism Design," Papers 1812.11896, arXiv.org, revised Aug 2020.
    9. Bergemann, Dirk & Pavan, Alessandro, 2015. "Introduction to Symposium on Dynamic Contracts and Mechanism Design," Journal of Economic Theory, Elsevier, vol. 159(PB), pages 679-701.
    10. Michael Curry & Tuomas Sandholm & John Dickerson, 2022. "Differentiable Economics for Randomized Affine Maximizer Auctions," Papers 2202.02872, arXiv.org.
    11. Archer, Aaron & Kleinberg, Robert, 2014. "Truthful germs are contagious: A local-to-global characterization of truthfulness," Games and Economic Behavior, Elsevier, vol. 86(C), pages 340-366.
    12. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Revenue-Optimal Efficient Mechanism Design with General Type Spaces," Papers 2505.13687, arXiv.org.
    13. Kos, Nenad & Messner, Matthias, 2013. "Extremal incentive compatible transfers," Journal of Economic Theory, Elsevier, vol. 148(1), pages 134-164.
    14. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    15. Song, Yangwei, 2018. "Efficient Implementation with Interdependent Valuations and Maxmin Agents," Rationality and Competition Discussion Paper Series 92, CRC TRR 190 Rationality and Competition.
    16. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    17. 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.
    18. Corchón, Luis C., 2008. "The theory of implementation : what did we learn?," UC3M Working papers. Economics we081207, Universidad Carlos III de Madrid. Departamento de Economía.
    19. Debasis Mishra & Abdul Quadir, 2012. "Deterministic single object auctions with private values," Discussion Papers 12-06, Indian Statistical Institute, Delhi.
    20. Dirk Bergemann & Alessandro Pavan, 2015. "Introduction to JET Symposium Issue on "Dynamic Contracts and Mechanism Design"," Cowles Foundation Discussion Papers 2016, Cowles Foundation for Research in Economics, Yale University.

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