The Power of Swap Deals in Distributed Resource Allocation
Palestrante(s) : Anastasia Damamme (LIP6)The resource allocation setting consisting in assigning resources to several agent. We work on problems in which each agent has a unique resource and is able to exchange this resource with another agent in order to increase its satisfaction. The preferences of an agent are assumed to be defined as a linear order over resources. The top trading cycle procedure stands out as being the undisputed method of choice. It remains however a centralized procedure which may not well suited in the context of multiagent systems, where distributed coordination may be problematic. We study a simple dynamics based on rational bilateral deals. Even though the efficiency loss may be high in the worst case, we provide theoretical results and experimental evidence showing that this approach has some merits.
cedric.herpson (at) nulllip6.fr