System for negotiation with mirroring

• US 20040083187A1
• 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,454,400 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 plurality of components are specified to perform a negotiation, where each component is a participant, a coordinator, or both. Each component is provided with a conversion table that maps a set of parameters between invocation patterns instantiated by the participants. Each coordinator is provided with a negotiation graph that it modifies to coordinate its neighborhood of negotiation graphs, and each participant is provided with a negotiation graph that it modifies for each invocation pattern it instantiates. Two message types are sent between components that communicate directly with each other in each neighborhood of negotiation graphs. The two message types are sent between the components to collaboratively mirror their negotiation graphs using their conversion tables in each neighborhood of negotiation graphs so that each participant only views information concerning those aspects in its negotiation graph that relate to the parameters of the invocation patterns it instantiated.

Claims

1. A method for conducting a negotiation among a plurality of participants, comprising:

specifying a plurality of components to perform the negotiation;

each component being a participant, a coordinator, or both;

providing each component with a conversion table that maps a set of parameters between invocation patterns instantiated by the participants;

providing each coordinator with a negotiation graph that it modifies to coordinate its neighborhood of negotiation graphs and each participant with a negotiation graph that it modifies for each invocation pattern it instantiates; and

sending a first message type and a second message type between components that communicate directly with each other in each neighborhood of negotiation graphs;

the first message type specifying a request for notification of changes to an aspect of a parameter at a node in the negotiation graph of the component sending the message;

the second message type specifying an assertion expressing a decision by a component concerning a property of an aspect of the parameter at a node in the negotiation graph of the component sending the message;

wherein the first message type and the second message type are sent between the components to collaboratively mirror their negotiation graphs using their conversion tables in each neighborhood of negotiation graphs so that each participant only views information concerning those aspects in its negotiation graph that relate to the parameters of the invocation patterns it instantiated.

2. The method according to claim 1, wherein responsive to receipt of a message of the first message type at a component, the method further comprises:

sending a message of the first type with the request for notification to each component that shares a parameter in the conversion table of the component that received the message of the first type; and

sending a message of the second type for each assertion made concerning the shared parameter that appears in the negotiation graph of the component that received the message of the first type.

3. The method according to claim 2, wherein responsive to receipt of a message of the second message type at a component, the method further comprises:

sending a message of the second type with the assertion made to each component that shares a parameter in the conversion table of the component that received the message of the second type and that requested information thereon with the message of the first type.

4. The method according to claim 3, wherein a component that received the message of the first type or the second type sends a message of a third type to open nodes in the negotiation graph when either requests for notification or assertions made concerning a shared parameter are directed to a node that does not exist in the negotiation graph of a component to which it is sent.

5. The method according to claim 1, wherein each coordinator communicates directly with two or more participants using its conversion table to define a neighborhood of negotiation graphs.

6. The method according to claim 5, wherein the negotiation includes a first coordinator that is not a participant in the negotiation and a second coordinator that is a participant of the neighborhood of negotiation graphs coordinated by the first coordinator.

7. The method according to claim 5, wherein the participants in each neighborhood of negotiation graphs communicates directly with no more than one coordinator.

8. The method according to claim 7, wherein at least one component is a coordinator that is not a participant.

9. The method according to claim 8, wherein the invocation patterns instantiated by the participants of a neighborhood of negotiation graphs defines a problem statement of the negotiation for which a solution is negotiated using the coordinator of the neighborhood.

10. The method according to claim 1, wherein the negotiation graph is a tree.

11. A system for conducting a negotiation among a plurality of participants, comprising:

a plurality of components for performing the negotiation;

each component being a participant, a coordinator, or both;

each component being provided with a conversion table that maps a set of parameters between invocation patterns instantiated by the participants;

each coordinator being provided with a negotiation graph that it modifies to coordinate its neighborhood of negotiation graphs and each participant with a negotiation graph that it modifies for each invocation pattern it instantiates; and

a first message type and a second message type for sending between components that communicate directly with each other in each neighborhood of negotiation graphs;

the first message type specifying a request for notification of changes to an aspect of a parameter at a node in the negotiation graph of the component sending the message;

the second message type specifying an assertion expressing a decision by a component concerning a property of an aspect of the parameter at a node in the negotiation graph of the component sending the message;

wherein the first message type and the second message type are sent between the components to collaboratively mirror their negotiation graphs using their conversion tables in each neighborhood of negotiation graphs so that each participant only views information concerning those aspects in its negotiation graph that relate to the parameters of the invocation patterns it instantiated.

12. The system according to claim 11, wherein each coordinator communicates directly with two or more participants using its conversion table to define a neighborhood of negotiation graphs.

13. The system according to claim 12, wherein the negotiation includes a first coordinator that is not a participant in the negotiation and a second coordinator that is a participant of the neighborhood of negotiation graphs coordinated by the first coordinator.

14. The system according to claim 12, wherein the participants in each neighborhood of negotiation graphs communicates directly with no more than one coordinator.

15. The system according to claim 14, wherein at least one component is a coordinator that is not a participant.

16. The system according to claim 15, wherein the invocation patterns instantiated by the participants of a neighborhood of negotiation graphs defines a problem statement of the negotiation for which a solution is negotiated using the coordinator of the neighborhood.

17. The system according to claim 11, wherein responsive to receipt of a message of the first message type at a component:

a message of the first type is sent with the request for notification to each component that shares a parameter in the conversion table of the component that received the message of the first type; and

a message of the second type is sent for each assertion made concerning the shared parameter that appears in the negotiation graph of the component that received the message of the first type.

18. The system according to claim 17, wherein responsive to receipt of a message of the second message type at a component:

a message of the second type is sent with the assertion made to each component that shares a parameter in the conversion table of the component that received the message of the second type and that requested information thereon with the message of the first type.

19. The system according to claim 18, further comprising a message of a third type wherein a component that received the message of the first type or the second type sends a message of the third type to open nodes in the negotiation graph when either requests for notification or assertions made concerning a shared parameter are directed to a node that does not exist in the negotiation graph of a component to which it is sent.

20. The system according to claim 11, wherein the negotiation graph is a tree.