@inproceedings{orchid2,
       booktitle = {Proc 10th Int Conf on Autonomous Agents and Multi-Agent Systems},
           title = {Bounded Decentralised Coordination over Multiple
Objectives},
          author = {Francesco Delle Fave and Ruben Stranders and Alex Rogers and Nicholas R Jennings},
            year = {2011},
           pages = {371--378},
        subjects = {Agent-based Computing, Agile Teaming},
             url = {http://www.orchid.ac.uk/eprints/2/1/bounded\%5fdecentralised\%5fcoordination.pdf},
        abstract = {We propose the bounded multi-objective max-sum algorithm
(B-MOMS), the first decentralised coordination algorithm
for multi-objective optimisation problems. B-MOMS extends
the max-sum message-passing algorithm for decentralised
coordination to compute bounded approximate solutions
to multi-objective decentralised constraint optimisation
problems (MO-DCOPs). Specifically, we prove the
optimality of B-MOMS in acyclic constraint graphs, and derive
problem dependent bounds on its approximation ratio
when these graphs contain cycles. Furthermore, we empirically
evaluate its performance on a multi-objective extension
of the canonical graph colouring problem. In so doing, we
demonstrate that, for the settings we consider, the approximation
ratio never exceeds 2, and is typically less than 1:5
for less-constrained graphs. Moreover, the runtime required
by B-MOMS on the problem instances we considered never
exceeds 30 minutes, even for maximally constrained graphs
with 100 agents. Thus, B-MOMS brings the problem of
multi-objective optimisation well within the boundaries of
the limited capabilities of embedded agents.}
}