Diffusion and Auction on Graphs
This work addresses resource allocation in online social and economic networks, offering a novel perspective for auction design, though it appears incremental as it builds upon existing diffusion mechanisms.
The paper tackles the classic auction problem by expanding it to social graphs, introducing a new class of incentive-compatible mechanisms that encourage information diffusion, leading to significant improvements in both seller revenue and allocation efficiency compared to the Vickrey auction.
Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller's revenue and the allocation efficiency, are generally conflicting in auction design. For the first time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentive-compatible and also promote all buyers to diffuse the auction information to others, whereby both the seller's revenue and the allocation efficiency are significantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efficient and optimal auction design and could be applied into the prevalent online social and economic networks.