Constraint Definition Rule to Achieve High Rate of Success in Negotiations? Raiye Hailu and Takayuki Ito Nagoya Institute of Technology Nagoya,Japan {raiye,ito.takayuki}@itolab.nitech.ac.jp http://www.itolab.nitech.ac.jp Abstract. Humans when evaluating possible options, often reduce the possibilities that have to be evaluated at each step by eliminating those that did not satisfy the previous criteria. We will show that when agents use this approach their utility space becomes less complex. As result, a negotiation mechanism can support more number of agents. Moreover we will show that negotiations between agents that use this approach have more chance of locating a deal. We call this approach the subset rule. Specifically we consider modeling negotiations where many agents have to agree upon one option among available many. We assume that the negotiation matter is described by multiple interdependent issues. Each issue can have multiple possible values. The issues are interdependent means that it is not possible simplify the negotiation by negotiating over one issue at a time. When this is the case, the contract space is usually large and we face two challenges. The first is the difficulty of evaluating each possible contract. The second is the computational complexity of searching for the optimal contract. We will show that enforcing the sub- set rule when eliciting preference from human users helps us to tackle these two challenges. We use a bidding based negotiation mechanism and constraint based utility space model of previous work. Keywords: Automated Negotiation,Interdependent Issues,Constraints 1 Introduction Negotiations can be over a single issue or multiple issues. Further issues can be independent or interdependent. Also negotiations can be bilateral or involve more than two agents. This work proposes solutions to problems faced when au- tomating negotiations over multiple and interdependent issues. The negotiations can be between two or more number of agents. There has been extensive research on negotiations over independent issues [1–4] . When the issues are independent and when generally the contract space is small, the research focus is on what strategy agents use to maximize their utility while reaching at an agreement. That is the conceding strategy [5]. This ? AT2012, 15-16 October 2012, Dubrovnik, Croatia. Copyright held by the author(s). is the main theme of competitions like ANAC [6] where agents use the alternating offers protocol to exchange offers until one agent offers a deal acceptable by both. Moreover, when the issues are independent, the utility function of an agent can be represented as the sum of the utility functions of the agent over each issue. Therefore it is possible for agents to negotiate over one issue at a time while still obtaining the optimal result. However when the issues are interdependent and the contract spaces are large computational complexity becomes the main problem. Large contract spaces make the task of representing all possible contracts for a negotiation including the utility value of each agent for each contract so that the selection of the optimal contract can be automated difficult. Moreover, the computational cost of searching for the optimal contract grows exponentially with number of issues and agents. Previously [15] we proposed a rule called subset rule that can be used by agents when creating their utility space that reduces the complexity of their utility space. This made our negotiation mechanism to support more number of agents and also increased success rate of negotiations.. In this paper we give additional experiment result to show the trade off of enforcing the rule and success rate of negotiations.Moreover we add an additional step to the deal identification that removes redundant intermediate results enabling us to support even more number of agents in negotiations. We abstract the matter in which the negotiation is done over as follows; We assume the negotiation matter can be represented by one or more issues. Each issue can have multiple possible values. We represent each possible values using positive integers. We assume the optimal contract to be the one that maximizes social welfare. In other words, the contract with the highest total utility. Total utility of a contract is the sum of utility value of each agent for the contract. As a working example, consider a negotiation between an employer (E) and a candidate employee (C)(adapted from [7]. ). They negotiate over the issues how many days the employee is going to work (W d) and the number of days of child care provided by the Employer (Ce). The possible issue values for W d are number of days from 1 to 5; represented by W d : [1..5]. For Ce the issue values are Number of child care days can be between 0 and 2;represented by Ce : [1..3]. The complete contract space is shown in Figure 1 A. In our model the utility of a contract is the sum of the weights of the con- ditions(constraints) it satisfies. For example the candidate employee’s may have two conditions. The first is that at least two days of child care must be pro- vided.This can be provided by the employer or the candidate can work less number of days (E.g. three days a week) and look after his child on his free time. The second condition is that the candidate prefers to work as many days as possible. Working four or five days satisfies this condition. Any contract that satisfies any one of the conditions will have utility equal to the weight of the condition. If contracts satisfy both conditions then the sum of the weights of the two conditions is used. But when applying the subset rule, first the agent ranks the conditions. Then when evaluating contracts using the second condition only contracts that satis- fied the first condition are considered and assigned utility. Therefore contracts that satisfy condition two but not condition one have utility of zero. There are two important experiment results. The first is that we are able to support negotiation between fifteen agents with high success rate. The second one is that at different levels of satisfaction levels different success rates were observed. When agents follow the rule strictly higher success rates are found. When agents do not follow the rule strictly the success rate of negotiations dropped. This further emphasizes that the rule and success of negotiations are highly coupled. In application setting the subset rule is used during preference elicitation of the human users. The user interface of the negotiation system should guide the users in a way that first, they list their conditions. Then, rank the conditions and assign weight to them. Internally the system should enforce the rule when assigning utility values to contracts. The work in [8] is similar to this work that it considers interdependent issues also. It applies fuzzy constraints to model such interdependent issue utility spaces in bilateral negotiations. But the negotiation protocol discussed here can be applied to two or more agents. We use the utility space model and negotiation protocol proposed in [9]. Fig. 1. Employer and Candidate negotiation contract Space and a constraint 2 Literature Review The constraints based utility space model proposed in [9] groups contracts when assigning utility values. A bidding based deal identification method makes agents bid high utility regions of their utility space to a central mediator which matches all bids from all agents to find the best deal. 2.1 Grouping Contracts - Constraints Based Utility Space Modeling The idea proposed by [9] is to group similar contracts when assigning utility values. That is, rather than dealing with each contract one by one, intervals of the issue values are used. For example if the Candidate prefers to work more number of days. This implies that U (W d = 5) > U (W d = 4) > ...(W d = 1) which results in at least five unique utility values in the contract space. However when the agent applies the constraints based utility space model it approaches the problem differently. It may divide the contracts in to two. Those with W d > 3, and those with W d ≤ 3. It then assumes that contracts with more than three working days satisfy the condition of working many days while the rest do not. Such a constraint corresponding to this condition is shown in Figure 1 B. Agents create their utility space by creating many such constraints. It is possible for constraints to overlap. The utility of contracts in the overlap region is the sum of the utility of the constraints that overlapped. Figure 2 shows such utility space. Please note that in this model the issue values do not necessarily have to be quantitive values. Moreover the model does not assume any ordering on the issue values except that all agents use the same ordering. Therefore if color is one issue of the negotiation any ordering of the color values is acceptable, but the ordering should be the same for all agents. 2.2 Bidding Based Deal Identification The Bidding based deal identification algorithm [9] was proposed to avoid match- ing of the entire utility space of agents to locate the optimal contract. But it faces certain limitations. Bids are regions of the utility space of an agent with high utility value. Such regions are usually created due to the overlapping of constraints. Each agent submits his bids to a mediator agent who exhaustively matches the bids to find those that intersect. Such an intersection which has the maximum total utility is selected to be the deal. Agents randomly sample their utility space and adjust these samples by simulated annealing to generate their bids(See Figure 3). The last step in the bidding based algorithm is deal identification. The media- tor exhaustively matches the bids from the agents to locate the optimal contract. The problem is that computational cost of exhaustive matching increases exponentially(N oOf AgentsN oOf Bids ). One may solve the problem by limiting the number of bids from agents. But this has a problem. Not only it affects the optimality of the contracts identified, but it can also make the negotiations fail. When the deal identification is not able to identify any contract, the negotiation is said to be a failed one[9]. Fig. 2. Utility Space Some researchers have proposed negotiation protocols to overcome the de- scribed shortcomings and other weaknesses of the bidding based deal identifica- tion algorithm but a conclusive solution to the problems is yet to be found. The threshold adjusting algorithm [10] makes agents bid in multiple rounds. In each round the minimum allowable utility value of a bid is lowered. This has the advantage of limiting the amount of private information revealed to a third party.The representative based algorithm [11] improves scalability of the bidding based algorithm by making only few agents called representatives participate in the bidding process. The iterative narrowing protocol [12] reduces failure rates by iteratively narrowing down the region of the contract space that the agents generate their bids from. Measures that reduce high failure rates that arise when agents use narrow constraints were discussed in [13]. In [14] an algorithm that could identify the optimal contract correctly and efficiently was proposed.But it was assumed that the agents in the negotiation can be classified into sensitive and insensitive ones. 3 Proposed Solution:Subset Rule The rule is that each new defined constraint should be a subset of the constraint defined before it. This means that the second constraint can only contain some (possibly all) of the contracts in the first constraint, the third constraint can only contain some (possibly all) of the contracts in the second constraint and so on.(see Figure 4 (b) ). Fig. 3. Adjusting Intuitively this means that each constraint corresponds to a criterion that the users use to evaluate the contracts. The first constraint (the widest constraint) is the minimum criteria that the contracts acceptable by the user should satisfy. The second constraint is the second criterion that the contracts should satisfy. It is possible that other contracts that does not satisfy the first criteria satisfy the second one. But as a principle the user does not consider contracts that did not satisfy previous constraints. Formally a constraint Cj is said to be subset of Ci (Cj ⊆ Ci ), if and only if ∀S ∈ Cj , S ∈ Ck , Where S is a contract. A set of n constraints C1 , C2 ...Cn satisfy the subset rule in the given order , if and only if, (C2 ⊆ C1 ) ∧ (C3 ⊆ C2 ) ∧ ...(Cn ⊆ Cn−1 ) The advantage of the rule can be seen by comparing the number of bids in Figure 4 (a) and (b) . The main reason for the reduction of possible bids is the absence of partial overlapping of constraints when the rule is applied. This means the number of agents that the negotiation mechanism supports will be higher. Moreover we observed that when agents use the rule the mediators interme- diate matching list usually contains redundant results. By removing this redun- dant results we were able to increase the even more number of agents can be supported in negotiations even more. This redundancy is closely tied to how the constraints are positioned (and hence) the bids from agents. In Figure 5 the top three intermediate result bids all represent the same area in the contract space. But only the top one (B11+ B21) is required for the next matching. Another advantage of the rule is that for every new constraint added the number of contracts that have to be evaluated decreases. This is because only contracts that satisfied the previous constraints are considered. Fig. 4. Advantage of The Subset Rule 4 Experimental Evaluation We evaluated the effect of applying the rule by using the constraint generation method used in [9] but by modifying it in order to make some constraints satisfy the subset rule. 4.1 Experiment Settings The constraint generation methods compared were Random generation (Ran) and Subset rule based generation. In both cases for a negotiation with I number of issues, each agent defines 4 ∗ I constraints. Each issue has 10 possible values represented by 1 − 10. One example of a constraint in a 3 issue negotiation is (C: [5..8][4...7][1...10] ). Each interval corresponds to one issue. This constraint is said to have width of 4, because each of the first and second intervals contain four of the issue values. In the experiments a constraint is defined so that all intervals have an equal width with exception of the intervals defined over the entire issue value like the third interval in the example constraint. Moreover, this constraint is said to be a 2-Issue constraint because we can check whether a contract belongs to the constraint or not by just using its values for Issue 1 and Issue 2. Intuitively, this means the constraint is a function of only the first two issues. Similarly, one could define 1-Issue constraints and 3-Issue constraints and so on. In the experiments the utility for a constraint is randomly chosen from num- bers which are multiples of 10 with the maximum being 100. Fig. 5. Removing Redundant Bids Fig. 6. No. Of Bids The two constraint generation methods differ in how they position the con- straints and the width they assign to them. Ran This is the constraint generation method used in [9]. As mentioned above for a negotiation with I number of issues each agent defines 4 ∗ I number of constraints. These are comprised of 4 1-Issue constraints, 4 2-Issue constraints, 4 3-Issue constraints,...4 I-Issue constraints. The width of each constraint is chosen randomly from the values 1 − 6. The constraints are positioned randomly. Subset Rule Based Unlike the Ran method all the 4 ∗ I constraints are I - Issue constraints. There are I groups of the constraints. Each group contains four constraints that satisfy the subset rule. Two types of groups were used in the experiments. 8to2s and 6to1s. 8to2s In this setting the base constraint in a group has width of eight. The second constraint has width of six. The third constraint has width of four. The last constraint has width of 2. The following is an example of a group in a negotiation over two issues. C1:[2..9] [2..9] C2:[3..8][3..8] C3:[4..7][4..7] and C4:[5..6][5..6]. 6to1s In this setting the base constraint in a group has width of six. The second constraint has width of four. The third constraint has width of two. The last constraint has width of 1. In this case a group covers relatively smaller area in the utility space than the 8to2s case. This means , there are more possible positions to place a group in the utility space. Which in turn means the agents utility space will be more dissimilar than the 8to2s case. The following is an example of a group in a negotiation over two issues. C1:[1..6] [1..6] C2:[2..5][2..5] C3:[3..4][3..4] and C4:[4..4][4..4]. 4.2 Experimental Results Figure 6 shows the number of bids generated when Ran and Subset rule were used.The number of bids generated when the rule is applied is significantly lower than the Random case. For bid generation the procedures described in 2.2 were used. For adjusting random samples, simulated annealing(SA) with initial tem- perature of 10 was used. Figure 7 shows the optimality of the contract the mediator identified for the two type of constraint generation methods. In the negotiations there were 7 agents. Each was allowed to submit only 5 bids. Generally an optimality of greater than 0.8 was obtained for negotiations between agents who applied the Subset rule. But it was not possible to locate any deal contracts for negotiation between agents that used Ran. Five bids per agent is simply not enough to locate any deal let alone an optimal deal. Figure 8 compares the success rate of negotiations when subset rule and Ran are used. Success rate of 1 means for all negotiations a contract was found. When subset rule is used negotiation mechanism was able to support more number of agents. For negotiations of between more than 15 agents we could not check whether the negotiations fail or not. This is because matching bids required took too much time. Note that without removing redundant bids it is not possible to support more than 10 agents. Figure 9 further showcases that in fact using the rule increases the success rate of negotiations. In the graph Subset rule satisfaction level refers to :from the I number of group of constraints what percentage satisfy the subset rule. As described in 4.1 there are I groups of constraints. When subset rule satisfaction level is 1 the constraints in all groups satisfy the rule. When the level is 0.4 only 40 percent of the groups satisfy the rule. For this experiment a negotiation over 10 issues between 10 agents was used. Fig. 7. Optimality:Subset vs Ran 5 Case Study: Effect of The Subset Rule We will investigate what the subset rule implies on the utility of real agents by applying it to the candidate’s utility space. First the candidate has promised to his/her partner that he/she will look after their child for two days of the five working days. This promise can be fulfilled either by working less than five days, or by making the employer provide child care or by combination of the two. Hence, Cc >= 2, Cc ≥ 5 − W d + Ce. Cc is the number of child care days the candidate managed to provide. The constraints corresponding to this condition are shown in 1. Please note that Ce= 1 actually means that number child care days provided by employe is zero as described in the introduction section. W d : [1..3]Ce : [1..3]W d : [4..4]Ce : [2..3]W d : [5..5]Ce : [3..3] (1) Next the candidate prefers to work many days a week. For example, working for five days is preferred to working for just one day. To define constraint for this condition , we divide the contracts in to two. Those with W d > 3, and those with W d ≤ 3. We assume that contracts with more than three working days satisfy the condition of working many days. The constraint corresponding to this condition is shown in 2. W d : [4..5]Ce : [1..3] (2) The last one is that the candidate prefers the child care to be provided by the employer. That is contracts with Ce = 3 are preferred to contracts with Ce = 1(which actually means no child care is provided). The constraint is shown in 3. W d : [1..5]Ce : [3..3] (3) Fig. 8. Success Rate of Negotiations:Subset vs Ran Applying the subset rule means, when making new constraint by taking only the part of it that has intersection with the previous constraint. Such constraints are shown in 4, 5 and 6. For example the constraints in 5 are made by taking the intersection of 2 and 1. W d : [1..3]Ce : [1..3]W d : [4..4]Ce : [2..3]W d : [5..5]Ce : [3..3] (4) W d : [4..4]Ce : [2..3], W d : [5..5]Ce : [3..3] (5) W d : [4..4]Ce : [3..3], W d : [5..5]Ce : [3..3] (6) 5.1 Desirable and Undesirable Effects The effect of applying the subset rule can be seen by comparing Figure 10(A) and Figure 10(B). While its effect around region (D) is a desirable one. Its effect on the region around (U) is not that useful or even erroneous. Contracts that intuitively should have zero utility have non zero utility when the candidate does not apply subset rule. These are contracts in the region (D) of Figure 10(A). For example the contract (5,1) , which means the candidate will work for five days while getting no child care service from the employee has a utility of more than zero. This is due to the fact that this contract satisfies the second condition that the candidate prefers to work more days. However, this contract has a utility of zero when the subset rule is applied. The contracts around the region labeled by (U) in figure 10(B) have a utility of lesser value than the same region in 10(A). Specifically these are the contracts Fig. 9. Trade off between Satisfying Rule and Success of Negotiations in the region Wd:[1..3] Ce:[3..3]. These contracts satisfy the third condition, which states that the candidate prefers that child care to be provided by the employer. However , since they don’t satisfy the second condition, the subset rule did not include them in the definition of the third constraints. If it is the case that ,since these contracts have Wd of less than four, it does not matter to the candidate whether the child care is provided or not, then applying the rule has at least no negative effect. But if it still matters to the candidate that the employer provides child care even though the candidate has enough free time to do it himself, then, applying the rule have led to an incorrect representation of the utility space. 5.2 Assigning Monetary Values as Weights to Constraints Here we will try to use monetary values as weights to constraints. Assume that the expected salary of working for one day is $100 and the estimated cost of child care for 0 , 1 and 2 days to be $0, $20 and $25 respectively. Then, roughly the weight for a constraint is the difference of the expected monetary gain and the incurred cost of contracts satisfying the constraint. But before proceeding we have to solve two problems. The first is , since a constraint might be satisfied by many contracts, we can not find a single value that can represent the monetary gain of the contracts correctly. As a result we have chosen to use the value of the contract with the Fig. 10. Candidate’s Utility Space without applying Subset Rule minimum monetary gain. Hence the weight of constraint 1(at least two days of child care) is chosen to be $100. The second problem is that when using money the weight of constraints may not be independent. For example, normally we would choose the weight of constraint 2(working more number of days) to be $400. But since it overlaps with constraint 1, it would for example give a utility of $500 for the contract (4,3) which is an over estimation. Using a weight $300, would give us result that conforms to our first choice of using the value of the contract with the minimum monetary gain. Again for constraint 3(prefers child care to be provided by Employer) one might be inclined to consider the monetary gain from the working days of the contracts satisfying it. But as it overlaps with the previous two constraints it suffices to use the $25 as the weight of the constraint. The value $25 is the money ”saved” by the candidate by not providing child care himself. 6 Conclusion and Future Works We proposed a rule that can be used during grouping of contracts (defining con- straints) that reduces the no of possible bids from agents and hence increases the no of agents that could participate in the negotiation. The rule simulates what humans commonly do when evaluating possible options. That is, when evaluat- ing possible options, we often reduce the possibilities that have to be evaluated at each step by eliminating those that did not satisfy the previous criteria. The experimental evaluations show that applying the rule can greatly reduce the number of bids from agents. This reduction means that the negotiation system can support more number of agents. The reason why this rule works can be understood by noticing that in large contract spaces agents are highly unlikely to have local maximums(bids) at the same regions. For example in 100 contracts contract space the probability that two agents pick the same contract is about zero (1/100). This gets worse as the number agents and the contract space grows. Therefore, the constraint genera- tion mechanism should guide agents in a way that they will attain local maxima at similar locations. The subset rule does exactly that. But it does it while still keeping the individuality of agents as only the locations of the local maxima are similar(probabilistically) but the exact utility of the this local maxima is entirely dependent on the agent. In the experiments random values were used for each constraint weight value. One possible concern that needs to be addressed is how to make sure agents follow the subset rule when defining their constraints. Currently we are starting to develop a system to support such negotiations. In the system, the mediator is not just responsible for identifying the deal contract but also designing the User Interface negotiators use to define their constraints. Through that UI the mediator can validate their constraints to check weather the subset rule and other domain specific rules are being followed or not. The subset rule significantly reduced the number of bids, but this alone does not solve the problem completely. The computational cost of exhaustive match- ing still rises exponentially with the number of agents. We want to look ways to solve this problem. References 1. Faratin,C. and Jenning: Using similarity criteria to make issue trade-offs in au- tomated negotiations.In: Artificial Intelligence. vol. 142,pp.205 - 237. ELSEVIER (2002). 2. Fatima,M. and Jenning: Optimal negotiation of multiple issues in incomplete infor- mation settings.In: The 3rd International Conference on Autonomous Agents and Multiagent Systems, pp.1080-1087. AAMAS Press, New York (2004). 3. Lin and S.: Bilateral multi-issue negotiations in a dynamic environment.In:The Agent-Mediated Electronic Commerce, Melbourne (2003). 4. Lau: Towards genetically optimized multi-agent multi-issue negotiations.In:The 38th Hawaii International Conference On System Sciences, pp.1080-1087. HICSS Press, Hawaii (2005). 5. Klein,P., Sayama ,Bar-yam.: Negotiating Complex Contracts. In: MIT Sloan Re- search Paper No. 4196, (2001) 6. Baarslag, K.V., Jonker, S., Lin:The First Automated Negotiating Agents Competi- tion (ANAC 2010). In: Ito,M., Robu, S., Matsuo (eds.) Studies in Computational Intelligence. LNCS, vol. 383. Springer, Heidelberg (2010) 7. Hindriks,C.M.,Tykhonov: Eliminating Interdependencies Between Issues for Multi- issue Negotiation. In: Klusch,M.,Payne (eds.) CIA 2006. LNAI, vol. 4149, pp. 1148– 1158. Springer, Berlin Heidelberg New York (2006) 8. Xudong, Shadbolt, H., Lee: Multi-issue negotiations in semi-competitive environ- ments. Artificial Intelligence. vol. 148,pp. 53-102. ELSEVIER (2003). 9. Ito, H., Klein: Multi-issue Negotiation Protocol for Agents Exploring Nonlinear Utility Spaces. In: The 20th International Joint Conference on Artificial Intelligence, pp.1347-1352. IJCAI Press, Barcelona(2001) 10. Fujita, T.,Hattori,M.: An Approach to Implementing A Threshold Adjusting Mech- anism in Very Complex Negotiations A Preliminary Result.In: The 2nd International Conference on Knowledge, Information and Creativity Support Systems, pp.185- 192. JAIST Press, Japan(2007) 11. Fujita,T.,Hattori,M.:Effects of Revealed Area based Selection Method for Representative-based Protocol. ACAN(2008) 12. Hattori,M.,Ito: Using Iterative Narrowing to Enable Multi-Party Negotiations with Multiple Interdependent Issues.In: The 6th International Conference on Autonomous Agents and Multiagent Systems, pp.1043-1045. IFAAMAS Press, Hawaii(2007) 13. Marsa-Maestre,M.,delahoze: Deal Identification for Negotiations in Highly Non- linear Scenarios.In: The 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 84-89. IFAAMAS Press, Budapest (2007) 14. Raiye,T.: Efficient Deal Identification For the Constraints Based Utility Space Model.In:ACAN(2011) 15. Raiye,T.: Reducing The complexity of negotiations over interdependent is- sues.In:ACAN(2012)