Automated Negotiation

    Negotiation is a form of decision-making where two or more parties jointly search a space of possible solutions with the goal of reaching a consensus [Rosenschein94] . 1 Examples where negotiation occurs in commerce are stock markets, auctions (e.g., fine art, flowers), and various ad-hoc haggling (e.g., automobile dealerships) [Guttman98] . Since many of these forms of commerce became available in the digital world, there are many projects under way to automate negotiation. In automated negotiations, the negotiation parties are represented by agents. A few of the more recent projects which support automated negotiation are AuctionBot, Kasbah, and Tete-a-Tete.

    AuctionBot is a general purpose Internet auction server at the University of Michigan [19] . AuctionBot users create new auctions to sell products by choosing from a selection of auction types and then specifying its parameters (e.g., clearing time, method for resolving bidding ties). In a typical AuctionBot scenario, a seller would bid a reservation price after creating the auction and let AuctionBot manage and enforce buyer bidding according to the protocol and parameters.

    The MIT Media Lab's Kasbah [20] is a Web-based multi-agent classified ad system where users create buying and selling agents to help transact products. The agents can be configured with one of three negotiation strategies: anxious, cool-headed, and frugal. In addition to this, the agents have a date by which the item should be sold or bought, a desired price, and a lowest (seller) or highest (buyer) price for the item. Negotiation in Kasbah is relatively simple. After sellers and buyers are matched, the only valid action in the negotiation protocol is for buying agents to offer a bid to selling agents with no restrictions on time or price. Selling agents simply respond with a binding yes or  no.

    The two above mentioned systems competitively negotiate over price. Tete-a-Tete is also a MIT Media Lab project [21] and provides a unique negotiation approach to retail sales. Unlike Kasbah and AuctionBot, Tete-a-Tete agents cooperatively negotiate across multiple terms of transactions (e.g., price, warranty, delivery times).

    All of the above mentioned systems are positioned in the retail environment. They mostly negotiate the price of items in order to close a deal. The OPA represents a somewhat different approach for automated negotiation. Many transactions in various forms of commerce require the exchange of information during the transaction or in order to complete transactions. This information may include a buyer's or a seller's personal information. As described earlier, the release of personal information automatically affects the person's privacy. The OPA represents a first approach to negotiate the conditions under which the use of personal information is acceptable in online transactions.

The Concept of Negotiating Sets of Information

    The concept of negotiating sets of information is based on the idea of specifying constraints on sets of information. These constraints define the conditions under which a particular set of information can be accessed (e.g., for manipulation, or for the release of data to another party). In a transaction, a party (e.g., person or computer) issues a request to gain access to a particular set of information. The owner of the information checks this request and tries to verify whether the requestor satisfies all the constraints defined on the requested set of information. If the constraints are satisfied, the requestor will be granted access to the information. In case the constraints are not satisfied, the owner can reject the request or start negotiation. This negotiation is the process of finding a suitable counter-offer if the initial request is unacceptable.

Terminology

    The goal of negotiation is to reach an agreement in a transaction that is satisfactory to all parties. The process of negotiation can go over several rounds and includes steps such as the evaluation of requests, and the creation and submission of counter-offers. Before going into the details of the definitions and algorithms for negotiating sets of information, we want to introduce the relevant terms that will be used throughout this chapter.

Information, Rules, Constraints, and Facts

    The following definitions will introduce the terms personal information, rules, and facts. These terms will be used later in order describe and define algorithms, and explain the concept of negotiating sets of information.

  1. The finite set of personal information
  2. P = { d_1
     , d_2 , ... , d_n} contains all data elements d_i , 1
                                 <= i <= n , that can be the subject of negotiation.

    In the context of negotiation, a data element is used as an identifier for a particular piece of information. A data element can represent any kind of information, such as a numeric value (e.g., a person's age), text (e.g., a person's name) and graphics (e.g., a person's image or fingerprint).

  1. A rule r specifies the circumstances under which a set of information can be accessed. The rule r is defined by a pair
  2. (D_r,C_r) that denotes a set of information D_r with D_r
           subset of P , and a set of constraints C_r = {
                                c_1 , ... , c_m } defined on D_r . Each constraint c_j , 1 <= j <= m , represents a particular condition that must be met in order to get access to D_r .

    The constraints of a rule specify the conditions that must be met by the requestor. Constraints can be unary, or a relation on values for a single variable; binary, or a relation on values for a pair of variables; or n-ary, meaning that it simultaneously limits the possible values of n variables [Stefik95] . A simple example of a rule is to use the above definition in order to control access to various items. Let's assume a family sets up rules to control access to their cars. The rule

r_1 = ({convertible},{(driver=parents),(season=summer)})

    specifies that access to the dataset

    D_r = {convertible} can only be granted when the constraints C_r={(driver=parents),(season=summer)} are satisfied. In this case, it means that the convertible can only be driven by the parents when it is summer.
  1. The facts f are associated with a request for information. The facts f are defined by a pair
  2. (D_f,V_f) . The set D_f is not empty contains the data elements demanded by the requestor. The set V_f = { p_1 , ... , p_l } denotes the conditions under which the elements of D_f are requested. V_f contains name-value pairs p_i =
                                (x_i,v_i), 1 <= i <= l , in which x_i denotes the name and v_i the value of a particular item.

    The facts formally describe a request for a set of data-elements and the conditions under which this request is made. The owner of the requested data-elements can evaluate the facts and match them against his rules. If the facts satisfy a rule, the owner may grant the requestor access to the requested information. An example of facts could look like

    f_1 =
     ({convertible},{(driver=mother),(season=winter)}) , which can be checked against the simple rule example ((r_1) ) as introduced above.
  1. The set
  2. F = {
     f_1 , ... , f_k } denotes all possible combinations of facts of a particular domain. The domain represents the context, the possible name-value pairs, value ranges, and combinations of data elements of a particular application.
Rulesets and their Representation as Trees

    The notion of a rule was introduced to define the conditions under which a set of information can be accessed. In order to express such constraints for various sets of information, more than one rule needs to be defined. Various rules are grouped together in rulesets.

  1. A ruleset
  2. R = {
     r_1 , ... , r_k } denotes a set of rules.

    In definitions and equations, we will use R throughout this document in order to refer to a ruleset. However, in order to visualize the concept of rules and rulesets we will also use a graphical representation of rulesets. According to Definition (2) on page 62 , a rule is a pair that defines constraints on a set of information. Instead of representing various rules by their definition, we want to use the notion of a tree to graphically express a ruleset. The following example demonstrates this.

    Assume a person X has three rules to control access to three different sets of information:

r_1 = (D_r1, {c_1, c_2}),
     r_2 = (D_r2, {c_3, c_4}), r_3 = (D_r3, {c_3, c_5})

    These rules can be grouped into a ruleset

    R_X = {
     r_1 , r_2 , r_3 } . As one can see, r_2 and r_3 specify the same constraint c_3 . Throughout this chapter we will represent rulesets like R_X as trees 2 (see Figure 4-1 ).
Tree representation of a ruleset R.

Tree

    Each of the three rules is represented by a path from the root

    R_X to one of the leafs of the tree (see arrows in Figure 4-1 on page 63 ). The leafs of the tree represent the data sets D_n , with i=1,2,3 . The constraints lie in-between the root and the leafs. The tree representation is very useful in order to check the facts against the rules. This process is called rule evaluation.
Rule Evaluation

    Rule evaluation is the process of matching facts against rules. When a rule was found that is matched by the facts, access to the requested information can be granted. In order to match a rule, the facts need to meet two requirements. Firstly, the facts must satisfy all of the rule's constraints.

  1. The constraint-matching function
  2. sigma is a boolean function that indicates whether a name-value pair p element of V_f of the facts f matches a certain constraint c element of C_r of a rule r.
(6.1) sigma(c,p) = true
     iff p satisfies c; (6.2) sigma^n(c,p-bar) = true iff p-bar
     satisfies c

    Definition (6) specifies two functions, one for unary constraints (6.1) and one for n-ary constraints (6.2) with

    n>=2 . In case of the latter p-bar represents a vector with n elements. (For simplicity, throughout the next sections we will only use the constraint-matching function for unary constraints.)

    Secondly, the requested information as specified in the facts must be a subset of the information specified in the rule. This means, that the facts can only ask for data elements that are part of the rule's set of information. With this in mind, we can formally define the matching of a rule:

  1. Given facts
  2. f=(D_f,V_f) match a rule r=(D_r,C_r) , if:
(a) forall c_i element of
     C_r and there exists p_j element of V_f with sigma(c_i,p_j)
     true; (b) D_f subset D_r if and only if forall d_i element
     of D_f and there exists d_i element of D_r

    To summarize the contents of Definition (7) , facts match a rule, when all of the rule's constraints are satisfied and the requested data elements (as specified in the facts) are covered by the rule. This has several implications. First of all, facts can contain more information than necessary to satisfy the constraints. Secondly, the rule can cover more data elements than requested in the facts.

A Sample Rule Evaluation

    Before describing how the previous definitions of rules, facts and rule evaluation can be used for negotiation, we want to take a look at a sample rule evaluation. Assuming a family of four (parents, two children) owns three cars (e.g., a convertible, a truck, and a sedan) and wanted to set-up rules for the usage of these cars. The rules specify the circumstances under which a family member can access and use one of the cars:

r_1 = ({convertible},
     {(driver=parents),(season=summer)}; r_2 = ({truck, sedan},
     {(familymember with DL),(season=allyear)})

    The rules specify that the convertible can only be used by the parents when it is summer. The other vehicles can be used all year long, by any family member with a drivers license. These rules can now be used to control access to the familiy's vehicles. 3 Assume it is winter and one of the parents wants to use the convertible for a shopping trip. The facts of her request then is:

f_1=({convertible},{(driver=mother),(season=winter)})

    The service, which matches the facts against the rules, cannot grant her access to the convertible because it is winter. Because she cannot wait until summer arrives, she issues a new request, resulting in the facts:

f_2=({truck},{(driver=mother),(season=winter)})
Facts f matches rule r in ruleset.

Tree

    The service grants her access to the truck, because the facts of her request match

    r_2 . This is indicated with the shaded part of Figure 4-2 on page 66 . However, the mother needed to issue two requests in order to gain access to one of the vehicles. If the service would have been a little smarter it could have offered her one of the other cars (if available) right away, after her initial request could not be satisfied. In order to support such a smart behavior, i.e., negotiate with the requestor, the service needs to know how to create a reasonable counter-offer which the requestor can then accept or reject.
How to Find a Counter-Offer

    We want to define now how a service can produce a reasonable counter-offer after it had to reject a request for information. First of all, we need to explain what it means to find a reasonable counter offer. The term reasonable in this context means that the service produces a counter-offer that is semantically related to the rejected request. Assume the service in our example also had rules to control the access to other items, e.g. computers or sports equipment. When the service rejected the mother's request for a car, we consider it unreasonable to offer her anything other than a vehicle because she wants to go on a shopping trip.

    For the service to be able to find a reasonable counter-offer, it needs to find out how good the counter-offer matches the facts. First of all, a counter-offer is produced from a particular rule in the ruleset. This rule specifies acceptable conditions for the release of a set of information. In order to offer a reasonable alternative to a user's rejected request, it is the service's goal now to find the rule that best matches the facts. Note that the best match in this context does not match the facts completely. This cannot happen, because rule evaluation would have found this rule and accepted the facts. The step of finding a reasonably close counter-offer can be seen as one negotiation round.

Metrics and Distances

    Our approach to find a reasonable counter-offer is to measure the distance between the individual rules in the ruleset and the facts. The rule with the minimum distance is considered the closest rule and is used to produce a counter-offer. In order to do so, we need to define a metric which specifies the distance between a rule and facts. Based on this metric, we can then measure how well the facts match particular rules. In order to compute the rule with the minimum distance, it needs to be determined how well the facts satisfy the constraints of the rule and to what degree the sets of information of the rule and the facts overlap. Firstly, we define a function that measures to what degree the facts satisfy a rule constraint.

  1. The function
  2. delta_c
     : C x F -> Z+ denotes the distance between the constraint of an individual rule r=(D_r,{c1,...,c_n}) and the facts f=(D_f,V_f) . It is defined, such that:
delta_c(c_i,f) = 0 if
     there exists p element of V_f with sigma(c_i,p)=true; and
     delta_c(c_i,f) > 0 otherwise

    Secondly, we need to measure how well the set of information requested overlaps with the set of information covered by the rule.

  1. The function
  2. delta_D
     = P x F -> Z+ denotes the distance between sets of information of a rule r and facts f. It defines a quantitative measure of how well sets of information match:
delta_D(D_r,f) = 0 if D_f
     element of D_r; and delta_D(D_r,f) > 0 otherwise

    We will call the distances of Definition (8) and Definition (9) the local distances, which are the basis to compute the overall distance between a rule and the complete facts. The functions for computing the local distances represent a set of functions with specific characteristics instead of a function that specifies how to do that. This was done in order to prevent limiting this concept to a particular field of applications. Real implementations of such functions highly depend on the context and characteristics (e.g., number of variables, constraint types, and value ranges) of the respective application.

  1. The function
  2. DELTA :
     R x F -> Z+ maps the distance between a rule r element of R, r = (D_r, {c_1, ..., c_n}) , and facts f element of F onto the set of positive integers. DELTA is defined as follows:
DELTA(r,f) = (sum (for i
     from 1 to n) of delta_c(c_r, f) x w_i ) + delta_D(D_r,f) x w_D

    The overall distance is computed by accumulating the local distances. The terms

    w_i and w_D in Definition (10) are weights which are related to the n constraints c_i and the information set D_r of a rule. Weights can be used to emphasize the importance of local distances and allow to specify which parts of the rule are more important than others, while searching for the closest rule. This measure can now be used to determine a reasonable counter-proposal from facts and a ruleset. If the facts f are checked against a ruleset R={r_1, ..., r_n} , and there is no r_i element of R such that DELTA(r_i,f) = 0 , the rule r_j element of R with
min(DELTA(r_j,f))>0, 1<=j<=n

    best matches the facts. Facts that do not completely match a certain rule will cause the distance function to return a value greater than zero. The rule with the lowest distance to the facts is used to create a counter-offer. Throughout the remainder of this chapter, we will call such a rule the closest rule. The ruleset and the distance function

    DELTA represent the negotiation knowledge base as introduced in Section 2.2.3.2 on page 16 .
Depth-First-Search

    We now want to define a method for finding a counter-offer. The easiest way to do this is to compute the distances of all rules to the current facts, i.e. brute-force exhaustion search. The rule with the lowest distance will then be used to produce the counter-offer. Since this approach is not very efficient, we want to explain now a more efficient way to find the closest rule. Our approach is based on the idea to represent the ruleset as a tree as shown in Figure 4-1 on page 63 , and based on the way trees can be searched. We assume here that the reader is somewhat familiar with graph and trees. One of the basic methods for searching in trees is Depth-First-Search (DFS) [Stefik95] .

    A Depth-First-Search (DFS).

    DFS Example

    In a DFS, the search processor tries to find a solution to the search problem by traversing the tree. At each level of the tree (including the root), the processor checks whether the current node is the solution. If so, DFS terminates and a solution (i.e., there can be more than one solution in the tree) was found. If the node does not represent a solution, the processor descends to the first child of the node, and then to the first successor of that node. If DFS reaches a leaf it backtracks to the nearest ancestor and tries the next child. This is called depth-first because DFS plunges quickly downward into search space (i.e., DFS visits child nodes before visiting sibling nodes). Figure 4-3 illustrates a DFS for a solution. The numbers in the nodes indicate the order in which the nodes are visited. Node number seven represents the solution.

    DFS is the basis for our approach to find the closest rule. Each rule in a ruleset-tree lies on a path from the root of the tree to a leaf. Each node on this path represents a constraint or the information set of the particular rule. As defined in the previous sections, the distance between a rule and the facts is the sum of all local distances (e.g., constraints, sets of information). Using the concept of DFS, the distance between a rule and the facts can be computed while traversing the tree. Figure 4-4 illustrates how DFS can be used to find the closest rule. The text in the nodes specifies the local distance (e.g., constraint distance or information set distance). The distance between a rule and the facts is the sum of all local distances on a path. As one can see in Figure 4-4 , DFS will first descend down into the tree, all the way to the first leaf. At this leaf, the accumulated distance is the distance of the currently closest rule. From there, DFS proceeds but only visits nodes as long as the accumulative distance of local distances is less than the distance of the currently closest rule. The problem of this approach is that in order to get to the comparison criteria of a currently closest rule, the search process always needs to traverse the left-most path. This can be avoided with a slight modification of the search process.

    Finding the closest rule (DFS).

    DFS Example 2

    Assume that we can parameterize DFS by defining a maximum distance for the closest rule. This search parameter specifies that the closest rule must have a smaller distance to the facts than specified by the maximum. We can use this maximum during the search process in order to skip parts of the tree in the search for the closest rule. This is called pruning and occurs when the accumulated local distances are greater than the specified maximum. The effect of our slight modification is shown in Figure 4-5 which illustrates that now the search process needs to visit fewer nodes. This can be especially important in larger rulesets in order to cut down the time spent on searching for the closest rule. However, the modification of the search for the closest rule could have the effect that a closest rule may not be found if its distance is greater than the maximum distance parameter. If no closest rule can be found, the service has to reject the request or search again with a modified maximum.

    Finding the closest rule (DFS, maximum distance (<4) for closest rule).

    DFS Example 3
Negotiation Strategy

    One issue we have not covered yet is the negotiation strategy, which plays an important role in real world negotiations. The negotiation strategy represents how a negotiation party wants to accomplish its goal in a transaction. For example, the MIT's Kasbah [20] allows user's to create agents which can negotiate prices for items. Among other things, these agents can possess a certain strategy (e.g., anxious, cool-headed, or frugal) which specifies the method for placing bids for items. The strategies are implemented by different functions (e.g., linear or exponential functions) that specify which price to use in the next bid.

    These strategies can also be applied in the framework for negotiating sets of information, such that they are used to specify the maximum distance allowed for the closest rule. In addition to this, our framework provides several other ways to configure the respective negotiation agent. First of all, the ability to specify weights on constraints provides a simple way of prioritizing constraints. This allows a user to switch focus on that part of the rule that is most important to the user, and thus, influence the production of a counter-offer. Secondly, by specifying a maximum number of negotiation rounds allowed during a single transaction, we can configure how quickly a goal should be accomplished. Thirdly, the implementation of the functions to compute the local distances have a substantial impact on how to produce a counter-offer.

Summary

    A rule in our framework specifies constraints on a set of information. Multiple rules can be grouped together in a ruleset. This ruleset can then be used to verify incoming requests for information (i.e., the facts), and produce a counter-offer if the request had to be rejected. The process of finding such a counter-offer represents a negotiation round. The counter-offer itself is produced from the rule that has the minimal distance to the facts. The purpose of a counter-offer is to propose an acceptable request to the requestor.

    For simplicity and flexibility, we omitted two aspects in our concept of negotiation of sets of information. So far, we distinguished between rule evaluation and finding the closest rule. This distinction was made to show explicitly that simple rule evaluation is often inefficient in order to reach an agreement in a transaction. However, rule evaluation can be done by finding the closest rule. If a closest rule was found, the distance between this rule and the facts indicates whether the request associated with the facts can be accepted (i.e., distance equals null) or rejected (i.e., distance larger than null). In case of a rejection, the rule can be automatically used for the production of a counter proposal.

    The second thing we have not mentioned yet is the negotiation protocol. An automated negotiation protocol defines the rules of a bargaining game between automated agents (e.g., Web browsers and Web servers). We believe that such a protocol highly depends on the particular application and the application's context. Though, this document discusses the automated negotiation of personal information, the introduced concept is not limited to this particular field of applications. The introduced framework can be applied in any other context in which control over the access and distribution of sets of information is needed.

Current Implementation (P3P, APPEL)

    Now that we have covered the underlying framework for the negotiation of sets of information, it is time to talk about the negotiation module of the OPA's current implementation. In order to support automated negotiation, the negotiation parties need to have the same knowledge about the particular field of application. In electronic commerce, this knowledge includes the definitions and semantics of consumer profiles, merchants, goods, services, and negotiation protocols (among others) [Guttman98] . In the more general context of online transactions and privacy, this knowledge must include standard ways to access pieces of information, exchange messages, and definitions of how to express privacy policies. P3P [5] and the Harmonized Vocabulary [17] provide such definitions. In addition to this, we need a way to express rules in a machine-readable form in order to implement the rules in our framework. APPEL [6] is a language to define a user's preferences. In the following sections we will explain the implementation of the OPA's negotiation module, based on APPEL 4 and P3P.

Conversion of APPEL Rulesets

    As mentioned above we use APPEL rulesets in order to support the automated negotiation according to our framework. However, there are three issues to consider when mapping an APPEL ruleset onto our framework: the number of APPEL rule types, the order of APPEL rules, and overlapping rules.

Rule Types and Canonical Accept-Trees

    APPEL rules (see Figure 3-3 on page 39 ) provide a way to define conditions under which the rule is matched by a P3P proposal, similar to the constraints of a rule in our framework. In addition to this, APPEL rules specify a behavior which specifies the next action to be taken by the user agent when the rule is matched. These behaviors are seamless-accept, seamless-reject, info-prompt, and warn-prompt. Whereas the rules with a seamless behavior are very useful for automated negotiation, the prompting behaviors require the interaction with the user. As you can see in our framework, rules define conditions under which a set of information is accessible. Thus, rules in our framework can be seen rules with a seamless-accept behavior. The respective ruleset is what we call a canonical accept-tree. Any rule in such a tree can be used to produce a counter-offer because it specifies acceptable conditions. In comparison, only APPEL rules with a seamless-accept behavior can be used to produce a counter-offer, all other rule types require user interaction or specify conditions under which a request should be rejected. Secondly, there is the issue of the structure of APPEL rulesets. The rules in an APPEL ruleset are ordered. APPEL rule evaluation checks the rules against a P3P proposal in the order in which they appear in the ruleset. When a rule is matched by the facts, rule evaluation terminates and the next action of the user agent is determined by the rule's behavior. Other rules are not checked anymore. Our framework does not support ordered rules, instead it provides a metric to measure the distance between a rule and the facts. Thus, we chose to consider only rules that allow a seamless completion of the transaction (e.g., seamless-accept, and seamless-reject). Furthermore, we consider the order in which these rules appear in the APPEL ruleset. The other kinds of APPEL rules are considered during rule evaluation, which is processed before negotiation.

    Thirdly, there is a chance that reject- and accept-rules overlap. This means that a reject-rule and an accept-rule could be matched by the same facts. The higher ordered rule will be matched and there is no need for the other rule to cover such cases. Although APPEL allows overlapping rules, we expect APPEL applications to prevent a user from creating such rules, or at least inform the user about such conflicts. However, we take such conflicts into consideration when converting APPEL rulesets. Taking the above mentioned in mind, we designed an algorithm for the creation of canonical accept-trees from APPEL rulesets.

Algorithm

    Figure 4-6 shows the three major steps of the algorithm. In the first step, we create an empty canonical accept-tree, i.e., a tree (with a root node) which does not contain any rules. In the second step, all accept- and reject-rules are extracted from the APPEL ruleset by maintaining the order in which they appear. In the third step, each extracted APPEL rule is transformed into an internal rule format, and added or merged into the tree, depending on the ruletype. The rules are processed in their reverse order. The result of this algorithm is a canonical accept tree which contains all the accept-rules of the APPEL ruleset, and does not conflict with any of the APPEL ruleset's reject-rules. This set of accept-rules represents our negotiation knowledge base, as shown Figure 2-2 on page 13 .

    Algorithm to convert an APPEL ruleset into a canonical accept-tree.

    Step 1: Create an empty canonical accept tree with a root node.

    Step 2: Extract all accept- and reject rules from APPEL ruleset.

    Step 3: For each extracted APPEL rule do in reverse order:

    (3.1) Transform APPEL rule into internal rule format.

    (3.2) if type of APPEL rule is reject

    then Merge rule into tree by checking it against the

    accept-rules in the tree.

    else Add rule to tree.

    Now that we have introduced the rather generic algorithm, we want to take a closer look at some of the individual steps. Before an XML-encoded APPEL rule can be added to or merged into the tree, it needs to be transformed into the internal rule format. This format is simply a list of constraints and the set of data elements covered by the particular rule.

    Transformation of APPEL rule into internal format.

    <APPEL:RULE behavior="seamless-accept">

    <P3P:PROP>

    <P3P:USES>

    <P3P:STATEMENT action="r" VOC:id="0"> <DATA:REF name="a"/>

    <DATA:REF name="b"/>

    </P3P:STATEMENT>

    </P3P:USES>

    </P3P:PROP>

    </APPEL:RULE>

    implies

    action="r"

    VOC:id="0"

    DataSet={a,b}

    Figure 4-7 on page 75 shows such a transformation. As one can see on the right side of Figure 4-7 , the list only contains those attributes of the rule that specify the constraints which need to be satisfied. For clarity, we omitted any attributes of other XML-elements than the P3P:STATEMENT-element. However, APPEL rules can also refer to other elements of a P3P proposal, in which case the respective element name will be included in the constraint. The same mechanism would be used for APPEL level 2 rules, which can contain constraints on elements that are not part of the P3P syntax. After a rule was transformed it can be added to the tree, if the rule is an accept-rule. Figure 4-8 on page 76 illustrates the process of adding two accept-rules in their reverse order to a canonical accept-tree. In the first step, the second rule of the APPEL ruleset is added to the empty tree. In the second step, the higher-order rule is added to the tree. In case the next rule to be processed is a reject-rule, the algorithm does not add but merges the rule into the tree. Merging a rule means to check the reject-rule against all accept-rules that were already in the tree. These checks are performed in order to resolve conflicts between reject- and accept-rules. Figure 4-9 on page 77 visualizes how a reject- and an accept-rule are merged into a tree when there is a conflict between the rules.

    Adding accept-rule into canonical accept tree.

    Example

    As one can see in Figure 4-9 , the accept rule in the tree and the reject rule could both be matched by the same P3P proposal, for example: 5

    <P3P:PROP>

    <P3P:USES>

    <P3P:STATEMENT VOC:recpnt="0,1,2">

    <DATA:REF name="c"/>

    <DATA:REF name="d"/>

    </P3P:STATEMENT>

    </P3P:USES>

    </P3P:PROP>

    In order to resolve such conflicts, the accept rule in the tree is modified. This is done by modifying the rule's constraints, such that the accept rule does not conflict with the reject rule anymore. In case the sets of information of the reject-rule and the accept-rule are not identical, a new accept-rule is added to the tree.

    Merging a reject-rule into canonical accept-tree.

    Example

    The added accept-rule is a copy of the original accept rule with a modified set of information. Only those data elements that are not listed in the reject-rule are listed in the new accept-rule's set of information. Merging reject-rules the way we described above assures that all accept-rules in the tree can be used to produce counter-offers. None of these counter-offers will match a reject-rule because these cases are eliminated during the conversion of the APPEL ruleset.

Combinations of Sets of Information

    For clarity, we omitted a special case that can occur when dealing with APPEL rulesets. As we have mentioned earlier, the P3P syntax allows multiple statement-blocks (i.e., the P3P:STATEMENT-element) in one P3P proposal and therefore, APPEL allows the same in a rule. This leads to the problems of how to deal with combinations of sets of information. During online transactions, a P3P proposal is sent by a Web server to inform the user about the site's privacy practices. This information is encoded in machine-readable form in one or more statement-blocks.

    Adding rule with multiple statement-blocks and additional information.

    Example

    Therefore, we decided to treat statement-blocks as the facts, i.e., each rule in a canonical accept tree refers to the constraints on a statement-block. A P3P proposal can also contain information about an assuring party (i.e., ASSURANCE-element), and a disclosure (i.e., VOC:DISCLOSURE-element). Thus, this information can be referenced in APPEL rules, for example that a rule requires the existence of a certain assuring third party before data can be given out. This information covers the whole proposal whereas the information in a statement-block covers only the content of the statement-block. The additional information will be linked to each of the proposal's statement-block and included in the canonical accept-tree (see Figure 4-10 on page 78 ).

How to Produce a Counter Proposal

    Now that we have explained how APPEL rulesets can be used as the negotiation knowledge base, we want to describe the process of extracting the facts out of P3P proposals. In addition to this, we will describe how a counter proposal can be produced, based on the canonical accept tree.

Extracting Facts from P3P Proposals

    Similar to the conversion of APPEL rules into canonical accept-rules, facts are extracted from P3P proposals by looking at the proposal's statement blocks and additional elements. Each statement-block produces separate facts, according to our framework, which contain the information from the statement-block and information valid for the whole proposal. Figure 4-11 illustrates the extraction of facts from a P3P proposal. Each of these facts will then be separately matched against the canonical accept-tree. In addition to the information contained in a P3P proposal, facts can contain other transaction-related information not included in the P3P message, such as the type of the connection (e.g., whether it is cryptographically secure).

    Extracting facts from a P3P proposal.

    <P3P:PROP ...>

    <P3P:USES>

    <P3P:STATEMENT action="r" VOC:id="0"> <DATA:REF name="a"/>

    <DATA:REF name="b"/>

    </P3P:STATEMENT>

    </P3P:USES>

    <P3P:USES>

    <P3P:STATEMENT action="rw"

    VOC:purp="0,1,2">

    <DATA:REF name="c"/>

    <DATA:REF name="d"/>

    </P3P:STATEMENT>

    </P3P:USES>

    <P3P:ASSURANCE service="a URL"/>

    </P3P:PROP>

    implies

    implies

    P3P:ASSURANCE,

    service="a URL"

    action="r"

    VOC:id="0"

    DataSet={a,b}

    P3P:ASSURANCE,

    service="a URL"

    action="rw"

    VOC:purp="0,1,2"

    DataSet={c,d}

Distance Functions and Weights

    In order to measure the distance between the facts, extracted from a P3P proposal, and a rule in the canonical accept-tree, we need to define the distance functions and specify the weights. The distance functions are used to compute the local distances constraints and the facts, and the degree of overlap between the rule's data set and the facts' data set. We chose a relatively simple approach to compute these local distances.

  1. The distance function
  2. delta_D to compute the distance between the rule's data set D_r and the data set D_f (facts), is defined as follows:
delta_d(D_r,f) =
     magnitude of (D_f/union(D_f,D_r)) x w_D, if D_f subset of
     D_r; delta_d(D_r,f) = M, some large number

    This definition specifies that the distance is the number of all data elements in the facts' data-set minus the number of shared data elements, if the data sets share elements. Otherwise, this function will return a large number in order to indicate a large distance. This big-M-method is very useful in this context in order to indicate that the respective rule covers a completely different dataset.

    In order to define a distance function

    delta_c(c_i,f) to compute the distance between a rule's constraint c_i and the facts f, we need to distinguish the different kinds of constraints. The kind of the constraint depends on the value-matching method specified in the rule's constraint. The following table specifies the value delta_c(c_i,f) will return depending on the constraint.
Definition of local distance function (constraints).

Constraint-Type

Distance computation method

Wildcard-Matching:

VOC:id="*"

The returned value is always 0.

The facts can contain any value.

Multi-Numeric Values (one or more):

VOC:purp="2,3,4"

see delta_D . Example: VOC:purp="0,1,4,5" has a distance of 3w_c to the rule value VOC:purp="2,3,4". If no shared values in t facts and rule constraint, the distance is M.

String value:

service="http://www.ibm.com"

0, if value-pair in facts matches string

M, otherwise

Sample Negotiation

    We have described how to convert APPEL rulesets, how to extract facts from P3P proposals, and how to measure the distance between a rule and the facts. Now, we want to take a look at a sample negotiation. Assume we have the following ruleset:

    Sample ruleset (canonical tree).

    Example

    Also assume, the OPA received a P3P proposal that results in the following facts f:

    VOC:purp="1,2,3,4"

    VOC:recpnt="1,2,3"

    action="r"

    VOC:id="0"

    DataSet={a,b,c,e,f,g,h}

    The facts f do not match any of the two rules in Figure 4-12 because the data sets do not match completely and some of the constraints are not satisfied (e.g., VOC:purp). However, the rules could be used to offer a counter proposal. With the definitions of the local distance functions we get the distances of the facts f to both rules.

DELTA(r_1,f) = 2w_purp +
     3w_recpnt + 0 + 0 + 4w_D;  alt=

    If all the weights are set to

    w=1 , rule r_2 should be chosen in order to produce a counter-offer. This counter-offer would propose access to the data set {e,f,g,h} under the conditions as specified in rule r_2 . One can also see that one of the local distances (i.e., VOC:purp) in this rule is larger than in rule r_1 .

    Now, if the purpose of a transaction is more important to the user than other parameters, the user can express this simply by adjusting the weights. If he changes the weight for the purpose to

    w_purp=3 , rule r_1 has a smaller distance to the facts than r_2 and will be chosen to produce a counter-offer.

    Whatever rule was chosen based on the weights, it will then be used to create a P3P proposal which then represents the counter-offer to be made. We now want to talk about how this counter-offer would look like. It is basically the reverse process of extracting the facts from a P3P proposal. In addition to this, the counter-offer will contain a reference to the rejected server-proposal, such that the respective Web server can relate the counter-offer to one of its own P3P proposals. Figure 4-13 illustrates how a counter offer would look like, produced from rule

    r_2 .
Rejected P3P proposal vs. counter-offer with proposal-fingerprint.

Rejected Proposal

<P3P:PROP ...>

<P3P:USES>

<P3P:STATEMENT

VOC:purp="1,2,3,4"

VOC:recpnt="1,2,3"

action="r"

VOC:id="0"

<DATA:REF name="a"/>

<DATA:REF name="b"/>

<DATA:REF name="c"/>

<DATA:REF name="e"/>

<DATA:REF name="f"/>

<DATA:REF name="g"/>

<DATA:REF name="h"/>

</P3P:STATEMENT>

</P3P:USES>

<ASSURANCE .../>

</P3P:PROP>

Counter-Offer

<P3P:PROP

agreeID="<MD-5 of rejected Prop>"

...>

<P3P:USES>

<P3P:STATEMENT

VOC:purp="0,1"

VOC:recpnt="0,1,2"

action="r"

VOC:id="0"

<DATA:REF name="e"/>

<DATA:REF name="f"/>

<DATA:REF name="g"/>

<DATA:REF name="h"/>

</P3P:STATEMENT>

</P3P:USES>

<ASSURANCE .../>

</P3P:PROP>

    The procedure of producing counter-offers can occur several times during a P3P transaction. The number of negotiation rounds allowed during a transaction limits the number of counter-offers to be produced. If this limit is reached during the transaction, either the user has to make a decision or the transaction should be finally rejected.


1. Like the term agent, there is no consensus definition of the term negotiation. Among many others, economists, game theorists, business managers each provide unique perspectives on its meaning. We chose a relatively broad definition which we can apply in the context of automated negotiation.

2. Trees are connected undirected graphs with no simple circuits [Rosen95] .

3. We assume here that there is a service (e.g., computer, servant) which administrates the keys to the cars.

4. The OPA's negotiation module was implemented and tested in order to support APPEL level 2 rulesets. However, for simplicity and clarity, we will use APPEL level 1 rulesets to describe the current implementation.

5. Note that APPEL accept- and reject-rules are matches differently. Accept-rules are matched if the P3P proposal specifies only data elements and attribute-values as listed in the rule. Reject rules are matched if any of the rule specifications are matched (see Appendix C for details).


April 9, 1999 · Jörg Meyer · jmeyer@almaden.ibm.com