專題二合作博弈

1、專題二： 合作博弈 在非合作的n人博弈中，局中人之間不允許事先協(xié)商和選擇策略，不允許他們把策略結(jié)合起來，不允許局中人對(duì)得到的支付重新分配。一個(gè)局中人不能分享另一個(gè)局中人得到的支付。 討論的n人合作博弈，對(duì)上述問題都不加限制。局中人在選擇策略時(shí)可以協(xié)商，并且局中人的支付可以相互轉(zhuǎn)讓。在n人合作博弈中，如何選擇自己的策略已不是主要討論的問題，n人合作博弈模型主要討論下述問題。1（1）n個(gè)局中人之間是如何構(gòu)成聯(lián)盟的。（2）各個(gè)聯(lián)盟的支付或收益有多大。（3）局中人最終在聯(lián)盟中分配到多少。 1.穩(wěn)定集 1、聯(lián) 盟 設(shè)局中人集合N=1,2,.,n，N的任意子集稱為聯(lián)盟。注 1：空子集 也稱為一個(gè)聯(lián)盟。 記

2、所有的聯(lián)盟構(gòu)成的集類為B。 對(duì)于 S B，用v(S)表示聯(lián)盟S中的局中人通過合作所得到的支付。因而v(S)可認(rèn)為定義在R上，取值于實(shí)數(shù)的一個(gè)函數(shù)。22、聯(lián)盟博弈 稱為一個(gè)聯(lián)盟博弈3、特征函數(shù) 稱v為該聯(lián)盟博弈的特征函數(shù)，它滿足v( )=0例1：局中人1（賣主）要把物品賣掉，局中人2和3（買主）分別出價(jià)9元和10元。如果局中人1將物品賣給局中人2的要價(jià)是x元，則局中人2贏利9-x元。 V(1,2)=9, v(1,3)=10, v(i)=v(2,3)=0. i=1,2,3, v(1,2,3)=10 于是建立了聯(lián)盟博弈3特征函數(shù)是研究聯(lián)盟博弈的基礎(chǔ)，確定特征函數(shù)的過程實(shí)際就是一個(gè)建立合作博弈的過程定

3、義1：稱向量x=(x1,x2,xm)是聯(lián)盟S=1,2,.m的一個(gè)分配，如果它滿足: (1) (整體合理性) (2) vi, i=1,2,.,m （個(gè)體合理性）注2： 的全部分配所構(gòu)成的集合記為I(v)注3：滿足（1）（2）的分配不唯一。4定義2：設(shè)有分配x,y I(v) ，及聯(lián)盟S B ，如果:(1) 對(duì) i S, (說明分配x比y好) (2) （說明分配中給聯(lián)盟成員的支付可由聯(lián)盟付出） 則稱對(duì)聯(lián)盟S，分配x優(yōu)于y，記作 。如果對(duì)于 ，能找到一個(gè)聯(lián)盟T，使 ，則稱 優(yōu)于 ，記作 。定義3：對(duì)于聯(lián)盟博弈，集合s(V) I(v) 稱為聯(lián)盟博弈 的穩(wěn)定集，如果以下條件成立：5（1）S (V) 中任意

4、分配x都不優(yōu)于 S (V)中的其余分配 。 (說明穩(wěn)定集內(nèi)部任何兩個(gè)分配無優(yōu)超關(guān)系即內(nèi)穩(wěn)定性)（2）不屬于S (V)中的任何分配y，總可以在 S (V)中找到優(yōu)于y的分配x。（ 外穩(wěn)定性）注4：穩(wěn)定集的概念由馮.諾依曼(V.Neumann)和摩根斯坦(Morgenstern)提出，也成為合作博弈的V-N-M解。6例2 設(shè)有三個(gè)局中人，擬合伙開商店，每月可贏利200元。要使商店正常營業(yè)，起碼需要兩人。試問，應(yīng)采用怎樣的方式經(jīng)營，以及怎樣分配利潤才是合理的。解：特征函數(shù)為 v(i)=0, i=1,2,3.v1,2= v2,3= v1,3= v1,2,3=2三人利潤分配是向量x=(x1,x2,x3)

5、，滿足x1+x2+x3= v1,2,3=2, (x1,x2,x3)=0 如果聯(lián)盟1，2形成，即局中人1、2合伙，則分配x=（1，1，0）是合理的。7 否則，局中人1要求采取分配（1+ ，1- ，0），其中 （0，1），那么局中人2與局中人3合伙。如果局中人3也采取類似的要求，則局中人2不與任何人結(jié)盟，余下1與3各持己見。（1+ ，1- ,）不構(gòu)成分配。同樣，如果2，3結(jié)盟，y=（0，1，1）是合理的分配；1，3結(jié)盟，z=（1，0，1）是合理的分配，易知 w=x,y,z是穩(wěn)定集（1 ） x,y,z之間沒有優(yōu)超關(guān)系8(2)對(duì)于w之外的任何一個(gè)分配a=(a1,a2,a3)滿足a1+a2+a3=2 且

6、ai=0，必被w中某個(gè)分配優(yōu)超。 2.核心定義1： n人聯(lián)盟博弈的所有不被優(yōu)超的分配構(gòu)成的集合稱為核心，記為c(v)定理1：分配方案x=(x1,x2,xn)在核心c(v)中的充要條件：(1)(2)對(duì)9例3：設(shè)有三人聯(lián)盟對(duì)策，其特征函數(shù)v1= v2= v3=0,v1,2=4, v2,3=1, v1,3=3,v1,2,3=5由定理1知：這個(gè)博弈的核心由下面不等式組確定: x1+x2=4 x1+x3=3 x2+x3=1 x1+x2+x3=5 xi=010其解為A=x=(x1,x2,x3)| x1+x2+x3=5, xi=0內(nèi)以(4,0,1,),(4,1,0),(3,2,0),(2,2,1)為頂點(diǎn)的四邊形，如圖：（0,0,5）0,5,03,2,0(4,1,0)(5,0,0)(4,1,0)(2,2,1)核11有些聯(lián)盟博弈的核可能是空的。滿足非空的條件:定理：對(duì)于n人的聯(lián)盟博弈，核心非空的充要條件是線性規(guī)劃有解：12 4 聯(lián)盟博弈的Shapley值 n人合作博弈的另一個(gè)解設(shè)為一聯(lián)盟博弈，對(duì)于給定的特征函數(shù)v可以確定出特定的分配 這里,13稱 為聯(lián)盟博弈的Shapley值 可以證明Shapley值是滿足下述公理的唯一向量。 A1：對(duì)