Repeated Stochastic Coalition Formation : representations and algorithmic approaches

Coalition formation is a cooperative game theory framework in which a set of agents, required to perform implicit or explicit tasks, must be divided into subgroups (called coalitions), according to collective criteria and a utility function describing the utility of each coalition. This is equivalent to a problem of partitioning the set of agents. The classic problem is to find a coalition structure (i.e. partitioning) that maximizes social welfare (sum of the utilities generated by the coalitions). A number of algorithmic approaches exist, based on the exploration of a representation of the solution space, in the form of an exhaustive lattice or integer partitions. However, the classical approach to coalition formation assumes that agents have perfect knowledge of the utilities of coalitions, and that these are deterministic, which is not representative of the actual application problems we may encounter.

We are therefore interested in exploring algorithmic solutions for a stochastic and repeated context of coalition formation, where agents have no a priori knowledge of utilities, which are now stochastic. In this context, classical representations (lattices, integer partitions) and algorithms show limitations. We are exploring approaches based on Monte-Carlo tree search methods, as well as the search for a suitable representation.