Project topics and materials
Get Complete Project Material File(s) Now! »
Distributed Negotiations
In this chapter, multi-agent negotiation problems are described. The combined use of negotiations and multi-agent systems raise several important issues, which are never addressed in centralized approaches. We will discuss issues related to the design of solving processes, focusing on agent behaviors and trying to answer a crucial question: “How do agents need to behave in order to lead negotiation processes to socially optimal solutions?”
The challenges related to the design of negotiation processes are described in Section 2.1, where we explain the difficulties related to such a process. Then, formal definitions of negotiation problems and agents are presented in Section 2.2. Their features are successively detailed in the next sections. Restrictions on agent communications are presented in Section 2.3, which describes different topologies of relationships that can be modeled and have their typical characteristics. Then, different classes of transactions are presented in Section 2.4. Section 2.5 details the decision-making criteria used by agents, i.e., the conditions that transactions must satisfy in order to be performed. Section 2.6 discusses agent behaviors, and presents different methods to model agents’ interactions. Finally, we present in Section 2.7 the evaluation of negotiation processes and the metrics used during the experiments that we carried out.
Challenges
The design of negotiation processes is an essential issue affecting a lot their efficiency. Different techniques based on multi-agent systems have been described in Section 1.3 with an emphasis on their advantages, but a suitable design is required to benefit from them. The challenges related to the negotiation process design can be illustrated by a proposition of (Sandholm, 1998), which was initially written in a task allocation context.
Property 2.1 ((Sandholm, 1998), path) A sequence of resource purchases (O-contracts) al-ways exists from any resource allocation to the optimal one. The length of the shortest path is at most m (the overall number of resources).
Proof. The transaction sequence can be constructed by moving a resource one at a time from the agent that initially owns it to the agent that gets it in the globally optimal resource allocation.
According to Proposition 2.1, a path of O-contracts, which corresponds to the pur-chase of a resource, always exists between any initial allocation to an optimal one.
Although this proposition is proposed in the case where communications are not re-stricted, it is still valid in the context of restricted communication possibilities, if no agent group is isolated from the others. Indeed, the proof is based on the existence of a path between any pair of nodes in the graph, which is always satisfied when the graph is complete. Such a path also exists if the restricted graph is connected. However, the length of the shortest path can be longer than m depending the agents’ relationships. Resources may have to go through different bundles in order to achieve an optimal solution. In practice, the main issue is to identify such a path.
In order to find it, agents have to accept any transaction. Resources should then freely circulate among the agents in order to finally be owned by the agent that has it in a globally optimal resource allocation. According to agent-based method principles, the initial allocation evolves thanks to local transactions among agents. However, since agents must accept any transaction, they do not distinguish a profitable transaction from another one. Thus, agents negotiate endlessly and the negotiation process cannot end. Even if an optimal resource allocation is achieved during the solving process, agents continue to negotiate and perform new transactions. This optimal resource allocation is then lost.
Agents must be able to identify profitable transactions. Agents should be au-tonomous and their decision-making should be based on a local acceptability criterion. This criterion must only be based on the information that agents can get themselves during a negotiation. When no agent can identify an acceptable transaction within its neighborhood, the negotiation process is over. The resource allocation achieved at this moment is the solution provided by the distributed negotiations. This is an important issue in order to ensure the quality of achieved allocation. Negotiation processes must be finite, agents must be able to make their own decision based on local information un-til no agent identifies acceptable transactions. These features can be achieved through a suitable design of agent behaviors and the choice of an appropriate acceptability criterion.
Definitions
A resource allocation problem in an agent society can be solved thanks to negotiation processes among agents. Such problems can be distributed using the notion of agent. Instead of maintaining an up-to-date state of the whole system and of all entities’ information in a single location, they are distributed inside agents. The notions of negotiation problem and agent, which are closely related, can be defined as follows:
Definition 2.1 (Negotiation Problem) A negotiation problem is a tuple R T , where P = {1 n} is a finite population of n agents, R = {r1 rm} is a finite set of m resources, and T corresponds to the set of transactions allowed during the negotiation process.
The transactions that can be allowed are presented later, in Section 2.4. An agent can be defined in a generic way by a resource bundle, a utility function describing its preferences, a list of agents with whom it is able to communicate, a behavior describing how it interacts with other agents and an acceptability criterion related to its decision-making.
Definition 2.2 (Agent) An agent i ∈ P is a tuple resources, ui is its utility function, Ni is the list of ni
i ui Ni Bi Ci , where Ri is its set of mi neighbors, Bi defines the agent behavior according to which the agent negotiates, and Ci is its acceptability criterion on which are based its decisions.
Preferences of agent i are defined according to Definition 1.3 by means of additive utility functions. The behavior Bi describes agent i from an external point of view, whereas the acceptability criterion Ci describes it from an internal point of view. Indeed, the behavior describes how an agent interacts with others while the acceptability criterion corresponds to the conditions that a transaction must satisfy in order to be performed. This criterion thus represents the central condition of the agent decision-making. Be-haviors and acceptability criteria are respectively detailed in Sections 2.5 and 2.6.
Two notions must be distinguished. First, a negotiation seeks to identify an acceptable transaction among agents. A negotiation is defined by interactions among agents (see Section 2.6). A negotiation process seeks to find a path of acceptable transactions, and thus includes many negotiation problems. In this thesis, we always consider a specific negotiation problem based on an agent population P, a set of resources R which are initially distributed over the population, and a set of transactions T allowed among agents of the population.
Social graphs
At the opposite of centralized solving processes, which always assume complete com-munication possibilities, solving methods based on multi-agent systems can handle the notions of neighborhood and social graph.
Definition 2.3 (Neighborhood) The neighborhood of agent i ∈ P, denoted by Ni, is a subset of the population P with whom it is able to communicate. Ni ⊆ P { i} i ∈ P
A graph of relationships, which we call a social graph, can be extracted from the neighborhood of all agents.
Definition 2.4 (Social graph) The social graph G is a graph of relationships describing the communication possibilities among agents of a population P. In such a graph, nodes repre-sent agents, and an edge between two nodes means that the corresponding agents are able to communicate.
Property 2.2 (Relationship symmetry) Let ei j be an edge of a social graph G between two nodes i and j. This edge means that both agents i j ∈ P are directly related. If agent j is a neighbor of agent i, then agent i must also be a neighbor of agent j. More formally: ei j ∈ G ⇒ j ∈ Ni and i ∈ Nj i j ∈ P
Such relationships are represented by non-oriented graphs.
The different classes of social graphs can be grouped into three main classes:
• Complete graphs;
• Structured graphs;
• Random graphs.
First, negotiation processes based on complete social graphs can be compared to centralized approaches. Indeed, both of them assume complete communication possi-bilities among all the agents, and then have similar solving conditions. However, such graphs are only used to carry out comparisons between distributed results and the ones provided by centralized techniques.
Then, graphs with regular topological characteristics belong to the class of structured graphs. For instance, a graph where all agents have the same number of neighbors belongs to this class. Structured graphs also include some specific topologies like grids (Berman et al, 2003), rings or trees.
Finally, unstructured graphs have an irregular topology. Several classes of random graphs exist (Bollobás, 2001), like Erd˝os-Rényi graphs (Erd˝os and Rényi, 1959), free-scale graphs or small worlds generated either by preferential attachment or by circle rewiring (Albert and Barabási, 2002). The probability distribution is uniform when Erd˝os-Rényi graphs are considered. Links between any pair of nodes have the same probability to be generated. In small-worlds, the larger number of neighbors has a node, the larger is the probability to link this node. Such topologies correspond to real-life graphs like the Internet. The algorithms used to generate the classes of social graphs considered in this thesis are detailed in Chapter 3.
Different classes of social graphs are illustrated in Figure 2.1. We will select specific graphs for the experiments in Chapter 3: complete graphs, grids, Erd˝os-Rényi graphs and small-worlds. These graphs correspond to a representative sample of what can be encountered in most applications. Indeed, their characteristics vary significantly when these graphs are evaluated with the most widely used metrics (Biggs et al, 1986), which are described in the next paragraphs.
The clustering coefficient is a metric that quantifies how well connected is the neigh-borhood of an agent. The more the neighbors of an agent are directly related, the higher is the clustering coefficient. This coefficient is weak when grids are considered since the four neighbors of an agent are not related directly, whereas the clustering coefficient becomes high when complete graphs are considered since the neighborhood of an agent is completely connected.
Only connected graphs are considered in this thesis. In such graphs, a path always exists between any pair of nodes, and its maximal length is n −1. If a social graph is not connected, then agents from disconnected parts cannot communicate with each other. Resources can circulate inside a portion of the graph, but cannot move to another one. Hence, these portions can be considered as independent. Thus, a resource allocation problem, which is based on a not connected social graph, can be split into as many independent sub-problems as there distinct portions in the social graph.
Property 2.3 (Not connected graph) Independently of the objective considered, the solution of an allocation problem based on a non-connected social graph is equivalent to the association of the partial solutions provided by the solving process applied to all the portions of the graph.
Proof. If a social graph is composed by x portions, there is no path between nodes that belong to different portions. Any pair of agents who do not belong to the same group cannot communicate. Then, no resource can circulate from one of them to another. The solution of the overall problem can be obtained by the union of the solution from each portion. The resource allocation problem can be divided into x independent sub-problems, each one restricted to the population of a portion. The optimal allocations provided by the different solving processes can be merged to constitute the solution of the whole problem.
Transactions
During negotiation processes, the resource allocation evolves, step by step, by means of local transactions among agents. The resource traffic is generated thanks to these transactions, which move resources successively from an agent bundle to another one.
Definition 2.5 (Transaction) A transaction is an operation on resources among several agents, which transforms an initial resource allocation A into a new one A′. Agents involved in a transaction are called participants, but two agent roles can be distinguished: the initiator who starts the negotiation, and the partners who are selected by the initiator in its neighborhood.
The definition of a transaction can be based on the offers made by the partici-pants. The number of resources that the participants can offer depends on the allowed transaction class. Indeed, different classes of transactions exist, which are more or less time-consuming, which involve more or less agents, which move more or less resources . . . Three classes of transactions can be distinguished.
• Bilateral transactions, which involve only two agents at a time (also called one-to-one transactions in the literature);
• Multilateral transactions, which involve more than two agents at once according to two different transaction patterns:
– One-to-Many transactions, where the initiator is involved in all resource operations;
– Many-to-Many transactions, where any resource operation is allowed among all the participants.
In this section, these three classes of transactions are described. For each class of transactions, the computational complexity, i.e., the number of possible transactions, is determined according to the number of participants and according to the size of their bundle.
Bilateral transactions
Bilateral transactions, also called one-to-one transactions, only involve two agents at a time. They represent the most widely used class of transactions in the literature. Bilat-eral transactions can be defined in a parametric way using two parameters representing the size of the offers proposed respectively by the initiator and its partner, as illustrated in Figure 2.2.
Definition 2.6 (Bilateral transactions) A bilateral transaction between two agents i j ∈ P, denoted by δij, is initiated by agent i who involves one of its neighbors j ∈ Ni. It is a pair δij u v = (ρδiρ δj), where the initiator i offers a set ρδi of u resources (ρδi ⊆ Ri) and the selected partner j offers a set ρδj of v resources (ρδj ⊆ Rj).
Table of contents :
Introduction
1 Resource Allocation Problems
1.1 Problem description
1.1.1 Resource characteristics
1.1.2 Representation of preferences and individual welfare
1.1.3 Social welfare theory
1.2 Centralized approaches
1.2.1 Description
1.2.2 Limiting cases
1.2.3 A typical application: combinatorial auction
1.3 Distributed approaches
1.3.1 Description
1.3.2 Characteristics
1.3.3 Application examples
1.4 Summary
2 Distributed Negotiations
2.1 Challenges
2.2 Definitions
2.3 Social graphs
2.4 Transactions
2.4.1 Bilateral transactions
2.4.2 Multilateral transactions
2.5 Acceptability criteria
2.5.1 Rational criterion
2.5.2 Social criterion
2.5.3 Difference and impact
2.6 Agent interactions
2.7 Evaluation of negotiation processes
2.7.1 Evaluation metrics
2.7.2 Negotiation efficiency
2.7.3 Computation time
2.8 Summary
3 Experimental Protocol
3.1 Generation of agents’ preferences
3.2 Generation of initial allocations
3.3 Generation of social graphs
3.3.1 Complete graphs
3.3.2 Erd˝os-Rényi graphs
3.3.3 Grids
3.3.4 Small-worlds
3.4 Negotiation processes
3.4.1 Simulation and practice
3.5 Experimental protocol
3.5.1 Instance characteristics
3.5.2 Simulation characteristics
4 Bilateral Negotiations
4.1 Utilitarian bilateral negotiations
4.1.1 Centralized techniques
4.1.2 Utilitarian negotiation properties
4.1.3 Evaluation of utilitarian negotiations
4.1.4 Conclusion
4.2 Egalitarian bilateral negotiations
4.2.1 Centralized techniques
4.2.2 Egalitarian negotiation properties
4.2.3 Evaluation of egalitarian negotiations
4.2.4 Conclusion
4.3 Nash bilateral negotiations
4.3.1 Centralized techniques
4.3.2 Nash negotiation properties
4.3.3 Evaluation of Nash negotiations
4.3.4 Conclusion
4.4 Elitist bilateral negotiations
4.4.1 Centralized techniques
4.4.2 Elitist negotiation properties
4.4.3 Evaluation of elitist negotiations
4.4.4 Conclusion
4.5 Summary
5 Multilateral Negotiations
5.1 Motivations and limitations
5.1.1 Motivations
5.1.2 Limitations
5.2 Related works
5.3 Problem statement
5.4 Introduction to column generation methods
5.4.1 The master problem
5.4.2 The pricing problem
5.5 Expression of the pricing problem
5.6 Experimental evaluations
5.6.1 Evaluation of multilateral transactions
5.6.2 Evaluation of multilateral negotiation processes
5.7 Conclusion
Conclusion
Bibliography
