Abstract
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 incentivecompatible 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.