How can I stably assign tasks to agents with complex preferences?
Stable Task Allocation in Multi-Agent Systems with Lexicographic Preferences
This paper explores stable task allocation in multi-agent systems where agents have preferences over combinations of tasks. It introduces a "one-to-many stable matching" problem where tasks are allocated to agents based on both agent capabilities and preferences, ensuring no agent-task group would prefer a different arrangement.
Key points for LLM-based multi-agent systems: The paper emphasizes the importance of lexicographic preferences, where agents rank entire sets of tasks based on individual task preferences. This structure, represented by lexicographic trees, allows efficient stability checking by focusing on agent-task pairs. While finding an optimal stable matching is computationally complex, the proposed integer programming formulation, coupled with column generation techniques, offers a systematic approach. The paper also highlights the concept of substitutability in agent preferences, which, when present, simplifies finding stable solutions and opens possibilities for adapting existing efficient stable-matching algorithms. Notably, traditional stable matching solutions like the "Rural Hospitals Theorem" don't always hold in this more general preference structure. This suggests the importance of considering more nuanced preference models when designing LLM-based multi-agent systems, where agents may have complex preferences over potential collaborations or courses of action.