Loading
Research Projects
On Allocations with Negative Externalities
|
Abstract
We consider the problem of a monopolist seller who wants to
sell some items to a set of buyers. The buyers are strategic, unit-demand,
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 sub-game 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 sub-polynomial 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 di erent 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 con guration for performing relaxed Nash dynamics. Finally, for
the maximum revenue Nash equilibrium, we show a 2-approximation for
bipartite graphs (without price relaxation), and complement this result
by showing that the problem is NP-Hard even on trees.
Advisor(s): Kamesh Munagala
Vincent Conitzer, John Reif