Network Extenality and Mechanism Design

<p>\abstract</p><p>{\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}. </p><p>{\em Prior-free} auctions can approximate meaningful benchmarks for</p><p>non-identical bidders only when sufficient qualitative information</p><p>about the bidder asymmetry is publicly known.</p><p>We consider digital goods auctions where there is a {\em</p><p>total ordering} of the bidders that is known to the seller,</p><p>where earlier bidders are in some sense thought to have higher</p><p>valuations. </p><p>We define</p><p>an appropriate revenue benchmark: the maximum revenue that can be</p><p>obtained from a bid vector using prices that are nonincreasing in the</p><p>bidder ordering and bounded above by the second-highest bid. </p><p>This {\em monotone-price benchmark} is always as large as the well-known</p><p>fixed-price benchmark, so designing prior-free auctions with</p><p>good approximation guarantees is only harder. </p><p>By design, an auction that approximates the monotone-price benchmark</p><p>satisfies a very strong guarantee: it is, in particular, simultaneously</p><p>near-optimal for </p><p>essentially every {\em Bayesian} environment in which bidders'</p><p>valuation distributions have nonincreasing monopoly prices, or in</p><p>which the distribution of each bidder stochastically dominates that</p><p>of the next. Even when there is no distribution over bidders'</p><p>valuations, such an auction still provides a quantifiable</p><p>input-by-input performance guarantee. We design a simple $O(1)$-competitive prior-free</p><p>auction for digital goods with ordered bidders.</p>Dissertatio