Market Mechanisms for Agent Coordination
Sven Koenig
U. of Southern California
Abstract
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