  This paper studies a mechanism design problem over a network, where agents
can only participate by referrals. The Bulow-Klemberer theorem proposes that
expanding the number of participants is a more effective approach to increase
revenue than modifying the auction format. However, agents lack the motivation
to invite others because doing so intensifies competition among them. On the
other hand, misreporting social networks is also a common problem that can
reduce revenue. Examples of misreporting include Sybil attacks (an agent
pretending to be multiple bidders) and coalition groups (multiple agents
pretending to be an agent). To address these challenges, we introduce a novel
mechanism called the Truthful Referral Diffusion Mechanism (TRDM). TRDM
incentivizes agents to report their social networks truthfully, and some of
them are rewarded by the seller for improving revenue. In spite of the fact
that some agents overbid in TRDM, the revenue is fixed, and it is higher than
the revenue of any mechanism without referrals. TRDM is budget-balanced
(non-negative revenue) and generates an efficient outcome (maximized social
welfare), making it attractive for both the seller and the buyers as it
improves revenue and reward.
