А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 15
Текст из файла (страница 15)
Èòàê, ìíîãîøàãîâà� èãð� � ïîëíî� èíôîðìàöèå� îïðå˜ Y˜ , F (˜äåëåí� � íîðìàëüíî� ôîðì� Γ = X, x, y) ˜ .� äàëüíåéøå� áóäå� ðàññìàòðèâàò� äâ� êëàññ� èãð:èãð� Γ0 , � êîòîðî� âñ� ìíîæåñòâ� Ut (·), Vt (·) êîíå÷íû;èãð� Γ00 , � êîòîðî� âñ� ìíîæåñòâ� Ut (·) ≡ Ut , Vt (·) ≡ Vt í� çàâèñÿ� î� ïðåäûñòîðè� � ÿâëÿþòñ� êîìïàêòàì� ìåòðè÷åñêè� ïðîñòðàíñòâ, � ôóíêöè� F (xT , y T ) íåïðåðûâí� í� ïðîèçâåäåíè� U1 × · · · × UT × V1 × · · · × VT . Îïðåäåëè� ïàð� ñòðàòåãè� x̃0 = (x̃0t , t = 1, ..., T ), ỹ 0 = (ỹt 0 , 1, ..., T ), èñïîëüçó� ìåòî� äèíàìè÷åñêîã� ïðîãðàììèðîâàíèÿ.
Äîîïðåäåëè� ôóíêöè� F í� âñå� îòðåçêà� ïàðòè� âèä� (xt , y t−1 ) èë� (xt , y t ) � íàçîâå� å� ôóíêöèå� Áåëëìàíà. Êîìïîíåíò� ñòðàòåãè� x̃0 t , ỹt 0 áóäå� çàäàâàò� � ïîðÿäêå, îáðàòíî� âûáîðà� èãðîêîâ. Îïðåäåëè� ñíà÷àë� ỹT 0 . Äë� ýòîã� çàôèêñèðóå� ïðîèçâîëüíî� çíà÷åíè� àðãóìåíòî� (xT , y T −1 ) � çàäàäè� çíà÷åíè� ôóíêöè� def ỹT 0 (xT , y T −1 ) = yT 0 : def F (xT , y T −1 , y T 0 ) = min F (xT , y T −1 , yT ) = F (xT , y T −1 ).
yT ∈VT (·)Îïðåäåëè� ôóíêöè� x̃0 T . Çàôèêñèðóå� ïðîèçâîëüíî� çíà÷åíè� àðãóìåíòî� (xT −1 , y T −1 ) � çàäàäè� çíà÷åíè� ôóíêöè� def x̃0 T (xT −1 , y T −1 ) = x0 T : def F (xT −1 , x 0 T , y T −1 ) = max F (xT −1 , xT , y T −1 ) = F (xT −1 , y T −1 ). xT ∈UT (·)Ïóñò� îïðåäåëåí� êîìïîíåíò� ñòðàòåãè� � çíà÷åíè� ôóíêöè� Áåëëìàí� ỹT 0 , x̃0 T , ..., ỹt0+1 , x̃0 t+1 , F (xT , y T −1 ), ..., F (xt , y t ).
Òîãä� ỹt 0 , x̃0 t , F (xt , y t−1 ), F (xt−1 , y t−1 ) çàäàþòñ� ï� ïðèâåäåííû� âûø� ôîðìóëà� � çàìåíî� T í� t. Ïîêàæåì, ÷ò� ñòðàòåãè� x̃0 , ỹ 0 îïðåäåëåí� êîððåêòí� äë� èã� Γ� � Γ00 . Äåéñòâèòåëüíî, � èãð� Γ� âñ� ìíîæåñòâ� Ut (·), Vt (·) êîíå÷í� � ïîýòîì� 77ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ìàêñèìóì� � ìèíèìóìû, ôèãóðèðóþùè� � îïðåäåëåíèÿ� x̃0 , ỹ 0 , äîñòèãàþòñÿ. Àíàëîãè÷íî� óòâåðæäåíè� ñïðàâåäëèâ� � äë� èãð� Γ00 , ïîñêîëüê� ï� òåîðåì� 2.2 ôóíêöè� Áåëëìàí� íåïðåðûâí� í� ñîîòâåòñòâóþùè� êîìïàêòàõ.
Îïðåäåëè� âåëè÷èí� def F (x1 ) ṽ = max F (x1 ) x1 ∈U1 = max min F (x1 , y1 ) = ... x1 ∈U1 y1 ∈V1 (·)= max min ... max x1 ∈U1 y1 ∈V1 (·) min F (xT , y T ). xT ∈UT (·) yT ∈VT (·)Ñïðàâåäëèâ� ñëåäóþùà� Òåîðåì� 8.1 (Öåðìåëî). Âñÿêà� ìíîãîøàãîâà� àíòàãîíèñòè÷åñêà� èãð� � ïîëíî� èíôîðìàöèå� Γ� (èë� Γ00 ) èìåå� ðåøåíè� (x̃0 , ỹ 0 , ṽ). Äîêàçàòåëüñòâî.
Äîêàæåì, ÷ò� ôóíêöè� F (x̃, ỹ) èìåå� ñåäëîâó� òî÷ê� (x̃0 , ỹ 0 ) í� X̃ × Y˜ . Äë� ýòîã� äîñòàòî÷í� äîêàçàòü, ÷ò� 1) F (x̃0 , ỹ) ≥ ṽ ∀ ỹ ∈ Ỹ ; ˜2) F (x̃, ỹ 0 ) ≤ v ˜ ∀ x̃ ∈ X.Äîêàæå� íåðàâåíñòâ� 1). Èìåå�F (˜x 0 , y) ˜ ≥ min F (˜x 0 , ỹ1 , ..., ỹT −1 , yT ) = F (˜x 0 , ỹ1 , ..., ỹT −1 ) = yT ∈VT (·)def x̃T 0 = max F (˜x 01 , ..., x̃0 T −1 , xT , ỹ1 , ..., ỹT −1 ) = xT ∈UT (·)= F (˜x 01 , ..., x̃0 T −1 , y˜1 , ..., ỹT −1 ) ≥ ... ≥ F (˜x 01 , ỹ1 ) ≥ max F (x1 ) = ṽ.
x1 ∈U1 Íåðàâåíñòâ� 2) äîêàçûâàåòñ� àíàëîãè÷íî. Ïðèìå� 8.1. Ïîêàæåì, ÷ò� èãð� "øàõìàòû"èìåå� ðåøåíèå. Ñóùåñòâóå� òàêî� öåëî� ÷èñë� T, ÷ò� � ñîîòâåòñòâè� � ïðàâèëàì� èãð� ëþáà� øàõìàòíà� ïàðòè� çàêàí÷èâàåòñ� í� ïîçäíå� õîä� T. Ïîýòîì� áå� ïîòåð� îáùíîñò� ìîæí� ñ÷èòàòü, âñ� ïàðòè� ïðîäîëæàþòñ� T õîäîâ1 .
Øàõìàò� ÿâëÿþòñ� èãðî� âèä� Γ0 . Ut (xt−1 , y t−1 ) åñò� ìíîæåñòâ� ðàçðåøåííû� ïðàâèëàì� àëüòåðíàòèâíû� âûáîðî� õîä� áåëûì� (ïåðâû� èãðîêîì) í� t-� õîä� � ïîçèöèè, îïðåäåëÿåìî� ïðåäûäóùèì� õîäàì� èãðîêî� (xt−1 , y t−1 ). 1 Åñë� ïàðòè� çàêàí÷èâàåòñ� ðàíüøå, ò� èãðîê� äåëàþ� íåîáõîäèìî� ÷èñë� ôèêòèâíû� õîäîâ, í� âëèÿþùè� í� èñõî� èãðû. 78 8. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð�Àíàëîãè÷í� èíòåðïðåòèðóåòñ� ìíîæåñòâ� Vt (xt , y t−1 ) âûáîðî� õîä� ÷åðíûì� í� t-� õîäó. Âûèãðû� áåëû� îïðåäåëÿåòñ� ï� ïðàâèë� ⎧ åñë� âûèãðàë� áåëûå,⎨ 1, F (xT , y T ) = 0, åñë� âûèãðàë� ÷åðíûå,⎩1/2, åñë� ñûãðàë� âíè÷üþ.Ï� òåîðåì� Öåðìåë� èãð� "øàõìàòû"èìåå� ðåøåíèå. Ïðàêòè÷åñêî� çíà÷åíè� ýòî� ðåçóëüòà� èìåå� äë� ïîçèöè� ýíäøïèëÿ, ãä� îáû÷í� èùó� ôîðñèðîâàííû� âûèãðûø, ëèá� íè÷üþ.
Ïðèìå� 8.2. Ðàññìîòðè� ìàòðèö� ⎛ 52A = ⎝343720123240 .3⎠5Ðàçîáüå� ìíîæåñòâ� å� ñòðî� í� ïîäìíîæåñòâ� M1 = {1, 2} � M2 = {3, 4}, � ìíîæåñòâ� ñòîëáöî� − í� ïîäìíîæåñòâ� N1 = {1, 2} � N2 = {3, 4}. Îïðåäåëè� äâóõøàãîâó� èãð� � ïîëíî� èíôîðìàöèåé. Øà� 1. Ñíà÷àë� ïåðâû� èãðî� âûáèðàå� íîìå� α ∈ {1, 2} ìíîæåñòâ� Mα , è� êîòîðîã� î� áóäå� í� âòîðî� øàã� äåëàò� âûáî� ñòðîê� ìàòðèö� A.
Çàòå� âòîðî� èãðîê, çíà� α, âûáèðàå� íîìå� β ∈ {1, 2} ìíîæåñòâ� Nβ , è� êîòîðîã� î� áóäå� í� âòîðî� øàã� âûáèðàò� íîìå� ñòîëáö� ìàòðèö� A. Øà� 2. Ïåðâû� èãðî� âûáèðàå� íîìå� ñòðîê� i ∈ Mα , çíà� α, β , çàòå� âòîðî� èãðî� âûáèðàå� íîìå� ñòîëáö� j ∈ Nβ , çíà� α, β, i. Âûèãðû� ïåðâîã� èãðîê� ðàâå� aij . Äë� ðåøåíè� çàäà÷� âîñïîëüçóåìñ� ïîçèöèîííî� ôîðìî� èãðû, êîòîðó� áóäå� îòîáðàæàò� í� ïëîñêîñò� � âèä� äåðåâà. 79 ÃËÀÂ� I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�1� � @@1 B� 2 1 B5 3 2 21 � 2 � � � 32� � � 2� @1 � 2 � @ � k3� � 1 B� @3� 1 k� 2 PPPP2 PP1� 2 � 7 3 1 2� J� 21 � 1� 0� � JJ 4 3 � 2� 0� B� B� B� � 4� 4 3 2 0 32 1 4B� 3 B� � 4 1 � 2B � 3 � 4� � � 32� 2 � 03 B�� 4� 3 3 2 � 4�5Ðèñ. 8.1 Íà÷àëüíà� (êîðíåâàÿ) âåðøèí� äåðåâà� ñîîòâåòñòâóå� ïåðâîì� õîä� ïåðâîã� èãðîê� (âûáî� àëüòåðíàòèâ� α), � âåðøèíà� âòîðîã� óðîâí� àëüòåðíàòèâ� β âûáèðàå� âòîðî� èãðî� � ò.ä.
� ôèíàëüíû� âåðøèíàõ, îòâå÷àþùè� ðàçëè÷íû� ïàðòèÿ� èãðû, óêàçàí� âûèãðûø� ïåðâîã� èãðîê� F (α, β, i, j) = aij . � âåðøèíà� ÷åòâåðòîã� óðîâí� óêàçàí� çíà÷åíè� ôóíêöè� Áåëëìàí� F (α, β, i) = min F (α, β, i, j), � âåðøèíà� j∈Nβ òðåòüåã� óðîâí� − F (α, β) = max F (α, β, i), � âåðøèíà� âòîðîã� óðîâi∈Mα í� − F (α) = min F (α, β), � � íà÷àëüíî� âåðøèí� − çíà÷åíè� èãð� β=1,2 ṽ = max F (α) = 2.
α=1,2 Óêàæå� îïòèìàëüíû� ñòðàòåãè� èãðîêî� x̃0 = (α0 , ĩ0 (α, β)), ỹ 0 = ( β̃ 0 (α), j̃ 0 (α, β, i)) : α0 = 2, ĩ0 (2, 1) = 3, ĩ0 (2, 2) = 3, β̃ 0 (1) = 2, β̃ 0 (2) = 1, j̃ 0 (1, 2, 1) = 3, , j̃ 0 (1, 2, 2) = 4, j̃ 0 (2, 1, 3) = j̃ 0 (2, 1, 4) = 2. Îòìåòèì, ÷ò� ñíà÷àë� ì� ïîäñ÷èòàë� ôóíêöè� Áåëëìàíà, � çàòå� ïîñòðîèë� � åñòåñòâåííî� ïîðÿäê� êîìïîíåíò� îïòèìàëüíû� ñòðàòåãèé. � ðåçóëüòàò� áûë� äîñòèãíóò� íåêîòîðà� ýêîíîìè� âû÷èñëåíèé, ïîñêîëüê� ýò� êîìïîíåíò� íåîáÿçàòåëüí� ñëåäóå� îïðåäåëÿò� ïð� âñå� çíà÷åíèÿ� 1 Äåðåâ� èçîáðàæåí� � ïåðåâåðíóòî� âèäå, ïîñêîëüê� òà� åã� óäîáíå� ðèñîâàòü. 80 8. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð�àðãóìåíòîâ. Íàïðèìåð, α0 = 2 � çíà÷åíè� ôóíêöè� ĩ0 (α, β) íóæí� íàõîäèò� òîëüê� ïð� α = 2.
Åù� áîëå� ñóùåñòâåííî� ñîêðàùåíè� âû÷èñëåíè� äîñòèãàåòñ� � èñïîëüçîâàíèå� ïðèåìî� òåîðè� èñêóññòâåííîã� èíòåëëåêòà. Ðàññìîòðè� âîïðî� � ïðîãðàììèðîâàíè� øàõìàò. � òåêóùå� ïîçèöè� øàõìàòíî� ïàðòè� ïð� õîäå, ñêàæåì, áåëû� äåðåâ� èãð� ïîðîæäàåòñ� í� ãëóáèí� íåñêîëüêè� õîäîâ. � ôèíàëüíû� âåðøèíà� äåðåâ� âûèãðû� áåëû� çàäàåòñ� � ïîìîùü� îöåíî÷íî� ôóíêöèè, ó÷èòûâàþùå� ìàòåðèàëüíû� � ïîçèöèîííû� îñîáåííîñò� ôèíàëüíî� ïîçèöèè. Ïîñë� ýòîã� ðåøàåòñ� ïîëó÷èâøàÿñ� èãð� � ïîëíî� èíôîðìàöèå� � íàõîäèòñ� îïòèìàëüíû� õî� áåëû� � òåêóùå� ïîçèöèè. Îáû÷í� äåðåâ� èãð� ïîðîæäàåòñ� � ïîìîùü� ðåêóðñèâíî� ïðîöåäóð� ïîñòðîåíè� ïîääåðåâüåâ.
Ïð� ýòî� � âåðøèíà� äåðåâ� âû÷èñëÿþòñ� çíà÷åíè� ôóíêöè� Áåëëìàíà. Ðàññìîòðè� âîçìîæíû� õî� áåëû� a1 � òåêóùå� ïîçèöèè. Ïóñò� ïîñòðîåí� ïîääåðåâ� èãðû, ñîîòâåòñòâóþùå� ýòîì� õîä� � ïîëó÷åí� îöåíê� õîä� a1 (òî÷íåå, ïîçèöèè, âîçíèêàþùå� ïîñë� ýòîã� õîäà), ðàâíà� 4.
Ðàññìîòðè� äðóãî� õî� áåëû� a2 � òåêóùå� ïîçèöèè. Òåïåð� ïóñò� ÷åðíû� âûáðàë� õî� b1 � óñòàíîâëåíî, ÷ò� åã� îöåíê� ðàâí� 1. Òîãä� îöåíê� õîä� a2 áóäå� í� áîëüø� 1 � åã� ìîæí� îòáðîñèòü, ïîñêîëüê� î� õóæ� õîä� a1 . Òàêè� îáðàçîì, çäåñ� í� ïîòðåáîâàëîñ� ïîëíî� ïîñòðîåíè� ïîääåðåâ� õîä� a2 .
Îöåíê� õîä� a1 � äàííî� ñëó÷à� íàçûâàåòñ� α-îòñå÷åíèåì. Åñë� � òåêóùå� ïîçèöè� õî� ÷åðíûõ, ò� àíàëîãè÷í� ìîæí� îïðåäåëèò� ïîíÿòè� β -îòñå÷åíèÿ. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð� � íåïîëíî� èíôîðìàöèåé. Îïðåäåëè� òåïåð� áîëå� îáùó� ìîäåë� ìíîãîøàãîâî� èãðû, � ïðîöåññ� êîòîðî� èãðîê� ìîãó� í� èìåò� ïîëíî� èíôîðìàöè� � ñäåëàííû� âûáîðàõ. Îãðàíè÷èìñ� èãðàì� Γ� � êîíå÷íûì� ìíîæåñòâàì� Ut (·), Vt (·), t = 1, ..., T. Ïóñò� Ht1 (Ht 2 ) − ìíîæåñòâ� âñå� îòðåçêî� ïàðòè� âèä� (xt−1 , y t−1 )(âèä� (xt , y t−1 )).
Ïðåäïîëîæèì, ÷ò� ìíîæåñòâ� Ht 1 ðàçáèò� í� íåïåðåñåêàþùèåñ� ïîäìíîæåñòâ� Ht 1 (αt ), αt ∈ Lt . Ïåðå� âûáîðî� xt ïåðâîìóèãðîê� èçâåñòíî, ÷ò� (xt−1 , y t−1 ) ∈ Ht 1 (αt ). Àíàëîãè÷íî, ïóñò� ìíîæåñòâ� Ht2 ðàçáèò� í� íåïåðåñåêàþùèåñ� ïîäìíîæåñòâ� Ht 2 (βt ), βt ∈ Bt . Ïåðåäâûáîðî� yt âòîðîì� èãðîê� èçâåñòíî, ÷ò� (xt , y t−1 ) ∈ Ht 2 (βt ). Åñëè, � ÷àñòíîñòè, αt = (xt−1 , y t−1 ), βt = (xt , y t−1 ), � ìíîæåñòâ� Ht 1 (αt ) � Ht 2 (βt )ñîäåðæà� ï� îäíîì� ýëåìåíò� αt � βt ñîîòâåòñòâåííî, ò� ïîëó÷è� èãð� � 81ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ïîëíî� èíôîðìàöèåé.
Ñòðàòåãè� x̃ ∈ X̃ ïåðâîã� èãðîê� çàäàåòñ� íàáîðî� ôóíêöè� x̃t î� αt , ïðèíèìàþùè� çíà÷åíè� x̃t (αt ) ∈ Ut (αt ), t = 1, ..., T. Ñòðàòåãè� ỹ ∈ Ỹâòîðîã� èãðîê� çàäàåòñ� íàáîðî� ôóíêöè� ỹt î� βt , ïðèíèìàþùè� çíà÷åíè� ỹt (βt ) ∈ Vt (βt ), t = 1, ..., T. Ï� îïðåäåëåíè� F (x̃, ỹ) = F (xT , y T ), ãä� ïàðòè� èãð� (xT , y T ) îäíîçíà÷í� çàäàåòñ� ñòðàòåãèÿì� èãðîêî� x̃ � ˜ Y˜ , F (x̃, ỹ) � íîðìàëüíî� ôîðìå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
