Colloquia / Seminars / Industry Talks

Combinatorial auctions play a key role in Distributed Artificial Intelligence as a mechanism for efficiently allocating resources or tasks, both for cooperative and competitive scenarios. They are of particular interest in Multi-Agent Systems, especially for agent-mediated electronic commerce. The problem of solving a combinatorial auction is difficult in general, and this has lead to interest in finding efficient algorithms for useful instances. Tennenholtz introduced an approach which finds polynomial solutions for certain classes of combinatorial auctions by a reduction to graph matching problems. This talk will look at the possibilities and limits of this graph-matching approach. The talk will present new results which extend the set of known tractable combinatorial auctions identified by Tennenholtz to accommodate subadditive symmetric bids over bundles of unlimited size, certain restricted cases of asymmetric discounts over bundles, and certain restricted cases of superadditive bids. The talk will also present results on the ultimate limits of the approach, identifying classes of auctions which cannot be reduced to 2D graph matching, and classes which are NP-equivalent. The talk will conclude with a discussion of the reasons for the limitations, and the practical implications of the results.

Frank Guerin graduated with a Ph.D. from Imperial College, London, in 2002. His Ph.D. research focussed on verifiable languages for agent communication. In 2003 he joined the University of Aberdeen as a Lecturer. His current research focuses on the applications of Game Theory in Multi-Agent Systems. He is the principal investigator on a UK EPSRC funded project on "Machine Understandable Auctions", which aims to allow agents to automatically participate in electronic auctions.