Resource Allocation Problems on Networks - Maximizing Social Welfare using an Agent-based Approach

Abstract

Numerous applications can be formulated as an instance of resource allocation problems. Different kinds of solving techniques have been investigated, but the theoretical results cannot always be applied in practice due to inappropriate assumptions. Indeed, in these studies, agents are most of the time omniscient and/or have complete communication abilities. These hypotheses are not satisfied real life applications. practice. We propose in this paper a distributed mechanism leading to optimal solutions with respect to a more realistic environment. Agents only have limited perceptions and knowledge. Using local negotiations, they elaborate themselves optimal allocations, which can be viewed as emergent phenomena. We show that negotiations between individually rational agents lead to sub-optimal states in the society, and we propose a more suitable decision-making criterion, the sociability, leading to socially optimal solutions. Our method provides a sequence of transactions leading to optimal allocations, according to any communication networks, when four different welfare objectives are considered.