Auction design in constrained settings
PI:
Kamesh Munagala
PostDocs: Sungjin Im
Graduate students: Sayan Bhattacharya, Janardhan Kulkarni, Xiaoming Xu
Undergrad students: Siyang Chen (2011-12)
We will consider facets of auction design that go beyond traditional
settings in economics, and are motivated by recent internet
applications. These facets include network effects on valuations of
agents, budget constraints, and the presence of uncertainty in certain
aspects of the valuations.
Auctions and Allocations with Externalities: We consider several
models of externalities in social networks. In this setting, the
valuation of any bidder or agent is affected by which of her neighbors
in the social network also own the item. This influence can be positive
(as with a trend) or negative (as with uniqueness). We study the
computational complexity of allocation, pricing, and auction design
problems in this setting. We show hardness results and present
approximation algorithms.
Game Theory: We
consider the impact of uncertainty on resource allocation in certain
kinds of security games. We present approximation algorithms for
several interesting cases.