Abstract
The capability to reallocate items—such as tasks, securities, or bandwidth—is a cornerstone of automated negotiation. When agents have preferences over combinations of items, reaching an optimal allocation is computationally intensive. This paper evaluates the performance of different contract types—Original (O), Cluster (C), Swap (S), and Multiagent (M)—within a marginal cost-based reallocation framework. Our experimental results demonstrate that while OCSM-contracts theoretically guarantee global optimality, simpler contract types offer practical time-quality tradeoffs. Specifically, O-contracts perform best when the agent-to-task ratio is high, while C-contracts excel in high-density task environments. We also identify significant overhead in verifying local optima for complex contracts, particularly M-contracts.
Introduction
In automated multiagent systems, agents must often redistribute tasks or resources to minimize collective costs. This process is complicated by task synergies, where the cost of performing a set of tasks is not simply the sum of individual costs. Traditional negotiation protocols often rely on simple, single-item transfers (O-contracts). However, myopically rational agents—those who only accept trades that immediately reduce their own costs—can easily become trapped in local optima.
To address this, more complex combinatorial contracts have been proposed. While these can break deadlocks and move the system toward a global optimum, they introduce significant computational overhead. This study investigates the fundamental tradeoff between the quality of the final allocation and the time required to reach it across various contract complexities.
Contract Taxonomy
We define four primary atomic contract types used in the negotiation process:
- Original (O): A single task is transferred from one agent to another.
- Cluster (C): A set of two or more tasks is transferred between two agents.
- Swap (S): Two agents exchange exactly one task each, maintaining their total task counts.
- Multiagent (M): Tasks are redistributed among three or more agents in a single atomic transaction.
A combination of these types, referred to as OCSM-contracts, is theoretically sufficient to reach the global optimum from any initial state, though the path may be prohibitively long.
Experimental Framework
The research utilizes the Multiagent Traveling Salesman Problem (TSP) as a testbed. In this model, multiple agents (salesmen) negotiate to trade cities (tasks) on a 2D plane to minimize the total distance traveled. This environment effectively captures the synergistic nature of task allocation, as the cost of visiting a city depends heavily on the agent's existing route.
The study evaluated 1000 randomly generated TSP instances for each configuration, ranging from 2 to 8 agents and 2 to 8 tasks. Global optima were established via exhaustive search to provide a baseline for calculating the "ratio bound" (the ratio of the negotiated cost to the optimal cost).
Results and Analysis
Our analysis reveals that the effectiveness of a contract type is highly dependent on the problem scale and the ratio of agents to tasks.
Key Findings:
- Agent-to-Task Sensitivity: O-contracts consistently provided the highest social welfare (lowest ratio bound) when the number of agents was large relative to the number of tasks. Conversely, C-contracts were superior in scenarios with high task density (e.g., 8 tasks across few agents).
- The Inefficiency of Swaps: S-contracts were found to be non-competitive. By restricting the search space to transfers that keep the number of items per agent invariant, they frequently fail to find significant cost-saving reallocations.
- Computational Burden of Verification: While M-contracts are powerful, they are slow. A major hidden cost is the "verification overhead"—the large number of failed contract trials required to confirm that no further profitable multiagent trades exist.
- Distributional Effects: Different contracts result in different final distributions. O-contracts tend to spread tasks evenly, whereas C and M-contracts often lead to task concentration, where a few agents handle the majority of the workload.
Conclusion
While OCSM-contracts guarantee global optimality, their practical application is limited by the time required to reach convergence. For real-time systems, choosing a contract type based on the agent-to-task ratio is more effective. Future work should explore optimal sequencing—starting with fast O-contracts to capture easy gains before transitioning to more complex C or M-contracts to refine the solution. Additionally, developing composite contract types that combine these atomic units could further optimize the path to global optimality.
Summary updated