Research map / Multi-agent systems and games / Games and equilibria
Coalition Formation for Task Allocation Using Multiple Distance Metrics (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MDM, a two-phase Hungarian-algorithm heuristic that combines seven distance metrics to solve coalition structure generation and assignment with multi-dimensional agent/task features (SCSGA-MF).
Problem
Simultaneous coalition structure generation and assignment (SCSGA) where agents and tasks have d-dimensional feature vectors and coalitions must be matched one-to-one to tasks while minimizing distance between coalition value and task requirement.
Approach
Combine multiple distance metrics (Minkowski and dot-product-based) into one cost matrix and iteratively assign free agents to unfulfilled tasks via the Hungarian algorithm in two phases, instead of relying on one metric or brute-force enumeration.
Key results
- On 13 agents and 3 tasks, MDM's solution values are close to the exact algorithm's (e.g., UPD 51.94 vs 46.83; FD 104.19 vs 99.81) while running in about 0.001-0.002 s versus about 95-103 s for EA.
- MDM scales to up to 60,000 agents and 18,000 tasks, with run time of 785 s for FD at the largest setting in Table 2.
- The exact algorithm takes 4261 seconds for UPD at 14 agents, which motivates the heuristic.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MDM instead of EA | SCSGA-MF · UPD, 13 agents, 3 tasks | solution value: 51.94 -> 46.83 | Hurt |
| Use MDM instead of EA | SCSGA-MF · NPD, 13 agents, 3 tasks | solution value: 111.24 -> 111.10 | Hurt |
| Use MDM instead of EA | SCSGA-MF · SUPD, 13 agents, 3 tasks | solution value: 4.94 -> 4.54 | Hurt |
| Use MDM instead of EA | SCSGA-MF · SNPD, 13 agents, 3 tasks | solution value: 3.86 -> 3.79 | Hurt |
| Use MDM instead of EA | SCSGA-MF · FD, 13 agents, 3 tasks | solution value: 104.19 -> 99.81 | Hurt |
| Use MDM instead of EA | SCSGA-MF · β, 13 agents, 3 tasks | solution value: 47.06 -> 46.65 | Hurt |
| Use MDM instead of EA | SCSGA-MF · UPD, 13 agents, 3 tasks | run time (seconds): 100.64 -> 0.002 | Helped |
| Use MDM instead of EA | SCSGA-MF · NPD, 13 agents, 3 tasks | run time (seconds): 102.09 -> 0.001 | Helped |
| Use MDM instead of EA | SCSGA-MF · SUPD, 13 agents, 3 tasks | run time (seconds): 95.07 -> 0.001 | Helped |
| Use MDM instead of EA | SCSGA-MF · SNPD, 13 agents, 3 tasks | run time (seconds): 96.6 -> 0.001 | Helped |
| Use MDM instead of EA | SCSGA-MF · FD, 13 agents, 3 tasks | run time (seconds): 95.7 -> 0.002 | Helped |
| Use MDM instead of EA | SCSGA-MF · β, 13 agents, 3 tasks | run time (seconds): 101.73 -> 0.001 | Helped |
Limitations
- Solutions are near-optimal rather than optimal, with small gaps to the exact algorithm.
- Evaluated only on synthetic distributions with small exact-baseline instances (13 agents, 3 tasks).
Experimental setup
Datasets: synthetic agent/task vectors from UPD, NPD, SUPD, SNPD, FD, and Beta distributions (d=5)
Benchmarks: synthetic UPD, NPD, SUPD, SNPD, FD, Beta distributions
Metrics: solution value run time (s)
Baselines: Exact Algorithm (brute-force)
Builds on: Hungarian algorithm Zhang et al. 2022 learned parameterized distance metrics Präntare, Appelgren, and Heintz 2021 benchmark distributions
Closest papers by meaning
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation (AAAI 2025 · similarity 0.85)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.83)
- Augmented Runtime Collaboration for Self-Organizing Multi-Agent Systems: A Hybrid Bi-Criteria Routing Approach (AAAI 2026 · similarity 0.83)
- Graph-of-Agents: A Graph-based Framework for Multi-Agent LLM Collaboration (ICLR 2026 · similarity 0.83)
- Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games (AAAI 2025 · similarity 0.82)
- Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.