Addressing uncertainty in coalition structure and profit allocation problems through stochastic programming: insights from the collaborative transportation problem

This paper studies characteristic function games in which the characteristic function is computed by solving a set of optimization problems that reflect the dynamics of cooperation. A common assumption for these types of games is that all parameters of the optimization problems are deterministic. In practice, however, these problems are affected by several sources of uncertainty, which ultimately impact deciding which coalitions of players should form and how the players should split the benefits. We tackle this issue by modeling the coalition structure and profit allocation problem under uncertainty as a two-stage stochastic program in which the characteristic function is a discrete random vector. Our two-stage formulation works as follows. In the first stage, we address a coalition structure problem to find a partition of the set of players that maximizes, on expectation, the allocated profits and the stability of the coalition formed. In the second stage, profits are allocated as a recourse action to compensate for the undesirable effects of uncertainty over the coalitions formed in the first stage. Using the collaborative transportation problem as a case study, we show how demand uncertainty defines a random characteristic vector and how its distribution impacts the coalitions formed. For this problem, we provide theoretical insights, show the detrimental effects of coordination costs on collaboration, and assess the performance of the stochastic programming formulation. We also tackle large-size instances of this problem, showing the dominance of the Multi-cut L-shaped algorithm over state-of-the-art solvers and the L-shaped method.