Self-Organized Team Formation via Multi-Task Hedonic Games for Capability-Heterogeneous Human–Machine Agents

Partitioning a pool of capability-heterogeneous human and machine agents into effective teams for multiple concurrent tasks is a fundamental challenge in hybrid human–machine collaboration. We formalize this problem as aMulti-Task Additively Separable Hedonic Game(MT-ASHG), in which every agent is a self-interested player whose utility combines (i) a task-specific proficiency score measuring how well the agent’s skill vector aligns with task requirements, and (ii) an inter-agent compatibility score capturing synergistic or conflicting partnerships. Building on this formulation, we design an Iterative Best Response (IBR) algorithm that lets agents autonomously migrate between task groups to improve their individual payoffs. We prove that the IBR dynamics converge in a finite number of steps to an individually stable partition, in which no agent can unilaterally improve its utility by switching teams, and analyze the computational complexity of the convergence process. To bridge theory and practice, we further introduce an empirical profiling method that extracts capability and compatibility vectors from historical agent interactions, addressing the cold-start problem in newly formed human–machine teams. Extensive experiments on synthetic benchmarks and the Overcooked-AI cooperative environment demonstrate that MT-ASHG consistently outperforms centralized assignment baselines and existing coalition-formation methods in terms of global task completion rate, fairness, and scalability.