ExperimentReport_Group6.pdf

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 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 the 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 negotiation 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 negotiating 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 agents 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 receive 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 importance 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,the 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 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 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 agents 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 can 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 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 interactions 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 literature.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 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 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 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 example 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 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 when 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 Space.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 Utility 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,completely 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 sum 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 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 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 reservation 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 typically 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 overall 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 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 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 computational 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 discount 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,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 factor.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 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 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“optimum”.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 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 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 protocolprotocol 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 not 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 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 round 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 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 Alternating 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 next 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 any)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