A distributed coalition formation algorithm for large-scale resource assignment under nonlinear coupling constraints

Abstract

Large-scale resource-to-task assignment under nonlinear coupling constraints represents a recurrent computational challenge in industrial engineering, spanning production scheduling, logistics coordination, and multi-agent mission planning. This study addresses a generalized formulation in which heterogeneous agents must be partitioned into coalitions, each assigned to a distinct objective with stringent compatibility and synergistic-effect requirements. A distributed optimization framework, termed the Distributed Coalition Formation Algorithm (DCFA), is developed by recasting the centralized assignment problem as a coalition partition game. Each agent acts as an independent decision-maker, evaluating marginal utility contributions when switching coalitions. The global utility function is proven to constitute an exact potential function, which guarantees finite-step convergence to Nash-stable partitions with a Price of Stability equal to unity over the set of reachable equilibria. A sigmoid-based utility mapping captures nonlinear saturation in cumulative effectiveness, while a Simulated Annealing Better-Response (SABR) mechanism enables systematic escape from suboptimal local partitions. Localized reallocation protocols further equip the framework to accommodate real-time disruptions without triggering full-scale recomputation. Extensive computational experiments, analyzed through Friedman ranking, Nemenyi post-hoc comparisons, and Cohen's d effect sizes, demonstrate that DCFA scales near-linearly with problem size and occupies the optimal compromise point on the utility–time Pareto frontier, achieving order-of-magnitude speedups relative to leading centralized metaheuristics at negligible solution-quality loss. The framework offers a general-purpose computational tool for distributed resource assignment in large-scale industrial systems.