2多主体系统中的协商（续） 多主体系统 基础与应用 中山大学逻辑与认知研究所

1、第九章 多主体系统中的协商（续）,1,中山大学逻辑与认知研究所,本次课程主要参考资料,Vidal： Fundamentals of Multiagent System， 第六，七章 Yoav Kevin, Leyton-Brown: Multiagent Systems-Algorithmic, Game-Theoretic, and Logical Foundations, 第 十一章 Wooldridge ：多agent系统引论，第七章 其他：蒙特和塞拉：博弈论与经济学，第五章,3,支付转移将一个交易可以转换为无穷个交易 爬山法的局限！ 转移支付可以可以帮助达到功利主义解；,4,能否达到功

2、利主义解取决于成本函数的形式， 在成本可加函数形式下可以获得。,可加成本函数易于分析,更正式的：,定理：如果成本函数式可加性的任务分配问题，且一次仅允许交换一个任务，任何允许支付转移的并总是使得交易转移到占优交易的协议都会逐步收敛到功利主义的解。,5,成本可加函数的支付转移,引入支付转移后，可以达到功利主义解,新产生的交易用平行线表示,6,灵活的交易语言OCSM，允许所有可能组合的任务转移 引入了更多的复杂性；,如果成本函数是任意的，则没有一般性的结论； 如果任意交易之间可以直接到达（全连接），爬山法同样会达到功利主义解。,任意成本函数,7,对任务撒谎,可能的撒谎： 不告诉其他人我拥有的任务

3、制造一些任务并且希望最后我能被分配去执行这些任务 制造一些任务并在需要的时候产生他们 假设指导最后的交易，如NASH讨价还价解。,8,如果没有t2，nash讨价还价解是 ， i的收益为1； 如果加入任务t2，解是 , i的收益为2.,9,如何面对违约？,杠杆承诺协议,初始点是交易点0。Agent j 发现如果把任务交给i，其收益为4. 因此如果在交易点1，Agent i支付j2，可以到达交易点2. 这时二者的收益均为3，帕累托改进。 危险是：干活不给钱或给钱不干活！ 解决：杠杆曾诺契约，毁约的话要支付罚金；如罚金是1； 这时如果违约的话，将不在交易点1,3 ，而是在交易点4,5.这样有效的降低

4、了风险； 罚金提高了系统的效率和交易的改善。,11,试探性契约,罚金降低了风险 但是：如果我们能够强制执行罚金，为何不强制执行最初的契约？,契约罚金,12,和多个agent协商-协商网络,13,14,威胁：,15,分钱：,16,根据实验结果，NET告知每个人对钱的分配方案的抵制用 衡量抵制函数：,17,18,19,20,21,22,23,仅在小网络上测试过 多个均衡 协商过程可能不会停止下来 仍然是一个可行的描述性解决方案,Auctions,第十章 MAS 中的资源分配机制-拍卖,中山大学逻辑与认知研究所,主要,Auctions Valuations,拍卖简介和标的估值 简单拍卖类型和分析 组

5、合拍卖 集中式的胜标决定 分布式的胜标决定 投标语言,主要内容,Auctions Valuations,拍卖简介,Auctions Valuations,拍卖简介,Auctions,Valuations,估值,Private value.,Common value. Correlated value.,私有价值 公共价值 关联价值,私有价值 公共价值 关联价值,Private value. Common value. Correlated value.,Auctions Valuations What type of value? Non-transferable tickets to a,c

6、oncert. Private Tickets to a concert. Correlated Collectible stamp. Common or Correlated,私有价值 公共价值 关联价值,估值,主要,Auctions Valuations,拍卖简介和标的估值 简单拍卖分析 组合拍卖 集中式的胜标决定 分布式的胜标决定 投标语言,主要内容,Canonical Single-Good Auctions,Comparing Auctions,拍卖：有结构的一种的协商 Any negotiation mechanism that is: market-based (determin

7、es an exchange in terms of currency) mediated (auctioneer) well-specied (follows rules) Dened by three kinds of rules: rules for bidding rules for what information is revealed rules for clearing,Canonical Single-Good Auctions 拍卖：有结构的一种的协商 Dened by three kinds of rules: rules for bidding who can bid,

8、 when what is the form of a bid restrictions on oers, as a function of: bidders own previous bid auction state (others bids) eligibility (e.g., budget constraints) expiration, withdrawal, replacement rules for what information is revealed rules for clearing Kevin Leyton-Brown,Comparing Auctions,Cano

9、nical Single-Good Auctions 拍卖：有结构的一种的协商 Dened by three kinds of rules: rules for bidding rules for what information is revealed when to reveal what information to whom rules for clearing,Canonical Single-Good Auctions 拍卖：有结构的一种的协商 Dened by three kinds of rules: rules for bidding rules for what infor

10、mation is revealed rules for clearing when to clear at intervals on each bid after a period of inactivity allocation (who gets what) payment (who pays what) Kevin Leyton-Brown,Comparing Auctions Canonical Single-Good Auctions,English Japanese Dutch First-Price Second-Price All-Pay,Auctions,Simple Au

11、ctions,常见简单拍卖类型,auctioneer starts the bidding at some “reservation price” bidders then shout out ascending prices once bidders stop shouting, the high bidder gets the good at that price,Auctions,Simple Auctions,English Auction,First-price open-cry ascending auction. Very common.,Initial prices is th

12、e reservation price.,Dominant strategy: bid current price plus epsilon until reservation price.,Winners curse if common or correlated.,Auctions,Simple Auctions,First-price Sealed-bid Auction,One bid per person in a sealed envelope are given to the auctioneer who then picks the highest bid.,Whoever s

13、ubmitted the highest bit wins and pays that price. It has no dominant strategy. Leads to spying.,Auctions,Simple Auctions,Dutch Auction,Ontario,Flower Growers Co-op.,Open-cry descending price. Equivalent to rst-price sealed-bid auction. Real-time ecient.,First-Price First-Price and Dutch Theorem Fir

14、st-Price and Dutch auctions are strategically equivalent. In both rst-price and Dutch, a bidder must decide on the amount hes willing to pay, conditional on having placed the highest bid. despite the fact that Dutch auctions are extensive-form games, the only thing a winning bidder knows about the o

15、thers is that all of them have decided on lower bids e.g., he does not know what these bids are this is exactly the thing that a bidder in a rst-price auction assumes when placing his bid anyway. Note that this is a stronger result than the connection between second-price and English.,First-Price Di

16、scussion So, why are both auction types held in practice? First-price auctions can be held asynchronously Dutch auctions are fast, and require minimal communication: only one bit needs to be transmitted from the bidders to the auctioneer. How should bidders bid in these auctions?,First-Price Discuss

17、ion So, why are both auction types held in practice? First-price auctions can be held asynchronously Dutch auctions are fast, and require minimal communication: only one bit needs to be transmitted from the bidders to the auctioneer. How should bidders bid in these auctions? They should clearly bid

18、less than their valuations. Theres a tradeo between: probability of winning amount paid upon winning Bidders dont have a dominant strategy any more.,Auctions,Simple Auctions,Vickrey Auction,William Vickrey.,19141996.,Nobel Prize in,Economics, 1996.,Second-price sealed-bid.,Bidding true valuation is

19、dominant strategy if private value. Eliminates strategizing. People dont like them.,bidders write down bids on pieces of paper auctioneer awards the good to the bidder with the highest bid that bidder pays the amount bid by the second-highest bidder,Second-Price Second-Price proof Theorem Truth-tell

20、ing is a dominant strategy in a second-price auction. Proof. Assume that the other bidders bid in some arbitrary way. We must show that is best response is always to bid truthfully. Well break the proof into two cases:,1 2,Bidding honestly, i would win the auction Bidding honestly, i would lose the

21、auction,Kevin Leyton-Brown,Second-Price Auctions, Slide 2,next-highest bid,is bid,Second-Price Second-Price proof (2) is true value i pays,Bidding honestly, i is the winner,Kevin Leyton-Brown,Second-Price Auctions, Slide 3,Second-Price Second-Price proof (2),next-highest bid,is bid,is true value i p

22、ays,next-highest bid,is bid,is true value i pays,Bidding honestly, i is the winner If i bids higher, he will still win and still pay the same amount,Kevin Leyton-Brown,Second-Price Auctions, Slide 3,Second-Price Second-Price proof (2),next-highest bid,is bid,is true value i pays,next-highest bid,is

23、bid,is true value i pays,next-highest bid,is bid,is true value i pays,Bidding honestly, i is the winner If i bids higher, he will still win and still pay the same amount If i bids lower, he will either still win and still pay the same amount.,Kevin Leyton-Brown,Second-Price Auctions, Slide 3,Second-

24、Price Second-Price proof (2),next-highest bid,is bid,is true value i pays,next-highest bid,is bid,is true value i pays,next-highest bid,is bid,is true value i pays,highest bid,is bid,winner pays,is true value,Bidding honestly, i is the winner If i bids higher, he will still win and still pay the sam

25、e amount If i bids lower, he will either still win and still pay the same amount.or lose and get utility of zero.,Kevin Leyton-Brown,Second-Price Auctions, Slide 3,highest bid,is bid,Second-Price Second-Price proof (3) is true value,Bidding honestly, i is not the winner,Kevin Leyton-Brown,Second-Pri

26、ce Auctions, Slide 4,Second-Price Second-Price proof (3),highest bid,is bid,is true value,highest bid,is bid,is true value,Bidding honestly, i is not the winner If i bids lower, he will still lose and still pay nothing,Kevin Leyton-Brown,Second-Price Auctions, Slide 4,Second-Price Second-Price proof

27、 (3),highest bid,is bid,is true value,highest bid,is bid,is true value,highest bid,is bid,is true value,Bidding honestly, i is not the winner If i bids lower, he will still lose and still pay nothing If i bids higher, he will either still lose and still pay nothing.,Kevin Leyton-Brown,Second-Price A

28、uctions, Slide 4,highest bid,is bid,is true value,highest bid,is bid,is true value,highest bid,is bid,is true value,next-highest bid,is bid,Second-Price Second-Price proof (3) i pays,is true value,Bidding honestly, i is not the winner If i bids lower, he will still lose and still pay nothing If i bi

29、ds higher, he will either still lose and still pay nothing.or win and pay more than his valuation.,Kevin Leyton-Brown,Second-Price Auctions, Slide 4,1,2,3,4,5,Sell,Auctions Simple Auctions Double Auction Sell,Sell,Sell,Sell,Buy Buy Buy Buy Buy,Auctions,Simple Auctions,Analysis of Auctions,Revenue Eq

30、uivalence,On which auction do sellers make more money?,Revenue Equivalence Revenue Equivalence Which auction should an auctioneer choose? To some extent, it doesnt matter. Theorem (Revenue Equivalence Theorem) Assume that each of n risk-neutral agents has an independent private valuation for a singl

31、e good at auction, drawn from a common cumulative distribution F(v) that is strictly increasing and atomless on v,v . Then any auction mechanism in which the good will be allocated to the agent with the highest valuation; and any agent with valuation v has an expected utility of zero; yields the sam

32、e expected revenue, and hence results in any bidder with valuation v making the same expected payment.,Kevin Leyton-Brown,Revenue Equivalence, Slide 1,Revenue Equivalence Revenue Equivalence Proof Proof. Consider any mechanism (direct or indirect) for allocating the good. Let ui(vi) be is expected u

33、tility given true valuation vi, assuming that all agents including i follow their equilibrium strategies. Let Pi(vi) be is probability of being awarded the good given (a) that his true type is vi; (b) that he follows the equilibrium strategy for an agent with type vi; and (c) that all other agents f

34、ollow their equilibrium strategies.,ui(vi) = viPi(vi) Epayment by type vi of player i,(1),From the denition of equilibrium, for any other valuation v i that i could have,ui(vi) ui(v i) + (vi v i)Pi(v i).,(2),To understand Equation (2), observe that if i followed the equilibrium strategy for a player

35、 with valuation v i rather than for a player with his (true) valuation vi, i would make all the same payments and would win the good with the same probability as an agent with valuation v i. However, whenever he wins the good, i values it (vi v i) more than an agent of type v i does. The inequality

36、must hold because in equilibrium this deviation must be unprotable.,Kevin Leyton-Brown,Revenue Equivalence, Slide 2,Revenue Equivalence Revenue Equivalence Proof,Revenue Equivalence Revenue Equivalence Proof,Auctions,Simple Auctions,Analysis of Auctions,Revenue Equivalence,On which auction do seller

37、s make more money?,Revenue Equivalence Theorem,All four auctions produce the same expected revenue in private value auctions and with bidders that are risk-neutral.,If risk-averse then Dutch and First-price are better.,In common or correlated value English gives higher revenue.,Auctions,Simple Aucti

38、ons,Analysis of Auctions,Collusion,Bidder collusion aects all 4 auctions.,English and Vickrey auctions self-enforce collusion agreements.,Auctions,Simple Auctions,Analysis of Auctions,Lying,A lying auctioneer can make money from a Vickrey auction. He can also place shills in an English auction.,Auct

39、ions Simple Auctions Analysis of Auctions Inecient Allocation Costs of Doing Tasks,tasks t1 t2 t1,t2,Agent 1 2 1 2,Agent 2 1.5 1.5 2.5,Leads to inecient allocation if auction t1 then t2. Implement full lookahead. Use a combinatorial auction.,主要,Auctions Valuations,拍卖简介和标的估值 简单拍卖分析 组合拍卖 集中式的胜标决定 分布式的

40、胜标决定 投标语言,主要内容,异质性标的物的互补和替代性,考虑有多个异质性的物品要卖的情况,考虑agnet对物品的估价类型,相对来说，替代性易于处理,互补性存在很多的问题,如按照顺序出卖或允许撤回投标,Auctions,Combinatorial Auctions,Combinatorial Auction,组合拍卖,在组合拍卖中，agent能够对一组物品进行投标,是相关投标的集合,Auctions Combinatorial Auctions 例子,Price $1 $3 $5 $6 $7 $8,Bid items Beast Boy Robin Raven, Starre Cyborg,

41、Robin Cyborg, Beast Boy Raven, Beast Boy,X = argmax X, b (S) SX,where X is a set of sets of goods that allocates each good to only one bidder.,胜利者的确定,胜者决定问题是找到投标的集合最大化卖方的利益：,一般CAP问题的形式化,CAP formula : x(S) = 1 : the highest bid on the set S is to be accepted 0 : no bid on the set S are accepted,CAP,C

42、AP formula : : no object in M is assigned to more than one bidder、 对拍卖品具有超可加性时成立,背包问题,Given a set of M elements collection V of subsets with weights Find the largest weight collection of subsets that are pairwise disjoint.,背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我

43、们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。,背包问题的形式化,Problem Complexity 将n各元素的结合划分为k个非空子集的数目是第二类的stirling数,这是个NP Hard 问题,Theorem,Winner Determination in Combinatorial Auction is NP-hard. That,is, nding the X that maximizes revenue is NP-hard.,胜者确定问题,如何处理组合拍卖中胜者确定的计算复杂性问题？,要求投标来自一个受到限制的集合，这样WDP能够在

44、多项式时间内解决,问题：这样的受限制集是非常有限的,使用AI启发式方法解决问题,这种方法在实践上工作的很好，这使得有可能解决有几百个拍卖品以及成千上万的投标的WDP问题,线性规划?,如果对所有的拍卖品都有singleton的投票,搜索算法,1 2 3,Number the goods from 1 to m. Create an empty root node. For each node, add as its children all the bids that,1 2,include the smallest good that is not on the path and do not

45、 include any good on the path.,12,35,4,3,4,5,135,2,4,14,25,3,2,35,3,5,1,25,3,4,2,35,4,3,4,Search Tree 1 2,3,4,5,12,135,14,25,35 5 9 leafs versus 52 allocations,加快了搜索速度，这里是9个投标集，而stirling数是：,Branch and Bound on Branch on Items Tree branch-on-items-ca(),g是已经出清的投标集，函数h简单的将不在g中的拍卖品的最大可能值加总，即使用对每个拍卖品支付最多

46、的投标，然后除以投标中的拍卖品数量。这个函数提供一个上限，因为没有可行的投标集能够有更高的收益。,Branch and Bound on Branch on Items Tree branch-on-items-ca-helper(i,g),1 2 3 4 5,if i = m then if bg bvalue r then g g r bg bvalue return,1,6 for b b B|i bitemsbitems b1g b1 items = 0 / 7 do g g +b bitemsdont overlap g 8 if b1g bvalue+h(g ) r,9,then

47、branch-on-items-ca-helper(i +1,g ),Branch on Bids Search Tree,35,25,14,Out 135,In 5,Out,14,Out 5,In 3,In,Out,14,12,Out 4,In 4,Out,2,Out,In,In,In,1,2,3 4,5,12,135 14,25 35,我们可以构造一个二叉树，其中每个节点是投标，边表示某个特定的投标是否在解中。,Branch and Bound on Branch on Bids Tree branch-on-bids-ca(),1 2,r 0 g 0 /, Max revenue fou

48、nd. Global variable. Best solution found. Global variable.,3 4,branch-on-bids(0 /,B) return g,Branch and Bound on Branch on Bids Tree,其他改进,Keep only the highest bid for any set.,Remove provably noncompetitive bids (i.e. they are dominated by another bid or sets of bids).,Decompose bids into connected sets. Each solved independently.,对任意集只保留最高的投标 移除已证明没有竞争力的投标 将投标分解为相连的子集，每个子集独立解决,主要,拍卖简介和标的估值 简单拍卖分析 组合拍卖 集中式的胜标决定 分布式的胜标决定 投标语言,主要内容,投标语言,or bids: b