Yuan Fang: Multi-unit Auction over a Social Network

Abstract

Diffusion auction is a business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. In this study, we focus on designing mechanisms for multi-unit diffusion auctions. Despite several attempts at this problem, existing mechanisms are unsatisfactory in one way or another. In particular, incentive compatibility seems to be hard to guarantee when a global diffusion tree structure is used to guide allocation. In this paper, we propose MUDA-1 and MUDA-m for single-demand and multi-demand cases of this problem, respectively. Our mechanism are the first multi-unit diffusion auction that is incentive compatible, individual rational, non-deficit and IDM-competitive. This closes the gap left open by the previous work. We also empirically analyse the effects of different graph exploration schemes to the auction outcomes.