Divide-and-Conquer in Automated Negotiations Through Utility Decomposition
DOI:
https://doi.org/10.52731/liir.v003.074Abstract
The success of a negotiation depends largely on the actors and the negotiation do- main. It is common that negotiators rely on an agenda to simplify the process and reach better deals. This is particularly the case when the preferences of the nego- tiators are complex and when multiple issues are at stake. Using an agenda to ex- plore and decompose the interdependence relationships between the issues is one way to address this problem. In this paper, we propose to address this challenge by applying the classical divide-and-conquer approach to automated negotiations through means of utility decomposition and bottom-up agenda construction. The approach does not impose an agenda from the top level of the negotiations, but builds it bottom-up given the individual utility functions of the agents and the relationships between the issues. Our approach reduces the cost of exploring the utility spaces of the agents and the resulting bidding processes. We implement the approach in a novel protocol called the Decomposable Alternating Offers Proto- col (DAOP). The experimental results show that our divide-and-conquer algorithm makes a positive influence on the global performance of an automated negotiation system.
References
Muddasser Alam, Enrico H Gerding, Alex Rogers, and Sarvapali D Ramchurn. A scalable interdependent multi-issue negotiation protocol for
energy exchange. In Twenty-Fourth International Joint Conference on Artificial
Intelli-gence, 2015.
Reyhan Aydogan, David Festen, Koen Hindriks, and Catholijn Jonker. Alter-nating
Offers Protocols for Multilateral Negotiation, volume 674, pages 153–167. 04 2017.
Tim Baarslag, Koen Hindriks, Catholijn Jonker, Sarit Kraus, and Raz Lin. The first
automated negotiating agents competition (anac 2010). In New Trends in
agent-based complex automated negotiations, pages 113–135. Springer, 2012.
Tim Baarslag and Michael Kaisers. The value of information in automated
negotiation: A decision model for eliciting user preferences. In Proceedings of
the 16th conference on autonomous agents and multiagent systems, pages 391–400,
Maxime Bouton, Kyle Julian, Alireza Nakhaei, Kikuo Fujimura, and Mykel J
Kochenderfer. Utility decomposition with deep corrections for scalable planning
under uncertainty. In Proceedings of the 17th International Conference on
Autonomous Agents and MultiAgent Systems, pages 462–469, 2018.
Shaheen Fatima, Michael Wooldridge, and Nicholas R. Jennings. Optimal
agendas for multi-issue negotiation. In Proceedings of the Second International
Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’03,
page 129–136, New York, NY, USA, 2003. Association for Computing
Ma-chinery.
Katsuhide Fujita, Takayuki Ito, and Mark Klein. An approach to scalable multiissue negotiation: Decomposing the contract space. Computational Intelligence,
, 02 2014.
Ali Ugur Guler, Emir Demirovi´c, Jeffrey Chan, James Bailey, Christopher
Leckie, and Peter J Stuckey. A divide and conquer algorithm for predict
+ optimize with non-convex problems. In Proceedings of the AAAI Conference
on Artificial Intelligence, volume 36, pages 3749–3757, 2022.
Rafik Hadfi and Takayuki Ito. Addressing complexity in multi-issue negotiation via
utility hypergraphs. In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 28, 2014.
Rafik Hadfi and Takayuki Ito. On the complexity of utility hypergraphs. In Recent
Advances in Agent-based Complex Automated Negotiation, pages 89–105. Springer,
James Hale, Peter Kim, and Jonathan Gratch. Preference interdependencies in a
multi-issue salary negotiation. In Proceedings of the 22nd ACM International
Conference on Intelligent Virtual Agents, pages 1–8, 2022.
Koen Hindriks, Catholijn M Jonker, Sarit Kraus, Raz Lin, and Dmytro
Tykhonov. Genius: negotiation environment for heterogeneous agents. In
Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 1397–1398, 2009.
Takayuki Ito, Hiromitsu Hattori, and Mark Klein. Multi-issue negotiation
protocol for agents: Exploring nonlinear utility spaces. pages 1347–1352, 01 2007.
Nicholas R Jennings, Peyman Faratin, Alessio R Lomuscio, Simon Parsons,
Carles Sierra, and Michael Wooldridge. Automated negotiation: prospects,
methods and challenges. International Journal of Group Decision and Negotiation, 10(2):199–215, 2001.
Ahmed Kattan and Shaheen Fatima. Evolving optimal agendas and strategies for
negotiation in dynamic environments: a surrogate based approach.
In Proceedings of the 14th annual conference companion on Genetic and
evolutionary computation, pages 1435–1436, 2012.
Frank Kelly, Peter Key, Neil Walton, et al. Incentivized optimal advert assignment
via utility decomposition. In ACM Conference on Economics and Computation.
Citeseer, 2014.
Desen Kirli, Benoit Couraud, Valentin Robu, Marcelo Salgado-Bravo, Sonam
Norbu, Merlinda Andoni, Ioannis Antonopoulos, Matias Negrete-Pincetic, David
Flynn, and Aristides Kiprakis. Smart contracts in energy systems: A
systematic review of fundamental approaches and implementations.
Renew-able and Sustainable Energy Reviews, 158:112013, 2022.
Ivan Marsa-Maestre, Miguel A Lopez-Carmona, Juan A Carral, and Guillermo
Ibanez. A recursive protocol for negotiating contracts under nonmonotonic preference structures. Group Decision and Negotiation, 22(1):1–43,
Yasser Mohammad, Shinji Nakadai, and Amy Greenwald. NegMAS: A Platform for
Situated Negotiations, pages 57–75. 05 2021.
Yasser Mohammad, Enrique Viqueira, Nahum Ayerza, Amy Greenwald, Shinji
Nakadai, and Satoshi Morinaga. Supply Chain Management World, pages 153–169.
2019.
Sriram Narayanan, Ramin Moslemi, Francesco Pittaluga, Buyu Liu, and Man-mohan
Chandraker. Divide-and-conquer for lane-aware diverse trajectory prediction.
In Proceedings of the IEEE/CVF Conference on Computer Vision and
Pattern Recognition, pages 15799–15808, 2021.
Raquel Ros and Carles Sierra. A negotiation meta strategy combining trade-off
and concession moves. Autonomous Agents and Multi-Agent Systems,
(2):163–181, 2006.
Ayan Sengupta, Yasser Mohammad, and Shinji Nakadai. An autonomous negotiating agent framework with reinforcement learning based strategies and
adaptive strategy switching mechanism, 02 2021.
Douglas R Smith. The design of divide and conquer algorithms. Science of
Computer Programming, 5:37–58, 1985.
Xun Tang, Ahmed Moustafa, and Takayuki Ito. The design of meta-strategy that
can obtain higher negotiating efficiency. In 2018 Thirteenth
International Conference on Knowledge, Information and Creativity Support
Systems (KICSS), pages 1–6. IEEE, 2018.
Gerhard Weiss. MULTIAGENT SYSTEMS. MIT Press, 2013.
Xiaoqin Zhang and Mark Klein. Hierarchical negotiation model for complex
problems with large-number of interdependent issues. volume 2, pages 126–133, 12
Xiaoqin Zhang, Mark Klein, and Ivan Mars´a-Maestre. Scalable complex con-tract
negotiation with structured search and agenda management. Proceedings of the
National Conference on Artificial Intelligence, 2:1507–1513, 06 2014.
Yicheng Zou, Hongwei Liu, Tao Gui, Junzhe Wang, Qi Zhang, Meng Tang,
Haixiang Li, and Daniel Wang. Divide and conquer: Text semantic matching with
disentangled keywords and intents. arXiv preprint arXiv:2203.02898, 2022.
