Market Mechanisms for Agent Coordination

Sven Koenig

U. of Southern California


In this talk, I will give an overview of our research on market mechanisms for the allocation of resources in cooperative domains. As example, I will use exploration tasks where a team of mobile robots needs to visit a number of given targets in known or partially unknown terrain. An important characteristic of these multi-robot routing tasks is that the assignment of targets to robots can turn out to be suboptimal as the robots gain more information about the terrain. Auctions promise to assign and re-assign targets to robots efficiently in terms of both the required amount of computation and communication since information is compressed into numeric bids that the robots can compute in parallel. I will discuss the advantages and disadvantages of different auction mechanisms, including recent theoretical results that show that sequential single-item auctions can provide constant factor performance guarantees in known terrain even though they run in polynomial time. Time permitting, I will also discuss generalizations of sequential single-item auctions, such as sequential single-item auctions with bundles.

This is joint work with D. Kempe, P. Keskinocak, M. Lagoudakis, V. Markakis, A. Meyerson, C. Tovey and our students.
Maintained by: Fei Sha