We present a new algorithm for automated negotiation, called BINGO, that we designed specifically for the main league of the Automated Negotiating Agents Competition of 2024 (ANL 2024). This means it was designed for negotiations that take place over a fixed number of rounds and in which the agents are fully aware of each others’ utility functions, but in which their reservation values are kept private. Our algorithm is based on the principle of backward induction, combined with the assumption that the belief each agent holds about its opponent’s reservation value can be modeled as a uniform probability distribution. We present an experiment in which BINGO negotiated against all finalists of ANL 2024 and we show that BINGO outperformed all of them. Furthermore, we present a number of theoretical results for so-called split-the-pie scenarios.

Abstract Recently, we have introduced a new algorithm for automated negotiation, called MiCRO, which, despite its simplicity, outperforms many state-of-the-art negotiation strategies (de Jonge, in: Raedt (ed) Proceedings of the thirty-first international joint conference on artificial intelligence, ijcai.org, Vienna, Austria, 2022). Furthermore, we claimed that under certain conditions which typically hold in the Automated Negotiating Agents Competition (ANAC), it is a game-theoretically optimal strategy. The goal of this paper is to formally prove those claims. Specifically, we define ‘negotiation’ as an extensive-form game and define the class of consistent strategies for this game, which consists of those strategies that satisfy a number of rationality criteria. We then prove that under the above mentioned conditions MiCRO is a best response against itself among all consistent negotiation strategies. Furthermore, we define the notion of a balanced negotiation domain, which is a domain in which two MiCRO agents would always come to an optimal agreement. Finally, we show that many of the domains used in ANAC indeed happen to be (approximately) balanced. The importance of this work is that if we know under which conditions MiCRO is theoretically optimal, then we can use this to test to what extent other negotiation algorithms are able to achieve similar results to MiCRO when applied under those same conditions. Furthermore, it would help researchers to design more challenging test cases for automated negotiation in which MiCRO is not optimal.

Abstract The bargaining problem deals with the question of how far a negotiating agent should concede to its opponent. Classical solutions to this problem, such as the Nash bargaining solution (NBS), are based on the assumption that the set of possible negotiation outcomes forms a continuous space. Recently, however, we proposed a new solution to this problem for scenarios with finite offer spaces de Jonge and Zhang (Auton Agents Multi-Agent Syst 34(1):1–41, 2020). Our idea was to model the bargaining problem as a normal-form game, which we called the concession game, and then pick one of its Nash equilibria as the solution. Unfortunately, however, this game in general has multiple Nash equilibria and it was not clear which of them should be picked. In this paper we fill this gap by defining a new solution to the general problem of how to choose between multiple Nash equilibria, for arbitrary 2-player normal-form games. This solution is based on the assumption that the agent will play either ‘side’ of the game (i.e. as row-player or as column-player) equally often, or with equal probability. We then apply this to the concession game, which ties up the loose ends of our previous work and results in a proper, well-defined, solution to the bargaining problem. The striking conclusion, is that for rational and purely self-interested agents, in most cases the optimal strategy is to agree to the deal that maximizes the sum of the agents’ utilities and not the product of their utilities as the NBS prescribes.

The Automated Negotiating Agents Competition (ANAC) is an annual competition that compares the state-of-the-art algorithms in the field of automated negotiation. Although in recent years ANAC has given more and more attention to more complex scenarios, the linear and bilateral negotiation domains that were used for its first few editions are still widely used as the default benchmark in automated negotiations research. In this paper, however, we argue that these domains should no longer be used, because they are too simplistic. We demonstrate this with an extremely simple new negotiation strategy called MiCRO, which does not employ any form of opponent modeling or machine learning, but nevertheless outperforms the strongest participants of ANAC 2012, 2013, 2018 and 2019. Furthermore, we provide a theoretical analysis which explains why MiCRO performs so well in the ANAC domains. This analysis may help researchers to design more challenging negotiation domains in the future.

Abstract This paper investigates a problem that lies at the intersection of three research areas, namely automated negotiation, vehicle routing, and multi-objective optimization. Specifically, it investigates the scenario that multiple competing logistics companies aim to cooperate by delivering truck loads for one another, in order to improve efficiency and reduce the distance they drive. In order to do so, these companies need to find ways to exchange their truck loads such that each of them individually benefits. We present a new heuristic algorithm that, given one set of orders for each company, tries to find the set of all truck load exchanges that are Pareto-optimal and individually rational. Unlike existing approaches, it does this without relying on any kind of trusted central server, so the companies do not need to disclose their private cost models to anyone. The idea is that the companies can then use automated negotiation techniques to negotiate which of these truck load exchanges will truly be carried out. Furthermore, this paper presents a new, multi-objective, variant of And/Or search that forms part of our approach, and it presents experiments based on real-world data, as well as on the commonly used Li & Lim data set. These experiments show that our algorithm is able to find hundreds of solutions within a matter of minutes. Finally, this paper presents an experiment with several state-of-the-art negotiation algorithms to show that the combination of our search algorithm with automated negotiation is viable.

This paper proposes the notion of experience to help situate agents in their environment, providing a link on how the continually evolving environment impacts the evolution of an agent's BDI model and vice versa. Then, using the notion of shared experience as a primitive construct, we develop a novel formal model of shared intention which we believe more adequately describes social behaviour than traditional BDI logics that focus on individual agents. Whilst many philosophers have argued that collective intentionality cannot always be equated to the collection of the individual agents' intentions, there has been no AI model that addresses this issue. We believe this is the first attempt to develop an explicit notion of shared experience from an AI perspective.