Distributed Multiagent Resource Allocation
   in Diminishing Marginal Return Domains

Speaker: Yoram Bachrach
Date: Thursday, 21 February 2008
Time: 2pm
Place: Ross 201

Abstract:

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).

Joint work with Jeffrey S. Rosenschein.