Abstract
This paper presents a multi-stage negotiation framework designed for autonomous agents to share non-consumable resources over time. In multi-agent systems, agents often need to balance the goal of task completion with the desire to maintain privacy regarding their internal schedules. The proposed framework addresses the Temporal Resource Reallocation Problem (T-RRP) by utilizing a hierarchy of negotiation stages with increasing levels of information disclosure. Agents progress from simple requests to reciprocal deals, ensuring they reveal only the minimum necessary information to reach an agreement. We provide a formal logic-based grounding for the framework and demonstrate its effectiveness through synthetic examples, proving properties such as termination and protocol conformance.
Introduction
In many multi-agent environments, agents representing distinct entities (e.g., different corporations or users) must share limited resources, such as specialized hardware or facilities. Traditional centralized scheduling requires complete transparency, which is often undesirable for self-interested agents who wish to protect their private schedules and internal logic. The challenge lies in finding a "minimally intrusive" negotiation method that allows for efficient resource reallocation without requiring total disclosure. This paper introduces a multi-stage approach where information is treated as a cost, and more intrusive negotiation tactics are only employed when simpler, more private methods fail.
Methodology: Multi-Stage Negotiation
The authors extend a logic-based negotiation framework to incorporate time windows, modeling activities with specific resource requirements and temporal constraints. The negotiation process is structured into distinct stages.
Stage 1: Request and Flexible Scheduling
In the first stage, an agent requests a resource for a specific time interval. The recipient evaluates this request by attempting to re-shuffle its own internal "concrete schedule." If a valid schedule exists that accommodates the request without compromising its own tasks, the recipient accepts; otherwise, it refuses. This stage is minimally intrusive as it only involves a binary response and no sharing of internal scheduling data.
Stage 2: Blind Deals and Reciprocity
If Stage 1 fails, agents proceed to Stage 2, which introduces reciprocity through "promises." An agent may offer to provide a resource at one time in exchange for receiving it at another. This stage allows for more complex reallocations but requires a higher degree of cooperation and information exchange.
The system is formalized using protocols (finite state machines) and policies (dialogue constraints grounded in abductive logic programming). This formalization allows for rigorous proofs of the negotiation's properties.
Key Insights and Results
A central insight of this work is the treatment of information disclosure as a currency. Agents only "pay" by moving to a more intrusive stage when necessary. Furthermore, the framework emphasizes the power of internal re-scheduling; a refusal is not a final state but a trigger for more sophisticated negotiation.
Key results include:
- Termination: Dialogues in both stages are guaranteed to terminate within a finite scheduling horizon.
- Protocol Conformance: Agent policies are proven to always adhere to the defined negotiation protocols.
- Subsumption: Stage 2 is shown to be strictly more powerful than Stage 1, capable of resolving resource conflicts that require "give-and-take" exchanges.
- Computational Trade-offs: While Stage 2 offers higher success rates for complex problems, it imposes a greater computational burden on the agents.
Conclusion and Future Work
The multi-stage framework provides a robust foundation for privacy-preserving resource negotiation. However, limitations remain. Currently, the framework struggles with complex multi-party exchanges (e.g., circular dependencies between three or more agents) and does not yet incorporate utility functions to optimize for fairness or efficiency. Future research will explore scaling these minimally intrusive stages to larger networks and developing even higher-level negotiation stages for more complex coordination tasks.
Summary updated