In the previous chapters we described the OPA's architecture, its underlying functional model and its current implementation based on WBI. Moreover, we demonstrated how the OPA monitors Web transactions and transfers information to Web browsers and Web servers. The OPA can evaluate privacy information (i.e., P3P proposals), and assist the user in the current transaction or complete the transaction on behalf of the user. In order to lessen the burden on the user in Web transactions, we want to show now that the user can benefit from the OPA's automated negotiation, in the context of P3P. The OPA can negotiate the terms and conditions of a transaction in order to try reach an agreement satisfactory to the user and the service. In this chapter, a brief overview about automated negotiation is given, before the details of the concept of negotiating sets of information will be explained. Following the more theoretical description, the concept will be illustrated with the current implementation of the OPA's negotiation module based on P3P and APPEL.
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  . 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  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  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 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.
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.
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.
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).
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
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, which can be checked against the simple rule example ( ) as introduced above.
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.
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.
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.
Definition (6) specifies two functions, one for unary constraints (6.1) and one for n-ary constraints (6.2) with. In case of the latter 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:
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.
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:
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:
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:
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.
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.
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.
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 functionrepresent the negotiation knowledge base as introduced in Section 18.104.22.168 on page 16 .
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] .
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.
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.
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  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.
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.
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  and the Harmonized Vocabulary  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  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.
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.
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.
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 .
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.
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.
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.
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.
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.
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 ).
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.
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).
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.
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.
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:
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.
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.
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] .
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).