Next: Changing Negotiation Modes Up: Negotiation Strategy Execution Previous: Negotiation Messages

Negotiation Graphs

It is possible to represent a negotiation between two SiFAs using negotiation graphs. A negotiation graph shows all possible sequences of messages sent and actions performed by the agents involved in a particular kind of conflict.

The start node of the graph shows the message sent by the initiator of the conflict. A path through a negotiation graph starting at the start node and ending at a node without any outgoing arcs is a full transcript of a possible negotiation. Whenever there is more than one outgoing arc from a node, this means that the negotiation can proceed in any one of those ways. Which one of those arcs is taken depends on the state of the particular agents involved in the negotiation.

Figure 6.2 shows a negotiation graph for a conflict between a critic of a value and the selector of that same value. What this graph indicates is that the critic asks the selector for alternatives and the selector either provides more alternatives or asks the critic to relax its constraint. If the selector proposes an alternative value, the critic may still disagree, and if the critic relaxes its constraint, the relaxed constraint may still be violated. So the negotiation process is a cycle of proposals of alternatives and constraint relaxations. The negotiation either ends in success if the critic is satisfied with the value or in failure if the critic cannot relax its constraint anymore and the selector can give no other alternative values for the parameter.

Figure 6.2: Selector-Critic negotiation graph

It should be noted that the negotiation graph does not give any information about the order of constraint relaxations by the critic and alternative proposals by the selector. This is dependent on the respective agents and the strategies they use. The selector may use one of the following strategies, where the first is one a greedy strategy, the second is maximally cooperative, and the third is a mixture of the two:

• When asked to supply an alternative value, decline and ask for a relaxation immediately,
• When asked to supply an alternative, give alternatives until there are no more possible alternatives, only then ask for a constraint relaxation,
• Supply alternatives and ask for relaxations in an interleaved manner, possibly giving one alternative and asking for a relaxations before giving another alternative.

Similarly, the critic may use a greedy, maximally cooperative or mixture strategy as follows:

• Wait for a ``no more alternatives'' message from the selector before relaxing a constraint,
• Relax a constraints before asking for alternatives,
• Relax constraints and ask for alternatives in an interleaved manner, possibly doing one relaxation and asking for one alternative before doing another relaxation.

Figure 6.3 shows another negotiation graph, this time for a conflict between two selectors with the same target. As for the selector-critic conflict, the selectors can ask each other for alternative values or constraint relaxations in any order that is dictated by their respective strategies. The left and right halves of the graph are identical except that the roles of selector1 and selector2 are reversed.

Figure 6.3: Selector-Selector negotiation graph

Negotiation graphs are helpful in building the negotiation knowledge into a SiFA since the graphs show all messages that the agent will need to respond to and all possible answers that it can give to a specific message for each conflict type that it can be involved in. Since the conflict situations in the SiFA paradigm are very well specified, the negotiation graphs are fairly small and easy to build.

The drawback of using negotiation graphs is that they get very complicated very quickly if we wish to allow the agents to use a larger vocabulary so that they can talk about things other than alternatives and relaxations. If the agents are to have history keeping and learning capabilities, then they do need a larger vocabulary and then it becomes infeasible to represent all possible paths of interaction between two agents. In that case, the designers of a SiFA should try to anticipate in advance what messages the agent they are building should be able to respond to, and build that capability into the agent.

Next: Changing Negotiation Modes Up: Negotiation Strategy Execution Previous: Negotiation Messages

Ilan Berker
Thu Apr 27 16:25:38 EDT 1995