Expressing multiagent coalition structure problems for optimisation by quantum annealing

ABSTRACT

This paper addresses the problem of finding the optimal coalition structure in a multiagent system by expressing it in a proper format that can be solved by an adiabatic quantum computer such as D-Wave. The general case with any number of agents and graphs of agent connections with arbitrary structure is considered, and a method to handle the issues that arise from mapping a weighted graph game with intersecting edges on the lattice of qubit cells is provided. A principled discussion about the parameter values and mathematical proofs for the design choices are also included.