Negotiation system and processor-based method

• US 20060160593A1
• Filed: 01/20/2005
• Published: 07/20/2006
• Est. Priority Date: 01/20/2005
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Karp, Alan H.
• Application Number:
  US11/038,717
• Publication Number:
  US 20060160593A1
• Time in Patent Office: Days
• US Class Current: 463/9
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions

Abstract

A processor-based method for automated negotiation with continuous game moves. A game tree is constructed with a root node that represents a current state of the negotiation. The game tree is evaluated, and a next offer selected. A range-term is defined based on the continuous game moves and the range-term is treated as a single continuous variable in the game tree. Expansion of a branch of the game tree is halted at a range-term node for which only the range-term was changed in a previous move leading to that range-term node. An optimum payoff value for each range-term node is then determined and output to a computer peripheral.

Claims

1. A processor-based method for automated negotiation with continuous game moves, comprising:

constructing a game tree with a root node that represents a current state of a negotiation;

defining a range-term based on continuous game moves;

treating a range-term as a single continuous variable in said game tree;

halting expansion of a branch of said game tree at a range-term node for which only a range-term was changed in a move leading to said range-term node; and

evaluating said game tree to select a next offer with an optimization process routine to determine an optimum payoff value for each range-term node.

2. The method of 1, wherein said optimization process routine comprises the recursive steps of:

selecting a probe discretization for the range-term;

expanding the game tree underneath the range-term node based on said probe discretization;

computing the payoff for the range-term node based on the expanded game tree; and

selecting a new probe discretization.

3. The method of 2, wherein selecting said probe discretization is based on constraints in the continuous game moves.

4. A system for automated negotiation with continuous game moves, the system including:

at least one processor and at least one associated memory device storing instructions for causing the at least one processor to construct a game tree with a root node that represents a current state of a negotiation;

evaluate the game tree;

select a next offer based on an output of the evaluating the game tree;

define a range-term based on the continuous game moves and for treating the range-term as a single continuous variable in the game tree; and

halt expansion of a branch of the game tree at a range-term node for which only the range-term was changed in the move leading to said range-term node, wherein the instructions include an optimization process routine for causing the at least one processor to determine an optimum payoff value for each range-term node.

5. The system of claim 4, wherein the optimization process routine further causes the at least one processor to:

select a probe discretization for a range-term;

expand a game tree underneath a range-term node based on said probe discretization;

compute a payoff for a range-term node based on a expanded game tree, and;

select a new probe discretization.

6. The system of claim 5, wherein selecting the probe discretization depends on the selection of constraints in the continuous game moves.

7. A computer program comprising program code instructing a computer to execute a procedure to perform a method for automated negotiation with continuous game moves, the method including the steps of:

a) constructing a game tree, wherein a root node of the game tree represents a current state of the negotiation;

b) evaluating the game tree; and

c) selecting a next offer based on step b), wherein step a) includes;

defining a range-term based on the continuous game moves and treating the range-term as a single continuous variable in the game tree;

halting expansion of a branch of the game tree at a range-term node for which only the range-term was changed in the move leading to said range-term node, and wherein step b) includes;

applying an optimization process routine to determine an optimum payoff value for each range-term node.

8. The program of claim 7, wherein the optimization process routine causes the computer to recursively:

select a probe discretization for the range-term;

expand the game tree underneath the range-term node based on said probe discretization;

compute the payoff for the range-term node based on the expanded game tree, and;

select a new probe discretization.

9. The program of claim 8, wherein the new probe discretization selection is based on constraints in the continuous game moves.