دانلود رایگان مقاله تخصیص عادلانه توزیع شده در محصولات غیر قابل تقسیم

Abstract

Distributed mechanisms for allocating indivisible goods are mechanisms lacking central control, in which agents can locally agree on deals to exchange some of the goods in their possession. We study convergence properties for such distributed mechanisms when used as fair division procedures. Specifically, we identify sets of assumptions under which any sequence of deals meeting certain conditions will converge to a proportionally fair allocation and to an envy-free allocation, respectively. We also introduce an extension of the basic framework where agents are vertices of a graph representing a social network that constrains which agents can interact with which other agents, and we prove a similar convergence result for envy-freeness in this context. Finally, when not all assumptions guaranteeing envy-freeness are satisfied, we may want to minimise the degree of envy exhibited by an outcome. To this end, we introduce a generic framework for measuring the degree of envy in a society and establish the computational complexity of checking whether a given scenario allows for a deal that is beneficial to every agent involved and that will reduce overall envy.

7. Conclusion

In this paper we have addressed the problem of designing mechanisms to fairly allocate indivisible goods to a set of agents. While previously this question has been mostly investigated in the context of assignment problems, in which agents can receive at most one such good [6], the domain considered here is combinatorial: agents may receive more than one object and have preferences over the possible sets of goods that they may receive. Unlike for other proposals in which payments ensuring fairness are arranged for a given efficient allocation [33,34], the approach advocated here is distributed: agents locally implement mutually beneficial reallocations of goods (furthering the efficiency of the allocation), while the payment rule updates the payments after each deal in a way that ensures fairness at the end of the process. That is, in this approach the quests for efficiency and fairness are intimately interleaved. The first contribution of this paper has been to provide simple conditions under which any sequence of such reallocative steps can be guaranteed to converge to a fair outcome. The fairness criteria considered are proportionality and envy-freeness. As the problem is combinatorial in nature, the approach necessitates that agents can potentially agree on complex deals, and the process itself can involve a large number of steps. If we assume, however, that preferences are modular (additive), then negotiation can be conducted by means of very simple deals, and the length of the process will be linearly bounded [29]. Note that the proposed mechanism never requires heavy central computation: only some simple redistribution of the social surplus (in terms of money) is performed at the global level.