Research Project
On Allocations with Negative Externalities
Speaker:  Xiaoming (Nate) Xu
xiaoming at cs.duke.edu 
Date: 
Monday, May 14, 2012 
Time: 
1:30pm  2:30pm 
Location: 
North 311, Duke 

Vincent Conitzer, John Reif 


Abstract
We consider the problem of a monopolist seller who wants to
sell some items to a set of buyers. The buyers are strategic, unitdemand,
and connected by a social network. Furthermore, the utility of a buyer
is a decreasing function of the number of neighbors who do not own the
item. In other words, they exhibit negative externalities, deriving utility
from being unique in their purchases. In this model, any xed setting of
the price induces a subgame on the buyers. We show that it is an exact
potential game which admits multiple pure Nash Equilibria. A natural
problem is to compute those pure Nash equilibria that raise the most and
least revenue for the seller. These correspond respectively to the most
optimistic and most pessimistic revenues that can be raised.
We show that the revenues of both the best and worst equilibria are hard
to approximate within subpolynomial factors. Given this hardness, we
consider a relaxed notion of pricing, where the price for the same item
can vary within a constant factor for dierent buyers. We show a 4
approximation to the pessimistic revenue when the prices are relaxed by a
factor of 4. The interesting aspect of this algorithm is that it uses a linear
programming relaxation that only encodes part of the strategic behavior
of the buyers in its constraints, and rounds this relaxation to obtain a
starting conguration for performing relaxed Nash dynamics. Finally, for
the maximum revenue Nash equilibrium, we show a 2approximation for
bipartite graphs (without price relaxation), and complement this result
by showing that the problem is NPHard even on trees.
Advisor(s): Kamesh Munagala