Network Extenality and Mechanism Design

Abstract

\abstract{\em Mechanism design} studies optimization problems taking into accounts of the selfish agents. {\em Network externality} is the effect a consumer receives from other consumers of the same good. This effect can be negative or positive. We first consider several mechanism design problems under the network externality assumption. The externality model used in this dissertation is more general than the widely used cardinality based model. In particular the network we consider in this dissertation is a graph, which is not necessarily complete. Our goal is to design {\em truthful} mechanisms to maximize the seller's revenue. Our main results under the network externality utility model are several optimal or near optimal mechanisms for {\em digital goods auctions}. To do so we invent several novel approximation schemes as well as applying results from the {\em approximation algorithm} literature. In particular when the agents exhibit negative network externality, we first model the problem as a two staged {\em pricing game}. We then show that the pricing game is an exact {\em potential game} which always admits a pure {\em Nash Equilibrium}. We then study the {\em best} and {\em worst} Nash Equilibrium in this game in terms of the revenue. We show two positive results. For the best Nash Equilibrium we show a $2$-approximation to the maximum revenue on bipartite graphs. For the worst Nash Equilibrium we use the notion of a {\em $\delta$-relaxed} equilibrium. In the sense that the prices for the same type of agents are within $\delta$ factor of each other. We accompany our positive results with matching hardness results. On the other hand, when the agents exhibit positive network externality, we take the {\em Myersonian} approach. We first give a complete characterization for all the truthful mechanisms. Using this characterization we present a truthful mechanism which achieves the optimal expected revenue among all the truthful mechanisms when the prior distributions of the agents are {\em independent} and {\em regular}. We also show near optimal mechanisms when the prior distributions are possibly {\em correlated}. {\em Prior-free} auctions can approximate meaningful benchmarks fornon-identical bidders only when sufficient qualitative informationabout the bidder asymmetry is publicly known.We consider digital goods auctions where there is a {\emtotal ordering} of the bidders that is known to the seller,where earlier bidders are in some sense thought to have highervaluations. We definean appropriate revenue benchmark: the maximum revenue that can beobtained from a bid vector using prices that are nonincreasing in thebidder ordering and bounded above by the second-highest bid. This {\em monotone-price benchmark} is always as large as the well-knownfixed-price benchmark, so designing prior-free auctions withgood approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmarksatisfies a very strong guarantee: it is, in particular, simultaneouslynear-optimal for essentially every {\em Bayesian} environment in which bidders'valuation distributions have nonincreasing monopoly prices, or inwhich the distribution of each bidder stochastically dominates thatof the next. Even when there is no distribution over bidders'valuations, such an auction still provides a quantifiableinput-by-input performance guarantee. We design a simple $O(1)$-competitive prior-freeauction for digital goods with ordered bidders.