1、 Group6 Report 付悦付悦 20182180282018218028 刘磊磊刘磊磊 20182180532018218053 郭健郭健 20182180332018218033 韩晓旭韩晓旭 21182180052118218005 目录 Chapter1 Background.3 Chapter2 introduction.6 2.1 concepts.6 2.2 protocol.13 Chapter3 Strategy.18 Chapter 4 testing result.19 Chapter1 Background Negotiation is a common and
2、important approach to resolve conflicts and reach agreements between different parties in our daily life.The topic of negotiation has been widely studied in various areas,such as decision and game theory,economics,and social science.Automated negotiation techniques can,to a large extent,alleviate th
3、e efforts of human and also facilitate human in reaching better negotiation outcomes by compensating for the limited computational abilities of humans when they are faced with complex negotiations.Until now,a lot of automated negotiation strategies and mechanisms have been proposed in different nego
4、tiation scenarios.The negotiation partner usually keeps its negotiation strategy and its preference as its private information to avoid exploitations.The major difficulty in designing automated negotiation agent is how to achieve optimal negotiation results given incomplete information on the negoti
5、ating partner.A lot of research efforts have been devoted to better understand the negotiation partner by either estimating.the negotiation partners preference profile or predicting its decision function.On one hand,with the aid of different preference profile modeling techniques,the negotiating age
6、nts can get a better understanding of their negotiating partners and thus increase their chances of reaching mutually beneficial negotiation outcomes.On the other hand,effective strategy prediction techniques enable the negotiating agents to maximally exploit their negotiating partners and thus rece
7、ive as much benefit as possible from negotiation.The simplest negotiation takes place between two agents on a single issue,such as price.Two agents interact to settle on a value for that single issue.The more complex negotiations take place over multiple issues.In a multi-issue negotiation the impor
8、tance of the issues may vary for the participants.One agent may consider a particular issue more important whereas the other agent may take another issue into account.However,in a multi-issue negotiation,it is possible to have trade-offs between issues,making consensus more plausible.For instance,th
9、e delivery time may be the main concern for a particular consumer whereas the price of the service may be more important for the producer.If the consumer pays more for fast delivery,both agents are at an advantage as far as their preferences are concerned.Meanwhile,when there is more than one issue
10、to be considered,the search space for the acceptable agreements increases,which complicates the entire negotiation process.When agents are given a large search space,an important challenge is to find ways to generate requests or counter offers.This is determined by the agents negotiation strategy.A
11、good negotiation strategy should not only consider the agents own utility but the utility of the opponent as well.Otherwise,no matter how good the generated offer is for the agent,it will not be accepted by the other agent.To find an agreement,which is mutually beneficial for both participants,the a
12、gents need to have sufficient knowledge about the negotiation domain and to take the other agents preferences into account.However,preferences of participants are almost always private and hence cannot be accessed by others.If the agent shares its preferences with the other agent,this information ca
13、n be exploited by the opponent agent.For example,if the producer knows that the buyer can pay up to 100 USD for the service,it may not offer a price lower than 100 USD,although it can possibly afford to provide the service for 80 USD.As a result,this negotiation will end up with a lower gain for the
14、 buyer.Thus,the agent may not prefer to reveal its preferences completely.Alternatively,the preferences of the agents may be complicated.Because of the communication cost,these preferences may not be shared.The best that can happen is that participants may learn each others preferences through inter
15、actions over time.In our experiments,we design a negotiation strategy for automated agents to negotiate in bilateral multi-issue negotiation environments in GENIUS platform.Bilateral multi-issue negotiations surround peoples daily life and have received lots of attention in the negotiation literatur
16、e.During negotiation,both the agents negotiation strategies and preference profiles are their private information,and for each agent the only available information about the negotiating partner is its past negotiation moves.Chapter2 introduction 2.12.1 conceptsconcepts (1)Domain The Domain describes
17、 which issues are the subject of the negotiation and which values an issue can attain.A domain contains n issues:D=(I1,.,In).Each issue i consists of k values:I=(1,.,).Combining these concepts,a party can formulate a Bid:a mapping from each issue to a chosen value(denoted by c),b=(,.,).Generally,we
18、assume that the knowledge of the negotiation domain is known to both agents beforehand and is not changed during the whole negotiation session.To give an example,in the laptop domain the issues are“laptop”,“hard disk”and“monitor”.In this domain the issues can only attain discrete values,e.g.the“hard
19、 disk”issue can only have the values“60Gb”,“80Gb”and“120Gb”.These issues are all instance of IssueDiscrete.A valid bid in the laptop domain is e.g.Laptop:Dell,Hard disk:80Gb,monitor:17.A bid Laptop Asus,Hard disk:80Gb,monitor:17 is not a valid bid because Asus is not a valid issue value in the examp
20、le domain,and Laptop Asus,Hard disk:80Gb,CPU:i7 is not valid because CPU is not an issue in this domain.(2)Bid Parties participating in a negotiation interact in a domain.The domain specifies the possible bids.The parties all have their own preferences,which is reflected in their profile.A bid price
21、 is the highest price that a buyer(i.e.,bidder)is willing to pay for a good.It is usually referred to simply as the bid.In bid and ask,the bid price stands in contrast to the ask price or offer,and the difference between the two is called the bidask spread.An unsolicited bid or purchase offer is whe
22、n a person or company receives a bid even though they are not looking to sell.(3)Preference file The Preference Profile describes how bids are preferred over other bids.Typically,each participant in a negotiation has his own preference profile.(4)Utility space One form of profile is the Utility Spac
23、e.The Utility Space specifies the preferences using an evaluator:a function that maps bids into a real number in the range 0,1 where 0 is the minimum utility and 1 is the maximum utility of a bid.So a bid is preferred if and only if it has a higher utility than another bid.A common form of the Utili
24、ty space is the Linear Additive Utility Space.This space is additive because each of the issue values in the domain have their own utility of their own,and all the sub-utilities just add up for the total utility of the bid.For instance,we like Apple with utility evaluation 0.7 and Dell with 0.4,comp
25、letely independent of how much memory the computer has.In an additive space the evaluator also specifies the importance of the issue relative to the other issues in the form of a weight.The weights of all issues sum up to 1.0 to simplify calculating the utility of a bid.The utility is the weighted s
26、um of the scaled evaluation values.(5)Partially ordered profile The UncertainAdditiveUtilitySpace is a profile type uses partially ordering(instead of assigning a utility value to bids).In a partial ordering,the available information is that bid X is preferred over bid Y for a subset of the possible
27、 bids.The generation of the partial ordering works as follows.The values comparisons,errors and experimental are additional parameters of the UncertainAdditiveUtilitySpace that control the generation.1.a subset of comparisons bids are selected randomly from all possible bids.2.the selected bids are
28、sorted in ascending utility (6)Reservation value A reservation value is a real-valued constant that sets a threshold below which a rational party should not accept any offers.Intuitively,a reservation value is the utility associated with the Best Alternative to a Negotiated Agreement(BATNA).A reserv
29、ation value is the minimum acceptable utility,offers with a utility would normally not be accepted by a party.For example,for a seller,this means the minimum amount they would be prepared to accept,while for a buyer it would mean the maximum that they would be prepared to pay.Reservation values typi
30、cally differ for each negotiation party.In case no reservation value is set in a profile,it is assumed to be 0.Notice that if a negotiation ends with no agreement,parties normally get a utility of 0,regardless of the reservation value.(7)Negotiation Protocol The negotiation protocol determines the o
31、verall order of actions during a negotiation.Parties are obliged to stick to this protocol,as deviations from the protocol are caught and penalized.Genius supports multiple protocols.(8)Time pressure A negotiation lasts a predefined time in seconds,or alternatively rounds.In Genius the time line is
32、normalized,i.e.:time t 0,1,where t=0 represents the start of the negotiation and t=1 represents the deadline.Notice that manipulation of the remaining time can be a factor influencing the outcome of the remaining time can be a factor influencing the outcome.There is an important difference between a
33、 time-based and rounds-based protocol.In a time-based protocol the computational cost of an party should be taken into account as it directly influences the amount of bids which canbe made.In contrast,for a rounds-based negotiation the time can be thought of as paused within a round;therefore comput
34、ational cost does not play a role.Apart from a deadline,a scenario may also feature discount factors.Discount factors decrease the utility of the bids under negotiation as time passes.While time is shared between both parties,the discount generally differs per party.The default implementation of dis
35、count factors is as follows:let d in 0,1 be the discount factor that is specifies in the preference profile of a party;let t in 0,1 be the current normalized time,as defined by the timeline;we compute the discounted utility Ut of an outcome from the undiscounted utility function U as follows:If d=1,
36、the utility is not affected by time,and such a scenario is considered to be undiscounted,while if d is very small there is high pressure on the parties to reach an agreement.Note that discount factors are part of the preference profiles and therefore different parties may have a different discount f
37、actor.If a discount factor is present,reservation values will be discounted in exactly the same way as the utility of any other outcome.It is worth noting that,by having a discounted reservation value,it may be rational for parties to end the negotiation early and thereby default to the reservation
38、value.(9)Optimality of a Bid In general,given the set of all bids,there are a small subset of bids which are more preferred as outcomes by all parties in the negotiation.Identifying these special bids may lead to a better agreement for both parties.For a single party,the optimal bid is the bid that
39、is most preferred/has maximum utility.Often this bid is not preferred so much/has a low utility for other parties,and therefore the chance of agreement is low.A more general notion of optimality of a negotiation involves the utility of all parties.There are multiple ways to define a more global“opti
40、mum”.One approach to optimality is that a bid is not optimal for both parties if there is another bid that has the higher utility for one party,and at least equal utility for the other party.Thus,only bids in the following picture for which there is no other bid at the top right is optimal.This type
41、 of optimality is called Pareto optimality and forms an important concept in automated negotiation.The collection of Pareto optimal bids is called the Pareto optimal frontier.A major challenge in a negotiation is that parties can hide their preferences.This entails that an party does not know which
42、bid the opponent prefers given a set of bids.This problem can be partly resolved by building an opponent model of the opponents preferences by analyzing the negotiation trace.Each turn the party can now offer the best bid for the opponent given a set of similar preferred bids.2 2.2.2 protocolprotoco
43、l The protocol determines the overall order of actions during a negotiation.This section focuses on the MultiParty protocols as these have been properly developed.There is also a protocol class for the bilateral negotiation,but this is basically a hard coded Stacked Alternating Offers Protocol and n
44、ot further developed.The(Multilateral)protocol describes if the negotiation is finished,what the agreement is,which actions can be done in the next round.Briefly,to run a session the system checks with the protocol if the negotiation is already finished,and if not which calls need to be made to the
45、parties(both chooseAction and receiveMessage).We recommend checking the javadoc of MultilateralProtocol for up-to-date detail information and how the protocol is used by the system to run sessions.The Multilateral protocol uses the notion of rounds and turns to describe the negotiation layout.A roun
46、d is a part of the negotiation where all participants get a turn to respond to the current state of the negotiation.A turn refers to the opportunity of one party to make a response to the current state of the negotiation.If a party violates the protocol-for instance by sending an action that is not
47、one of the allowed ones,or by crashing,the negotiation ends and the outcome usually is no agreement for all parties.In bilateral negotiation we have a special case then:the partys utility is set to its reservation value,whereas the opponent is awarded the utility of the last offer.2.2.1 Stacked Alte
48、rnating Offers Protocol According to this protocol,all of the participants around the table get a turn per round.Turns are taken clockwise around the table.One of the negotiating parties starts the negotiation with an offer that is observed by all others immediately.Whenever an offer is made,the nex
49、t party in line gets a call to receiveMessage containing the bid,followed by a call to chooseAction from which it can return the following actions:Accept the offer(not available the very first turn).send an Offer to make a counter offer(thus rejecting and overriding the previous offer,if there was a
50、ny)send an EndNegotiation and ending the negotiation without any agreement.2.2.2 Alternating Multiple Offers Protocol According to this protocol,all parties have a bid from all parties available to them,before they vote on these bids.This implemented in the following way:The protocol has a bidding p