Network Extenality and Mechanism Design

Mechanism design studies optimization problems taking into accounts of the selfish agents. 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 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 digital goods auctions. To do so we invent several novel approximation schemes as well as applying results from the approximation algorithm literature. In particular when the agents exhibit negative network externality, we first model the problem as a two staged pricing game. We then show that the pricing game is an exact potential game which always admits a pure Nash Equilibrium. We then study the best and 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 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 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 independent and regular. We also show near optimal mechanisms when the prior distributions are possibly correlated..;Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark, so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders' valuations, such an auction still provides a quantifiable input-by-input performance guarantee. We design a simple O(1)-competitive prior-free auction for digital goods with ordered bidders.