Algorithms for Auctions with budget constraints
ABSTRACT:
Inspired by Internet ad auctions, we study the following budgeted
allocation problem: We are given a set of m indivisible items and n
agents; each agent i is willing to pay b_ij for the item j and has a
maximum overall budget of B_i. The goal is to find an allocation of items
to the agents so as to maximize the total revenue.
In this talk, I will briefly survey our recent results on designing
approximation algorithms and truthful mechanisms for the above problem,
and analyzing its computational complexity. Then, I will describe in
detail one of the algorithms.
BIO:
Gagan Goel is currently a postdoc fellow at Georgia Tech. He got his Ph.D
in Algorithms, Combinatorics and Optimization (ACO) from Georgia Tech in
Aug 2009, and B.Tech in Computer Science from Indian Institute of
Technolgy, Delhi in 2004. His research interests lie in algorithmic game
theory, with focus on problems related to optimization, mechanism design,
and computing equilibrium for various market models.