Improving Optimality of n Agent Envy-Free Divisions

摘要

Division of a resource among multiple agents is a frequent problem in multiagent systems and fair, efficient, and decentralized allocation procedures are highly valued. A division of a good is envy-free when every agent believes that its share is not less than anyone else's share by its own estimate. As envy-free procedures are not efficient (in the sense of Pareto optimality) we have previously worked on improving the efficiency of such envy-free division procedures among two agents using models of other agents' utility functions. Though guaranteed envy-free division procedures are available for small number of agents, only approximately envy-free procedures are available for division of a good among an arbitrary number of agents. In this paper, we present an approach by which the outcome of any such approximate algorithms for arbitrary n, or guaranteed algorithms for small number of agents, can be improved in terms of optimality. We propose a two-stage protocol where the first stage identifies possible beneficial exchanges, and the second stage chooses the maximal set of such exchanges that is still envy-free. We map the second stage into a matching problem and present a graph-theoretic algorithm that improves the efficiency of the initial allocations while maintaining the envy-free property.