Nash Welfare Allocation Problems: Concrete Issues

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. Many counter-examples describe the pitfalls of this resolution. 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.