Distributed multiagent resource allocation in diminishing marginal return domains

We consider a multiagent resource allocation domain where the marginal production of each resource is diminishing. A set of identical, self-interested agents requires access to sharable resources in the domain. We present a distributed and random allocation procedure, and demonstrate that the allocation converges to the optimal in terms of utilitarian social welfare. The procedure is based on direct interaction among the agents and resource owners (without the use of a central authority). We then consider potential strategic behavior of the self-interested agents and resource owners, and show that when both act rationally and the domain is highly competitive for the resource owners, the convergence result still holds. The optimal allocation is arrived at quickly; given a setting with k resources and n agents, we demonstrate that the expected number of timesteps to convergence is O(k ln n), even in the worst case, where the optimal allocation is extremely unbalanced. Our allocation procedure has advantages over a mechanism design approach based on Vickrey-Clarke-Groves (VCG) mechanisms: it does not require the existence of a central trusted authority, and it fully distributes the utility obtained by the agents and resource owners (i.e., it is strongly budget balanced).