Fatima-Wooldridge2018_Article_ComputingOptimalCoalitionStruc.pdf (1.2 MB)
Download file

Computing optimal coalition structures in polynomial time

Download (1.2 MB)
journal contribution
posted on 02.11.2018, 15:33 authored by Syeda FatimaSyeda Fatima, Michael Wooldridge
The optimal coalition structure determination problem is in general computationally hard. In this article, we identify some problem instances for which the space of possible coalition structures has a certain form and constructively prove that the problem is polynomial time solvable. Specifically, we consider games with an ordering over the players and introduce a distance metric for measuring the distance between any two structures. In terms of this metric, we define the property of monotonicity, meaning that coalition structures closer to the optimal, as measured by the metric, have higher value than those further away. Similarly, quasi-monotonicity means that part of the space of coalition structures is monotonic, while part of it is non-monotonic. (Quasi)-monotonicity is a property that can be satisfied by coalition games in characteristic function form and also those in partition function form. For a setting with a monotonic value function and a known player ordering, we prove that the optimal coalition structure determination problem is polynomial time solvable and devise such an algorithm using a greedy approach. We extend this algorithm to quasi-monotonic value functions and demonstrate how its time complexity improves from exponential to polynomial as the degree of monotonicity of the value function increases. We go further and consider a setting in which the value function is monotonic and an ordering over the players is known to exist but ordering itself is unknown. For this setting too, we prove that the coalition structure determination problem is polynomial time solvable and devise such an algorithm.

History

School

  • Science

Department

  • Computer Science

Published in

Autonomous Agents and Multi-Agent Systems

Citation

FATIMA, S. and WOOLDRIDGE, M., 2018. Computing optimal coalition structures in polynomial time. Autonomous Agents and Multi-Agent Systems, 33 (1-2), pp. 35–83.

Publisher

Springer Verlag © The Author(s)

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/

Acceptance date

24/10/2018

Publication date

2018-11-03

Notes

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

ISSN

1387-2532

eISSN

1573-7454

Language

en