7 March 2008, Computational Social Choice Seminar, Nicolas Maudet

Abstract:
When distributing the process of solving a problem, it is likely that the computational task faced by each single agent will be simpler than that of a central solving entity, but it is also likely that the communication burden of the overall process will increase. In this talk, I shall examine the case of distributed reallocative processes of indivisible goods. In this approach, agents negotiate autonomously and locally the reallocation of (some of) their resources with fellow agents, in order to improve their well-being. Having introduced different ways to measure communication complexity in this context, I will discuss more specifically the problem of determining the number of exchanges that are needed for agents to come up with a ``satisfying'' solution. Different situations will be examined, depending on (i) assumptions on agents' preference structures; (ii) the existence of various communication constraints; and finally (iii) whether we are interested in worst-case or average-case analysis. This is joint work with Yann Chevaleyre and Ulle Endriss.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle at illc.uva.nl).