A Negotiator's Backup Plan: Optimal Concessions with a Reservation Value
This work addresses the need for efficient negotiation strategies in autonomous agents, particularly for scenarios involving backup plans, but it is incremental as it builds on existing negotiation frameworks.
The paper tackles the problem of developing an optimal bidding strategy for automated bilateral negotiations when agents have private reservation values, resulting in the MIA-RVelous algorithm that finds optimal bid sequences in O(n^2D) time.
Automated negotiation is a well-known mechanism for autonomous agents to reach agreements. To realize beneficial agreements quickly, it is key to employ a good bidding strategy. When a negotiating agent has a good back-up plan, i.e., a high reservation value, failing to reach an agreement is not necessarily disadvantageous. Thus, the agent can adopt a risk-seeking strategy, aiming for outcomes with a higher utilities. Accordingly, this paper develops an optimal bidding strategy called MIA-RVelous for bilateral negotiations with private reservation values. The proposed greedy algorithm finds the optimal bid sequence given the agent's beliefs about the opponent in $O(n^2D)$ time, with $D$ the maximum number of rounds and $n$ the number of outcomes. The results obtained here can pave the way to realizing effective concurrent negotiations, given that concurrent negotiations can serve as a (probabilistic) backup plan.