Résumé en anglais

Negotiation over resources in multiagent systems is a timely and fruitful area of ongoing research. However, the prohibitively high complexity of the task of identifying rational deals, i.e. deals that are beneficial for all participants, currently hinders the successful transfer of theoretical results to practical applications. To address this issue, we propose several protocols designed to tame the complexity of negotiation by exploiting structural properties of the utility functions used by agents to model their preferences over alternative bundles of resources. In particular, we consider domains where utility functions are k-additive (that is, synergies between different resources are restricted to bundles of at most k items) and “tree- structured” in the sense that the bundles for which there are synergies do not overlap. We show how protocols exploiting these properties can enable drastically simplified negotiation processes.