1、Agent TechnologyNegotiationOutline1. Introduction2. Vote3. Bid4. Bargain5. Summary從田忌賽馬談起田忌賽馬齊王以“上馬、中馬、下馬”出賽；齊王的馬優(yōu)于田忌的馬；每一場(chǎng)勝者贏黃金100兩，負(fù)者輸黃金100兩；田忌以何種次序出馬呢？囚徒困境如果齊王的策略也是變化的？如果從零和擴(kuò)展到非零和？囚徒困境問(wèn)題每個(gè)囚徒如果只考慮自身的利益，則會(huì)選擇坦白行為；而囚徒困境的最優(yōu)策略是雙方都選擇抗拒行為。囚徒困境問(wèn)題的本質(zhì)在多Agent系統(tǒng)中，如果每個(gè)Agent都是自利的（使自身獲利最大），那么每個(gè)Agent的最優(yōu)策略的組合未必是多A

2、gent系統(tǒng)的最優(yōu)策略。多Agent協(xié)商在自利多Agent系統(tǒng)中，通過(guò)協(xié)商獲得最優(yōu)策略。不同于分布式系統(tǒng)，設(shè)計(jì)者無(wú)須為每個(gè)agent指定策略。個(gè)體利益與集體利益沖突的矛盾本質(zhì)究竟什么是最優(yōu)策略？三個(gè)術(shù)語(yǔ)CoordinationIs a property of a system of agents performing some activity in a shared environment.Cooperation (Collaborative)Is coordination among nonantagonistic agents.NegotiationIs coordination amo

3、ng competitive or simply self-interested agents.Distributed rational decision making協(xié)商研究目標(biāo)Classical DAISystem designer fixes an Interaction-Protocol which is uniform for all agents. The designer also fixes a strategy for each agent.MASInteraction-Protocol is given up. Each agent determines its own s

4、trategy (maximizing its own good, via a utility function, without looking at the global task)四條不同準(zhǔn)則We need to compare negotiation protocols. Each such protocol leads to a solution. So we determine how good these solutions are.社會(huì)福利（Social Welfare）: 最大化所有Agent的效益Sum of all utilities.It requires inter-

5、agent utility comparisons.帕利脫最優(yōu)（Pareto Efficiency）帕利脫最優(yōu)（Pareto Efficiency）: 一個(gè)方案x是帕利脫最優(yōu)，當(dāng)且僅當(dāng)不存在另一個(gè)方案 x滿足 A solution x is Pareto-optimal (also called efficient), if there is no solution x withPareto efficiency measures global good, and it does not require questionable inter-agent utility comparisons.

6、Social welfare maximizing solutions are a subset of Pareto efficient ones. (Why?)Answer: Once the sum of the payoffs is maximized, an agents payoff can increase only if another agents payoff decreases.Stability?四條不同準(zhǔn)則（續(xù)）納什均衡（ Nash-equilibrium ）Agent 的策略依賴于其他agent. 如果 S*A= 為納什均衡策略, 當(dāng)且僅當(dāng)對(duì)Agent i： S*i

7、對(duì)于 agent i 是最優(yōu)策略當(dāng)其他Agent選擇以下策略時(shí) Two main problems in applying Nash equilibrium;No Nash equilibrium exists in some games. Multiple Nash equilibria in some games, agents should play which? (See next page)優(yōu)超（ dominant ） Agent 的策略不依賴于其他agent. 這樣的策略稱之為優(yōu)超。無(wú)純Nash均衡解多個(gè)Nash均衡解When bacd不同準(zhǔn)則下囚犯困境的最優(yōu)策略社會(huì)福利: Bot

8、h defect.帕利脫最優(yōu): All are Pareto optimal, except when both cooperate.優(yōu)超策略: Both cooperate.納什均衡: Both cooperate.How to escape from PD?多Agent系統(tǒng)的類型合作多Agent系統(tǒng)典型例：合作推箱子，有共同的目標(biāo)半競(jìng)爭(zhēng)多Agent系統(tǒng)典型例：機(jī)器人行走，有不同的目標(biāo)，但目標(biāo)不沖突競(jìng)爭(zhēng)多Agent系統(tǒng)典型例：下棋，有沖突的目標(biāo)三種協(xié)商機(jī)制投票機(jī)制拍賣機(jī)制談判機(jī)制投票機(jī)制Agents give input to a mechanism and the outcome of i

9、t is taken as a solution for the agents.Motivation: 3 candidates, 3 votersComparing A and B: majority for A. Comparing A and C: majority for C. Comparing B and C: majority for B. Desired Preference ordering: ABCA?Nonexistence of desired preference orderingHow to design this software?投票機(jī)制Let A the se

10、t of agents, O the set of possible outcomes (O could be equal to A, or a set of laws).The voting of agent i is described by a binary relation which we assume to be asymmetric, strict and transitive. We denote by Ordering the set of all such binary relations.投票機(jī)制的六準(zhǔn)則Six properties of a social choice

11、ruleA social preference ordering should exist for all possible inputs (individual preferences) . should be defined for every pair . should be asymmetric and transitive over O.The outcome should be Pareto efficient: The scheme should be independent of irrelevant alternatives.No agent should be a dict

12、ator in the sense that implies for all preferences of the other agents.阿羅定理Arrows impossibility theoremNo social choice rule satisfies all of these six conditions.沒(méi)有任何一種投票機(jī)制是完全公平，民主！Nobel Prize in Economics, 1972 2010年世界杯申辦侯選國(guó)家埃及利比亞摩洛哥尼日利亞南非突尼斯投票方法？多數(shù)投票Plurality protocolA majority voting protocol wh

13、ere all alternatives are compared simultaneously, and the one with the highest number of votes wins.Dont satisfies the irrelevant rule.For example:二叉投票Binary protocolThe alternatives are voted on pairwise, and the winner stays to challenge further alternatives while the loser is eliminated.As in plu

14、rality protocol, couldt satisfy irrelevant rule.Further, the agenda can change the socially chosen outcome.二叉投票（續(xù)）Binary protocol example35% of agents have preferences33% of agents have preferences32% of agents have preferences記分投票Borda protocolThe Borda count assigns an alternative |O| points whene

15、ver it is highest in some agents preference list, |O|-1 whenever it is second and so on.The alternative with the highest count becomes the social choice.Can also lead to paradoxical result, for example via irrelevant alternatives.記分投票（續(xù)）Borda protocol exampleAgentPreferencesa b c d Points1a b c d4 3

16、 2 1 2b c d a1 4 3 2 3c d a b2 1 4 3 4a b c d4 3 2 1 5b c d d1 4 3 2 6c d a b2 1 4 3 7a b c d4 3 2 1 Borda countC wins with 20, b has 19, a has 18, d loses with 13Borda count with d removedA wins with 15, b has 14, c loses with 13不誠(chéng)實(shí)投票How to design a social choice mechanisms in insincere voting?But

17、if an agent can benefit from insincerely declaring his preferences, he will do so.投票的對(duì)策論分析效用首先構(gòu)造每個(gè)Agent關(guān)于選民的序結(jié)構(gòu)；通過(guò)函數(shù)給出序的值（在0，1之間）；定義損失函數(shù)dj(oi)=（在方案中oi與agent j理想分配之間的歐氏距離）。方案比較重心模型Pareto模型基于Game theory的理論分析拍賣機(jī)制In voting, the protocol designer is assumed to want to enhance the social good.While in auc

18、tions, the auctioneer wants to maximize his own profit.The auctioneer wants to sell an item and get the highest possible payment for it.The bidders wants to acquire the item at the lowest possible price.拍賣機(jī)制的環(huán)境設(shè)置Private valueThe value of the good depends only on the agents own preferences.The key is

19、 that the winning bidder will not resell the item in order to get utility.For example: auctioning off a cake.In other words, value depends only on the bidder.拍賣機(jī)制的環(huán)境設(shè)置（續(xù)）Common valueAn agents value of an item depends entirely on other agents values of it.For example: auctioning treasury bills.In oth

20、er words: value depends only on other bidders.拍賣機(jī)制的環(huán)境設(shè)置（續(xù)）Correlated valueAn agents value depends partly on its own preferences and partly on others values.For example: a negotiation within a contracting setting.An agent decreases the cost of task.An agent can recontract out the task.In other words,

21、 partly on owns value, partly on others.英格蘭拍賣English (first-price open-cry)Each bidder is free to raise his bid. When no bidder is willing to raise anymore, the auction ends, and the highest bidder wins the item.An agents strategyIs a series of bids as a function of his private value, his prior esti

22、mates of other bidders valuations, the past bids of others.英格蘭拍賣（續(xù)）In private value English auctionsAn agents dominant strategy is to always bid a small more than the current highest bid, and stop when his private value price is reached.In correlated value auctionsThe rules are often varied to make

23、the auctioneer increase the price at a constant rate or at a rate he thinks appropriate.密封拍賣First-price sealed-bid auctionEach bidder submits one bid without knowing the others bids. The highest bidder wins the item.An agents strategyas a function of his private value, his prior estimates of other b

24、idders valuations.No dominant strategy for bidding in this auction.Best strategyIs to bid less than his true valuation, but how much less depends on what the others bid.密封拍賣In private value auction(Common knowledge assumptions) The probability distributions such as uniform distribution of the agents

25、 value.Nash equilibrium for every agent i is 荷蘭式拍賣Dutch (descending) auctionThe seller continuously lowers the price until one of the bidders takes the item at the current price.An agents strategyThe Dutch auction is strategically equivalent to the first-price sealed-bid auction.Vickery拍賣Vickrey (se

26、cond-price sealed-bid) auctionEach bidder submits one bid without knowing the others bids. The highest bidder wins, but at the price of the second highest bid.An agents strategyas a function of his private value, his prior estimates of other bidders valuations.TheoremA bidders dominant strategy in a

27、 private value Vickrey auction is to bid his true valuation.Vickery拍賣（續(xù)）Vickrey auctions are used toAllocate computation resources in operation systems,Allocate bandwith in computer networks,Control building heating.Vickery拍賣（續(xù)）Are first-price auctions better for the auctioneer than second-price auc

28、tions?Theorem: All 4 types of protocol produce the same expected revenue to the auctioneer (assuming (1) private value auctions, (2) values are independently distributed and (3) bidders are risk-neutral).Why are second prices not so popular among humans?Lying auctioneer.When the result are published

29、, subcontractors know the true valuations and what they saved. So they might want to share the profit. 拍賣的對(duì)策論分析拍賣的對(duì)策假定、要素和過(guò)程分析拍賣的對(duì)策理論假定拍賣是具有不完全信息的非合作對(duì)策Agent I對(duì)其他Agent私有價(jià)值的主觀概率Agent的決策是獨(dú)立作出的，不存在協(xié)議。拍賣的對(duì)策論分析（續(xù)）拍賣的要素效用函數(shù)：用vi表示第i個(gè)Agent對(duì)拍賣品的私人價(jià)值，而bi為報(bào)價(jià)。則效用值為未獲得標(biāo)的 ui=0獲得標(biāo)的預(yù)期所獲支付 拍賣的對(duì)策論分析（續(xù)）拍賣的過(guò)程分析如果是n個(gè)Agen

30、t，則為（n-1）v/n。因此招標(biāo)中對(duì)拍賣者來(lái)講，投標(biāo)人數(shù)越多越有利。相關(guān)資源的拍賣Inefficient Allocation and Lying in Interrelated AuctionsExtended Auctioningauction of multiple items of a homogeneous good,auction of heterogeneous irrelated goods,auction of heterogeneous interrelated goods.相關(guān)資源的拍賣（續(xù)）Example (Task Allocation)Two delivery t

31、asks t1, t2, two agents 1, 2,c1(t1)=2c1(t2)=1c1(t1,t2)=2c2(t1)=1.5c2(t2)=1.5c2(t1,t2)=2.5相關(guān)資源的拍賣（續(xù)）The global optimal solution is not reached by auctioning independently and truthful bidding.t1 goes to agent 2 (for a price of 1.5) and t2 goes to agent 1 (for a price of 1).Even if agent 2 considers (

32、when bidding for t2) that he already got t1 (so he bids cost(t1,t2)-cost(t1)=2.5-1.5=1) he will get it only with a probability of 0.5.相關(guān)資源的拍賣（續(xù)）What about full lookahead?Therefore:It pays off for agent 1 to bid more for t1 (up to 1.5 more than truthful bidding).It does not pay off for agent 2, becau

33、se agent 2 does not make a profit at t2 anyway.Agent 1 bids 0.5 for t1 (instead of 2), agent 2 bids 1.5. Therefore agent 1 gets it for 1.5. Agent 1 also gets t2 for 1.5.相關(guān)資源的拍賣（續(xù)）If a1 have t1, c1(t1,t2)-c1(t1)=2-2=0. else c1(t2)=1If a2 have t1, c2(t1,t2)-c2(t1)=2.5-1.5=1 else c2(t2)=1.5So when a1 h

34、ave t1, it bids t2 will get extra profit 1.5-0=1.5 when a2 have t1, it bids t2 will get extra profit 1-1=0So when a1 bids t1, it will bid c1(t1)-extra profit=2-1.5=0.5 when a2 bids t1, it will bid c2(t1)-extra profit=1.5-0=1.5A1 wins!拍賣中的調(diào)查Does it make sense to counterspeculate at private value Vick

35、ery auctions?Vickery auctions were invented to avoid counterspeculation. But what if the private value for a bidder is uncertain? The bidder might be able to determine it, but he needs to invest c.ExampleSuppose bidder 1 does not know the (private-) value v1 of the item to be auctioned. To determine

36、 it, he need to invest cost. We also assume that v1 is uniformly distributed: satisfies 0 = v1 = 1.拍賣中的調(diào)查（續(xù)）For bidder 2, the private value v2 of the item is fixed: 0 =v2 R. if the agents do not agree on the result o the fallback ofallback is tacken. Example (Sharing 1 apple)How to share 1 apple?Age

37、nt 1 offers p (0 p 1), agent 2 agrees!Such deals are individually rational and each one is in Nash-equilibrium! Therefore we need axioms!公理談判理論Axioms on the global solutions u*=.Invariance: Absolute values of the utility functions do not matter, only relative values.Symmetry: Changing the agents doe

38、s not influence the solution o*.Irrelevant Alternatives: If O is made smaller but o* still remains, then o* remains the solution.Pareto: The players can not get the higher utility than u*=.可行解的說(shuō)明公理談判理論的解Theorem (Unique solution)The four axioms above uniquely determine a solution. This solution is gi

39、ven by策略談判理論No axioms: view it as a game!Example revisited: Sharing 1 apple.Protocol with finitely many steps: The last offerer just offers e, This should be accepted, so the last offerer gets 1-e.This is unsatisfiable. Ways out:1. Add a discountfactor : in round n, only the n-1th part of the original value is available.2. Bargaining costs: bargaining is not for free fees have to be paid.策略談判理論（續(xù)）Strategic Bargaining TheoryFinite Games: Suppose =0.9. Then the outcome depends on # rounds.RoundIs share2s shareTot