Probability Bounds for Overlapping Coalition Formation

Probability Bounds for Overlapping Coalition Formation

Michail Mamakos, Georgios Chalkiadakis

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 331-337. https://doi.org/10.24963/ijcai.2017/47

In this work, we provide novel methods which benefit from obtained probability bounds for assessing the ability of teams of agents to accomplish coalitional tasks. To this end, our first method is based on an improvement of the Paley-Zygmund inequality, while the second and the third ones are devised based on manipulations of the two-sided Chebyshev’s inequality and the Hoeffding’s inequality, respectively. Agents have no knowledge of the amount of resources others possess; and hold private Bayesian beliefs regarding the potential resource investment of every other agent. Our methods allow agents to demand that certain confidence levels are reached, regarding the resource contributions of the various coalitions. In order to tackle real-world scenarios, we allow agents to form overlapping coalitions, so that one can simultaneously be part of a number of coalitions. We thus present a protocol for iterated overlapping coalition formation (OCF), through which agents can complete tasks that grant them utility. Agents lie on a social network and their distance affects their likelihood of cooperation towards the completion of a task. We confirm our methods’ effectiveness by testing them on both a random graph of 300 nodes and a real-world social network of 4039 nodes.
Keywords:
Agent-based and Multi-agent Systems: Coordination and cooperation
Agent-based and Multi-agent Systems: Cooperative Games
Uncertainty in AI: Uncertainty in AI