Mechanisms with referrals: VCG Mechanisms and Multilevel Mechanisms

We study mechanisms for environments in which only a part of agents are directly connected to a mechanism designer and the other agents can participate in a mechanism only through the connected agents' referrals. Agents' network connections are private information, which can be strategically concealed by avoiding making referrals; while the mechanism designer wants to elicit the agents' private information about both payoff types and network connections. The set of feasible allocations is endogenously determined by the actual participants induced by referrals.
As an efficient mechanism, we generalize and characterize a VCG mechanism. It is incentive compatible and individually rational if the social welfare is monotone in participants, but it generically runs deficit as it requires too much compensation for referrals. Alternatively as a budget surplus mechanism, we introduce a multi-level mechanism, in which each agent is compensated by the agents who would not be able to participate without his referrals. Under a multilevel mechanism, we show that fully referring one's acquaintances is a dominant strategy and agents have no incentive to under-report their payoff type if the social welfare is monotone and submodular. As applications, a single-item auction and a public good provision game are studied.