Computing Publications

Publications Home » Egalitarian Allocations of Indivi...

Egalitarian Allocations of Indivisible Resources: Theory and Computation

Paul-Amaury Matt, Francesca Toni

Conference or Workshop Paper
10th International Workshop on Cooperative Informatio n Agents(CIA 2006)
10th International Workshop on Cooperative Informatio n Agents(CIA 2006)
September, 2006
Springer Verlag

We present a mechanism for collaboration and coordination amongst agents in multi-agent societies seeking social equity. This mechanism allows to compute egalitarian allocations of indivisible resources to agents, reached via progressive revisions of social consensus. Egalitarian allocations are allocations with maximal egalitarian social welfare, where the egalitarian social welfare is given by the minimum worth (utility) assigned by agents to the resources they are given by the allocation. Egalitarian allocations are useful in a number of applications of multi-agent systems, e.g. service agents, satellite earth observation and agent oriented/holonic manufacturing systems. The mechanism we propose is distributed amongst the agents, and relies upon an incremental construction whereby agents join progressively in, forcing a revision of the current set of agreements amongst the prior agents. The mechanism uses search trees and a reduction operator simplifying the search for egalitarian allocations. We finally show how to reduce the negotiation time using social order-based coordination mechanisms and make agents find consensus efficiently using well-suited resource-preference orders.

PDF of full publication (200 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.