This work presents several new and efficient algorithms that can be used by negotiating agents to explore very large outcome spaces. The proposed algorithms can search for bids close to a utility target or above a utility threshold, and for win-win outcomes. While doing so, these algorithms strike a careful balance between being rapid, accurate, diverse, and scalable, allowing agents to explore spaces with as many as 10 250 possible outcomes on very run-of-the-mill hardware. We show that our methods can be used to respond to the most common search queries employed by 87 % of all agents from the Automated Negotiating Agents Competition between 2010 and 2021. Furthermore, we integrate our techniques into negotiation platform GeniusWeb in order to enable existing state-of-the-art agents (and future agents) to handle very large outcome spaces.

, ,
Annals of Mathematics and Artificial Intelligence
Coordinating Multi-deal Bilateral Negotiations
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Koca, T, de Jonge, D, & Baarslag, T. (2023). Search algorithms for automated negotiation in large domains. Annals of Mathematics and Artificial Intelligence. doi:10.1007/s10472-023-09859-w