  Many multi-agent coordination problems can be represented as DCOPs. Motivated
by task allocation in disaster response, we extend standard DCOP models to
consider uncertain task rewards where the outcome of completing a task depends
on its current state, which is randomly drawn from unknown distributions. The
goal of solving this problem is to find a solution for all agents that
minimizes the overall worst-case loss. This is a challenging problem for
centralized algorithms because the search space grows exponentially with the
number of agents and is nontrivial for standard DCOP algorithms we have. To
address this, we propose a novel decentralized algorithm that incorporates
Max-Sum with iterative constraint generation to solve the problem by passing
messages among agents. By so doing, our approach scales well and can solve
instances of the task allocation problem with hundreds of agents and tasks.
