System for negotiation using graphs

• US 20040083186A1
• Filed: 10/24/2002
• Published: 04/29/2004
• Est. Priority Date: 10/24/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Castellani, Stefania, Andreoli, Jean-Marc
• Granted Patent: US 7,409,378 B2
• Time in Patent Office: Days
• US Class Current: 705/80
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 50/188 Electronic negotiation

Abstract

A negotiation is carried out between a plurality of participants. Each participant defines an invocation pattern. A set of coordinator parameters are attached to each invocation pattern, where the set of coordinator parameters define interdependencies between parameters of the plurality of participants that are shared across their invocation patterns. A graph is constructed to carry out the negotiation of a set of actions to be performed by selected ones of the plurality of participants, with nodes of a first node type that represents a negotiating context or a second node type that represents a decision point. The participants construct the graph with primitives instantiated by the invocation patterns. At least one node in the graph is a decision point that merges two or more negotiation contexts into a single decision point. The single decision point combines values of the parameters from the two or more negotiation contexts.

Claims

1. A method for carrying out a negotiation between a plurality of participants, comprising:

defining an invocation pattern for each participant;

each invocation pattern being a tuple having at least a name and a set of parameters;

attaching a set of coordinator parameters to each invocation pattern;

the set of coordinator parameters defining interdependencies between parameters of the plurality of participants that are shared across their invocation patterns;

constructing a graph to negotiate a set of actions to be performed by selected ones of the plurality of participants;

the graph being constructed with nodes of one of a first node type representing a negotiating context and a second node type representing a decision point;

wherein the graph is constructed by the participants with primitives instantiated by the invocation patterns that are used to negotiate values of parameters; and

wherein at least one node in the graph is a decision point that merges two or more negotiation contexts into a single decision point;

the single decision point combining values of the parameters from the two or more negotiation contexts.

2. The method according to claim 1, wherein properties of each parameter are defined by a set of one or more aspects, with each aspect having a constraint.

3. The method according to claim 1, wherein each negotiating context is associated with a parameter and a term describing an aspect of the value of the parameter in the invocation pattern.

4. The method according to claim 1, wherein each decision point in the graph has one or more parent nodes that must all be negotiation contexts.

5. The method according to claim 4, wherein each negotiation context in the graph has one or no parent node that must be a decision point.

6. The method according to claim 5, wherein the negotiation context with no parent node is a root node that is not the result of a decision.

7. The method according to claim 4, wherein each decision point is a hyper-arc.

8. The method according to claim 1, wherein the primitives define a protocol for collaboratively building a graph at each participant.

9. The method according to claim 8, wherein the graph built at each participant contains only properties of parameters in its invocation pattern.

10. The method according to claim 1, wherein each negotiation context in the graph is labeled with one or more pairs of:

an aspect on a parameter, and a property constraining the aspect'"'"'s value.

11. A system for carrying out a negotiation between a plurality of participants, comprising:

means for defining an invocation pattern for each participant;

each invocation pattern being a tuple having at least a name and a set of parameters;

means for attaching a set of coordinator parameters to each invocation pattern;

the set of coordinator parameters defining interdependencies between parameters of the plurality of participants that are shared across their invocation patterns;

means for constructing a graph to negotiate a set of actions to be performed by selected ones of the plurality of participants;

the graph being constructed with nodes of one of a first node type representing a negotiating context and a second node type representing a decision point;

wherein the graph is constructed by the participants with primitives instantiated by the invocation patterns that are used to negotiate values of parameters; and

wherein at least one node in the graph is a decision point that merges two or more negotiation contexts into a single decision point;

the single decision point combining values of the parameters from the two or more negotiation contexts.

12. The system according to claim 11, wherein properties of each parameter are defined by a set of one or more aspects, with each aspect having a constraint.

13. The system according to claim 11, wherein each negotiating context is associated with a parameter and a term describing an aspect of the value of the parameter in the invocation pattern.

14. The system according to claim 11, wherein each decision point in the graph has one or more parent nodes that must all be negotiation contexts.

15. The system according to claim 14, wherein each negotiation context in the graph has one or no parent node that must be a decision point.

16. The system according to claim 15, wherein the negotiation context with no parent node is a root node that is not the result of a decision.

17. The system according to claim 14, wherein each decision point is a hyper-arc.

18. The system according to claim 11, wherein the primitives define a protocol for collaboratively building a graph at each participant.

19. The system according to claim 18, wherein the graph built at each participant contains only properties of parameters in its invocation pattern.

20. The system according to claim 11, wherein each negotiation context in the graph is labeled with one or more pairs of:

an aspect on a parameter, and a property constraining the aspect'"'"'s value.