Title: Mechanism Design in Social Networks,
Abstract: This paper studies an auction design problem for a seller to sell a commodity
in a social network, where each individual (the seller or a buyer) can only
communicate with her neighbors. The challenge to the seller is to design a
mechanism to incentivize the buyers, who are aware of the auction, to further
propagate the information to their neighbors so that more buyers will
participate in the auction and hence, the seller will be able to make a higher
revenue. We propose a novel auction mechanism, called information diffusion
mechanism (IDM), which incentivizes the buyers to not only truthfully report
their valuations on the commodity to the seller, but also further propagate the
auction information to all their neighbors. In comparison, the direct extension
of the well-known Vickrey-Clarke-Groves (VCG) mechanism in social networks can
also incentivize the information diffusion, but it will decrease the seller's
revenue or even lead to a deficit sometimes. The formalization of the problem
has not yet been addressed in the literature of mechanism design and our
solution is very significant in the presence of large-scale online social
networks.