  The auction of a single indivisible item is one of the most celebrated
problems in mechanism design with transfers. Despite its simplicity, it
provides arguably the cleanest and most insightful results in the literature.
When the information that the auction is running is available to every
participant, Myerson [20] provided a seminal result to characterize the
incentive-compatible auctions along with revenue optimality. However, such a
result does not hold in an auction on a network, where the information of the
auction is spread via the agents, and they need incentives to forward the
information. In recent times, a few auctions (e.g., [13, 18]) were designed
that appropriately incentivized the intermediate nodes on the network to
promulgate the information to potentially more valuable bidders. In this paper,
we provide a Myerson-like characterization of incentive-compatible auctions on
a network and show that the currently known auctions fall within this class of
randomized auctions. We then consider a special class called the referral
auctions that are inspired by the multi-level marketing mechanisms [1, 6, 7]
and obtain the structure of a revenue optimal referral auction for i.i.d.
bidders. Through experiments, we show that even for non-i.i.d. bidders there
exist auctions following this characterization that can provide a higher
revenue than the currently known auctions on networks.
