Negotiation system and processor-based method

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.

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.