  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.
