Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 477-1LECTURE 7: Reaching AgreementsAn Introduction to MultiAgent Systemshttp://www.csc.liv.ac.uk/~mjw/pubs/imas7-2Reaching AgreementsHow do agents reaching agreements when they are self interested?In an extreme case (zero sum encounter) no agreement is possible — but in most scenarios, there is potential for mutually beneficial agreement on matters of common interestThe capabilities of negotiation and argumentation are central to the ability of an agent to reach such agreements7-3Mechanisms, Protocols, and StrategiesNegotiation is governed by a particular mechanism, or protocolThe mechanism defines the “rules of encounter” between agentsMechanism design is designing mechanisms so that they have certain desirable propertiesGiven a particular protocol, how can a particular strategy be designed that individual agents can use?7-4Mechanism DesignDesirable properties of mechanisms:Convergence/guaranteed successMaximizing social welfarePareto efficiencyIndividual rationalityStabilitySimplicityDistribution7-5AuctionsAn auction takes place between an agent known as the auctioneer and a collection of agents known as the biddersThe goal of the auction is for the auctioneer to allocate the good to one of the biddersIn most settings the auctioneer desires to maximize the price; bidders desire to minimize price7-6Auction ParametersGoods can haveprivate valuepublic/common valuecorrelated valueWinner determination may befirst pricesecond priceBids may beopen crysealed bidBidding may beone shotascendingdescending7-7English AuctionsMost commonly known type of auction:first priceopen cryascendingDominant strategy is for agent to successively bid a small amount more than the current highest bid until it reaches their valuation, then withdrawSusceptible to:winner’s curseshills7-8Dutch AuctionsDutch auctions are examples of open-cry descending auctions:auctioneer starts by offering good at artificially high valueauctioneer lowers offer price until some agent makes a bid equal to the current offer pricethe good is then allocated to the agent that made the offer7-9First-Price Sealed-Bid AuctionsFirst-price sealed-bid auctions are one-shot auctions:there is a single roundbidders submit a sealed bid for the goodgood is allocated to agent that made highest bidwinner pays price of highest bidBest strategy is to bid less than true valuation7-10Vickrey AuctionsVickrey auctions are:second-pricesealed-bidGood is awarded to the agent that made the highest bid; at the price of the second highest bidBidding to your true valuation is dominant strategy in Vickrey auctionsVickrey auctions susceptible to antisocial behavior7-11Lies and CollusionThe various auction protocols are susceptible to lying on the part of the auctioneer, and collusion among bidders, to varying degreesAll four auctions (English, Dutch, First-Price Sealed Bid, Vickrey) can be manipulated by bidder collusionA dishonest auctioneer can exploit the Vickrey auction by lying about the 2nd-highest bidShills can be introduced to inflate bidding prices in English auctions7-12NegotiationAuctions are only concerned with the allocation of goods: richer techniques for reaching agreements are requiredNegotiation is the process of reaching agreements on matters of common interestAny negotiation setting will have four components:A negotiation set: possible proposals that agents can makeA protocolStrategies, one for each agent, which are privateA rule that determines when a deal has been struck and what the agreement deal isNegotiation usually proceeds in a series of rounds, with every agent making a proposal at every round7-13Negotiation in Task-Oriented DomainsImagine that you have three children, each of whom needs to be delivered to a different school each morning. Your neighbor has four children, and also needs to take them to school. Delivery of each child can be modeled as an indivisible task. You and your neighbor can discuss the situation, and come to an agreement that it is better for both of you (for example, by carrying the other’s child to a shared destination, saving him the trip). There is no concern about being able to achieve your task by yourself. The worst that can happen is that you and your neighbor won’t come to an agreement about setting up a car pool, in which case you are no worse off than if you were alone. You can only benefit (or do no worse) from your neighbor’s tasks. Assume, though, that one of my children and one of my neighbors’ children both go to the same school (that is, the cost of carrying out these two deliveries, or two tasks, is the same as the cost of carrying out one of them). It obviously makes sense for both children to be taken together, and only my neighbor or I will need to make the trip to carry out both tasks.--- Rules of Encounter, Rosenschein and Zlotkin, 19947-14Machines Controlling and Sharing ResourcesElectrical grids (load balancing)Telecommunications networks (routing)PDA’s (schedulers)Shared databases (intelligent access)Traffic control (coordination)7-15Heterogeneous, Self-motivated AgentsThe systems:are not centrally designeddo not have a notion of global utilityare dynamic (e.g., new types of agents)will not act “benevolently” unless it is in their interest to do so7-16Mechanism designSocial engineering for communities of machinesThe creation of interaction environments that foster certain kinds of social behaviorThe exploitation of game theory tools for high-level protocol designThe exploitation of game theory tools for high-level protocol design7-17Broad Working AssumptionDesigners (from different companies, countries, etc.) come together to agree on standards for how their automated agents will interact (in a given domain)Discuss various possibilities and their tradeoffs, and agree on protocols, strategies, and social laws to be implemented in their machines7-18Attributes of
View Full Document
Unlocking...