Bien-être de Nash: enjeux et difficultés pour une société d'agents

L'allocation optimale de m ressources entre n agents est un problème d'IA important pour la négociation automatique. La question centrale est de savoir comment les agents doivent interagir afin d'induire une allocation de ressources socialement optimale pour la société. Il existe dans la littérature de nombreuses propositions permettant d'évaluer la valeur du bienêtre de la société en fonction du bien-être de ses membres, en général évaluée dans ce cadre à l'aide d'une fonction d'utilité. Parmi ces propositions, le bien-être de Nash bénéficie de bonnes propriétés pour une société d'agents égalitaire. Il garantit une distribution équitable des ressources aux agents tout en respectant leurs préférences. On peut alors s'étonner que l'évaluation du bien-être collectif à l'aide de la fonction de Nash soit si peu utilisée en pratique. Dans un premier temps, cet article illustre par de nombreux contre-exemples les difficultés liées au calcul de la valeur optimale du bien-être de Nash, difficultés qui expliquent sans doute sa faible utilisation pratique. Dans un second temps, nous décrivons notre solution distribuée s'appuyant sur des comportements d'agents, et les résultats obtenus sur des instances difficiles que notre approche “anytime” est jusqu'à présent seule à résoudre efficacement. The allocation of m resources between n agents is an AI problem with a great practical interest for automated trading. The general question is how to configure the behavior of bargaining agents to induce a socially optimal allocation. The literature contains many proposals for calculating a social welfare but the Nash welfare seems to be the one which has the most interesting properties for a fair agent society. It guarantees that all resources are fairly distributed among agents respecting their own preferences. This article shows first that the computation of this welfare is a difficult problem, contrary to common intuition, illustrated by many counterexamples. In a second step, we describe our distributed multi-agent solution based on a specific agent's behavior and the results we get on difficult instances. We finally claim that this anytime solution is the only one able to effectively address this problem of obvious practical interest.