Measuring and analyzing agents’ uncertainty in argumentation-based negotiation dialogue games

• We define a new set of uncertainty measures for negotiation dialogue games.
• We analyze the complexity of argumentation selection mechanism.
• We formalize and analyze the uncertainty index of playing the right move.
• We formalize and analyze the uncertainty of the move to be accepted by the addressee.

Nowadays, multiagent systems have become a widely used technology in everyday life, and many authors have adopted the view of communication or interaction between agents as a joint activity regulated by means of dialogue games. Dialogue games are a set of communication rules that agents can combine in their complex interactions. In these games, uncertainty is an important problem that each agent faces when making decisions, especially in the absence of enough information. This paper focuses on the uncertainty in a particular type of dialogue games, namely argumentation-based negotiation. There exist several proposals on this type of dialogue games in the literature, and most of them are concerned with proposing protocols to show how agents can communicate with each other, and how arguments and offers can be generated, evaluated and exchanged. Nevertheless, none of them is directly targeting the agents’ uncertainty about the exchanged arguments and how this uncertainty could be measured at each dialogue step to assist those agents make better decisions. The aim of this paper is to tackle this problem by defining a new set of uncertainty measures in negotiation dialogue games from an external agent’s point of view. In particular, we introduce two types of uncertainty: Type I and Type II. Type I is about the uncertainty index of playing the right move. For this, we use Shannon entropy to measure: (i) the uncertainty index of the agent that he is selecting the right move at each dialogue step; and (ii) the uncertainty index of participating agents in the negotiation about the whole dialogue. This is done in two different ways; the first is by taking the average of the uncertainty index of all moves, and the second is by determining all possible dialogues and applying the general formula of Shannon entropy. Type II is about the uncertainty degree of the agent that the move will be accepted by the addressee. In this context, we introduce a new classification for the arguments based on their certainty to be accepted by the addressee.