Strategyproofness and Monotone Allocation of Auction in Social Networks
This work addresses the challenge of strategyproofness in network auctions, which is incremental as it builds on prior research by providing a general principle for allocation rules.
The paper tackles the problem of designing strategyproof auctions in social networks, where bidders must truthfully report valuations and invite neighbors, by identifying two categories of monotone allocation rules (ID-MON and IP-MON) that encompass existing rules and characterizing conditions for strategyproof payment rules, resolving the obstacle for combinatorial network auctions with single-minded bidders.
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.