Characterizations of Network Auctions and Generalizations of VCG

With the growth of networks, promoting products through social networks has become an important problem. For auctions in social networks, items are needed to be sold to agents in a network, where each agent can bid and also diffuse the sale information to her neighbors. Thus, the agents' social relations are intervened with their bids in the auctions. In network auctions, the classical VCG mechanism fails to retain key properties. In order to better understand network auctions, in this paper, we characterize network auctions for the single-unit setting with respect to IR, WBB, IC, SWM, and other properties. For example, we present sufficient conditions for mechanisms to be social welfare maximizing and (weakly) incentive compatible. With the help of these properties and new concepts such as rewards, participation rewards, and so on, we show how to design SWM mechanisms to satisfy IC as much as possible, and IC mechanisms to maximize the revenue. Our results provide insights into understanding auctions in social networks.