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.

KEYWORDS:

• Coalition structure
• optimisation
• agents
• weighted graph game
• quantum annealing
• D-Wave quantum computer

Acknowledgments

This work was supported by the “Program 4, Fundamental and Border Research, Exploratory Research Projects” financed by UEFISCDI, project no. 51/2017.

Disclosure statement

No potential conflict of interest was reported by the authors.