Multi-agent Reinforcement Learning for Decentralized Coalition Formation Games

We study the application of multi-agent reinforcement learning for game-theoretical problems. In particular, we are interested in coalition formation problems and their variants such as hedonic coalition formation games (also called hedonic games), matching (a common type of hedonic game), and coalition formation for task allocation. We consider decentralized multi-agent systems where autonomous agents inhabit an environment without any prior knowledge of other agents or the system. We also consider spatial formulations of these problems. Most of the literature for coalition formation problems does not consider these formulations of the problems because it increases computational complexity significantly. We propose novel decentralized heuristic learning and multi-agent reinforcement learning (MARL) approaches to train agents, and we use game-theoretic evaluation criteria such as optimality, stability, and indices like Shapley value. A coalition formation game is a cooperative game in which agents form groups, or coalitions, based on their preferences. Most of the previous approaches for different types of coalition formation games have been centralized, assuming the presence of the central agency to control agents. However, this assumption is infeasible for many real-world scenarios. In our work, we model the variants of coalition formation problem as decentralized multi-agent systems and train autonomous agents to learn behavior strategies using novel decentralized learning and MARL approaches. Moreover, all the agents are autonomous, very much like most of the real-world scenarios. We focus on the three main variants of coalition formation game: Hedonic coalition formation games, Matching problems and, Coalition formation for task allocation. Hedonic games have applications in team formation and social group formation where agents can have preferences over coalitions. Matching, which is a variant of hedonic games, finds application in problems like matching between workers-employers, students-colleges, residentshospitals, etc. Several real-world scenarios like robot teams, rescue teams, merger of organizations, inter-organization team formation can be characterized as a coalition formation for task allocation problem. As we model the problems as decentralized multi-agent systems with fully autonomous agents, challenges arise due