Введение в теорию игр (сторонняя методичка) (1184510), страница 29
Текст из файла (страница 29)
Âäàëüíåéøåì áóäåì ðàññìàòðèâàòü òîëüêî ñóùåñòâåííûå èãðû.166 15. Êîîïåðàòèâíûå èãðûÎïðåäåëåíèå. Äâå êîîïåðàòèâíûå èãðû K = A, v è K0 = A, v 0íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëèòàêèå ÷èñëà c > 0 èP íàéäóòñÿa0ad , a ∈ A, ÷òî v (K) = cv(K) +d ∀ K ⊆ A.a∈KÏåðåõîä îò èãðû K ê ýêâèâàëåíòíîé èãðå K0 ìîæíî ñâÿçàòü ñ èçìåíåíèåì â c ðàç äåíåæíîé åäèíèöû.
Ïîëîæèòåëüíàÿ âåëè÷èíà da èíòåðïðåòèðóåòñÿ êàê äîïîëíèòåëüíàÿ âûïëàòà èãðîêó a. Åñëè æå âåëè÷èíàda îòðèöàòåëüíà, òî −da ìîæíî ðàññìàòðèâàòü êàê ïëàòó èãðîêà a çàó÷àñòèå â èãðå. Äåëåæ y èãðû K ïåðåõîäèò â äåëåæ z èãðû K0 ñ êîìïîíåíòàìè z a = cy a + da ∀ a ∈ A.Îïðåäåëåíèå. Ãîâîðÿò, ÷òî êîîïåðàòèâíàÿ èãðà K0 èìååò(0 − 1)-ðåäóöèðîâàííóþ ôîðìó, åñëè v 0 (A) = 1, v 0 (a) = 0 ∀ a ∈ A.Äëÿ êîîïåðàòèâíîé èãðû K ýêâèâàëåíòíàÿ èãðà K0 èìååò(0 − 1)-ðåäóöèðîâàííóþ ôîðìó,åñëèPc = (v(A) −v(a))−1 è da = −cv(a), ∀a ∈ A.a∈AÓïðàæíåíèå 15.3.
Äëÿ èãðû "äæàç-îðêåñòð"íàéòè ýêâèâàëåíòíóþ èãðó â (0 − 1)-ðåäóöèðîâàííîé ôîðìå. êîîïåðàòèâíîé òåîðèè íåò åäèíîãî ïîíÿòèÿ "ðàçóìíîãî"äåëåæà.Áîëåå òîãî, ðàçëè÷íûå ñîîáðàæåíèÿ "îïòèìàëüíîñòè"ïðèâîäÿò ê ðàçíûììíîæåñòâàì "ðàçóìíûõ"äåëåæåé. Ðàññìîòðèì äâà ïîäõîäà, îñíîâàííûåíà ïîíÿòèÿõ ÿäðà è âåêòîðà Øåïëè.Îïðåäåëåíèå. Ìíîæåñòâî äåëåæåéXC = {y ∈ Y |y a ≥ v(K) ∀ K 6= A}a∈Kíàçûâàåòñÿ ÿäðîì (èëè c-ÿäðîì îò àíãëèéñêîãî ”core”).Äåëåæ y, ïðèíàäëåæàùèé ÿäðó, óäîâëåòâîðÿåò óñëîâèþ "ãðóïïîâîéðàçóìíîñòè":âûèãðûø v(K) ëþáîé êîàëèöèè K íå ïðåâîñõîäèò åå äîëèP ay ïî äåëåæó y.a∈KÇàéìåìñÿ âûâîäîì óñëîâèÿ ñóùåñòâîâàíèÿ ÿäðà, ò.å.
êîãäà C 6= ∅.ÏîëîæèìXy a ≥ v(K) ∀ K 6= A}.C 0 = {y ∈ E |A| |a∈KÓïðàæíåíèå 15.4. Äîêàæèòå, ÷òî ÿäðî C ñóùåñòâóåò òîãäà è òîëüêî167ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖòîãäà, êîãäàmin0y∈C óñëîâèè (15.2) min0Py∈C a∈AXy a ≤ v(A).(15.2)a∈Ay a çàïèøåì ñ ïîìîùüþ äâîéñòâåííîé çàäà÷èëèíåéíîãî ïðîãðàììèðîâàíèÿXXmin0y a = maxλK v(K),y∈Cλ∈Λa∈AK6=AãäåΛ = {λ = (λK , K 6= A) |XλK = 1 ∀a ∈ A, λK ≥ 0 ∀ K 6= A}.K:a∈KÏîñëåäíèé ìàêñèìóì ìîæíî áðàòü òîëüêî ïî ìíîæåñòâó Λ0 êðàéíèõ òî÷åê (âåðøèí) ìíîãîãðàííèêà Λ (ñì. óïðàæíåíèå 5.5).
Îêîí÷àòåëüíî íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ ÿäðà çàïèñûâàåòñÿ â âèäåXλK v(K) ≤ v(A) ∀ λ ∈ Λ0 .(15.3)K6=AÂåêòîðû èç ìíîæåñòâà Λ íàçûâàþòñÿ ñáàëàíñèðîâàííûìè ïîêðûòèÿìèìíîæåñòâà A, à âåêòîðû èç ìíîæåñòâà Λ0 − ïðèâåäåííûìè (èëè ìèíèìàëüíûìè) ñáàëàíñèðîâàííûìè ïîêðûòèÿìè. Äëÿ êîàëèöèè K ⊂ Aîïðåäåëèì âåêòîð(1, a ∈ K,|A|aχ(K) ∈ E : χ (K) =0, a ∈/ K.Ýòè âåêòîðû ÿâëÿþòñÿ ñòîëáöàìè ìàòðèöû ñèñòåìû óðàâíåíèé, çàäàþùåé ìíîæåñòâî Λ.Äëÿ òîãî ÷òîáû ñáàëàíñèðîâàííîå ïîêðûòèå λ áûëî ïðèâåäåííûì,íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñèñòåìà âåêòîðîâ {χ(K) | λK > 0} áûëàëèíåéíî íåçàâèñèìîé.
Ýòîò ôàêò äîêàçûâàåòñÿ àíàëîãè÷íî óïðàæíåíèþ5.5.Îïðåäåëåíèå. Ñåìåéñòâî B êîàëèöèé íàçûâàåòñÿ ñáàëàíñèðîâàííûì,åñëè íàéäåòñÿ òàêîå ïðèâåäåííîå ñáàëàíñèðîâàííîå ïîêðûòèå λ, ÷òîB = {K | λK > 0}.168 15. Êîîïåðàòèâíûå èãðûÏðèìåðîì ñáàëàíñèðîâàííîãî ñåìåéñòâà êîàëèöèé ÿâëÿåòñÿ ðàçáèåíèå B ìíîæåñòâà A íà ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà.
Äëÿñîîòâåòñòâóþùåãî ïðèâåäåííîãî ñáàëàíñèðîâàííîãî ïîêðûòèÿ λ êîìïîíåíòû λK = 1, K ∈ B. Îòìåòèì, ÷òî äëÿ òàêîãî ïîêðûòèÿ íåðàâåíñòâî èç (15.3) âûïîëíÿåòñÿ "àâòîìàòè÷åñêè", â ñèëó ñóïåðàääèòèâíîñòèõàðàêòåðèñòè÷åñêîé ôóíêöèè. Ïîýòîìó ïðèâåäåííûå ñáàëàíñèðîâàííûåïîêðûòèÿ, îòâå÷àþùèå ðàçáèåíèÿì ìíîæåñòâà A, â äàëüíåéøåì íå ðàññìàòðèâàþòñÿ. Ñïðàâåäëèâ è áîëåå îáùèé ðåçóëüòàò.Óïðàæíåíèå 15.5. Ïóñòü äëÿ ïðèâåäåííîãî ñáàëàíñèðîâàííîãî ïîêðûòèÿ λ íàéäóòñÿ òàêèå êîàëèöèè T è L, ÷òî T ∩ L = ∅, λT ≥ λL > 0.Ïîêàæèòå, ÷òî ïîêðûòèå µ ñ êîìïîíåíòàìè Tλ − λL ,0,µK =λL , Kλ ,KKKK= T,= L,= T ∪ L,6= T, L, T ∪ L,ÿâëÿåòñÿ ïðèâåäåííûì ñáàëàíñèðîâàííûì èXXλK v(K) ≤µK v(K).K6=A(15.4)K6=AÈç (15.4) âûòåêàåò, ÷òî íåðàâåíñòâà (15.3) äîñòàòî÷íî ïðîâåðÿòü òîëüêî äëÿ ñóùåñòâåííûõ ïðèâåäåííûõ ñáàëàíñèðîâàííûõ ïîêðûòèé λ, äëÿêîòîðûõ íå ñóùåñòâóþò íåïåðåñåêàþùèõñÿ êîàëèöèé T è L ñ ïîëîæèòåëüíûìè λT è λL .Íàéäåì íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ ÿäðà â êîîïåðàòèâíîé èãðå òðåõ ëèö.
Êîìïîíåíòû âåêòîðà λ ∈ Λ0 óïîðÿäî÷èìñëåäóþùèì îáðàçîì: λ = (λ1 , λ2 , λ3 , λ23 , λ13 , λ12 ). Ïåðå÷èñëèì âñå ïðèâåäåííûå ñáàëàíñèðîâàííûå ïîêðûòèÿ ìíîæåñòâà A:λ(1) = (1, 1, 1, 0, 0, 0), λ(2) = (1, 0, 0, 1, 0, 0), λ(3) = (0, 1, 0, 0, 1, 0),λ(4) = (0, 0, 1, 0, 0, 1), λ(5) = (0, 0, 0, 1/2, 1/2, 1/2).Ñ ó÷åòîì ðåçóëüòàòà óïðàæíåíèÿ 15.5 ñóùåñòâåííûì ïîêðûòèåì ÿâëÿåòñÿ òîëüêî λ(5) è óñëîâèå ñóùåñòâîâàíèÿ ÿäðà çàïèñûâàåòñÿ â âèäåv(23) + v(13) + v(12) ≤ 2v(123).169ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÓïðàæíåíèå 15.6. Äëÿ êîîïåðàòèâíîé èãðû "äæàç-îðêåñòð"ïðîâåðüòå,÷òî ÿäðî C ñóùåñòâóåò.
Èçîáðàçèòå ïðîåêöèþ ÿäðà íà ïëîñêîñòü (y 1 , y 2 )è íàéäèòå åãî âåðøèíû. òàáëèöå 15.1 ïåðå÷èñëåíû âñå ñóùåñòâåííûå ïðèâåäåííûå ñáàëàíñèðîâàííûå ïîêðûòèÿ ìíîæåñòâà A èãðû ÷åòûðåõ ëèö.Òàáë. 15.1BA\{a}, a = 1, 2, 3, 4{1,2,3},{1,2,4}, {3,4}{1,2,3},{1,4}, {2,4},{3,4}{1,2,3},{1,4}, {2,4},{3}λK , K ∈ B1/3, 1/3, 1/3, 1/31/2, 1/2, 1/22/3, 1/3, 1/3, 1/31/2, 1/2, 1/2, 1/2Îñòàëüíûå ñóùåñòâåííûå ïîêðûòèÿ îòëè÷àþòñÿ îò óêàçàííûõ ïåðåñòàíîâêàìè íîìåðîâ èãðîêîâ.Ðàññìîòðèì ÷àñòíûé ñëó÷àé êîîïåðàòèâíîé èãðû, êîãäà óñëîâèå ñóùåñòâîâàíèÿ ÿäðà ìîæåò áûòü çàïèñàíî â ïðîñòîé ôîðìå.Îïðåäåëåíèå. Êîîïåðàòèâíàÿ èãðà K = A, v íàçûâàåòñÿ ñèììåòðè÷íîé, åñëè õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v çàâèñèò òîëüêî îò ÷èñëàèãðîêîâ â êîàëèöèè: v(K) = v|K| ∀ K ⊂ A.Óïðàæíåíèå 15.7. Ïîêàæèòå, ÷òî äëÿ ñèììåòðè÷íîé êîîïåðàòèâíîéèãðû K ÿäðî C òîãäà è òîëüêî òîãäà ñóùåñòâóåò, êîãäà âûïîëíåíû íåðàâåíñòâà|K|v|A| ∀ K ⊂ A.(15.5)v|K| ≤|A|Íåäîñòàòêîì ÿäðà ÿâëÿåòñÿ òîò ôàêò, ÷òî îíî ìîæåò íå ñóùåñòâîâàòü.
Äîêàæåì, ÷òî C = ∅, åñëè êîîïåðàòèâíàÿ èãðà K = A, v èìååòïîñòîÿííóþ ñóììó. Äåéñòâèòåëüíî, åñëè y ∈ C, òîXy b ≥ v(A\{a}) = v(A) − v(a), y a ≥ v(a).b6=aÏîñëåäíèå äâà íåðàâåíñòâà Pìîãóò âûïîëíÿòüñÿ òîëüêî êàê ðàâåíñòâà.aÎòñþäà y = v(a) ∀ a ∈ A èy a < v(A) (ïðîòèâîðå÷èå).a∈AÓêàçàííûì íåäîñòàòêîì íå îáëàäàåò âåêòîð Øåïëè. Îïðåäåëèì åãî,èñïîëüçóÿ âåðîÿòíîñòíóþ èíòåðïðåòàöèþ. Ïîëîæèì v(∅) = 0.170 15. Êîîïåðàòèâíûå èãðûÎïðåäåëåíèå. Äëÿ èãðîêà a ∈ K âåëè÷èíà v(K)−v(K\{a}) íàçûâàåòñÿâêëàäîì èãðîêà â êîàëèöèþ K.Ïóñòü êîàëèöèÿ A îáðàçóåòñÿ â ðåçóëüòàòå ñëåäóþùåãî ñëó÷àéíîãîïðîöåññà.
Ñíà÷àëà ñ âåðîÿòíîñòüþ 1/|A| âûáèðàåòñÿ èãðîê a1 , çàòåì èçîñòàâøèõñÿ |A| − 1 èãðîêîâ ñ âåðîÿòíîñòüþ 1/(|A| − 1) âûáèðàåòñÿ èãðîê a2 è ïðèñîåäèíÿåòñÿ ê èãðîêó a1 è ò.ä.  ðåçóëüòàòå ñ âåðîÿòíîñòüþ1/|A|! áóäåò âûáðàíà ïåðåñòàíîâêà èãðîêîâ a1 , ..., a|A| . Ìîæíî ïîäñ÷èòàòüâêëàä èãðîêà al â êîàëèöèþ {a1 , ..., al }. Òàêèì îáðàçîì, äëÿ êàæäîãî èãðîêà a åãî âêëàä (â êàêóþ-òî êîàëèöèþ K ) áóäåò ñëó÷àéíîé âåëè÷èíîé,ïðèíèìàþùåé çíà÷åíèå v(K) − v(K\{a}) (ãäå a ∈ K ) ñ âåðîÿòíîñòüþ(|K| − 1)! (|A| − |K|)!/|A|!.Îïðåäåëèì òåïåðü ñïåöèàëüíûé äåëåæ ϕ − âåêòîð Øåïëè. Åãî êîìïîíåíòà ϕa ðàâíà ìàòåìàòè÷åñêîìó îæèäàíèþ âêëàäà èãðîêà a, ò.å.ϕa =Ïðîâåðèì, ÷òîX (|K| − 1)! (|A| − |K|)!(v(K) − v(K\{a})).|A|!K:a∈KX (|K| − 1)! (|A| − |K|)!= 1.|A|!K:a∈K(15.6)Äåéñòâèòåëüíî,|A|X (|K| − 1)! (|A| − |K|)! X=|A|!K:a∈Kl=1XK:a∈K, |K|=l(l − 1)! (|A| − l)!.|A|!×èñëî êîàëèöèé, ñîäåðæàùèõ l èãðîêîâ è ñðåäè íèõ èãðîêà a, ðàâíîl−1C|A|−1=(|A| − 1)!.(l − 1)! (|A| − l)!Ïîýòîìó â ïîñëåäíåé äâîéíîé ñóììå ïðè ëþáîì l âíóòðåííÿÿ ñóììà ðàâíà 1/|A|.
Îòñþäà è ñëåäóåò (15.6).Óïðàæíåíèå 15.8. Ïîêàæèòå, ÷òî âåêòîð Øåïëè ϕ = (ϕa , a ∈ A)ÿâëÿåòñÿ äåëåæîì êîîïåðàòèâíîé èãðû.Óïðàæíåíèå 15.9. Âûïèøèòå ÿâíûå ôîðìóëû äëÿ ïîäñ÷åòà âåêòîðàØåïëè â èãðå òðåõ ëèö. Íàéòè âåêòîð Øåïëè äëÿ êîîïåðàòèâíîé èãðû "äæàç-îðêåñòð"è ïîêàçàòü åãî ïðèíàäëåæíîñòü ÿäðó. Ïðîâåðèòü, ÷òîåñëè v(123) óìåíüøèòü íà $3 , òî âåêòîð Øåïëè ÿäðó íå ïðèíàäëåæèò.171ÃËÀÂÀ III.
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÓïðàæíåíèå 15.10. Ïîêàçàòü, ÷òî äëÿ ñèììåòðè÷íîé êîîïåðàòèâíîéèãðû âåêòîð Øåïëè ϕ = (v|A| /|A|, ..., v|A| /|A|).Êîììåíòàðèé è áèáëèîãðàôèÿ ê ãëàâå III 12. Îïðåäåëåíèå ñèòóàöèè ðàâíîâåñèÿ äëÿ èãðû ìíîãèõ ëèö ïðèíàäëåæèò Äæ. Íýøó [76]. Òåîðåìà 12.1 äîêàçàíà Ñ. Êàêóòàíè [47] è èñïîëüçîâàíà äëÿ äîêàçàòåëüñòâà òåîðåìû 2.3 î âîãíóòî-âûïóêëîé ôóíêöèè. Òåîðåìà ñóùåñòâîâàíèÿ ñèòóàöèè ðàâíîâåñèÿ â èãðàõ ñ êîíå÷íûìèìíîæåñòâàìè ñòðàòåãèé äîêàçàíà Äæ. Íýøåì [76].
Òàì æå ïðèâåäåíûñâîéñòâà ñèòóàöèé ðàâíîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ. Ïðèìåð 12.1ïðèíàäëåæèò Í.Í. Âîðîáüåâó [34]. Îïðåäåëåíèå èãðû, ðàçðåøèìîé ïîäîìèíèðîâàíèþ, ââåäåíî Ý. Ìóëåíîì [71]. 13. Îñíîâíûå ïîíÿòèÿ òåîðèè ïîçèöèîííûõ èãð îïðåäåëåíû Äæ. ôîíÍåéìàíîì è Î. Ìîðãåíøòåðíîì â [72]. Ïîëíàÿ ôîðìàëèçàöèÿ ýòèõ èãðïðîâåäåíà Ã.Ó. Êóíîì [58]. Îïðåäåëåíèå ñîâåðøåííîãî ïîäûãðîâîãî ðàâíîâåñèÿ ïðèíàäëåæèò Ð. Ñåëòåíó [98].
Òåîðåìà 13.1 î ñóùåñòâîâàíèè ñèòóàöèè ðàâíîâåñèÿ â ïîçèöèîííîé èãðå ñ ïîëíîé èíôîðìàöèåé äîêàçàíàÃ.Ó. Êóíîì [58]. Êîíöåïöèÿ âîçìóùåííîé èãðû, â êîòîðîé èãðîêè ìîãóòîøèáàòüñÿ ïðè âûáîðå ñâîèõ ñòðàòåãèé, ââåäåíà Ð. Ñåëòåíîì [99]. 14. Ïðèìåð 14.1 è òåîðåìà 14.1 îá ýêâèâàëåíòíîñòè ñìåøàííûõ ñòðàòåãèé ñîîòâåòñòâóþùèì ñòðàòåãèÿì ïîâåäåíèÿ â èãðàõ ñ ïîëíîé ïàìÿòüþïðèíàäëåæèò Ã.Ó. Êóíó [58]. Äðóãèå ðåçóëüòàòû ïî òåîðèè ïîçèöèîííûõèãð ñì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
