Optimal Coalition Structures for Probabilistically Monotone Partition Function Games

We define probabilistically monotone partition function games, a subclass of the well-known partition function games in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.

Authors

• Shaheen Fatima Loughborough University
• Michael Wooldridge University of Oxford

Keywords

• AI
• MAS
• Coalition games
• Externalities
• Optimal coalition structure