Network Extenality and Mechanism Design

Loading...
Thumbnail Image

Date

2015

Authors

Xu, Xiaoming

Advisors

Munagala, Kamesh

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

365
views
409
downloads

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 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 {\em

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 {\em 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 {\em 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.

Description

Provenance

Citation

Citation

Xu, Xiaoming (2015). Network Extenality and Mechanism Design. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/9964.

Collections


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.