Source: https://patents.google.com/patent/US7756772?oq=6480844
Timestamp: 2018-04-23 17:46:57
Document Index: 163793326

Matched Legal Cases: ['arty 104', 'arty 106', 'arty 110', 'arty 112', 'arty 104', 'arty 106', 'arty 110', 'arty 112', 'arty 104', 'arty 106', 'arty 110', 'arty 112', 'arty 104', 'arty 106', 'arty 110', 'arty 112', 'arty 106', 'arty 110', 'arty 112']

US7756772B1 - System and method for automated contract formation - Google Patents
System and method for automated contract formation Download PDF
US7756772B1
US7756772B1 US10069234 US6923400A US7756772B1 US 7756772 B1 US7756772 B1 US 7756772B1 US 10069234 US10069234 US 10069234 US 6923400 A US6923400 A US 6923400A US 7756772 B1 US7756772 B1 US 7756772B1
US10069234
Dealigence Inc
A system, method and device for (semi-)automated e-commerce on the Internet, the WWW and other networks. Trading parties present intentions, made of more elementary components, which are used to express their willingness to engage in deals subject to constraints. Parts of intentions may be variable components. Some variable components may be associated with computational devices that transform them, optionally communicating via messages, into more specified components. This mechanism encodes business rules. By fitting intentions, contracts are formed. While fitting intentions, negotiations are carried out via the exchange of messages. Negotiations are automated by encoding users wishes as mathematical programs. Following the deal formation an optional deal improvement phase, in one-to-one mode or one-to-many mode, is carried out to improve the deal. The improvement phase may be based on a trading mechanselected from an available collection of such mechanisms including such mechanisms as constructed by users of the system.
The present invention is of a system and method for automated and semi-automated contract formation, and in particular, for automated negotiations which lead to the construction of a contract between two parties.
E-commerce (electronic commerce) is an increasingly popular type of business activity. The term “e-commerce” refers to business activities conducted through the Internet, and in particular through Web sites on the World-Wide Web (WWW). The amount of merchandise sold on the World Wide Web is constantly growing, including products and services which range from the delivery of flowers to the purchase of books and computer hardware. The current architecture for e-commerce on the Web mainly relies upon a Web page-based interface, which is navigated by using the Web browser of the user. Such an architecture has several disadvantages.
First, each vendor must establish a separate, non-standardized, Web site. Therefore, each vendor must rely upon its own technology and non-standardized interface, which is inefficient and time consuming for the vendor. Second, the requirement to navigate through Web sites with a Web browser is inefficient for the user, or potential customer, who may wish to consider only specific products and/or services. Third, there is no standard for conducting automatic negotiations in either business-to-business (B2B) or business-to-consumer (B2C) settings (some sites do offer ad-hoc negotiations, for example “Hagglezone” [http://www.hagglezone.com as of Jan. 2, 2000] and to a limited extent “Priceline” [http://www.priceline.com as of Jan. 2, 2000]. In addition, there are also auctions which offer a form of negotiation as in “eBay” [http://www.ebay.com as of Jan. 2, 2000]). Fourth, there are no facilities and standards for conducting negotiations on package deals, such that most commerce is on single items or a collection of items (also called a basket or a shopping cart) in which each item is considered in isolation (for example http://www.buywiz.com).
One attempted solution to these problems is the provision of automated agents, known as “shopbots”, which navigate through a plurality of Web sites in an attempt to locate products and/or services which fit certain parameters specified by the user. For example, such an automated agent may optionally be used to locate a product within a certain price range. Although the automated agent enables the user to consider products from a plurality of Web sites according to one or more specific criteria, the user is still required to navigate through the Web site of the vendor in order to actually purchase the product. Examples of such automated agents include “R U Sure” [http://www.rusure.com as of Jan. 2, 2000], and “BuyWiz” [http://www.buywiz.com as of Jan. 2, 2000] which are agents for buying goods, as well as various types of information brokers, which retrieve information about products and services through the Internet [1]. Such systems are generally task-oriented and do not define a general framework for negotiation. Thus, this attempted solution does not address the previously described disadvantages.
Other examples of attempted solutions for the specific problems of negotiation are described in “Agents as Mediators in Electronic Commerce” [2]. For example “AuctionBot” describes an automated auction server, which permits the seller to select from various predetermined protocols for conducting an auction. However, the protocols cannot be flexibly determined during the auction itself. Similarly, “Kasbah” is a Web-based multiagent classified ad system which offers very limited negotiation features, related to the rate with which a buyer increases a bid to a seller over time. “Tete-a-Tete” is a system which provides more flexibility, in that terms other than price can be negotiated, but the negotiation features which are provided are still very limited.
A more useful approach would involve the use of dynamic trees which can be adjusted, or even created, “on the fly” during the course of the negotiations. The trees are only partially defined for initiating the process of negotiation. As the process continues, the trees are constructed, thereby enabling the process of negotiations to be conducted flexibly and dynamically. Furthermore, these data structures enable the ultimate resolution of the process of negotiation to be expressed as a contract, since the dynamically constructed trees are then converted into a language-based description. Unfortunately, such a solution is not available.
There is thus a need for, and it would be useful to have, a system and a method for automated or at least semi-automated, dynamic negotiation between a potential customer and a vendor, in which the Web site of the vendor is capable of interacting with software-based automated tools, and in which the process of negotiation involves the construction of a tree “on the fly”, which can then be expressed as a natural language-based description for the determination of a contract between the parties.
The present invention is of a system and method for the automated, or at least semi-automated, process of negotiation between a potential customer and a vendor through software tools, for example at a Web site, although optionally through computational devices connected by any network. The process of negotiation, if successful, results in the construction of a contract between the parties.
According to another embodiment of the present invention, there is provided a system for at least semi-automatically negotiating a relationship, the system comprising: (a) a plurality of party modules, including at least a first party module and a second party module, each party module featuring an intention for determining the relationship, the intention featuring a plurality of components to be determined fox the relationship, such that a process of negotiation matches the intention of the first party module to the intention of the second party module; and (b) a central server for initially connecting the first party module to the second party module for performing negotiations. Hereinafter, the term “network” refers to a connection between any two or more computational devices which permits the transmission of data.
Hereinafter, the term “computer” includes, but is not limited to, personal computers (PC) having an operating system such as DOS, Windows™, OS/2™ or Linux; Macintosh™ computers; computers having JAVA™-OS as the operating system; graphical workstations such as the computers of Sun Microsystems™ and Silicon Graphics™, and other computers having some version of the UNIX operating system such as AIX™ or SOLARIS™ of Sun Microsystems™; or any other known and available operating system, or any device, including but not limited to: laptops, hand-held computers, enhanced cellular telephones, wearable computers of any sort, which can be connected to a network as previously defined and which has an operating system, as well as electronic or biological hardware, systems, servers and the like. Hereinafter, the term “Windows™” includes but is not limited to Windows95™, Windows 3.x™ in which “x” is an integer such as “1”, Windows NT™, Windows98™, Windows CE™, Windows2000™, and any upgraded versions of these operating systems by Microsoft Corp. (USA).
Examples of a “computational device” include, but are not limited to, a computer as defined above, or an independently operated software module or agent in any suitable programming language.
Hereinafter, the term “semi-automatic” refers to a process in which a human decision maker participates in the negotiation/decision phases of a commercial activity.
EC Party: A legal entity that may be involved in a deal. In particular, it can designate individuals, corporations, countries, state and local authorities, organizations and associations.
Reference to a value: This term refers to one of the following items—the value itself, a request for the value, or a set of values from which one value is to be selected.
Deal Splitting: A process of forming a deal in which one intention is matched with a number of intentions, thereby “splitting the deal”.
The system and method of the present invention have a number of advantages over the background art. First, entire negotiated agreements, which could be termed a package deal, or contracts can be specified, rather than a single product or “shopping baskets”, which are simply collections of products. This advantage is significant, as it enables complex relationships between parties to be negotiated and specified.
Eighth, the agreement can easily be expressed in natural language. Certain of these concepts were briefly explored in two papers: D. Konopnicki, L. Leiba, a Shmueli, and Y. Sagiv; “Toward automated electronic commerce”; In First IAC Workshop on Internet-Based Negotiation Technologies; IBM TJ Watson Research Center, Yorktown Heights, N.Y.; March 1999; and D. Konopnicki, L. Leiba, O. Shmueli, and Y. Sagiv; “A Formal Yet Practical Approach To Electronic Commerce”; In Proc. COOPIS '99, Edinburgh, Scotland, September 1999. However, the former paper in particular did not include the detailed, complete realization of the present invention as described herein.
Structuring Electronic Commerce (EC) is expected to be the main activity on the Internet, private networks and the WWW. A universal formalism (“the HTML of EC”) is required, which supports business relationships and negotiations on a global scale, as well as protocols which support automatic tools (agents). The present invention provides such a formalism by enabling parties to specify intentions, a formal outline of deals in which such parties are ready to engage. Intentions are made of components.
Components may be atomic or compound (to any required depth). Furthermore, a component may be a variable component, that is unspecified, or alternatively is specified only according to its type (see below for an explanation of types of components). Components may also be inter-related (e.g., by containment, by edge or labeled-edge connection, or by arbitrary predicates). An important facet of a variable component is its possible association with one or more computational devices, although one-to-one association of a variable component with a computational device is particularly preferred, and is described herein. Such a computational device, based on its perceived state and messages, transforms a variable component into a component. The term “perceived state” is intended to include inputs, values of various components, values of certain other entities such as files, databases and the like. The “new” component is usually “more specific” than the variable component it replaces. According to the present invention, such variable components and their associated computational devices embody transient or policy dependent aspects of the willingness to engage in a deal. It is desirable, although not mandatory, that the functionality of the computational device be readily understood by inspection, a property termed herein analyzability.
Forming an agreement, or negotiating a contract, requires the reconciliation of the constraints placed on deals by the (two or more) parties involved. For simplicity, the present invention is described with regard to two parties, it being understood that the concepts presented herein are easily generalized to multi-party scenarios. Reconciliation involves forming an agreement or contract which, as much as possible, is subject to the directives of the parties, as well as to any general laws which may apply. When examining two intentions, the process of reconciling the constraints may be considered to be a form of “fitting” to these constraints. Abstractly, this process fits the component structure of one party with the corresponding components of the other party.
Each party is assumed to employ a computational entity, or “party machine” (PM), which controls the fitting of intentions. The PM may communicate with other computational devices, and in particular other PMs, in attaining its mission. For example, it may be responsible for activating the “fitting process” or activating the computational device associated with a variable component.
According to the present invention, a number of mechanisms must be implemented for the process of negotiations to be conducted with automated or semi-automated tools. The first step is to ensure that intentions are universally understood. In EContracts, a component is represented as a rooted labeled tree. In fact, an intention is also a rooted labeled tree which is composed of components, together with various constraints and computational devices. The most basic components are simple atomic entities, e.g., of type integer, float, string. Next are basic components that are essentially (usually small) trees whose structure is agreed upon to represent a concept (e.g. car, sale, address). These basic components are called classes and they form the “words” of the common language. The word “class” hints at the fact that in an object oriented realization, these components are likely to be represented as object oriented classes, although the present invention is not limited to such a representation. A component may be a variable component. In this case it appears as a single node labeled with a typed variable. Such a type may be atomic, atomic list, class or list of classes. Such a variable component cannot exist in isolation but must be a leaf of a class.
Using classes, the parties compose their intentions, essentially forming “sentences” which in turn define possible deals. As noted, the purpose of an intention is to describe a deal that a party is willing to engage in. For example, an intention can express that the BooksOnline Corp. is selling books and that if you buy more than five books, you receive a 10% discount. In EContracts, the mechanism that composes words into sentences, or classes into intentions, relies on “variable instantiation” and the introduction of “operator nodes”. A (leaf) variable component of an intention is optionally and preferably associated with a computation device, called a “commerce automaton” (CA) in this realization, which prescribes how the variable may be instantiated further during a later phase. A commerce automaton may outline a message exchange sequence between the parties. However, it should be noted that a commerce automaton, and the related entity, the “negotiation automaton” (NA, described in greater detail below), are only one realization of a device or entity for exchanging messages between the parties according to the present invention, and is in no way limiting. In addition to intentions, an e-commerce party also maintains party information, a database or file containing information relevant to the party's activities. This is part of the “system state”.
A deal is manifested by creating a mutually agreed upon electronic contract (EContract). The process of obtaining an EContract begins with two initial intentions, presented by the parties. A formal process, called unification, a part of the realization of “fitting”, is used to construct an agreed upon EContract, provided such a contract is feasible. Unification may also be used by an e-commerce party to determine whether an EContract is at all possible, prior to entering actual negotiations with the other party, hence the importance and desirability of machine analyzability.
An Automata Execution Engine (AEE), controlled by the NCP, is responsible for conducting negotiations and the business rules enforcement. This is done by executing commerce automata (CA), as described in greater detail in Section 3 below. When the execution ends, the AEE controlling the CA returns either SUCCESS, i.e., the CA reached a final state, or FAILURE, i.e., the CA did not reach a final state. If the AEE returns SUCCESS, the NCP in control of the overall process (say NCP1) may optionally modify the EContract with the output of the CA. In this description, the AEE is optionally run by NCP1, preferably in case the CA is associated with a variable in the intention of NCP1's party, or optionally it is run by NCP2 (the NCP of the ‘other’ party), preferably in case the CA is associated with a variable in the intention of NCP2's party.
Section 2 Basics of the EContracts Framework
The parties involved in an e-commerce activity must agree on a common vocabulary. The “words” of this vocabulary are called classes and, formally, they are rooted labeled ordered trees. The root of a class is labeled with the class name; the edges of the class are labeled with strings which hint at the function of the vertices; the leaves of the classes are labeled with typed variables.
The presence of variables in a class enables the class to be customized. There are preferably four types of variables. A first type of variable is an atomic varia. The names of atomic variables begin with a “$” and the values that can be assigned to these variables are values such as string, real and integer. Examples of atomic variables in FIGS. 1A-1D include the identification string $id in FIG. 1C, and the string $amount in FIG. 1B, and so forth.
A second type of variable is a class variable. The names of class variables begin with an ampersand “&” and the values that can be assigned to these variables are class instances. Examples of variables in FIGS. 1A-1D include the payment variable &payment and the EC authority variables &customer and &company in FIG. 1A.
A third type of variable is an atomic list variable. The names of atomic list variables begin with a percentage symbol, “%”, and the values that can be assigned to these variables are lists of atomic values.
Definition 2.3 A class, over a proper set of unbound variables VAR, is a rooted labeled ordered (RLO) tree, denoted (V,E,r,t,<e, elf, vlf), where V is a set of vertices; E is a set of edges, E⊂V×V; rεV is the root of the tree; t, the label of the root, is a class name; <e is a partial order relation over E that defines the relative order of the edges that emanate from the same vertex; elf: E→STRINGS is the edge labeling function (defined so that the labels of the edges that emanate from the same vertex are all distinct); and let V′⊂V be the leaves of T. vlf: V′→VAR is the (total and onto) leaf labeling function. In FIG. 1, each variable (t, n, N) was represented by t: n.
Section 3 Intentions
In addition to the party information, in order to advertise its business intentions as well to be machine analyzable, a party should include a formal specification of the way it operates, i.e., the skeleton of contracts it may enter as well as the business rules and the constraints it enforces. The EContracts framework represents this information in intentions. Whereas classes are the words of the common language, intentions are the sentences of this language. Sentences are built by connecting words, such that an intention is composed of an intention tree which is derived from classes, commerce automata which encode business rules, and constraints.
If x is an atomic variable, and v is a value of type t, α (T, x=v) is defined to be T′ where T is presented in FIG. 2A. In the figure, “boxed T” symbols represent (sub-)trees and “boxed x” symbols represent vertices. If x is a class variable, let t′ be a class name which is a descendant of t in an ontology and let O′2 be an instance of type t′. α (T, x=O′2) is defined to be T′ where T′ is presented in FIG. 2B.
Constraints. An intention contains a set of constraints. A constraint is a function from a value assignment (to a set of variables) to the boolean values TRUE and FALSE. The sub-language used for the expression of constraints is not part of the EContracts framework specification. For the sake of simplicity, in examples, a simple constraints sub-language is used, which is called SIMPLE-C and which is presented through examples. For example, not(Ground($title)) AND ($price>100) AND ($name=“John”) AND (($name, $price)εR) is a constraint. Note that Ground means “is not null” and R denotes a set (relation) of tuples. The assignment C={$title→null, $price→150, $name→“John”, R→{(“John”,150), (“Steve”,170)}} satisfies the constraint.
Similarly, the values which are transmitted in messages, including values which appear inside tables or lists, may optionally be specified to be either hard values which are not negotiable, or soft values, which are negotiable. Soft values may be so indicated by a marker such as a question mark, for example. For example, if the active party sends the message “confirm price=5?”, the other party may answer with a counter offer, since “5?” is a soft value. On the other hand, if the message is “confirm price=5”, the price is not negotiable and there is no point in sending a counter offer. A similar mechanism may apply when sending values in a table or list from which a selection should be made.
A negotiation strategy for particular items may involve determining acceptable prices or delivery dates, for example. The strategy optionally includes a “bottom line” offer and modes of reacting to counter offers, preferably including a “rate of convergence” to the bottom line offer. Such strategies may also optionally include mechanisms for performing parallel negotiations, for example in order to determine how negotiations with one party should affect negotiations with other parties.
Instruction Current Assignment
Initially $a → 2, $b → 3, R(C, D) → {(1, 3), (2, 4)}
$b = 5 $a → 2, $b → 5, R(C, D) → {(1, 3), 2, 4)}
SELECT * AS :$a, :$b The values of the columns of the first
FROM R; tuple returned by the query are
Send $a The active party sends the message
“Send $a”. The value returned by the
Q = Choose n = 1 from The active party sends the message
R Format “Choose . . . ”. The one tuple relation
Col[1].Name = C, returned by the passive party is
Col[1].Type = Number, assigned to Q.
Col[2].Name = D, $a → 8, $b → 3, R(C, D) → {(1, 3),
Col[2].type = Number (2, 4)}, Q(C, D) → {(2, 4)}
Definition 3.1 (Commerce Automaton) A commerce automaton, say A, is a tuple A=(S, b, Sf, O, V, P, fP, δ) in which the following definitions apply. S is a set of states. bεS is the starting state. Sf ⊂S is the set of final states. O is the output specification. V is the set of the automaton variables. P is a set of assignment programs and fp is a function that maps states in S to programs in P. δ is the (partial) transition function δ: S×SC→S, where SC is the set of all SIMPLE-C constraints. O may be an instance of a class t or optionally obtained from such an instance using a sequence of variable instantiations.
Section 4 Unifying Two Intentions
As previously described, the unification of the intention trees of two parties leads to the establishment of an EContract. Such unification is preferably performed through a process which is essentially a process of negotiation, and which can be either automated or semi-automated, as previously described. This Section provides a formal description of the process of unification, along with examples of preferred unification algorithms.
The Acar CA is executed as follows. Since the variable $class is ground, the automaton moves to state 1. The automaton assigns to the relation variable A all the cars that correspond to the customer's class specification (Economy). Then, the automaton asks the customer (party) to choose a model. This choice may be done in several ways; human intervention may be requested, or an automatic tool, for example, an NA as defined above may be used. Such an automatic “expert” tool may, simply, choose an arbitrary car or employ more complex user-defined strategies. It can also try every choice, one after the other, and use backtracking if some choice leads to the failure of the automaton (The term “backtracking” indicates repeated trials by returning to earlier choices and considering alternatives to these previous choices, and is a technique which is known in the art. For example, this technique is employed in the Prolog language and interpreter as well in certain AI (artificial intelligence) systems.).
After receiving the model name, say “Cavalier”, the automaton selects the car, say (Cavalier, 322, Economy, 230), from the database (state 2). When the automaton reaches its final state (state 2) the assignments are $model←E-“Cavalier”, $id←322, $class E-Economy, $pric1←230. These assignments are applied to the output instance of the automaton. The (modified) output instance replaces the node labeled &Car in the intention tree of the used car dealer (FIG. 8) and the subtree rooted at the “boxed” Car node in the customer's intention tree (FIG. 7).
For an implementation with SQL as the access language to the data in relations, the backtracking of SQL commands within a CA or an NA is preferably performed as follows. An assignment out of a “select” command simply moves to the next tuple, which is similar to the traditional SQL cursor mechanism. When no further tuples are available, the “next” tuple is assigned a null value, such that retrieving this tuple results in a failure. An insert or delete statement is backtracked by moving to a savepoint immediately prior to the insertion or deletion, respectively.
Priorities in nodes and edges can be used as follows. Suppose unification fails, then a low priority node can be replaced with a less constraining node. This replacement is optionally performed by “upgrading” the node. A node upgrade can be any sequence of actions (as defined below) applied to nodes in the intention which result in an acceptable tree. Some actions apply to edges and make them less constraining. An action is defined as one of the following.
So, upgrading provides further options to the unification algorithm to explore. It may result in solutions that only approximate true unification of the pre-upgraded intentions, thereby “unifying as much as possible”.
Section 5 Examples of Preferred Implementations
The previous Sections considered a formal description of one implementation of the system and method of the present invention. This Section describes preferred embodiments of the present invention, which are specific examples of different applications of the present invention. These examples are intended only to illustrate the present invention, and should not be construed as being limiting in any way.
For example, suppose first party 104 is a buyer who wishes to purchase 4 of product A and 4 of product B. Central server 102 identifies second party 106 who supplies product A, third party 110 who supplies product B and fourth party 112 who supplies both product A and product B. Negotiation is preferably performed in parallel between first party 104 and each of second party 106, third party 110 and fourth party 112. First party 104 may therefore optionally be required to present portions of its intention as separate intentions to each of second party 106, third party 110 and fourth party 112. The optional separation of intentions is performed by party software module 108. First party 104 may then optionally choose to purchase one of product A from second party 106, one of product B from third party 110 and three each of products A and B from fourth party 112. For this embodiment, central server 102 is optionally replaced by any Internet search engine, such as “Google” for example [http://www.google.com as of Jan. 2, 2000].
In a second illustrative embodiment, each buyer is equipped with basic software for determining intentions, automata and preferences for negotiation. Each seller is equipped with similar software, as well as with connections to corporate data. Buyers and sellers, who may be one of the parties 104, 106, 110 or 112 of FIG. 11 for example, register with central server 102. However, now party software modules 108 of each party are preferably restricted in function, such that central server 102 performs the process of negotiation, as a trustee of the parties. Therefore, party software modules 108 could even optionally be implemented through a Web browser, for example, optionally with applets or Java scripts, or other scripts, or even with a specially built “thin” Web browser which is dedicated for this purpose.
In a third illustrative embodiment, central server 102 itself may be a party to commercial arrangements. For example, central server 102 may optionally purchase three of product A from second party 106, one of product B from third party 110 and three each of products A and B from fourth party 112. At end of the negotiating process, central server 102 remains holding two units of product A, which central server 102 can then sell to another party. This provides the possibility of brokering a plurality of commercial arrangements in “back to back” deals, packaging by combining the intentions of various buyers to obtain a larger volume, and so forth. Thus, in this embodiment, central server 102 is a broker.
The plurality of parts of party machine 10 include a Negotiation Control Program (NCP) 18, which is an overall coordinator of the activities of party machine 10. NCP 18 is preferably operated by the server for the second embodiment of FIG. 10, in which the server acts as a trustee. More preferably, the server also operates all of the parts of party machine 10 which are controlled by NCP 18 for this embodiment. Also in this embodiment, NCP 18 is implemented as an instance (i.e., a “copy”) of an NCP for the particular process of negotiations being handled by the server. The NCP also encompasses and controls the negotiation automata (NA's) which are associated with intention trees nodes.
One example of a method for operating the system of FIG. 11 is explained in greater detail below, with regard to the flowchart of FIG. 12. The description of this method refers to “two parties”, it being understood that these are two separate party machines 12, which could optionally be located at two separate clients, at a client and at the server, or alternatively both could be located at the server. In step 1, preferably the first party receives a copy of the intentions data structure 16 of the second party. In step 2, NCP 18 of the first party compares at least a portion of intentions data structure 16 for the first party to intentions data structure 16 for the second party.
Section 6 Translating Users' Constraints and Preferences into Mathematical Programs
This Section describes preferred embodiments of the present invention, which relates to a specific method of translating (or compiling) users' specifications into mathematical programs. The specific forms of mathematical programs we consider are the well-known Goal Programs [6, 7, 8, 10, 11] as well as their multiplex generalization [10]. The constraint solver can handle a wide variety of goal programs including linear, non-linear, integer goal programs.
1. Direct specification at the GUI level.
2. Questions & Answers at the GUI level. This may be accompanied by a structured technique such as the Analytic Hierarchy Process (AHP) [9].
3. Presentation of examples and discerning the user's goals based on which ones are preferred.
4. Observed user behavior over time. Based on past deals the user's preferences are determined.
5. Market “wisdom” as obtained through general surveys, which may be processed using traditional Conjoint Analysis or via methods such as the Analytic Hierarchy Process (AHP) [9].
In general, a deal specification may result in a number of contexts. Each new specification can be global within the current context or create a new context. Consider the following example. If one specifies the condition (X<15) OR (X>20), then one can state that these alternatives will apply to all derived contexts. Alternatively, one can state that this specification should split the current context into two separate contexts, one with (X<15) and one with (X>20). In the latter case, the current context is duplicated and the continuation of specification will be done separately in each context at the GUI level. The end result is that we may have a number of contexts. Each such context may give rise to one or more intentions. Each of these intentions is preferably handled separately.
1 Variables, e.g. integer X, float Y.
2 Hard constraints, of the form expression θ value, where expression is a function involving variables, θ is a comparison (<,≦, =, ≧, >), and value is a real number; e.g. X+3Y<17. The function θ may be linera or non-linear.
3 Soft constraints take the form soft (expression θ value).
Intuitively, these constraints are less stringent than hard constraints. When θ is =we call the soft constraint a target constraint. The relative importance of deviations from target may be indicated, e.g., exceeding a target is three times as important as under-achieving the target.
4 Preferences are of the form maximize expression or minimize expression. For example, minimize (2X−3y+Z).
5 Alternatives take the form (expression θ value) OR (expression θ value). For example, (X>17) OR (Y<9Z).
6 Rules are of the form IF expression θ value THEN expression θ value. For example, IF X>17 THEN PRICE<1200. We can view such a rule as a form of an alternative (disjunction). They are mentioned here mainly for completeness.
7 Priorities indicate that one entity (which may be a hard constraint, soft constraint, target, alternative or preference) is more important than another entity. This is an ordinal specification. Usually priorities are numbered 1, 2, 3, etc., with the understanding that 1 is the highest priority, then 2, etc. Observe that priority 1 entities are considered absolutely more important then priority 2 entities, which in turn, are considered absolutely more important than priority 3 entities, etc.
8 Weights: indicate, within a priority level, the relative importance of an entity relative to others. This is a cardinal specification. In case of target constraints, an option is to provide two weights, one for deviation below and one for deviation above; if not specified these deviations are considered equally unwanted.
9 Integral constraints, e.g., integer (X1), indicate that an expression needs to be evaluated to an integer. Generally, such constraints imply the usage of techniques for handling integers, such as the well-known branch and bound (see Chapter 11 in [10]).
Building blocks. The general idea is to use the technique of goal programming (G), suitably adjusted, to represent the constraints and preferences of a deal. We shall first discuss how constituent elements are handled, and then proceed to a simple intention, then to intentions containing usage of disjunction(s). The general form of a GP program is as follows: lexicographically_minimize {Expression 1, . . . , Expression m} such that for i=1, . . . , k we have goal constraints, gi, of the form:
ciX+(Di−)≧ti, or
ciX−(Di+)≦ti, or
ciX+(Di−)−(Di+)=ti,
and, in addition we have the constraint that
The Di variables are called aeviation variables; those of the form (Dj+) indicate an amount by which a goal is exceeded (“overshooting”), whereas those of the form (Di−) indicate under-achievement of goals. The Expression j's are called minimization expressions. The term lexicographically minimize (lex_min for short) implies an order on minimization, where the results of the Di's, of minimizing up to Expression i are used as values in Expression i+1, . . . , Expression m. So, the lower index expressions have a higher priority. Each Expression may refer to decision variables (X's), to deviation and other variables and to weights. Note that one may enforce hard constraints by setting some deviation variables to zero. For example, to enforce a≧ type constraint one may set (Di−)=0.
Minimize:Priority 1((D1−)+(D2−)+(D3+))Priority 2(D4+)Priority 3(D5−).
X1+X2+(D1−)−(D1+)=30
X3+X4+(D2−)−(D2+)=30
3X1+2X3+(D3−)−(D3+)=120
3X2+2X4+(D4−)−(D4+)=20
10X1+9X2+8X3+7X4+(D5−)−(D5+)=800
X1,X2,X3,X4,(D1−),(D1+),(D2−),(D2+),(D3−),(D3+),(D4−),(D4+)≧0
A hard constraint involving ‘<’ or ‘>’ is transformed into a hard constraint involving ‘≦’ or ‘≧’, respectively, by subtracting (respectively, adding) a small quantity. A hard constraint, of the form expression θ value, is compiled into expression+(D−)−(D+)=value Depending on hardness, we may add constraints (D+)=0 for θ=‘≦’ or (D−)=0 for θ=‘≧’ and (D−)=(D+)=0 for θ=‘=’. If hardness is more “limited” we may add a goal to minimize, of the highest priority, whose content is (D−)+(D+). The understanding is that at the highest priority minimization expression should evaluate to zero. Alternatively, we may simply derive a goal of the form LARGE*(D−), or LARGE*(D+) or LARGE*(D−)+LARGE*(D+) and treat it according to its weight. This latter form increases feasibility of a solution. Here LARGE is a sufficiently large value in the domain considered.
1. Define (Dp1+)=(D1+)/target and (Dp1−)=(D1−)/target.
2. What we minimize is the expression minimize (A*(Dp1−)+(1−A)*(Dp1+), [0≦A≦1] e.g., minimize (0.80*(Dp1−)+0.20*(Dp1−)).
3. If, in addition, the overall weight of this soft constraint is W, then we will minimize the minimization expression minimize (W*2)[0.80*(Dp1−)+0.20*(Dp1+)]. W*2 is an estimate, as only one (Dpi) variable will contribute to the result, evidently the other will be set to zero in solving the goal program.
Now consider a constraint of the form expression≦ value. It is compiled as above into:
Here the goal to minimize is W*(Dp1+), where W and (Dp1+) are as above. The cases of θ=‘≧’, ‘>’, ‘<’ are handled similarly.
This preference is compiled as follows. First, an “optimistic” yet “reasonable” target for the minimization is determined (by using default intervals, user specification or solving a simplified linear program). For example, if a reasonably optimistic small value for the above expression is 100, the preference is restated as the soft constraint: W1: 2*X+5*Y≦100.
Recall that in general we have a number of preferences, each translated into a soft constraint, say P0, . . . , Pk. These, and the “original”, soft constraints are partitioned into a number of priority levels. Priority levels are handled one by one using lexicographic minimization. Conceptually, the results of minimization at level i, that is, minimization expressions of higher priority, are inserted as constraints in the minimization at level i+1. Consider again the example goal program above. If we solve it using a linear programming package, we first present the highest-level linear program:
Minimize:(Expression of Priority 1)((D1−)+(D2−)+(D3+))
X1,X2,X3,(D1−),(D1+),(D2−),(D2+),(D3−),(D3+)>0
(D1−),(D1+),(D2−),(D2+)≦30
(D3−),(D3+)≦120
Minimize:(Expression of Priority 2)1(D4+)
((D1−)+(D2−)+(D3+))=0(This is the “newly fed” constraint.)
(D4−),(D4+)≦20
The solution turns out to be (D4+)=10. This is “fed” into yet one more (f) linear program that optimizes 10X1+9X2+8X3+7X4.
One problem is that if we do satisfy the “current feasibility set” other sets are not necessarily explored (unless we exhaustively backtrack over all possibilities). If not all are explored, during negotiations, we may be “locked in” optimizing within one feasible sub-region. Also, if we do exhaustively backtrack we are within a “single thread” of control, had we duplicated, we could have worked in parallel on several intentions. Unlike comparing general contexts, here comparing duplicates makes more sense, as they are all essentially the “same” optimization problem.
Yet another way to handle disjunction is by employing integer variables, and using them to “simulate” if-then-else. The disadvantage is that the constraint solver need employ costly techniques; the advantage is that the complexities are confined to the constraint solver, and all possibilities for optimization are explored.
1 Suggest a tuple of values when asked to provide one.
2 Choose from a number of alternative tuples of values; we can choose more than one by repeatedly applying choose.
3 Rank tuples of values according to their desirability. This ability is needed when evaluating intentions. Rank is implemented via choose.
4 Suggest an “improvement” to an input tuple of values, which improvement improves the “score” of the input tuple. This is needed when improving a suggested deal.
We may also need to handle a situation in which we have an offer, from the other party, that is not feasible. We need to “convert” such an offer into a feasible one, such that it retains, as much as possible, its “goodness”. This situation may also happen in a negotiation setting in which sides tell each other their overall value function (as represented by their goal program) as well as constraints they have (or portions thereof), yet some constraints remain untold and therefore the other party may come up with an infeasible offer.
If the optimization problem is infeasible, offer a default-selected tuple of values. Otherwise, solve the goal program. Observe that as this procedure may be called when only a portion of the variables are bound to actual values, there may be a range of possibilities of values of variables that are feasible. Get the values for the variables in question from the solution of the goal program. If nothing else is specified, return an “optimal” tuple, according to the user's preferences, as the one to suggest.
Method 1. Adding constraints per variable and analyzing dual variables (dual variables indicate how to improve the objective function by modifying constraints; see Chapters 8, 10 and 18 in [7]). This is done by adding to the goal program constraints of the form Xi=ai, where Xi is a variable associated with the i'th component of the optimal tuple, that is first computed, and ai is the value for that component. We then solve the resulting goal program, level by level. We examine the dual variables associated with the new constraints we introduced. To get a “lesser” tuple we need to modify the value associated with such a constraint so as to increase the (level's) objective function (recall that we minimize at the top). The amount of increase is according to the specification of percent-off-best-per-level applied individually per level. We change values of variables one by one, until the overall change, at the level, is according to the percentage specification.
Method 2: Adding a “level-wise constraint”. Here we consider the minimized function at the particular level, say f(Di's). Assume the minimum value is f(Di's)=a. Based on the percent-off-best-per-level specification for this level, say p, let a′=a+|a|p, here | |indicates absolute value. Add a constraint of the form f(Di's)≧a′, and solve the goal program at this level again. Use the results for the next level, where the same technique is applied. What we achieve is a “less optimal” solution of the original goal program as per the percentage specification per level. If at any point the goal program is not feasible we “undo” the last change by dropping the constraint introduced at the previous level.
If average is specified, we calculate best and worst tuples and form the “average tuple” by setting each tuple position to the average of the values in that position in the best and worst tuples.
In case of a non-linear goal programs we can search in the neighborhood of a solution for “less optimal” tuples.
If the optimization problem is infeasible, offer a default value per tuple entry (i.e., variable), in case there are default ranges, choose one, which is “closest” to an offered alternative. Otherwise, solve the goal program and return a tuple out of those to choose from, which is “closest” to the goal program solution implied tuple. If more than one choice is required, get the next best choice, and so on. As default, the distance is measured as the average percentage deviation from the tuple, computed over all tuple components. There are other methods for calculating distance that the user may choose and thereby override the default, for example Euclidean distance where each coordinate is normalized to a range, say [1-100].
Suppose we are provided with no additional information from the GUI level concerning the order of importance of variables in improving tuples. This case is very similar to the case of producing “less optimal” tuples, with the exceptions that (i) the added tuple-generated constraints are based on the values of the tuple we are improving; and (ii) we are trying to decrease the level-wise minimization functions or overall value function. Therefore, we handle this case using the methods for suggesting a tuple that we have described above (in A). In Method 1, we add the current tuple values as constraints; as before, we use dual variables, this time to further minimize. In methods 2 and 2′, we add the tuple values as soft (target) constraints with relatively low weights; as before, we also add constraints to decrease the minimization expressions, at each level, as compared to their current value.
Another issue is the possibility that the tuple we are trying to improve leads to an infeasible solution. In that case, rather than adding the tuple values as constraints of the form Xi=ai (Method 1), we add them as soft constraints. Alternatively, we can use default values and improve them, that is, an “infeasible tuple” is replaced by a “default tuple” and is then improved.
Alternatively, we can use the idea of relaxation. We relax the value for a variable, say X1, by adding the constraints, for i=2 . . . n, Xi=ai. Intuitively, we “bind” all other variables and leave X1 “free”. Now, we solve the resulting goal program. If the resulting program is feasible then we get a “better” value for X1. If this new value, say a1′, is reasonable (measured in percentage difference from a1) we move on to set X1=a1′ and apply relaxation next to X2. We repeat this process and end up with a new tuple of values to return. Note that as each variable is treated, the constructed tuple is “improved”.
1. Get the user's specification of deal from both deal, and item catalogs.
2. Build an intention—list of items, attributes, quantities, specifications concerning delivery and deal splitting.
3. Identify and scale atomic variables of interest.
4. Add any number of hard constraints.
5. Add any number of soft constraints.
6. Add choices out of a finite set of alternatives (e.g., color) with weights.
7. Add preferences (max, min, and desired values).
8. Add disjunction constraints and preferences.
9. Indicate priorities on preferences and soft constraints (ordinal). All hard constraints are at level 1 (highest).
10. Add weights (cardinal) relating preferences and constraints within each priority level.
11. Add integral constraints.
12. Obtain the method of combining objectives per priority level: for example, summation or min-max (which is the default).
13. Combine objectives into a lexical minimization problem where at each level the chosen method of combination is used.
14. Obtain the negotiation strategy to be employed and its parameters.
15. Partition the above into independent components (ICs). Each IC contains its own set of variables, preferences, constraints and objectives. That is, each IC can be handled independently of other ICs. For example, suppose we have W1: X+Y<20, W2: 2X−Y<7, minimize 3X+4Y, W3: Z−W<8 and W2: Z+W<30, maximize 2X+4Y. We can construct two ICs for these constraint set, one made of the first three terms mentioning X and Y and the other of the rest. In forming ICs, a disjunction is considered as “connecting” all variables appearing within it, that is, they will appear in the same IC.
16. For each IC form the following functions:
17. Boolean isFeasible (current values of variables, set of constraints—hard and soft)
18. TupleofValues suggest_Tuple (list of variable names, current values of variables, set of constraints—hard and soft, suggestion mode)
19. Set of TupleofValues choose_Tuple (list of variable names, current values of variables, set of constraints—hard and soft, set of alternative tuples for variables, choice mode)
20. Ordered Set of TupleofValues rank_Tuples (list of variable names, current values of variables, set of constraints—hard and soft, set of alternative tuples for variables, choice mode)
21. TupleofValues improve_Tuple (list of variable names, current values of variables, set of constraints—hard and soft, improvement mode)
22. With each intention tree leaf variable, associate a commerce automaton (CA). In the automaton one can perform:
Access to intention variables
Database access using SQL
Calls to IC functions as defined above
Messages to the “other party”
Add calls to user-defined functions (optional capability)
Automata have an associated input tree, an associated output tree, states and transitions.
1. With each IC, associate a negotiation automaton (NA) and construct it so that it can confirm, choose, suggest or improve tuples by using the IC functions. Attach the NA to the lowest node that is a parent of all the IC's variables. Attach a trivial NA to other nodes that simply transfers the message up the tree.
2. Based on the negotiation strategy, construct a negotiation control program (NCP). The NCP uses the procedure matchIntentions. This procedure performs unification on two intentions. During unification the above-mentioned functions are utilized. Backtracking is used to explore the space of possibilities. The unification is not necessarily in left-to-right order. A heuristic is to explore first highly “grounded” portions of the intention tree. Based on the negotiation mechanism, the NCP utilizes the negotiation API. The negotiation mechanism accesses the negotiation-oriented functions constructed during compilation (namely, to confirm, suggest, choose or improve tuples of values).
3. If necessary, customize backtracking to handle disjunction. This means, in particular, that one needs to construct the equation sets in real-time, the particular set depends on the alternatives used. This also means that some compilation activity needs to be done at run-time in combining the preferences associated with various alternatives.
Deal Splitting
Residual algorithm. Here the initial deal is submitted to the system. The system satisfies it as much as possible using best effort unification. What is left is considered as a “new” residual deal. The residual deal is submitted to the system and it is satisfied independently. Of course it may give rise, recursively, to more residual deals. The group of deals resulting from the original request needs to satisfy the initial deal constraints.
Section 7 Negotiations
In this section we consider the post-matching phase. A user's desired deal is potentially translated into a set of intentions. Each intention is separately matched (unified) with relevant intentions. The matching may involve exchange of messages as well as database and external data accesses. At this point a deal may be finalized (either automatically or by human decision). Alternatively, the deal may be further negotiated upon. Intentions may be modified while negotiating with one or more parties. Finally, automated or human decision is reached. As presented in Section 6, NAs and the NCP can form responses to CAs' inquiries based on the procedures, which are constructed as negotiation infrastructure (Section 6). Let us summarize the negotiations scenario.
1. A party generates a “better intention” using the deal improvement procedure (as per Section 6).
2. The party presents it to the other party.
3. The other party either agrees to continue improving, or presents a counter-offer.
4. The parties repeat improving the outstanding deal, based on the parameters.
5. Eventually, a decision is reached. The decision is reached when one of the parties declares that this is the last offer and asks the other party to either confirm or stop negotiating.
Observe that the above mechanism is symmetric in the sense that negotiations can be brought to conclusion by either party. We also foresee a variation in which only one of the parties has this ability.
1. Alternating levels −1, 1′, 2, 2′ . . . . This gives high priority to the other party's important interests.
2. Layered −1, 2, 3 . . . 1′, 2′, 3′ . . . . This takes one party's interests first into account and only then the other party's interests.
3. Layering & alternation. A more flexible combination, e.g., 1, 1′, 2, 3, 2′3′,
Consider a party that is about to improve an outstanding deal. Improvement is done in two steps. The combined program is used in a first step of deal improvement. Then, in a second optional step, the party modifies (that is, improves) the deal according to its own goal program. The latter program is optionally augmented with some of the constraints of the other party. This “double improvement” is designed to take into account the other party's interests as much as possible.
We note that the 1-1 mechanisms we have just discussed may be used in unstructured negotiations of a party with many parties. In this situation, one party (the “1”) negotiates is a structured way with many parties (the “N”). This mechanism uses the 1-1 mechanism without revealing as a sub-program. It operates as follows. Following the basic deal formation via matching, the “1” has outstanding deals with each of the “N” parties. The mechanism is on rounds (late arrivals may be excluded from a particular round). The “1” ranks intentions at the beginning of each round. It sets improvement targets for each participant so that each participant must beat the previous round best deal. With high probability (a parameter) the “1” drops non-improving participants except for the best performer of the previous round. The “1” continues based on perceived improvements, and time limits. Target setting is a function of time. Deal improvement with each party is done as in the non-revealing 1-1 mechanism.
At some point (see below) the “1” decides on an end-game phase. This phase is performed as follows:
1. The “1” ranks the outstanding intentions.
2. The “1” sets improvement targets for each participant so that each beats the best deal of the previous round.
3. The “1” makes offers, one by one, to each of the “N” so that if a deal offer is accepted, a deal is sealed and negotiations are over.
4. Out of the “N”, the one that proposed the best deal in the previous phase is asked first, then the second best, and so on. This creates extra motivation for the “N” parties.
5. If the “N” parties accepted no deal offer, the best deal from the previous phase is selected and sealed.
Section 8 Dynamic Negotiations
As presented thus far, a user U specifies his/her business intention(s). These are submitted to the system, which matches them with outstanding intentions (these may arrive at any point after submitting U's intentions). Intentions are associated with various parameters, which, as discussed in Section 6, are compiled (translated) into mathematical programs. These programs are used during the matching process and in the optional 1-1 or 1-N negotiation phase, as described in Section 7. In this section we allow running the above scenario while dynamically changing parameters. Parameter changing can be done through a GUI. In this case, while observing the state of negotiations, a party may decide to change the values of some parameters. Parameters can be associated with the deal itself, for example, the maximum price a party is ready to pay. Parameters may also be associated with the negotiation process, for example, the overall time allotted.
Changing some parameters at run-time can be implemented by replacing associated values in the intentions and the compiled goal programs. It may necessitate goal program re-compilation. If active negotiation sessions have already used the ‘old’ parameters during matching, they may have to be backtracked. In some cases, changes may necessitate re-forming of goal programs. In this case, a currently active negotiation session using such a goal program may have to be backtracked to a previous phase. For example, in 1-N negotiation, the session may be brought from the 1-N rounds to the 1-1 phase.
1. R. Fikes, R. Engelmore, A. Farquhar, and W. Pratt. Network-based information brokers, 1995. See http://www.ksl.stanford.edu/KSL_Abstracts/KSL-96-18.html as of Jan. 2, 2000.
APPENDIX Unification Algorithm
The input of the unification algorithm is two intention trees I1 and I2. C is the set of local constraints defined on I1 and I2. We assume that I1 and I2 do not contain OR vertices.
instance(T,S) Generates an isomorphic copy S of T with a disjoint set of variables including association to automata).
var(V) Satisfied if V is an unbound variable.
nonvar(V) Satisfied if V is not an unbound variable.
atomic(V) Satisfied if V is an atomic variable.
class(V) Satisfied if V is a class variable.
int(V), float(V), string(V) Satisfied if V is ground and is an integer (float, string, resp.).
mode(V,Structure,Type) Satisfied if variable V has the structure Structure (Structure can be: atomic, class or list) and type Type (Type can be: int, float, string or a class name).
bassert(Edb) Backtractable assertion of the fact Edb.
bretract(Edb) Backtractable retract of the fact Edb.
classDesc(C1, C2) Class C1 is a descendant of class C2 in a class hierarchy of an ontology.
automaton (V, A, O, ModeStmts) Satisfied if automaton A is assigned to V, its output instance is O and O's mode statements are ModeStmts.
run(A,O) Execute automaton A on instance O.
checkConstraints(T,C) Satisfied if the variables in T satisfy the constraints set C.
permute([X1, . . . Xn], [Y1, . . . Yn]) Satisfied if (Y1, . . . Yn) is a permutation of (X1, . . . Xn). Backtracking generates the “next” permutation.
ground(V) Satisfied if variable V has a non-null value.
bassert(ModeStmts), unify(O,T2), /*Prepare automaton “inputs”*/
US10069234 1999-08-31 2000-08-29 System and method for automated contract formation Active 2025-07-20 US7756772B1 (en)
US15179599 true 1999-08-31 1999-08-31
US50485300 true 2000-02-16 2000-02-16
PCT/IL2000/000516 WO2001016665A3 (en) 1999-08-31 2000-08-29 System and method for automated contract formation
US7756772B1 true US7756772B1 (en) 2010-07-13
ID=26848980
US10069234 Active 2025-07-20 US7756772B1 (en) 1999-08-31 2000-08-29 System and method for automated contract formation
US (1) US7756772B1 (en)
WO (1) WO2001016665A3 (en)
US20090106166A1 (en) * 2001-07-02 2009-04-23 International Business Machines Corporation Method and apparatus for privacy negotiation
GB0117542D0 (en) * 2001-07-18 2001-09-12 Hewlett Packard Co Improvements in and relating to digital communication methods for determining admittance to a negotiation
Fikes et al. "Distributed Repositories of Highly Expressed Reusable Ontologies", www.kls.stanford.edu, 1998. Abstract.
Jannik et al. "Encapsulation and Composition of Ontologies", www.kls.stanford.edu. Abstract.
Konopnicki et al "Toward Automated Electronic Commerce", First IAC Workshoop on Internet-Based Negotiations Technologies, IBM, Watson Research Center, Yorktown Heights, N.Y., 1999. Abstract.
US8655721B2 (en) * 2001-07-02 2014-02-18 International Business Machines Corporation Method and apparatus for privacy negotiation
US8407261B2 (en) * 2008-07-17 2013-03-26 International Business Machines Corporation Defining a data structure for pattern matching
US8495101B2 (en) 2008-07-17 2013-07-23 International Business Machines Corporation Defining a data structure for pattern matching
WO2001016665A3 (en) 2002-04-11 application
WO2001016665A2 (en) 2001-03-08 application
Sandholm et al. 1996 Negotiation among self-interested computationally limited agents
McIlraith et al. 2002 Adapting golog for composition of semantic web services
Owner name: DEALIGENCE INC., DELAWARE
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KONOPNICKI, DAVID;LEIBA, LIOR;SHMUELI, ODED;AND OTHERS;SIGNING DATES FROM 20020214 TO 20020217;REEL/FRAME:012827/0589