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. Speci cally 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 rst is the di culty of evaluating each possible contract. The second is the computational complexity of searching for the optimal contract. We will show that enforcing the subset 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.
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 automating 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 [
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 di cult. 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 o of enforcing the rule and success rate of negotiations.Moreover we add an additional step to the deal identi cation 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 [
In our model the utility of a contract is the sum of the weights of the conditions(constraints) it satis es. For example the candidate employee's may have two conditions. The rst is that at least two days of child care must be provided.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 ve days satis es this condition. Any contract that satis es 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, rst the agent ranks the conditions. Then when evaluating contracts using the second condition only contracts that satised the rst 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 rst is that we are able to support negotiation between fteen agents with high success rate. The second one is that at di erent levels of satisfaction levels di erent 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 rst, 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 [
The idea proposed by [
However when the agent applies the constraints based utility space model it approaches the problem di erently. 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
The Bidding based deal identi cation algorithm [
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 nd 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 identi cation. The mediator 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 AgentsNoOfBids). One may solve the problem by limiting
the number of bids from agents. But this has a problem. Not only it a ects the
optimality of the contracts identi ed, but it can also make the negotiations fail.
When the deal identi cation is not able to identify any contract, the negotiation
is said to be a failed one[
Some researchers have proposed negotiation protocols to overcome the described shortcomings and other weaknesses of the bidding based deal identi cation 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 e ciently was proposed.But it was assumed that the agents in the negotiation can be classi ed into sensitive and insensitive ones. 3
The rule is that each new de ned constraint should be a subset of the constraint de ned before it. This means that the second constraint can only contain some (possibly all) of the contracts in the rst constraint, the third constraint can only contain some (possibly all) of the contracts in the second constraint and so on.(see Figure 4 (b) ).
Intuitively this means that each constraint corresponds to a criterion that the users use to evaluate the contracts. The rst 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 rst 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 8S 2 Cj ; S 2 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 intermediate matching list usually contains redundant results. By removing this redundant 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 satis ed the previous constraints are considered.
We evaluated the e ect of applying the rule by using the constraint generation
method used in [
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 rst and second intervals contain four of the issue values. In the experiments a constraint is de ned so that all intervals have an equal width with exception of the intervals de ned 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 rst two issues. Similarly, one could de ne 1-Issue constraints and 3-Issue constraints and so on.
In the experiments the utility for a constraint is randomly chosen from numbers which are multiples of 10 with the maximum being 100.
The two constraint generation methods di er in how they position the constraints and the width they assign to them.
Ran This is the constraint generation method used in [
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 signi cantly 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 temperature of 10 was used.
Figure 7 shows the optimality of the contract the mediator identi ed 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. 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 ve working days. This promise can be ful lled either by working less than ve 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 ve days is preferred to working for just one day. To de ne 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] 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. (2) (3)
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]
W d : [4::4]Ce : [2::3]; W d : [5::5]Ce : [3::3] W d : [4::4]Ce : [3::3]; W d : [5::5]Ce : [3::3] (4) (5) (6) 5.1
The e ect of applying the subset rule can be seen by comparing Figure 10(A) and Figure 10(B). While its e ect around region (D) is a desirable one. Its e ect 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 ve 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 satis es 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 gure 10(B) have a utility of lesser value than the same region in 10(A). Speci cally these are the contracts 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 de nition 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 e ect. 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
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 di erence of the expected monetary gain and the incurred cost of contracts satisfying the constraint. But before proceeding we have to solve two problems.
The rst is , since a constraint might be satis ed by many contracts, we can not nd 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 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 rst 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 su ces 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
We proposed a rule that can be used during grouping of contracts (de ning constraints) 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 evaluating 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 generation 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 de ning 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 de ne their constraints. Through that UI the mediator can validate their constraints to check weather the subset rule and other domain speci c rules are being followed or not.
The subset rule signi cantly reduced the number of bids, but this alone does not solve the problem completely. The computational cost of exhaustive matching still rises exponentially with the number of agents. We want to look ways to solve this problem. 10. Fujita, T.,Hattori,M.: An Approach to Implementing A Threshold Adjusting Mechanism in Very Complex Negotiations A Preliminary Result.In: The 2nd International Conference on Knowledge, Information and Creativity Support Systems, pp.185192. JAIST Press, Japan(2007) 11. Fujita,T.,Hattori,M.:E ects 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 Identi cation for Negotiations in Highly Nonlinear Scenarios.In: The 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 84-89. IFAAMAS Press, Budapest (2007) 14. Raiye,T.: E cient Deal Identi cation For the Constraints Based Utility Space
Model.In:ACAN(2011) 15. Raiye,T.: Reducing The complexity of negotiations over interdependent issues.In:ACAN(2012)