Rapport de stage - briot/documents/Rapport_Stage_M2_09_2017_Anis... · Rapport de stage Expert agents in negotiation and argumentation for serious games on participatory management

Rapport de stage

Expert agents in negotiation and argumentation

for serious games on participatory management

GARGOURI Anis

[email protected]

Université Paris DESCARTES

Master 2 Recherche en Intelligence Artificielle

Parcours : Intelligence Artificielle Distribuée

Encadrants :

BRIOT Jean–Pierre Directeur de Recherche CNRS, UPMC – LIP6

MAUDET Nicolas Professeur, UPMC – LIP6

Enseignant référant :

MORAÏTIS Pavlos Professeur, Paris Descartes – LIPADE

2016 – 2017

FLVCTVAT

NEC MERGITVR

Acknowledgments

First of all, I want to express my profound gratitude to my advisors:

Mr Nicolas Maudet and Mr Jean–Pierre Briot for having welcomed me into

the SMA team at LIP6, but above all for their valuable advices, for their

guidance and encouragement during my internship.

I am grateful to the members of my master thesis committee for their time

and effort to evaluate this work.

I am also thankful to all of my master course teachers at Paris Descartes.

Specially to Mr Pavlos Moraïtis.

I want to thank also all those who, from near or far, have helped me realize

this master thesis.

Contents

1 Introduction 1

1.1 What is Participatory Management? . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Why Negotiation and Argumentation? . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Contribution of the master thesis . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Structure of the document . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Related work 5

2.1 Participatory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Agent–Based modeling of Participatory Management . . . . . . . . . . . 5 2.1.2 The SimParc project (2007–2017) . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Negotiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Parameters of Negotiation . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 Types of Negotiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3 Classical approaches of Negotiation . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 Multilateral Mediated Negotiation approach . . . . . . . . . . . . . . . . . 13 2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Contribution: Participatory Management Negotiation Framework 15

3.1 Role–Playing Game Aspect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Inter–Agent Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.1 Protocol Stages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 Negotiation Speech Acts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Agent Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3.1 BDI Model and Logical Language . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2 Personal Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.3 Learned Knowledge Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.4 Qualitative Bipolar Desires . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.5 Rules and Evaluation Mechanism . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.6 Conversation and explanatory arguments . . . . . . . . . . . . . . . . . . . 26 3.3.7 Agent’s architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Mediator Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.1 Offer proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.2 Negotiation cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.3 Negotiation response time . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.4 Proposition validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Conclusion and perspectives 30

Bibliography 31

Appendix 35

A Example of application of Framework. . . . . . . . . . . . . . . . . . . . . . . 35

B SimParc Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

1

Introduction

With the advances in Information and Communications Technology and in Multi–Agent Systems (MAS), the need for software agents able to negotiate with others, instead human users, becomes increasingly important. It seems interesting to us to use the Multi–Agent Sys-tems applied to participatory management, to build a tool both pedagogical and epistemic. It is a matter of assisting the negotiation until decision–making. More specifically, we would like to help social actors to first understand the reasons for existing conflicts and then to negotiate strategies to solve them. The Multi–Agent technology is particularly adapted to implement such applications. Indeed, the use of autonomous, cognitive and social agents [Woolridge, 2001] can automate negotiation processes, decision–making and increase the autonomy of the system.

This project aims to explore the use of argument–based formalisms for decision support and negotiation in a context of participatory management of socio–ecosystems, such as pro-tected areas and natural parks to conserve biodiversity and promote social inclusion. The con-text of the project is the serious game (computer–based pedagogical role play/training and exploratory) on the participatory management of socio–environmental resources (such as pro-tected areas for the conservation and/or sustainable use of natural resources). In such game, abstracting real situations and conflicts (e.g. activities of the management consultancy of a protected space), different players embody different roles of social actors (e.g. environmental-ist, fisherman, tourism operator, mayor, etc.) having different perceptions and objectives. The application objective is to train actors and decision–makers to identify conflicts (conflicts of access to or protection of resources, e.g. marine resources) and to collectively develop strate-gies for resolving conflicts, essential objectives to escape the tragedy of the commons [Ostrom, 1999].

1.1 What is Participatory Management?

Participatory management is a pluralist approach for managing natural resources, incorpo-rating a variety of partners in a variety of roles, generally to the end goals of environmental conservation, sustainable use of resources and the equitable sharing of resource–related bene-fits and responsibilities. It is a political and cultural process by excellence: seeking social jus-tice and “democracy” in the management of natural resource. It is a process that needs some basic conditions to develop, among which are: full access to information on relevant issues and options, freedom and capacity to organize, freedom to express needs and concerns, a non–discriminatory social environment, the will of partners to negotiate, confidence in the respect

2 INTRODUCTION

of agreements, etc. Also, it is a complex often lengthy and sometimes confused process, involv-ing frequent changes, surprises, sometimes contradictory information, and the need to retrace one’s own steps. And finally, it is the expression of a mature society, which understands that there is no “unique and objective” solution for managing natural resources but, rather, a mul-tiplicity of different options which are compatible with both indigenous knowledge and scien-tific evidence and capable of meeting the needs of conservation and development (and that there also exists a multitude of negative or disastrous options for the environment and devel-opment).

The three major phases of a participatory management process are: – Organizing: Preparation for the partnership – Negotiating: Negotiation of participatory management plans and agreements – Learning by doing: Implementation and revision of plans and agreements

In the following the main concepts and elements of the participatory management of natu-ral resources, according to Borrini–Feyerabend [Borrini–Feyerabend, 2000]:

Adaptive management A management approach recognizing, on one hand, the lack of definitive univocal

knowledge about the behavior of the actors and, on other hand, the uncertainty that domi-nates our interaction with others. It is based on the observation that resource management is always experimental, that there are always lessons to be learned from the implemented activi-ties and that it is possible to improve the management of resources based on acquired experi-ence.

Pluralism A pluralistic approach focuses on recognizing that in every society there are different ac-

tors, interests, concerns and values. In particular: There are several categories of social actors (e.g. governmental and non–governmental organization, groups and individuals, local and ex-ternal communities with rights to exploit local resources), which are complementary to natu-ral resource management. Moreover, communities are in themselves actors and constitute the most natural and convincing unit of identity, integration and defense for many disadvantaged groups and individuals.

Conflict management Conflict management is a non–violent process that promotes dialogue and negotiation. It

consists of guiding conflicts towards constructive rather than destructive results. It implies: – taking care of disagreements before they generate hostility; – helping the institutional actors to explore a multiplicity of options for agreement and sub-

sequently select an option everyone can live with; – recognizing and intervening in the underlying causes of conflict, with a view to preventing

them in the future.

Whenever the conflicts are serious and the parties involved are distant and hostile, the presence of a facilitator, mediator or arbitrator is highly recommended. A conflict–

INTRODUCTION 3

management instructor could also be called upon. Their role is similar, but not exactly the same (see below). These key figures in conflict management are often private individuals (reli-gious leaders, retired judges, local wise–men and women, etc.) possessing special characteris-tics and capacities [Borrini–Feyerabend, 2000]:

– Facilitators: Assist only in the running of the process. They never allow themselves to be drawn into the arguments.

– Mediators: Act as facilitators, but also help develop a wide range of options for the par-ties to discuss and choose from. They help conflicting parties to reach an agreement satis-factory for everyone.

– Arbitrators: Act as judges: they listen to the various parties, review pertinent docu-ments and issue a decision, which is treated by all concerned as an expert opinion or an obligation, depending on what was decided in advance.

– Instructors: Help the parties (usually in separate sessions) to learn the elements of con-flict management, which the parties will hopefully succeed in applying to their own con-flict situation.

Social communication Communication may be personal (one–to–one), inter–personal (among a few individu-

als) and social (when it involves social groups, such as a local community). Social communi-cation for participatory management is about providing the conditions for informed decision–making in society, i.e. promote the sharing of information and the discussion of problems, opportunities and alternative options for decisions/actions.

1.2 Why Negotiation and Argumentation?

Modern processes of conflict management are quite close to the processes used to negotiate a participatory management agreement; both express the same values (dialogue, transparency, pluralism, fairness, etc.), have the same main constituents and can be facilitated in similar way. We can highlight the main constituents of modern conflict management approaches there is: a concern of social actors, a common area of interest and some points of conflict (dif-ferent values, interests and needs of the various actors involved), a forum for negotiation and some basic rules providing a framework for the actors concerned to meet and discuss issues together, some reliable data on the points of conflict, various options for action generated by the actors concerned and discussed among themselves, a written agreement on one of these options, legitimization of the agreement, and implementation of the agreement.

We are considering an agreement in a negotiation as a reason to believe in a conclusion, to make an action or to adopt a goal. It is then that the utility of the use of argumentation dur-ing a negotiation, is initially influence others: influencing the beliefs, the goals and the prefer-ences of other agents. And in a second time to make explanatory arguments following a deci-sion–making process.

4 INTRODUCTION

1.3 Contribution of the master thesis

The objective is therefore to move towards support of negotiation. Indeed, the prototype of the previously developed manager/decision–maker agent [Sordoni et al., 2010] uses arguments only internally, to its deliberation, leading to its decision. Our objective is to extend this first study that is limited to internal deliberative approach, as support and assistance to the nego-tiation between players based on arguments (where exchange and confrontation of arguments and counter arguments will be the basis of negotiations) [Parsons et al., 1998].

There are different formalisms of argumentation systems, including [Rahwan & al., 2006], extending the Belief Desire Intention model (BDI). Which served as a foundation for the arti-ficial decision–making agent [Sordoni & al., 2010], implemented in the Multi–Agent program-ming language AgentSpeak [Rao, 1996], above the Jason platform [Bordini & al., 2007].

From a more epistemological point of view, we also seek to reconcile the strengths and weaknesses of these two approaches: The technical assistance at the level of an ex-pert/decision–maker and its risks of technocratic drifts; And the purely participatory man-agement and its risks of relativistic drift due to the lack of objective and shared technical ar-guments for the decision. Our objective is to explore the insertion of technical expertise at the level of social actors (assistants, or possibly autonomous artificial players) and its impact on the negotiation and participatory decision–making process.

1.4 Structure of the document

This master thesis is organized in the following way. The second chapter presents the relat-ed work of the two sides of our master thesis, namely participatory management and negotia-tion in multi–agent systems. Chapter 3 presents our Participatory Management Framework for the negotiation of natural resources, based on an exchange of arguments. It considers two types of agents: the participant agents (social actors) and the mediator (administrator of the natural resources park), and it is composed of two levels: the inter–agent level (the interaction environment) and the agent level (the agent's internal representation). We start by presenting the Role–Playing Game aspect of the framework. Thereafter, we present the inter–agent level, and the agent level architectures (participant agents and mediator). The last chapter is devot-ed to some concluding remarks and future perspectives.

A detailed example of the application of our framework is in an Appendix at the end of the document.

2

Related work

In this chapter, we present the related work of the two sides of our master thesis, namely participatory management and negotiation in multi–agent systems.

2.1 Participatory Management

Participatory Management – A situation in which two or more social actors negotiate, define and guarantee amongst themselves a fair sharing of the management functions, enti-tlements and responsibilities for a given territory, area or set of natural resources [Borrini–Feyerabend, 2000].

This section presents the Agent–Based approach for the participatory management, and the SimParc project.

2.1.1 Agent–Based modeling of Participatory Management The basic principle is that multi–agent systems constitute a paradigm of knowledge repre-

sentation relevant to support interdisciplinary research. The model then serves mainly as a mediating object for discussions between different researchers or actors engaged in the co–construction of a common point of view.

ComMod (Companion Modeling) [Barreteau, 2003] proposed to jointly use multi–agent sys-

tems/simulation (MAS) and role–playing games (RPG) for purposes of research, training and negotiation support in the field of renewable resource management. This joint use was later labeled the “MAS/RPG methodology”. The ComMod community had (and still has) a pro-found impact on research and methods for participatory management of environmental re-sources and on multi–agent simulation. More specifically, ComMod is about methods for par-ticipatory management of renewable resources, with interaction between natural resources inner processes (e.g. hydrodynamics, animal’s population evolution, etc.) and the human and social processes of their usage (consumption, control, etc.). They have proposed MAS/RPG model to represent and compute the dynamics of the natural resources to represent the dia-logue between stakeholders, to explore individual and collective decision strategies about the resources (e.g. actual use, access control, conflict resolution, etc.).

The multi–agent simulation platform Cormas [Le Page & al., 2012] is used to implement the simulation part. In the MAS/RPG combination, simulation runs are interlaced with the

6 RELATED WORK

different game steps, thus allowing players to understand the consequences of their deci-sions/actions and their interrelations with decisions/actions of other players. Initially, and still in most of ComMod projects, RPG is conducted manually or semi manually. Pioneering works, such as JogoMan–ViP by [Adamatti & al., 2007] and Simulación by [Guyot & al., 2006], have aimed at integrating MAS and RPG, that is providing a support for distributed players (inspired by distributed video games) and interfacing it with the multi–agent simula-tion, thus leading to a more fluid integration between simulation steps and decision steps. They have also started introducing some artificial agents, as players or as assistants.

Characteristic features of agent–based modeling for participatory management

– Ontological Correspondence: There can be a direct correspondence between the com-putational agents in the model and real–world actors, which makes it easier to design the model and interpret its outcome than would be the case with, for example, an equation–based model. For instance, a model of a commercial organization can include agents rep-resenting the employees, the customers, the suppliers, and any other significant actors. In each case, the model might include an agent standing for the whole class (e.g. ‘‘employ-ees’’), or it might have a separate agent for each employee, depending on how important the differences between employees are [Gilbert, 2008].

– Heterogeneous Agents: Theories in economics and organization science make the sim-plifying assumption that all actors are identical or similar in most important respects. Ac-tors may differ in their preferences, but it is unusual to have agents that follow different rules of behavior, and when this is allowed, there may be only a small number of sets of such actors, each with its own behavior. This is for the good reason that unless agents are homogeneous, analytical solutions are very difficult or impossible to find. A computation-al model avoids this limitation: Each agent can operate according to its own preferences or even according to its own rules of action [Fagiolo & al., 2006].

– Representation of the Environment: It is possible to represent the ‘‘environment’’ in which actors are acting directly in an agent–based model. This may include physical as-pects (e.g. physical barriers and geographical hurdles that agents have to overcome), the effects of other agents in the surrounding locality, and the influence of factors such as crowding and resource depletion [Gilbert, 2008].

– Agent Interactions: An important benefit of agent–based modeling is that interactions between agents can be simulated. At the simplest, these interactions can consist of the transfer of data from one agent to another, typically another agent located close by in the simulated environment. Where appropriate, the interaction can be much more complicat-ed, involving the passing of messages composed in some language, with one agent con-structing an ‘‘utterance’’ and the other interpreting it (and not necessarily deriving the same meaning from the utterance as the speaker intended) [Fagiolo & al., 2006].

– Bounded Rationality: Many models implicitly assume that the individuals whom they model are rational, that is, that they act according to some reasonable set of rules to op-timize their utility or welfare. (The alternative is to model agents as acting randomly or irrationally, in a way that will not optimize their welfare. Both have a place in some

RELATED WORK 7

models.) Some economists, especially those using rational choice theory, have been ac-cused of assuming that individuals are ‘‘hyperrational,’’ that is, that people engage in long chains of complex reasoning in order to select optimal courses of action, or even that people are capable of following chains of logic that extend indefinitely. Many researchers, criticized this as unrealistic and proposed that people should be modeled as boundedly ra-tional, that is, as limited in their cognitive abilities and thus in the degree to which they are able to optimize their utility [Kahneman, 2003]. Agent–based modeling makes it easy to create boundedly rational agents. In fact, the challenge is usually not to limit the ra-tionality of agents but to extend their intelligence to the point where they could make decisions of the same sophistication as is commonplace among people [Fagiolo & al., 2006].

– Learning: Agent–based learning can be modeling in any or all of three ways: as individ-ual learning in which agents learn from their own experience; as evolutionary learning, in which the population of agents learns because some agents ‘‘die’’ and are replaced by bet-ter agents, leading to improvements in the population average; and social learning, in which some agents imitate or are taught by other agents, leading to the sharing of experi-ence gathered individually but distributed over the whole population [Gilbert & al., 2006].

2.1.2 The SimParc Project1 (2007–2017)

Project motivation [Briot & al., 2007; Briot & al., 2008]

A significant challenge involved in biodiversity management is the management of protect-ed areas (e.g. national parks), which usually undergo various pressures on resources, use and access, which results in many conflicts. This makes the issue of conflict resolution a key issue for the participatory management of protected areas. Methodologies intending to facilitate this process are being addressed via bottom–up approaches that emphasize the role of local actors. Examples of social actors involved in these conflicts are: park managers, local commu-nities at the border area, tourism operators, public agencies and non–governmental organiza-tions (NGOs). Examples of inherent conflicts connected with biodiversity protection in the area are: irregular occupation, inadequate tourism exploration, water pollution, environmental degradation and illegal use of natural resources. These conflicts occur because of different cul-tures, contexts and practices [Irving, 2006].

The SimParc project aim is to help various stakeholders at collectively understand conflicts in parks management and negotiate strategies for handling them. The origin of the name SimParc stands in French for “Simulation Participative de Parcs”. It is based on the observa-tion of several case studies in Brazil.

Game Objectives

Current SimParc game [Briot & al., 2017] has an epistemic objective: to help each partici-pant discover and understand the various factors, conflicts and the importance of dialogue for

1 http://www–desir.lip6.fr/~briot/simparc/

8 RELATED WORK

a more effective management of parks. Note that this game is not (or at least not yet) aimed at decision support (i.e. we do not expect the resulting decisions to be directly applied to a specific park).

The game is based on a negotiation process that takes place within the park council. This council, of a consultative nature, includes representatives of various stakeholders (e.g. com-munity, tourism operator, environmentalist, non–governmental association, water public agen-cy, etc.). The actual game focuses on a discussion within the council about the “sectoring” of the park, i.e. the decision about a desired level of conservation (and therefore, use) for every sub–area (also named “landscape unit”) of the park.

The game considers a certain number of players’ roles, each one representing a certain stakeholder. Each player, as in any role–playing game, has to embody the designed/selected role with its respective background culture, postures and objectives. Each player will try to influence the decision about the type of conservation for each landscape unit. It is clear that conflicts of interest will quickly emerge, leading to various strategies of negotiation (e.g. coali-tion formation, trading mutual support for respective objectives, etc.).

A special role in the game is the park manager. He is a participant of the game, but as an arbiter and decision maker, and not as a direct player. He observes the negotiation taking place among players and takes the final decision about the types of conservation for each landscape unit. (It is important to note that this follows the situation of a real national park in Brazil, where the park management council – composed of representatives of diverse stake-holders – is only of a consultative nature, thus leaving the final decisions to the manager.) Decision by the park manager is based on the legal framework, on the negotiation process among the players, and on his personal profile (e.g. more conservationist or more open to so-cial concerns) [Irving, 2006]. He may also have to explain his decision, if the players so de-mand.

Game Cycle

The game is structured along six steps, as illustrated in Figure 2.1. At the beginning (step 1), each participant is associated to a role. Then, an initial scenario

is presented to each player, including the setting of the landscape units, the possible types of use and the general objective associated to his role. Then (step 2), each player decides a first proposal of types of use for each landscape unit, based on his/her understanding of the objec-tive of his/her role and on the initial setting. Once all players have done so, each player’s proposal is made public.

In step 3, players start to interact and to negotiate about their proposals. This step is, in our opinion, the most important one, where players collectively build their knowledge by means of an intercultural argumentation process. In step 4, they revise their proposals and commit themselves to a final proposal for each landscape unit. In step 5, the park manager makes the final decision, considering the negotiation process, the final proposals and also his personal profile (e.g. more conservationist or more sensitive to social issues). Each player can then consult various indicators of his/her performance (e.g. closeness to his initial objective, degree of consensus, etc.). He can also ask for an explanation about the park manager decision rationales.

RELATED WORK 9

The last step (step 6) “closes” the epistemic cycle by considering the possible effects of the decision. In the current game, the players provide a simple feedback on the decision by indi-cating their level of acceptance of the decision.

A new negotiation cycle may then start, thus creating a kind of learning cycle. The main objectives are indeed for participants: to understand the various factors, cultures and perspec-tives involved and how they are interrelated; to negotiate; to try to reach a group consensus; and to understand cause–effect relations based on the decisions.

2.2 Negotiation

There are several definitions of negotiation. One of the most common and widespread de-fines negotiation as: the interaction and the communication process of a group of agents (two or more agents) in order to reach a mutually accepted agreement on some matter [Hafid & al., 1998].

Later, previous definition of negotiation was extended by Jennings as: Negotiation is the process by which a group of agents come to a mutually acceptable agreement on some matter (...) to make proposals, trade options, offer concessions and (hopefully) come to a mutually acceptable agreement [Jennings & al., 2001].

All researchers agree on the finality of the negotiation, namely the conclusion of a satisfac-tory common agreement. But negotiation itself is defined as a process. All the diversity of research in negotiation comes from this word: process. The negotiation can therefore be seen as a black box having a conflict as input and an agreement as output. Research on negotiation therefore consists of studying the mechanisms of this black box to make it transparent.

FIG. 2.1 – The six steps of the SimParc Game [Briot & al., 2008]

10 RELATED WORK

For this master thesis, the following definition summarizes our point of view: Negotiation – Is a form of interaction in which a group of agents, with conflicting inter-

ests and a desire to cooperate, try to come to a mutually acceptable agreement on the division of scarce resources [Rahwan & al., 2003].

This section presents the various concepts related to negotiation, namely [Luo & al., 2003;

Jain & al., 2009; Huang & al., 2010]: the negotiation parties, the arrangement, the negotiation protocol, and the negotiation process. It also introduces the types of negotiation as well as the different approaches adopted for the implementation of an automated negotiation between intelligent agents.

2.2.1 Parameters of Negotiation

Negotiation is a solution to overcome conflicts between intervening agents named propo-nent and opponent [Luo & al., 2003]. It is a process that allows the satisfaction of each agent to evolve during the discussion of a proposal in order to arrive at a mutually acceptable ar-rangement. As described in [Verrons, 2004], the mutually acceptable arrangement can be reached on a distribution of a set of financial or material resources available to the proponent, called multilateral resources.

According to Aydogan [Aydogan, 2011], there are several issues making up the negotiation process, such as:

– Negotiation domain (object): A negotiation domain represents a set of issues that the participants try to agree on [Jennings & al., 2001]. A negotiation issue can be defined as “a particular interest in a negotiation” such as price, neighborhood, and so on [Tykhonov, 2010] and a negotiation domain may consist of one issue or multiple issues. In other words, the participants can negotiate on a single issue or multi–issue [Raiffa, 1982]. For instance, a consumer and a producer may negotiate only on “price” issue whereas they may negotiate on several issues related to the service such as the content of the service, the delivery time and so on.

– Negotiating parties (participants): A negotiating party can be a human or an auton-omous agent that takes a part in a negotiation [Tykhonov, 2010]. If we have two agents negotiating, it is a bilateral (one–to–one) negotiation [Li & al., 2003]. If a negotiation in-volves more than two participants, it is called a multilateral negotiation [Sierra & al., 1997].

– Negotiation bid: A bid is an offer or a counter–offer made by one of the negotiating parties during the negotiation.

– Negotiation outcome: A negotiation outcome represents the mutually accepted agree-ment at the end of the negotiation when the negotiation is terminated with an agreement.

– Negotiation session: A negotiation session is a single process of negotiation between parties on a particular matter that ends up with a consensus or failure.

RELATED WORK 11

– Negotiation strategy: A negotiation strategy determines how a negotiating party acts during the negotiation. It dictates how offers are generated and which counter–offers are acceptable. In literature, there are a variety of strategies such as concession–based strate-gies, trade–off strategies and so on.

– Negotiation protocol: A negotiation protocol manages the interaction between negoti-ating parties by determining how the parties interact, how the bids exchanges are done, what the valid bids are, when the negotiation closes and so on [Jennings & al., 2001]. The negotiating parties should agree on the negotiation protocol before starting negotiation.

– Negotiation cardinality: The cardinality is an important notion in the Multi–Agents Systems. It's about how many agents negotiate with each other. Different types of negoti-ation cardinality exist [Guttman & al., 1998], beginning with one–to–one and ending with many–to–many negotiation. One–to–one negotiation is useful only when at most two agents are involved in the negotiation. But when it involves several participants with a mediator, it is called one–to–many negotiation, this is the case with our protocol.

2.2.2 Types of Negotiation

There are three types of negotiation: distributed negotiation, integrative negotiation and centralized negotiation [Huang & al., 2010].

In a distributed negotiation, bargaining agents are in a zero–sum logic, that is to say, a

win–lose logic. Everything that one wins the other loses. In such situation, the objective of each agent is to maximize his own earnings, and the negotiation thus becomes a competition where the stronger outweighs the weakest [Lee & al., 2009]. This kind of negotiation is used in several areas such as e–commerce, trading markets, etc.

The logic of an integrative negotiation is that of the win–win. Any gain for one will also be

a gain for the other. The context created by this partnership clearly define the problem to share all available information and explore all possible solutions to commit to an equitable and sustainable solution to the problem [Mohan & al., 2006]. This type of negotiation is ap-plied in the supply chains where the main objective to be achieved represents the global and final objective [Jain & al., 2009].

Centralized negotiation is an iterative process in which a third negotiating party (Arbitra-

tor), called “neutral” [Lin & al., 2004], oversees and detects conflicts between other negotiat-ing parties (Conflict Agents). The resolution of the problem is thus interactive since it is a mutual dialogue between the three parties. Based on the proposals formulated by the Arbitra-tor, the dialogue overcomes the conflict between the negotiating agents. It gives them the opportunity to analyze and imagine possible solutions for a definitive agreement. The objec-tive of centralized negotiation is not to reach an arrangement immediately, but to promote dialogue between opposing parties to analyze the problem and the factors fueling the conflict [Lin & al., 2004; Lee & al., 2009]. By exploring motivations, needs and values of integrity and recognition of their identity, the negotiating parties are led to gradually transform not only

12 RELATED WORK

the nature of the conflict but also their conflictual relationship [Huang & al., 2010]. This type of centralized negotiation is observed, for example, in the negotiation of salary increment, where the company and the employees are the two conflicting parties. In this example, the syndicate plays the role of the arbitrator where its objective is to reach a mutually acceptable arrangement.

2.2.3 Classical Approaches of Negotiation

Each automated decision–making mechanism can take one of the following three approach-es: game–theoretic approaches, heuristic–based approaches and argumentation–based ap-proaches. This classification was proposed by Jennings [Jennings & al., 2001], and later adopt-ed by other researches e.g. [Rahwan & al., 2003].

Game theory is a tool for studying strategies for interaction between autonomous agents in

automated negotiation [Wolters & al., 1997]. Several works have used game theory to design automated negotiation processes in different domains. This works tends to determine the op-timal strategy to be used for achieving a balance of a game simulation between identical bar-gaining agents [Rao, 1987; Wolters & al., 1997]. This approach allows agents to adopt rational behavior when making decisions and choosing strategies [Esmaeili & al., 2009]. However, clas-sical game–theoretic approaches have some significant limitations from the computational perspective [Dash & al., 2003]. Specifically, most of these approaches assume that agents have unbounded computational resources and that the space of outcomes is completely known. In most realistic environments, however, these assumptions fail due to the limited processing and communication capabilities of the information systems [Vesic, 2011].

Agents always adopt a rational behavior in game theory. This type of behavior can some-

times lead to unsatisfactory solutions [Esmaeili & al., 2009]. As a result, approximate strate-gies and heuristics seems to be a promising way [Bichler & al., 2001]. Heuristics are rules that do not necessarily provide the optimal solution, but they provide a solution closer to the op-timal one. The heuristic approach is based on testing and evaluating the different results. It is used in several negotiation domains, namely multimedia applications [Hafid & al., 1998], e–market [Bichler & al., 2001], etc. Nevertheless, the heuristic approach has a number of limita-tions. Indeed, it does not necessarily lead to an optimal solution, because it uses approximate strategies and it does not examine all the possible space of the results. This approach cannot predict the exact behavior of the system and those of its agents and it assumes that the agent has a complete knowledge of its desires and preferences.

Although game theoretic and heuristic based approaches both have desirable features and

are widely studied by researches, they share some limitations. In most game–theoretic and heuristic models, agents exchange proposals (i.e. potential agreements or potential deals). This, for example, can be a promise to purchase a given object at a specified price. However, agents are not allowed to exchange any additional information other than what is expressed in the proposal itself. This can be problematic, for example, in situations where agents have lim-ited information about the environment, or where their rational choices depend on those of

RELATED WORK 13

other agents. Another limitation of conventional approaches to automated negotiation is that the agent’s preference relation on the set of offers is supposed to stay fixed during the interac-tion [Vesic, 2011].

Argument–based negotiation is used by agents who possess a knowledge base with predi-cates and inference rules. The purpose of a proponent agent's argument is to modify and in-fluence the beliefs of other agents (opponents) to adopt the same viewpoint and beliefs.

In this context, the argument is defined as the information that allows the agent firstly to justify its position in the negotiation and, secondly, to influence the positions of other agents. Justification allows agents to provide additional information in their proposals. They can ex-plain the reasons for rejecting or accepting of a given proposal [Caminada & al., 2007].

Sycara [Sycara, 1990] was among the first to emphasize the importance of using argumen-tation techniques in negotiation. Since then, several works were done including those by Par-sons and Jennings [Parsons & al., 1996], Tohmé [Tohmé, 1997], Reed [Reed, 1998], Kraus, Sycara, and Evenchik [Kraus & al., 1998], Amgoud, Parsons, and Maudet [Amgoud & al., 2000], Amgoud and Prade [Amgoud & al., 2004], Kakas and Moraitis [Kakas & al., 2006], Amgoud, Dimopoulos, and Moraitis [Amgoud & al., 2007], or Dimopoulos and Moraitis [Dimopoulos & al., 2014].

2.2.4 Multilateral Mediated Negotiation Approach According to the mediated single text negotiation protocol presented in [Klein & al., 2003],

the mediator initially generates a bid randomly and asks the negotiating agents to vote for this bid. Each agent can vote to either “accept” or “reject” in accordance with its negotiation strategy. If all negotiating agents vote to accept, the bid is labeled as the most recent mutual-ly accepted bid. In further rounds, the mediator modifies the most recent mutually accepted bid by exchanging one value with another randomly in the bid and asks negotiating agents to vote for the current bid. This process continues iteratively until a predefined number of bids are reached.

Inspired from the mediated negotiation approach explained above, [Aydogan & al., 2014] present feedback based mediated multilateral protocol, considering the feedbacks given by the negotiating agents during the negotiation. The mediator agent tries to model the preferences of each negotiating agent by using their feedbacks about the mediator’s bids. Consequently, the mediator aims to generate better bids for all of the agents by using the learnt model over time.

Basically, in the proposed approach, the mediator initially generates its first bid randomly and for the further bids it modifies its previous bid by exchanging one value with another in the bid randomly or according to a heuristic based on the learnt preference models during the negotiation. When the negotiating agents receive a bid from the mediator, they give a feed-back such as “better”, “worse”, and “same” rather than simply voting the mediator’s current bid either to accept or reject. To do this, the agents compare the mediator’s current bid with its previous bid and accordingly give their feedback. For example, if the current bid is better than the previous one for the agent, it says “better”.

14 RELATED WORK

Based on those feedbacks, the mediator tries to model the preferences of each negotiating party. To achieve this, the mediator only assumes that the negotiating agents give their feed-back truly, preferences are total preorder, and there is no preferential interdependency among the issues. It is worth noting that the mediator does not make any other assumptions about the negotiating agents’ preference representation. The agents may use a qualitative preference model to represent their preferences as well as they may represent their preferences by means of additive utility functions. Furthermore, this allows each negotiating agents to choose their preference representation freely. Unless there exist preferential interdependencies among the issues, the agents can employ different preference representations for their preferences.

Figure 2.2 presents the general schema of the multilateral mediated negotiation process.

2.3 Conclusion

In this chapter, firstly, we presented the agent–based approach for participatory manage-ment, essentially the MAS/RPG methodology, and we presented the SimParc project, it’s motivation, objectives and working.

Then, we presented an overview about negotiation in multi–agent systems, we started by giving a global definition, and we exposed major parts of negotiation process. Thereafter, we summarized the different types and different approaches used in automated negotiation. And finally, we presented a particularly interesting approach, the multilateral mediated negotia-tion, for which we were inspired for our work.

FIG. 2.2 – Multilateral mediated negotiation protocol with feedback [Aydogan & al., 2014]

3

Contribution: Participatory Man-

agement Negotiation Framework

In this chapter, we present our framework for the negotiation of natural resources, based on an exchange of arguments. It considers two types of agents: the participant agents (social ac-tors) and the mediator (administrator of the natural resources park), and it is composed of two levels: the inter–agent level (the interaction environment) and the agent level (the agent's internal representation). We start by presenting the Role–Playing Game aspect of the framework. Thereafter, we pre-sent the inter–agent level, and the agent level architectures (participant agents and mediator).

3.1 Role–Playing Game Aspect

Since our main contribution is to set up a negotiation framework for SimParc, let's start by recalling the main components of the SimParc game. The environment of the park is modeled with a map with icons: these icons represent the natural resources present in the region (Ap-pendix B). The park is divided into sectors (landscape units), meaning that players are asked to express their views on each sector. The negotiation focuses on Conservation Policies CP for each sector: environmental law2 in Brazil sets out a set of nine possible policies, from the most restrictive to the most flexible, CP = {Intangible, Primitive, Extensive, Historical–Cultural, Intensive, Special, Recovery, Conflicting, Temporary occupation}.

In our Framework, the game begins with assigning the roles to the players (step 1). Each one of them represents a social actor (local communities, tourism operators, public agencies, NGOs, etc.), And has a knowledge base that represents its beliefs, desires and possible ac-tions. Once the mediator begins the negotiation session, it starts by proposing an offer to the player agents (step 2). It is then that each player interprets individually the (new) received offer, and considers the stakes and consequences of this offer in relation to its potential desires or in relation to old offers already accepted (step 3–4). Only after this, players transmit their votes to the mediator.

If the offer is rejected (step 5’), the mediator revises the initial proposed offer and can, af-ter a decision–making phase, propose a new offer, taking into account the received feedbacks, (In the following sections, we will detail the mediator's decision–making, for the moment, for

2 Brazil. Decreto 5.758 de 13 de abril de 2006, que institui o Plano Nacional Estratégico de Areas Prote-gidas. Brasilia, Brazil, 2006.

16 PARTICIPATORY MANAGEMENT NEGOTIATION FRAMEWORK

the simplicity of the illustration we will represent in Figure 3.1 only the proposition of a new offer in case of rejection feedback).

If the offer is rejected (step 5”), the mediator informs the players about the success of the consensus and can then restart the cycle with a new proposal, thus activating the learning cycle for better solutions.

3.2 Inter–Agent Level

We present in this section the global architecture of our negotiation model, where agents are considered as black boxes interacting with each other through speech acts, with respecting of the negotiation protocol. The Figure 3.2 shows three sides of the inter–agent level: The world knowledge side, where agents can know about map and sectors, different possibilities of propositions, predefined rules, etc. The personal/private side, where each agent has its own knowledge base, rules and strategies. And the communication protocol side, where the media-tor and agents exchange some information for negotiation purposes.

The negotiation framework � is defined as follow:

� = ⟨Ag, �, � ⟩, where:

– Ag = M ⋃ A: all the agents involved in the negotiation

– M: the mediator of negotiation

– A: set of participant agents – �: negotiation language that represents all speech acts – ΠΠΠΠ: negotiation protocol

FIG. 3.1 – Simplified Game cycle and Learning cycle

PARTICIPATORY MANAGEMENT NEGOTIATION FRAMEWORK 17

3.2.1 Protocol Stages

The objective of the protocol is to define the speech acts that agents can send with the as-sociated operational dynamics. The negotiation protocol that we propose is characterized by a series of messages exchanged between a mediator and participants, as in the framework of Contract Net Protocol [Smith, 1980]. The protocol ΠΠΠΠ is represented by a finite–state machine3 (cf. Figure 3.3).

ΠΠΠΠ = ⟨ �, SA, Ag, Reply, Back, Turn, NMove⟩, where: – � : negotiation language that represents all speech acts – SA : set of Speech Acts – Ag = {M, A1, A2, …, An} set of Agents – Reply: SA � 2SA – Back = 0, Backtrack is not allowed, a Speech Act can be only a reply to another previ-

ous received Speech Act. – Turn: � � Ag, where � = {t1, t2, …, tk, … | ti ∈ IN, ti < ti+1}

– NMove: � ×Ag � IN with ∀(ti, Aj), NMove(ti, Aj) = 1 iff Turn(ti)=Aj

The protocol is composed of three stages: a proposal stage, a conversation stage and a deci-sion–making stage.

– Proposal stage: This stage is the first stage of our protocol, it initiates the negotia-tion. It includes the proposal of an offer by the mediator to the participants and the collection of the feedback of each one of them. Each participant can either accept or re-

3 The finite–state machines are used in several works such as [Sierra & al., 1997; Parsons & al., 1998]. A finite–state machine is able of describing different states of negotiation and establish for each state the potential speech act to use.

FIG. 3.2 – Inter–Agent Level


ject the proposed offer. We have chosen not to include the explicit counter–proposal because this functionality is not common to all multilateral mediated types of negotia-tion. implicit counter–offer is constructed the next stage of the protocol, via speech act exchange between rejecting agent and the mediator.

– Conversation stage: This stage of our protocol is optional. A conversation between the mediator and the participants takes place during which beliefs, desires, rules, and more generally arguments are exchanged in order to introduce modifications to the proposal. Following the proposed changes, one of the cases is presented, or the partici-pants accept the offer initially rejected, or the mediator proposes a new offer and we are in a new proposal phase.

– Decision stage: This final decision–making stage leads to, either the confirmation of the proposed offer and thus the continuing of the negotiation session, with learning ob-jective to find some better solutions, either the closure of the negotiation session. This decision is taken by the mediator according to the answers of the participants to its modification propositions and arguments.

3.2.2 Negotiation Speech Acts

In order to carry out a process of negotiation between agents, it is necessary to define the speech acts for negotiation between agents. It takes specific illocutions for the mediator and specific illocutions for agents. Our objective here is not to have one of our agents communi-cate with any other agent from a different platform (which would require a “FIPA compliant” platform), but to facilitate the implementation of a negotiation application with our agents. The sequence diagram of these speech acts is illustrated in Figure 3.4 in the Agent UML 1.0 formalism [Bauer & al., 2001; Huget & al., 2003].

FIG. 3.3 – Negotiation Protocol


FIG. 3.4 – Sequence diagram of Speech Acts between the Mediator and Agents


– Mediator’s Speech Acts:

Speech Act Description

SessionOpen(M, Ai) The Mediator M announces to agent Ai the opening of the nego-tiation session

Type: Broadcasting Speech Act

Expected response: Ready(Ai, M)

SessionClose(M, Ai, ϕ) The Mediator M announces to agent Ai the closure of the nego-tiation session, with the consensus about the offer ϕ. ϕ may be empty in case of no agreement reached.


Expected response: Confirm(Ai, M)

Propose(M, Ai, ϕ) The Mediator M proposes an offer ϕ to Agent Ai or a modifica-tion on an offer. The offer contains the different propositions by sector to be negotiated


Expected response: Accept(Ai, M, ϕ), Reject(Ai, M, ϕ)

AcceptedOffer(M, Ai, ϕ) The Mediator M announces to agent Ai announces that a con-sensus has been reached and that the accepted offer is ϕ


Expected response: Confirm(Ai, M, ϕ)

Assert(M, Ai, ψ) The Mediator informs Agent Ai that formula ψ is true

Type: Individual Speech Act

Expected response: ∅

Question(M, Ai, ψ) The Mediator M asks Agent Ai to answer if ψ is true or not


Expected response: Assert(Ai, M, ψ)

Request(M, Ai, ψ) The Mediator M asks Agent Ai to make ψ true


Expected response: Declare(Ai, M, ψ)

Challenge(M, Ai, ψ) The Mediator M asks Agent Ai to give an argument for ψ


Expected response: Argue(Ai, M, ⟨S, ψ⟩)


– Agent’s Speech Acts:

Speech Act Description

Ready(Ai, M) The Agent Ai informs the Mediator M that it is ready for negotiation session.


Respond to: SessionOpen(M, Ai)

Confirm(Ai, M, ϕ) The Agent Ai confirms to the Mediator M the good reception of ϕ


Respond to: SessionClose(M, Ai, ϕ), AcceptedOffer(M, Ai, ϕ)

Accept(Ai, M, ϕ) The Agent Ai Accepts proposed offer ϕ by the mediator M


Respond to: Propose(M, Ai, ϕ)

Reject(Ai, M, ϕ) The Agent Ai Rejects proposed offer ϕ by the mediator M


Respond to: Propose(M, Ai, ϕ)

Assert(Ai, M, ψ) Agent Ai informs the Mediator M that formula ψ is true


Respond to: Question(M, Ai, ψ)

Declare(Ai, M, ψ) Agent Ai informs the Mediator M that it makes ψ true


Respond to: Request(M, Ai, ψ)

Promise(Ai, M, ψ) Agent Ai informs the Mediator M that ψ will be true


Respond to: Request(M, Ai, ψ)

Argue(Ai, M, ⟨S, ψ⟩) Agent Ai informs the Mediator M that the argument A=⟨S, ψ⟩ holds, (SUPP(A)= S and CONC(A)= ψ), and respecting basic definition of an argument, let Σ be a propositional knowledge base of Ai: ① S ⊆ Σ ② S is consistent

③ S ⊢ ψ

④ S is minimal (for set ⊆) satisfying ①, ② and ③


Respond to: Challenge(M, Ai, ψ)


3.3 Agent Level

The agent level contains different components that ensure the application of agent's strate-gy in accordance with the negotiating protocol and satisfying as best as possible agent’s de-sires, according to specific agent's criteria, in the sense that each agent has its own beliefs, desires, strategy, and rules.

We present in this section the global model of negotiating agent of our framework, which is able to evaluate the mediator's proposals in an autonomous way.

3.3.1 BDI model and Logical Language

The BDI architecture [Rao & al., 1991] – Beliefs, Desires, Intentions – was designed to model the mental states and rational activity of a cognitive agent. It proposes to structure a cognitive agent in three distinct parts:

– Beliefs: the information the agent has about the environment and about the other agents;

– Desires: the states of the environment, and sometimes of itself, that the agent would like to see realized;

– Intentions: the desires that the agent has decided to accomplish or the actions he has decided to do to fulfill his desires.

A cognitive agent is therefore capable of an epistemic reasoning – about the truth values of his knowledge – and practical – about the actions that enable him to accomplish his objec-tives. Parsons and Jennings [Parsons & al., 1998] propose to upgrade the logical formulas with a degree of belief in the sense of the Dempster–Shafer theory4. Their work was motivated by the desire to design decision–makers who can both inherit the BDI architecture and Decision–making under uncertainty.

Since our framework is placed within the context of the argumentative logic, we must spec-ify our logical language; Let � be the logical language. The classical deduction is denoted ⊢ and logical equivalence ≡.

In the context of negotiation and decision–making, we define: – * the set of Beliefs, i.e. propositional symbols representing epistemic affirmations; – + the set of Desires, i.e. propositional symbols that represent all possible desires of the

agent; – , the set of Actions, i.e. propositional symbols that represent all possible actions of the

agent.

In order to take into account, the conflicts in the logic language, we will consider the form of classical negation, also called a strong negation.

4 The Dempster–Shafer theory is a mathematical theory based on the notion of evidence using belief functions and plausible reasoning.


Definition

A theory T is a logical program of the form: - ⟵ -1, …, -n where: -1, …, -n are strong literals and - called the head of the rule, and is noted head( - ⟵ -1, …, -n) . The finite set -1, …, -n is called body of the rule, and is noted body( - ⟵ -1, …, -n) .

3.3.2 Personal Knowledge Bases

In order to model the bases of the agent, we make modifications to the framework theo-rized by Amgoud and Rahwan [Rahwan & al., 2006].

First, introducing the notion of intensity of desire. Every rule for desires Φ is complement-ed with a unique value expressing the intensity of the desire head( Φ) according to the body of the rule body( Φ) . Intuitively, our motivation to satisfy a desire depends on the own moti-vations of this desire.

Moreover, in parallel to the frame of reference, we have the possibility of having a relation of preference on the desires. These two parameters allow us to define bipolar desires (positive desires: those we want to be satisfied, and negative desires: those ones we do not want them to be satisfied) in addition with a preferential ranking. This formalism allows us to apply the qualitative rules of comparisons already defined (section 3.3.2). + = {(di, 5i), i = 1, …, n}, where di is a formula of the language � and 5i is an element of ℤ. The pair (di, 5i) means that the intensity degree of the desire di is at least equal to 5i .

Beliefs are informational attitudes and concern the state of the world, they are defined as: * = {(bi, 7i), i = 1, …, m}, where bi is a formula of the language � and 7i is an element of the interval [0,1]. The pair (bi, 7i) means that the certainty degree of the belief bi is at least equal to 7i. When 7i is equal to 1 this means that bi is an integrity constraint which should be ful-filled. For the sake of simplicity and mainly for the purpose of logical argumentation, we sup-pose that all beliefs are completely certain i.e. 7i = 1 for i = 1, …, m. However, this work can be easily generalized to the case where beliefs are more or less certain.

Actions are logic rules express that if a set of desires are satisfied then the action is achieved, they are defined as: , = {(ai ⟵ d1, …, dn), i = 1, …, p}, where ai is an element of the set of conservation policies CP (defined section 3.1), and d1, …, dn elements of +.

Let us note +* and ** the bases described above deprived of their numerical components, respectively intensity degree and certainty degree.

We also define rules of inference to describe epistemic rules, rules on desires and rules on decisions, these rules of inference are defined as: di ⟵ d1, …, dn, b1, …, bm or bi ⟵ d1, …, dn, b1, …, bm where ∀di ∈ +*, ∀bi ∈ **.

3.3.3 Learned Knowledge Bases

During a negotiation, an agent always needs to store, exploit and update local knowledge. We distinguish two types of local knowledge: the knowledge that represents the mental state of the agent (Beliefs, Desires and Actions), we call it Personal Knowledge Base ;<= and


knowledge that depends on the environment, we call it Learned Knowledge Base �<= (histor-ic of exchanged speech acts, state of negotiation, latest accepted offers, opponent agent's be-liefs and desires, etc.).

Learned Knowledge allow the agent to represent the outside world, and the negotiation map in order to implement an effective negotiation strategy.

3.3.4 Qualitative Bipolar Desires

Inspired from the Qualitative Comparison of Decisions [Dubois & al., 2008], we introduce bipolar desires for our framework.

In a formal way for a finite set of desires +, we have a set X of criteria or arguments, viewed as attributes ranging on a bipolar scale, say V; and a totally ordered scale L expressing the relative importance of criteria or groups of criteria. In this master thesis, we use the sim-plest possible bipolar scale V = {−, 0, +}, whose elements re\ect negativity, neutrality, and positivity, respectively. With this scale, any argument in X is either completely against, total-ly irrelevant, or totally in favor of each desire in +.5

By applying the qualitative rules of Bonnefon and Fargier [Bonnefon & al., 2006], compar-ing decisions then amounts to comparing sets of arguments, i.e. subsets A, B of 2X. X can be divided in three disjoint subsets: X+ is the set of positive arguments, X− the set of

negative arguments, X0 the set of indifferent ones. Any A ⊆ X can likewise be partitioned: let A+ = A ∩ X+, A− = A ∩ X−, A0 = A ∩ X0 be respectively the positive, negative and indiffer-ent arguments of A. Arguments can be of varying importance. In a purely qualitative, ordinal approach, the importance of arguments can be described on a totally ordered scale of magni-tude L = [0L, 1L], for example by the following function π:

π : X ↦ L = [0L, 1L]

π(x) = 0L means that the decision maker is indifferent to argument x: this argument will not affect the decision process. The order of magnitude 1L (the highest level of importance) is at-tached to the most compelling arguments that the decision–maker can consider. Finally, the order of magnitude OM(A) of a set A is defined as the highest of the order of magnitude of its elements [Bonnefon & al., 2006]:

∀A ⊆ X, OM(A) = max π(x), x ∈ A

3.3.5 Rules and Evaluation Mechanism

Our autonomous agent uses seven rules according to [Bonnefon & al., 2006], and one own rule AtLeastH. In the following the presentation of these rules:

The qualitative Pareto comparison: Pareto

This rule compares the two sets of arguments as a problem of bicriteria decision. The first criterion compares negative arguments, the second criterion compares positive arguments. A is strictly preferred to B in two cases: OM(A+) ≥ OM(B+) and OM(A−) < OM(B−), or OM(A+) 5 For further information, we invite the reader to refer to [Dubois &al., 2008] and [Bonnefon &al., 2006].


> OM(B+) and OM(A−) ≤ OM(B−). A and B are indifferent when OM(A+) = OM(B+) and OM(A−) = OM(B−). In other cases, A is not comparable with B.

The implication rule: DPoss

This rule focuses on the most important arguments in the situation. A is at least as good as B iff, at level OM(A ∪ B), the presence of arguments for B is cancelled by the existence of arguments for A, and the existence of arguments against A is cancelled by the existence of arguments against B. Formally: A ≥ B iff OM(A ∪ B) = OM(B+) ⇒ OM(A ∪ B) = OM(A+) and OM(A ∪ B) = OM(A−) ⇒ OM(A ∪ B) = OM(B−).

The ordinal bipolar rule: Poss

This rule considers any argument against A as an argument for B; any argument for A as an argument against B; and reciprocally. Then, the decision supported by the strongest argu-ment(s) is preferred: A ≥ B iff max(OM(A+), OM(B−)) ≥ max(OM(B+), OM(A−)).

Discriminating arguments: Discri and DDiscri

Pareto, Poss and DPoss suffer from a severe drowning effect that is often found in purely possibilistic frameworks. For example, when B is included in A, and even if all of the proper elements of A are positive, A is not necessarily strictly preferred to B. Discri and DDiscri incorporate the principle of preferential independence6, by cancelling el-

ements that appear in both sets before applying Poss or DPoss:

A ≥Discri B ⇔ A\B ≥Poss B\A A ≥DDiscri B ⇔ A\B ≥DPoss B\A

Cardinality rules: BiLexi and Lexi

These rules are based on a level wise comparison by cardinality. The arguments in A and B are scanned top–down, until a level is reached such that there is a difference either in the number of arguments for A and B, or in the number of arguments against A and B. At this point, the set that presents the lower number of negative arguments and the greater number of positive ones is preferred. Formally: for any level i ∈ L, let Ai = {x ∈ A, π(x)= i} ; Ai + = Ai ∩ X+ ; Ai− = Ai ∩ X− Let δ be the highest value of i s.t. |Ai+| ≠ |Bi+| or |Ai−| ≠ |Bi−|. Then:

A ≥BiLexi B ⇔ |Aδ+| ≥ |Bδ

+| and |Aδ−| ≤ |Bδ

−|

The idea behind Lexi is to simplify each set before the comparison, accepting that one posi-tive and one negative argument of A can cancel each other. In other terms, at each level j, A is assigned the score |Aj+| − |Aj−|. A top–down comparison of the scores is then performed: A ≥Lexi B ⇔ ∃i ∈ L such that:

∀ j > i, |Aj+| − |Aj−| = |Bj+| − |Bj−| and |Ai+| − |Ai−| > |Bi+| − |Bi−|

6 ∀A, B, C such that (A ∪ B) ∩ C = ∅ : A ≥ B ⇔ A ∪ C ≥ B ∪ C


At Least Highest rule: AtLeastH

We define the AtLeastH rule, in order to have a less restrictive comparison rule for starting purposes: we assume that starting with a rule that gives a lower level of restriction will allow us to subsequently improve the result of the negotiation, and this from a collective perspec-tive, which will more democratically satisfy all the agents. This rule does not depart much from the DPoss rule, formally:

A ≥ B iff OM(A ∪ B) = OM(B) ⇒ OM(A ∪ B) = OM(A)

3.3.6 Conversation and explanatory arguments

According to Rahwan [Rahwan & al., 2006], an illocution goes through three steps: the evaluation of the received proposal, the generation of a set of candidate arguments and finally the selection of the strongest argument. Applying this to the conversation stage (presented section 3.2.2) and adopting the hypothesis that agents are rational and without trick. The speech acts of the agent and the mediator fit in a simple case of question/answer.

However, for the case of Challenge/Argue we are dealing with explanatory arguments. Amgoud and Kaci have introduced explanatory arguments as a means for generating desires from beliefs [Amgoud & al., 2004]. Later this was extended by Rahwan and Amgoud, combin-ing belief argumentation with desire argumentation in a single framework [Rahwan & al., 2006]. We adapt their definition of an explanatory argument as follow:

If ∃(⇒ ψ) ∈ CP then ⇒ ψ is an explanatory argument (E) with: BELIEFS( E) = ∅

DESIRES(E) = ∅

CONC(E) = ψ

If b1, …, bn are belief arguments constructed from ** and d1, …, dm are desires arguments constructed from +*, and ∃CONC(b1) ∧ … ∧ CONC(bn) ∧ CONC(d1) ∧ … ∧ CONC(dm) ⇒ ψ ∈ CP Then b1, …, bn,d1, …, dm ⇒ ψ is an explanatory argument (E) with:

BELIEFS( E) = SUPP(b1) ∪ … ∪ SUPP(bn) ∪ BELIEFS( d1) ∪ … ∪ BELIEFS( dm)

DESIRES(E) = DESIRES(d1) ∪ … ∪ DESIRES(dm)

CONC(E) = ψ

By now, our framework only provide explanatory arguments for ψ ∈ CP. This can be ex-tended by including explanatory arguments for +*, according to the argumentation frame-work presented by [Rahwan & al., 2006].

3.3.7 Agent’s architecture

Now, we are able to define the structure of an agent in our framework. An agent is a tuple ⟨ ;*, ;+, ;,, ;F, �*, �+, �F, ;⟩ where:

– ;* is the personal beliefs base; – ;+ is the personal desires base; – ;, is the personal actions base; – ;F is the personal inference rules base;


– �* is the learned beliefs base, that the agent learned about other agents; – �+ is the learned desires base, that the agent learned about other agents; – �F is the learned inference rules base, that the agent learned about other agents; – ; is the profile of the agent; – G is the evaluation rule of the agent.

At the beginning of the serious game cycle, each agent is associated to a role of a social ac-tor (local communities, tourism operators, public agencies, NGOs, etc.), each one of them is represented in the formal way by a profile ;, which include predefined beliefs, desires, and

rules. This profile is known by the mediator unlike the bases that are private.

Figure 3.5 below illustrates a graphical representation of our agent. Where each incoming

Speech Act is decomposed into a Performative and a Content, each one is evaluated and in-terpreted in the knowledge representation phase, according to the agent’s knowledge bases and world knowledge. All of this will let the agent to construct the Outcoming Speech Act based either on the evaluation mechanism (case of new offer received), ei-ther on the argument construction phase (case of explanatory arguments).

FIG. 3.5 – Agent architecture


3.4 Mediator Level

3.4.1 Offer proposition

We distinguish two levels in the proposition of offers: the first start–up offer, which is of a somewhat special nature, and the rest of the offers that evolve during the negotiation. This distinction is motivated by the fact that if the mediator proposes a first offer that satisfies the desires of some agents at the expense of others, these agents who have accepted the initial offer will have little chance of making concessions on future offers.

At the moment, our mediator generates offers randomly, but we have already prepared the ground with the ;<= and �<= bases specific to the mediator, in such a way that learning and generating more elaborate offers will be possible.

3.4.2 Negotiation cycle

We have chosen to build a mediator that operates through negotiation cycles. During each cycle, the mediator is totally autonomous, proposing offers without external intervention based only on his own knowledge bases. In order, not to have an infinite conversation phase, we have defined the number of negotiation rounds, i.e. the number of times the mediator pro-poses an offer and the participants return their feedback. We have chosen to limit the dura-tion of the negotiation by a number of turns of speech coupled with a waiting time (TTL) for the answers rather than a maximum duration, as is often the case, because we think that the negotiation will be more effective so. We can indeed assume that negotiation deadline will encourage agents to make more concessions on the offer that is proposed to them. Because, for every round that passes, the negotiation approaches a negotiation of type take it or leave it.

3.4.3 Negotiation response time

In distributed negotiations, as is the case in our framework, when agents are acting on be-half of a user (assistant agents) a participant may not respond to the mediator's proposal, either because the participant is absent or because a breakdown has occurred, then negotia-tion must not be blocked. In order to allow the negotiation to continue, a response waiting time mechanism (TTL) is set up, and when this time elapses, the mediator considers a default response for the participant. This default answer will very often be an acceptance of the pro-posal: indeed, in such situations of resource management a silence is equivalent to a non–contestation of the proposal.

3.4.4 Proposition validation

In order for the mediator to decide whether to validate or to cancel a proposition, accord-ing to the feedbacks of the participants, a parameter setting the minimum number of agree-ments necessary to confirm the contract is set up. This number may take the form of a per-


centage. For example, for a 100% acceptance rate the validation must take place only if all participants have accepted this offer, this is called a vote by Veto. However, for an acceptance rate of at least 50%, it is a vote by Absolute Majority.

3.5 Conclusion

In this chapter, we presented our Participatory Management Negotiation Framework based on an exchange of arguments, we presented the inter–agent level describing the negotiation protocol and Speech Acts. Then we presented the Agent level, we presented the agent's BDI bases, the qualitative bipolar desires, the evaluation mechanism, and the agent’s architecture. Thereafter we presented the Mediator level with the negotiation cycle, negotiation response time and proposition validation.

4

Conclusion and Perspectives

Negotiation is an important issue in multi–agent systems. It concerns the interaction be-tween at least two agents regulated by the protocol of negotiation. Each agent has its own reasoning mechanism and negotiation strategy. As said Iyad Rahwan: “There is no universal approach to automated negotiation that suits every problem domain”.

In general, our Participatory Management Negotiation Framework satisfies the different properties required for a negotiation framework described by Jennings [Jennings & al., 2001], namely:

– The minimum requirement of a negotiating agent is the ability to make and respond to proposals. – The minimal requirement for the agents is that they are able to indicate dissatisfaction with proposals that they find unacceptable. – If agents can only accept or reject proposals, then negotiation can be very time consum-ing and inefficient. To improve the efficiency of the negotiation process, the agents needs to be able to provide more useful feedback on the received proposals. This feedback can take the form of a critique. From such feedback, the mediator should be in position to generate a proposal that is more likely to lead to an agreement.

We have presented in this master thesis the bases of our framework, we succeeded in im-plementing and validating our model under Jason/AgentSpeak, however this is only a first version of our work that will be extended and improved in future work. Our vision on the Negotiation under Participatory management is that the mediator generates bids and asks negotiating agents for their feedback about those bids. Accordingly, the mediator generates and updates a preference model – modelized by an argumentation system – for each negotiat-ing agent by interpreting the agents’ feedbacks during the negotiation. By using the learnt model, the mediator generates better bids for all agents over time.

On the agent’s side, we have already prepared the ground with the evaluations rules, the learned bases and the modelling of a universal language of communication between agents. The next step will be the implementing of the coalitions, attack/support arguments and the use of tactical strategies for negotiation.

We want to conclude by: In the negotiation process, the multiplicity of views and voices is a fundamental condition of fairness and justice. But this does not mean that all points of view and voices are equal, that they have the same weight, and that they can, by the same right, participate in the negotiation of participatory management plans and agreements. There is a profound difference between equity and equality!

Bibliography

[Adamatti & al., 2007] ADAMATTI, D. F., SICHMAN, J. S., et COELHO, H. Virtual players: From manual to semi–autonomous RPG. AIS–CMS, 2007, vol. 7, p. 159–164.

[Amgoud & al., 2000] AMGOUD, Leila, PARSONS, Simon, et MAUDET, Nicolas. Arguments, dialogue, and negotiation. In : Proceedings of the 14th European Conference on Artificial Intelligence. IOS Press, 2000. p. 338–342.

[Amgoud & al., 2004] AMGOUD, Leila et KACI, Souhila. On the Generation of Bipolar Goals in Argumenta-tion–Based Negotiation. ArgMAS, 2004, vol. 3366, p. 192–207.

[Amgoud & al., 2004] AMGOUD, Leila et PRADE, Henri. Reaching Agreement Through Argumentation: A Possibilistic Approach. KR, 2004, vol. 2004, p. 175–182.

[Amgoud & al., 2007] AMGOUD, Leila, DIMOPOULOS, Yannis, et MORAITIS, Pavlos. A unified and general framework for argumentation–based negotiation. In : Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems. ACM, 2007. p. 158.

[Aydogan & al,. 2014] AYDOGAN, Reyhan, HINDRIKS, Koen V., et JONKER, Catholijn M. Multilateral mediated negotiation protocols with feedback. In : Novel Insights in Agent–based Complex Automated Nego-tiation. Springer Japan, 2014. p. 43–59.

[Aydogan, 2011] AYDOGAN, Reyhan. Negotiating with Qualitative Preferences: Methods for Generating Bids Effectively, Ph.D. Thesis, Bogaziçi University, Turkey, 2011.

[Barreteau & al., 2003] BARRETEAU, Olivier, ANTONA, Martine, D'AQUINO, Patrick, et al. Our companion modelling approach. Journal of Artificial Societies and Social Simulation, 2003, vol. 6, no 1.

[Bauer & al., 2001] BAUER, Bernhard, MÜLLER, Jörg P., et ODELL, James. Agent UML: A formalism for specifying multiagent software systems. International journal of software engineering and knowledge engi-neering, 2001, vol. 11, no 03, p. 207–230.

[Bichler & al., 2001] BICHLER, Martin et SEGEV, Arie. Methodologies for the design of negotiation protocols on E–markets. Computer Networks, 2001, vol. 37, no 2, p. 137–152.

[Bonnefon & al., 2006] BONNEFON, Jean–François et FARGIER, Hélène. Comparing sets of positive and negative arguments: Empirical assessment of seven qualitative rules. FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS, 2006, vol. 141, p. 16.

[Bordini & al., 2007] BORDINI, Rafael H., HÜBNER, Jomi Fred, et WOOLDRIDGE, Michael. Programming multi–agent systems in AgentSpeak using Jason. John Wiley & Sons, 2007.

[Borrini–Feyerabend, 2000] BORRINI–FEYERABEND, Grazia. La gestion participative des ressources na-turelles: organisation, négociation et apprentissage par l'action. Kasparek Verlag, 2000.

[Briot & al,. 2017] BRIOT, Jean–Pierre, IRVING, Marta De Azevedo, VASCONCELOS FILHO, José Eurico, et al. Participatory Management of Protected Areas for Biodiversity Conservation and Social Inclusion. 2017.

[Briot & al., 2007] BRIOT, Jean–Pierre, GUYOT, Paul, et IRVING, Marta. Participatory simulation for collec-tive management of protected areas for biodiversity conservation and social inclusion. AIS–CMS, 2007, vol. 7, p. 183–188.

[Briot & al., 2008] BRIOT, Jean–Pierre, VASCONCELOS, Eurico, ADAMATTI, Diana, et al. A computer–based support for participatory management of protected areas: The SimParc project. In : Anais do XXVIII Congresso da SBC (SBC’08)–Seminário Integrado de Software e Hardware “Grandes Desafios. 2008. p. 1–15.

32 BIBLIOGRAPHY

[Caminada & al., 2007] CAMINADA, Martin et AMGOUD, Leila. On the evaluation of argumentation formal-isms. Artificial Intelligence, 2007, vol. 171, no 5–6, p. 286–310.

[Dash & al., 2003] DASH, Rajdeep K., JENNINGS, Nicholas R., et PARKES, David C. Computational–mechanism design: A call to arms. IEEE intelligent systems, 2003, vol. 18, no 6, p. 40–47.

[Dimopoulos & al.,2014] DIMOPOULOS, Yannis et MORAITIS, Pavlos. Advances in argumentation–based negotiation. Negotiation and Argumentation in Multi–agent Systems: Fundamentals, Theories, Systems and Applications, 2011, p. 82–125.

[Dubois & al., 2008] DUBOIS, Didier, FARGIER, Hélène, et BONNEFON, Jean–François. On the qualitative comparison of decisions having positive and negative features. Journal of Artificial Intelligence Research, 2008, vol. 32, p. 385–417.

[Esmaeili & al., 2009] ESMAEILI, Maryam, ARYANEZHAD, Mir–Bahador, et ZEEPHONGSEKUL, Panlop. A game theory approach in seller–buyer supply chain. European Journal of Operational Research, 2009, vol. 195, no 2, p. 442–448.

[Fagiolo & al., 2006] FAGIOLO, Giorgio, WINDRUM, Paul, et MONETA, Alessio. Empirical validation of agent–based models: A critical survey. LEM Working Paper Series, 2006.

[Gilbert, 2006] GILBERT, Nigel, DEN BESTEN, Matthijs, BONTOVICS, Akos, et al. Emerging artificial societies through learning. Journal of Artificial Societies and Social Simulation, 2006, vol. 9, no 2.

[Gilbert, 2008] GILBERT, Nigel. Agent–Based Models, Quantitative Applications in the Social Science153. London, Thousand Oaks, 2008.

[Guttman & al., 1998] GUTTMAN, Robert H. et MAES, Pattie. Cooperative vs. competitive multi–agent negotiations in retail electronic commerce. In : International Workshop on Cooperative Information Agents. Springer, Berlin, Heidelberg, 1998. p. 135–147.

[Guyot & al., 2006] GUYOT, Paul et HONIDEN, Shinichi. Agent–based participatory simulations: Merging multi–agent systems and role–playing games. Journal of Artificial Societies and Social Simulation, 2006, vol. 9, no 4.

[Hafid & al., 1998] HAFID, Abdelhakim, VON BOCHMANN, Gregor, et DSSOULI, Rachida. A quality of service negotiation approach with future reservations (nafur): A detailed study. Computer Networks and ISDN Systems, 1998, vol. 30, no 8, p. 777–794.

[Huang & al., 2010] HUANG, Chun–Che, LIANG, Wen–Yau, LAI, Yu–Hsin, et al. The agent–based negotiation process for B2C e–commerce. Expert Systems with Applications, 2010, vol. 37, no 1, p. 348–359.

[Huget & al., 2003] HUGET, Marc–Philippe, ODELL, James, HAUGEN, Øystein, et al. FIPA modeling: Inter-action diagrams. Working Draft Version, 2003, p. 07–02.

[Irving, 2006] IRVING, Marta de Azevedo. Áreas protegidas e inclusão social: construindo novos significados. Rio de Janeiro: Aquarius, 2006.

[Jain & al., 2009] JAIN, Vipul et DESHMUKH, S. G. Dynamic supply chain modeling using a new fuzzy hybrid negotiation mechanism. International Journal of Production Economics, 2009, vol. 122, no 1, p. 319–328.

[Jennings & al,. 2001] JENNINGS, Nicholas R., FARATIN, Peyman, LOMUSCIO, Alessio R., et al. Automated negotiation: prospects, methods and challenges. Group Decision and Negotiation, 2001, vol. 10, no 2, p. 199–215.

[Kahneman, 2003] KAHNEMAN, Daniel. A perspective on judgment and choice: mapping bounded rationality. American psychologist, 2003, vol. 58, no 9, p. 697.

[Kakas & al.,2006] KAKAS, Antonis et MORAITIS, Pavlos. Adaptive agent negotiation via argumentation. In : Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems. ACM, 2006. p. 384–391.

BIBLIOGRAPHY 33

[Klein, 2003] KLEIN, Mark, FARATIN, Peyman, SAYAMA, Hiroki, et al. Protocols for negotiating complex contracts. IEEE Intelligent Systems, 2003, vol. 18, no 6, p. 32–38.

[Kraus & al., 1998] KRAUS, Sarit, SYCARA, Katia, et EVENCHIK, Amir. Reaching agreements through argumentation: a logical model and implementation. Artificial Intelligence, 1998, vol. 104, no 1–2, p. 1–69.

[Le Page & al., 2012] LE PAGE, Christophe, BECU, Nicolas, BOMMEL, Pierre, et al. Participatory agent–based simulation for renewable resource management: the role of the cormas simulation platform to nurture a community of practice. Journal of artificial societies and social simulation, 2012, vol. 15, no 1, p. 10.

[Lee & al., 2009] LEE, Chun Ching et OU–YANG, C. A neural networks approach for forecasting the supplier’s bid prices in supplier selection negotiation process. Expert Systems with Applications, 2009, vol. 36, no 2, p. 2961–2970.

[Li & al., 2003] LI, Cuihong, GIAMPAPA, Joseph, et SYCARA–CYRANSKI, Katia. A review of research literature on bilateral negotiations. 2003.

[Lin & al., 2004] LIN, Raymund J. et SENG–CHO, T. Chou. Mediating a bilateral multi–issue negotiation. Electronic Commerce Research and Applications, 2004, vol. 3, no 2, p. 126–138.

[Luo & al., 2003] LUO, Xudong, JENNINGS, Nicholas R., SHADBOLT, Nigel, et al. A fuzzy constraint based model for bilateral, multi–issue negotiations in semi–competitive environments. Artificial Intelligence, 2003, vol. 148, no 1–2, p. 53–102.

[Mohan al., 2006] MOHAN, Kannan, XU, Peng, et RAMESH, Balasubramaniam. Supporting dynamic group decision and negotiation processes: A traceability augmented peer–to–peer network approach. Information & management, 2006, vol. 43, no 5, p. 650–662.

[Ostrom, 1999] OSTROM, Elinor. Coping with tragedies of the commons. Annual review of political science, 1999, vol. 2, no 1, p. 493–535.

[Parsons & al., 1996] PARSONS, Simon et JENNINGS, Nicholas R. Negotiation through argumentation—a preliminary report. In : Proceedings of the 2nd international conference On multi agent systems. 1996. p. 267–274.

[Parsons & al., 1998] PARSONS, Simon, SIERRA, Carles, et JENNINGS, Nick. Agents that reason and negoti-ate by arguing. Journal of Logic and computation, 1998, vol. 8, no 3, p. 261–292.

[Rahwan & al,. 2003] RAHWAN, Iyad, RAMCHURN, Sarvapali D., JENNINGS, Nicholas R., et al. Argumen-tation–based negotiation. The Knowledge Engineering Review, 2003, vol. 18, no 4, p. 343–375.

[Rahwan & al., 2006] RAHWAN, Iyad et AMGOUD, Leila. An argumentation based approach for practical reasoning. In : Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems. ACM, 2006. p. 347–354.

[Raiffa, 1982] RAIFFA, Howard. The art and science of negotiation. Harvard University Press, 1982.

[Rao & al., 1991] RAO, Anand S. et GEORGEFF, Michael P. Modeling rational agents within a BDI–architecture. KR, 1991, vol. 91, p. 473–484.

[Rao, 1987] RAO, S. S. Game theory approach for multiobjective structural optimization. Computers & Struc-tures, 1987, vol. 25, no 1, p. 119–127.

[Rao, 1996] RAO, Anand S. AgentSpeak (L): BDI agents speak out in a logical computable language. In : European Workshop on Modelling Autonomous Agents in a Multi–Agent World. Springer, Berlin, Heidel-berg, 1996. p. 42–55.

[Reed, 1998] REED, Chris. Dialogue frames in agent communication. In : Multi Agent Systems, 1998. Proceed-ings. International Conference on. IEEE, 1998. p. 246–253.

34 BIBLIOGRAPHY

[Sierra & al., 1997] SIERRA, Carles, FARATIN, Peyman, et JENNINGS, Nicholas R. A service–oriented nego-tiation model between autonomous agents. Collaboration between human and artificial societies, 1997, vol. 1997, p. 201–219.

[Smith, 1980] SMITH, Reid G. The contract net protocol: High–level communication and control in a distribut-ed problem solver. IEEE Transactions on computers, 1980, no 12, p. 1104–1113.

[Sordoni & al., 2010] SORDONI, Alessandro, BRIOT, Jean–Pierre, ALVAREZ, Isabelle, et al. Design of a participatory decision–making agent architecture based on argumentation and influence function–Application to a serious game about biodiversity conservation. RAIRO–Operations Research, 2010, vol. 44, no 4, p. 269–283.

[Sycara, 1990] SYCARA, Katia P. Persuasive argumentation in negotiation. Theory and decision, 1990, vol. 28, no 3, p. 203–242.

[Tohmé & al., 1997] TOHME, Fernando. Negotiation and defeasible reasons for choice. In : Proceedings of the Stanford spring symposium On qualitative preferences in deliberation and practical reasoning. 1997. p. 95–102.

[Tykhonov, 2010] TYKHONOV, Dmytro. Designing Generic and Effcient Negotiation Strategies, Ph.D. thesis, Delft University of Technology, Delft, The Netherlands, 2010.

[Verrons, 2004] VERRONS, Marie–Hélène. GeNCA: un modèle général de négociation de contrats entre agents. 2004. Thèse de doctorat. Université des Sciences et Technologie de Lille–Lille I.

[Vesic, 2011] VESIC, Srdjan. Preference–based argumentation frameworks: application in decision making and negotiation. 2011. Thèse de doctorat. Université Paul Sabatier–Toulouse III.

[Wolters & al., 1997] WOLTERS, Heiko et SCHULLER, Frank. Explaining supplier–buyer partnerships: a dynamic game theory approach. European Journal of Purchasing & Supply Management, 1997, vol. 3, no 3, p. 155–164.

[Wooldridge, 2009] WOOLDRIDGE, Michael. An introduction to multiagent systems. John Wiley & Sons, 2009.

Appendix A: Example of application

of Framework

Each landscape unit (sector), includes different types of resources: natural resources (e.g. forest, beach, etc.), infrastructure resources (e.g. road, village, hotel, etc.) and usage resources (e.g. risk of fires, hunting, etc.). For example, the landscape unit below (sector 6) includes:

– primary forest in the north – secondary forest – risk of forest fires – road - in red - which passes through the unit – public dumps – important tourist inflows

– villages – beach – turtle breeding area – hotel – shopping center – etc.

Consider 4 Agents, respectively, the Government Agency of Energy, the Green Peace NGO, the Tourist Operator, and the Chef Raoni 7, who want to negotiate natural resources of 7

7 https://en.wikipedia.org/wiki/Raoni_Metuktire

36 APPENDIX A

sectors. Each one has its own beliefs and desires, for example: Agent 1 (Government Agency of Energy), desires to build dams in sectors 4 and 5 and, and Agent 4 (Chef Raoni) opposes it.

For the simplicity of the proof, assume that there are three CP conservation policies CP = {Intangible, Primitive, Intensive}

And we have a mediator M that orchestrates the negotiation between the four agents de-fined as follow:

A1 = ⟨ ;*, ;+, ;,, ;F, �*, �+, �F, ;⟩ where:

– ;* = {B(1,foret_secondaire), B(1,chute_eau), B(1,route), B(2,foret_primaire), B(3,foret_primaire), B(3,chute_eau), B(4,foret_primaire), B(4,chute_eau), B(4,route), B(5,foret_primaire), B(5,route), B(5,chute_eau), B(6,foret_primaire), B(6,foret_secondaire), B(6,route), B(6,chute_eau), B(6,village), B(6,hotel), B(6,centre_commercial), B(7,mer)}

– ;+ = {D(4,construction_barrage)[1], D(5,construction_barrage)[1]}

– ;, = {intangible ⟶ proteger_foret, intangible ⟶ proteger_paturages, intangible ⟶ proteger_habitations, intangible ⟶ proteger_tortues, intangible ⟶ proteger_poisons, intangible ⟶ proteger_animaux, intangible ⟶ proteger_oiseaux, intangible ⟶ retirer_route, intangible ⟶ retirer_decharge, primitif ⟶ visite_safari, primitif ⟶ visite_monastere, primitif ⟶ proteger_foret, primitif ⟶ proteger_habitations, primitif ⟶ proteger_tortues, primitif ⟶ eco_tourisme, intensif ⟶ visite_safari, intensif ⟶ visite_monastere, intensif ⟶ visite_tortues, intensif ⟶ construction_barrage}

– ;F = ∅ – �* = ∅ – �+ = ∅ – �F = ∅ – ; = Government Agency – G = AtLeastH

A2 = ⟨ ;*, ;+, ;,, ;F, �*, �+, �F, ;⟩ where:

– ;* = { B(1,foret_secondaire), B(1,plage), B(1,risque_feux), B(1,route), B(1,mer), B(2,foret_primaire), B(2,risque_feux), B(2,animaux_sauvages), B(3,foret_primaire), B(3,chasse), B(3,animaux_sauvages), B(4,foret_primaire), B(4,chute_eau), B(4,afflux_touristique), B(4,route), B(4,oiseaux), B(5,foret_primaire), B(5,route), B(5,risque_feux), B(5,animaux_sauvages), B(5,oiseaux), B(5,crabes), B(5,afflux_touristique), B(6,foret_primaire), B(6,foret_secondaire), B(6,risque_feux), B(6,route), B(6,decharge), B(6,afflux_touristique), B(6,chasse), B(6,plage), B(6,tortues), B(7,poissons), B(7,peche), B(7,mer)}

APPENDIX A 37

– ;+ = { D(2,proteger_foret)[4], D(3,proteger_foret)[4], D(3,retirer_route)[1], D(4,proteger_foret)[4], D(5,proteger_foret)[4], ~D(5,construction_barrage)[3], D(6,proteger_foret)[4], D(6,proteger_tortues)[5], D(7,proteger_poisons)[3] }


– ;F = { D(ID,retirer_decharge)[X] ⟵ B(ID,decharge) & D(ID,proteger_poisons)[X]}

– �* = ∅ – �+ = ∅ – �F = ∅ – ; = Environment ONG – G = AtLeastH

A3 = ⟨ ;*, ;+, ;,, ;F, �*, �+, �F, ;⟩ where:

– ;* = {B(1,chute_eau), B(1,afflux_touristique), B(1,plage), B(1,route), B(1,mer), B(2,foret_primaire), B(3,foret_primaire), B(3,chute_eau), B(3,chasse), B(3,animaux_sauvages), B(4,foret_primaire), B(4,monastere), B(4,chute_eau), B(4,afflux_touristique), B(4,route), B(4,oiseaux), B(4,centre_observation), B(5,foret_primaire), B(5,route), B(5,alpinisme), B(5,chute_eau), B(5,crabes), B(5,afflux_touristique), B(6,foret_primaire), B(6,route), B(6,chute_eau), B(6,afflux_touristique), B(6,village), B(6,plage), B(6,tortues), B(6,hotel), B(6,centre_commercial), B(7,poissons), B(7,plongee), B(7,mer) }

– ;+ ={ D(3,visite_safari)[4], D(6,visite_tortues)[5], D(4,visite_monastere)[5], D(5,parc_escalade)[1] }

– ;, = {intangible ⟶ proteger_foret, intangible ⟶ proteger_paturages, intangible ⟶ proteger_habitations, intangible ⟶ proteger_tortues, intangible ⟶ proteger_poisons, intangible ⟶ proteger_animaux, intangible ⟶ proteger_oiseaux, intangible ⟶ retirer_route, intangible ⟶ retirer_decharge, primitif ⟶ visite_safari, primitif ⟶ visite_monastere, primitif ⟶ proteger_foret, primitif ⟶ proteger_habitations, primitif ⟶ proteger_tortues, primitif ⟶ eco_tourisme, intensif ⟶ visite_safari, intensif ⟶ visite_monastere, intensif ⟶ visite_tortues,

38 APPENDIX A

intensif ⟶ construction_barrage}

– ;F = {~D(ID,retirer_route)[X] ⟵ B(ID,animaux_sauvages) & D(ID,visite_safari)[X], D(4,visite_monastere_hiver)[1] ⟵ DAg4(6,eco_tourisme) }

– �* = ∅ – �+ = ∅ – �F = ∅ – ; = Tourist Operator – G = AtLeastH

A4 = ⟨ ;*, ;+, ;,, ;F, �*, �+, �F, ;⟩ where:

– ;* = {B(1,foret_secondaire), B(1,afflux_touristique), B(1,plage), B(1,route), B(1,mer), B(2,foret_primaire), B(2,animaux_sauvages), B(3,foret_primaire), B(3,animaux_sauvages), B(4,foret_primaire), B(4,monastere), B(4,route), B(4,afflux_touristique), B(5, afflux_touristique), B(5,route), B(5,betail), B(5,animaux_sauvages), B(5,foret_primaire), B(5,crabes), B(6,foret_primaire), B(6,foret_secondaire), B(6,route), B(6,decharge), B(6,afflux_touristique), B(6,village), B(6, centre_commercial), B(6,plage), B(6,tortues), B(6,hotel), B(6, chasse), B(7,poissons), B(7,peche), B(7,mer) }

– ;+ ={ D(2,proteger_foret)[10], D(3,proteger_foret)[10], D(4,proteger_foret)[10], D(5,proteger_foret)[10], D(5,proteger_paturages)[7], D(4,proteger_habitations)[5], D(5,proteger_habitations)[5], ~D(4,visite_monastere)[7], ~D(4,construction_barrage)[10], ~D(5,construction_barrage)[10]}


– ;F = ∅ – �* = ∅ – �+ = ∅ – �F = ∅ – ; = null – G = AtLeastH

APPENDIX A 39

The system was implemented using the Jason multi–agent platform. This choice was moti-vated by several reasons. Based on the AgentSpeak language, the platform allows complete control over the BDI architecture. Having the interfaces with the Java language, it offers the possibility of coupling logic and imperative programming. This has helped us considerably in the implementation of the negotiation process. Moreover, the platform includes inter–agent communication based on Speech Acts.

In what follows the screenshots of the mediator who carries out a negotiation cycle with agents, and the conversation phase between the mediator and an agent (at this stage of the work, the conversation remains manual, at the initiative of the human).

The mediator being configured at 70% acceptance level, starts the negotiation phase (in-stantiated for 7 rounds). The first proposed offer {intangible, intangible, intensif, intensif, intangible, intensif, intensif} is randomly generated.

Each agent replies either by accept or reject (as shown in the Connected Agents box). This offer is approved by the mediator for Sectors 1, 2 and 7. The next proposal will no longer con-cern these sectors, until reaching a consensus. After for the learning phase, the mediator re-sumes proposals from the beginning.

Since there is no consensus on the whole offer, the mediator proposes the offer N° 2, {in-tangible, intangible, primitif, primitif, intensif, intangible, intensif}

40 APPENDIX A

Following the same logic, the mediator continues his cycle with the offer N° 3 and N° 4.

Before continuing, let’s take an example of the agent's internal reasoning. For example, let's see why the agent N°3 rejected the proposition primitif for the sector 5?

APPENDIX A 41

Agent N°3 desires parc_escalade with an intensity [1], but the proposition primitif for the sector 5 does not allow to do this (that’s why we use -1 to tell that this desire is not satisfied). Also note that the autonomous agent operates using the comparison rule AtLeastH, for this particular example all rules give the same result (>). Below is the state of the agent for the previous proposed offer N°2.

42 APPENDIX A

Let's go back to our mediator, who proposed offer N°4. With this offer we are entering a dead end, because all the possibility of offers has been exhausted for the sector 6 (i.e. intangi-ble, intensif, primitif).

Here begins the conversation phase, launched by the mediator (at this stage of develop-

ment, it happens manually). The mediator starts by asking for example the agent N°4 to give its arguments for the re-

jection of proposition primitif for sector 6. This is expressed by:

Challenge : (ag4, 6, primitif)

APPENDIX A 43

The agent N°4, gives his arguments in terms of potential desires that supports the conclusion primitif (i.e. the internal meaning of the conclusion for the agent):

Argue : [visite_safari, visite_monastere, proteger_foret, proteger_habitations, proteger_tortues, eco_tourisme]

The mediator continues by asking the agent if it desires eco_tourisme,

Question : desire (ag4, 6, eco_tourisme)

and the agent answers: Assert : not (desire (ag4, 6, eco_tourisme))

With this new learned information, and based on the internal knowledge, the mediator asks agent N°3 if there is no opposition for desire visite_monastere_hiver for sector 4:

Question : ~desire (ag3, 4, visite_monastere_hiver))

The agent replies the there is no opposition to have this desire: Assert : not (~desire (ag3, 4, visite_monastere_hiver)))

As shown in the figure below:

44 APPENDIX A

The mediator goes back to agent N°4 and informs it that the agent N°3 is able to have the desire desire (ag3, 4, visite_monastere_hiver):

Assert : desire (ag3, 4, visite_monastere_hiver)

And asks if the agent N°4, with this new information, desires eco_tourisme now:

Question : desire (ag4, 6, eco_tourisme)

APPENDIX A 45

This time, the agent replies: Assert : desire (ag4, 6, eco_tourisme)

The mediator goes back again to agent N°3, informs it about the agent N°4 new desire and asks it if with this new information it desires visite_monastere_hiver. And the agent N°3 con-firms its desire.

Now the mediator proposes offer N°5, which leads to a global consensus.

Appendix B: SimParc Map

Documents

Rapport de stage - briot/documents/Rapport_Stage_M2_09_2017_Anis... · Rapport de stage Expert agents in negotiation and argumentation for serious games on participatory management