
Title: Algorithms and Mechanism Design for MultiAgent Systems
Time:  Monday, September 13th, 4:00pm 
Location:  Klaus Conference Room 3100 
Advisor:  Prof. Vijay Vazirani, College of Computing 
Committee:  Prof. Robin Thomas, School of Mathematics 
Prof. William Cook, School of Industrial and Systems Engineering  
Prof. Eric Vigoda, College of Computing  
Prof. MariaFlorina Balcan, College of Computing  
Reader:  Prof. MariaFlorina Balcan, College of Computing 
Abstract:
A scenario where multiple entities interact with a common environment to achieve individual and common goals can be classified as a MultiAgent System, e.g., the Internet. We study natural mathematical models of optimization problems faced in such systems by companies such as Google, Yahoo! and Microsoft. We provide approximation algorithms, online algorithms and hardness of approximation results for these problems.
Our main result is an optimal (11/e)competitive randomized algorithm for this problem. Our solution constitutes the first known generalization of the seminal work of Karp, Vazirani and Vazirani [STOC'90]. It also solves the online budgeted allocation problem when all the bids of an agent are equal, complementing the known solutions that apply when the bids are much smaller than the budgets (Mehta et al [FOCS'05] and Buchbinder et al [ESA'07]).
We present a general technique, based on maximalinrange mechanisms, that converts any capproximation nontruthful algorithm (c <= 1) for this problem into \Omega(c/log{n}) and \Omega(c)approximate truthful mechanisms which run in polynomial time and quasipolynomial time, respectively.
We consider the following fundamental problems in this framework: Combinatorial reverse auction, vertex cover, shortest path, minimum spanning tree and minimum perfect matching. We provide both algorithmic and hardness results to establish the approximability of these problems.

. . . . . . . . . . . . . .  
This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: October 30, 2011
