Value-based network externalities and optimal auction design

We study revenue maximization in settings where agents’ valuations exhibit positive network externalities. In our model, items have unlimited supply, and agents are unit demand. In a departure from previous literature, we assume agents have value based externalities, meaning that their valuation depends not only on their own signal, but also on the signals of other agents in their neighborhood who win the item. We give a complete characterization of ex-post incentive compatible and individually rational auctions in this setting. Using this characterization, we show that the optimal auction is in fact deterministic, and can be computed in polynomial time when the agents’ signals are independent. We further show a constant factor approximation when the signals of agents are correlated, and an optimal mechanism in this case for a constant number of bidders.

Duke Scholars

Author Kamesh Munagala Computer Science