Strategyproofness and Monotone Allocation of Auction in Social Networks

Strategyproofness and Monotone Allocation of Auction in Social Networks

Yuhang Guo, Dong Hao, Bin Li, Mingyu Xiao, Bakh Khoussainov

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 3883-3890. https://doi.org/10.24963/ijcai.2025/432

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.
Keywords:
Game Theory and Economic Paradigms: GTEP: Auctions and market-based systems
Game Theory and Economic Paradigms: GTEP: Mechanism design
Multidisciplinary Topics and Applications: MTA: Economics