NSF Award CCF-1008065

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.

Mechanisms and allocations with positive network externalities (with Anand Bhalgat and Sreenivas Gollapudi) EC 12

Optimal auctions with positive network externalities.  (with Nima Haghpanah, Nicole Immorlica, and Vahab Mirrokni)  EC '11

On allocations with negative externalities. (with Sayan Bhattacharya, Janardhan Kulkarni, and Xiaoming Xu)  WINE '11

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.

Approximation algorithm for security games with costly resources. (with Sayan Bhattacharya and Vincent Conitzer)  WINE '11