Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò
Êàôåäðà ìàòåìàòè÷åñêîé òåîðèè èãð è ñòàòèñòè÷åñêèõ ðåøåíèé
Áëèçíèêîâà Àííà Âàëåíòèíîâíà
Âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà áàêàëàâðà
Ñòðàòåãè÷åñêàÿ ïîääåðæêà êîîïåðàöèè â
äèñêðåòíûõ ìíîãîøàãîâûõ èãðàõ
Íàïðàâëåíèå 010400
Ïðèêëàäíàÿ ìàòåìàòèêà, ôóíäàìåíòàëüíàÿ èíôîðìàòèêà è
ïðîãðàììèðîâàíèå
Íàó÷íûé ðóêîâîäèòåëü,
äîêòîð ôèç.-ìàò. íàóê,
ïðîôåññîð,
Ïåòðîñÿí Ë.À.
Ñàíêò-Ïåòåðáóðã
2016
Ñîäåðæàíèå
Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ïîñòàíîâêà çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Îáçîð ëèòåðàòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ãëàâà 1. Íåîáõîäèìûå ñâåäåíèÿ è îñíîâíûå îïðåäåëåíèÿ . . . . . . .
1.1. Çàäàíèå ìíîãîøàãîâîé äèñêðåòíîé èãðû íà äðåâîâèäíîì ãðàôå
1.2 Êîîïåðàöèÿ â ìíîãîøàãîâûõ èãðàõ . . . . . . . . . . . . . . .
Ãëàâà 2. Óñòîé÷èâîñòü ïðèíöèïîâ îïòèìàëüíîñòè . . . . . . . . . . .
2.1. Ðåãóëÿðèçàöèÿ êëàññè÷åñêèõ ïðèíöèïîâ îïòèìàëüíîñòè . . .
Ãëàâà 3. Ïîñòðîåíèå ìíîãîøàãîâîé èãðû, êàæäûé óçåë êîòîðîé ÿâëÿåòñÿ áèìàòðè÷íîé èãðîé . . . . . . . . . . . . . . . . . . . . . . . . . .
Ãëàâà 4. Ñòðàòåãè÷åñêàÿ ïîääåðæêà . . . . . . . . . . . . . . . . . . .
Âûâîäû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ñïèñîê ëèòåðàòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ïðèëîæåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
3
5
6
7
7
9
11
13
17
22
27
28
29
30
Ââåäåíèå
Òåîðèÿ èãð ïðåäñòàâëÿåò ñîáîé ðàçäåë ìàòåìàòèêè, â êîòîðîì èññëåäóþòñÿ ìîäåëè ïðèíÿòèÿ îïòèìàëüíûõ ðåøåíèé â ðàìêàõ êîíôëèêòà.
Èçíà÷àëüíî òåîðèÿ èãð ðàçâèâàëàñü â îáëàñòè ýêîíîìè÷åñêîé íàóêè îíà
îáúÿñíÿëà ïîâåäåíèå ýêîíîìè÷åñêèõ àãåíòîâ â ðàçíîîáðàçíûõ ñèòóàöèÿõ.
Âïîñëåäñòâèè, îáëàñòü èñïîëüçîâàíèÿ ìîäåëåé òåîðèè èãð áûëà ðàñøèðåíà íà ðàçëè÷íûå ñîöèàëüíûå íàóêè: ñåãîäíÿ ýòîò ðàçäåë ìàòåìàòèêè èñïîëüçóåòñÿ äëÿ îáúÿñíåíèÿ ïîâåäåíèÿ ëþäåé â ïñèõîëîãèè, êóëüòóðîëîãèè,
ïåäàãîãèêå, ñîöèîëîãèè è ïîëèòîëîãèè.
 íàñòîÿùåå âðåìÿ òåîðèÿ èãð âñå ãëóáæå ïðîíèêàåò â ïðàêòèêó ýêîíîìè÷åñêèõ èññëåäîâàíèé. Åå ìîæíî ðàññìàòðèâàòü êàê èíñòðóìåíò, êîòîðûé ïîìîãàåò ïîâûñèòü ýôôåêòèâíîñòü óïðàâëåí÷åñêèõ è ïëàíîâûõ ðåøåíèé, ÷òî èìååò áîëüøîå çíà÷åíèå ïðè ðàññìîòðåíèè ïðàêòè÷åñêèõ çàäà÷ â
ñàìûõ ðàçíûõ ñôåðàõ: â ñåëüñêîì õîçÿéñòâå, â ïðîìûøëåííîñòè, â òîðãîâëå, íà òðàíñïîðòå, à òàêæå â äèïëîìàòè÷åñêèõ ìèññèÿõ.
 ðåàëüíîì ìèðå ÷àñòî ïîÿâëÿåòñÿ íåîáõîäèìîñòü â ñîãëàñîâàíèè äåéñòâèé ïðîèçâîäñòâåííûõ ïðåäïðèÿòèé, ìèíèñòåðñòâ, ôèðì, îáúåäèíåíèé è
äðóãèõ ó÷àñòíèêîâ ðàçëè÷íûõ ïðîåêòîâ â ñëó÷àÿõ, êîãäà èõ èíòåðåñû íå
ñîâïàäàþò. Â òàêèõ ñèòóàöèÿõ ìîäåëè òåîðèè èãð ïîçâîëÿþò íàéòè ëó÷øåå,
îïòèìàëüíîå ðåøåíèå äëÿ ïîâåäåíèÿ ó÷àñòíèêîâ, êîòîðûì ñëåäóåò ñîãëàñîâûâàòü äåéñòâèÿ ïðè ñòîëêíîâåíèè (êîíôëèêòå) èíòåðåñîâ. Íàïðèìåð,
ìîæíî îïðåäåëèòü íàó÷íî-îáîñíîâàííûå óðîâíè ñíèæåíèÿ ðîçíè÷íûõ öåí
è îïòèìàëüíûé óðîâåíü òîâàðíûõ çàïàñîâ, ðåøàòü çàäà÷è ýêñêóðñèîííîãî è òðàíñïîðòíîãî îáñëóæèâàíèÿ, çàäà÷è âûáîðà íîâûõ ëèíèé ãîðîäñêîãî
òðàíñïîðòà, çàäà÷è îðãàíèçàöèè ýêñïëóàòàöèè ìåñòîðîæäåíèé ïîëåçíûõ
èñêîïàåìûõ â ðåãèîíå è äð.
Ìíîæåñòâî âûäàþùèõñÿ ó÷åíûõ â îáëàñòè òåîðèè èãð áûëè îòìå÷åíû íîáåëåâñêèìè ïðåìèÿìè ïîñëåäíèõ ëåò ïî ýêîíîìèêå.  1994 ã. Äæ.
Íýø, Ä. Õàðñàíüè è Ð. Çåëüòåí çà âêëàä â àíàëèç ðàâíîâåñèÿ â òåîðèè
áåñêîàëèöèîííûõ èãð.  2004 ã. Ô. Êèäëàíä è Ý. Ïðåñêîòò çà èçó÷åíèå âëèÿíèÿ ôàêòîðà âðåìåíè íà êîíêóðåíòíóþ ïîëèòèêó è èññëåäîâàíèå
áèçíåñ-öèêëîâ.  2005 ã. - Ò. Øåëëèíã, ðàáîòû êîòîðîãî ñåãîäíÿ ñòàëè îñíîâîé ñîâðåìåííîãî ñòðàòåãè÷åñêîãî àíàëèçà âî âíåøíåé ïîëèòèêå, è Ð.
Àóìàí, çà óãëóáëåíèå íàøåãî ïîíèìàíèÿ ñóòè êîíôëèêòà è ñîòðóäíè÷åñòâà
ïóòåì àíàëèçà ìåòîäàìè òåîðèè èãð. Â 2007 ã. Ë. Ãóðâèö, Ð. Ìàéåðñîí, Ý.
Ìàñêèí çà ñîçäàíèå îñíîâ òåîðèè àóêöèîíîâ è îðãàíèçàöèè ñòðàòåãè÷åñêèõ
âçàèìîäåéñòâèé.
Ëþáîå ñîöèàëüíî-ýêîíîìè÷åñêîå ÿâëåíèå ïðè åãî ìàòåìàòè÷åñêîì ìîäåëèðîâàíèè âîçìîæíî, íàðÿäó ñ äðóãèìè åãî ïðåäñòàâëåíèÿìè, åùå è
ïðåäñòàâëÿòü â âèäå êîíôëèêòà, â êîòîðîì îòðàæåíû ñëåäóþùèå ìîìåíòû:
3
1. çàèíòåðåñîâàííûå ñòîðîíû (èãðîêè )
2. âîçìîæíûå äåéñòâèÿ êàæäîé èç ñòîðîí (ñòðàòåãèè êàæäîãî èãðîêà )
3. èíòåðåñû ñòîðîí [2]
Èíòåðåñû èãðîêîâ ìîãóò áûòü äèàìåòðàëüíî ïðîòèâîïîëîæíûìè, êîãäà âûèãðûø îäíîãî èãðîêà íåìèíóåìî âëå÷åò çà ñîáîé ïðîèãðûø äðóãîãî. Ïðèìåðàìè ÿâëÿþòñÿ âîåííûå êîíôëèêòû, èãðû "êðåñòèêè-íîëèêè "ìîðñêîé
áîé" è äðóãèå. Òàêèå ìîäåëè îïèñûâàþòñÿ àíòàãîíèñòè÷åñêèìè èãðàìè.
Îäíàêî â äåéñòâèòåëüíîñòè, îñîáåííî åñëè ÷èñëî èãðîêîâ áîëüøå äâóõ,
èõ èíòåðåñû ìîãóò ïåðåñåêàòüñÿ, íî íå îáÿçàòåëüíî áûòü ïðîòèâîïîëîæíûìè.  ýòîì ñëó÷àå âïîëíå ëîãè÷íî ïðåäïîëîæèòü, ÷òî çàðàíåå îãîâîðåííûå
ñîâìåñòíûå äåéñòâèÿ è îáúåäèíåíèå (êîîïåðàöèÿ ) ìîãóò ïðèâåñòè ê óâåëè÷åíèþ âûèãðûøà êàæäîãî èç ó÷àñòíèêîâ. Òàêàÿ ìîäåëü ãîðàçäî òî÷íåå
õàðàêòåðèçóåò ïðîöåññû, ïðîèñõîäÿùèå â ñîâðåìåííîì ìèðå.
Èãðû, â êîòîðûõ èãðîêè ìîãóò îáúåäèíÿòüñÿ, áóäåì íàçûâàòü êîîïåðàòèâíûìè. Äàëåå â ðàáîòå ìû áóäåì ðàññìàòðèâàòü êîîïåðàòèâíûå èãðû
â ôîðìå õàðàêòåðèñòè÷åñêîé ôóíêöèè, ôîðìàëüíîå îïðåäåëåíèå êîòîðîé
äàäèì ÷óòü ïîçæå. Ñîãëàñíî êëàññè÷åñêîé òåîðèè êîîïåðàòèâíûõ èãð ìû
ïðåäïîëàãàåì, ÷òî ïåðåä íà÷àëîì èãðû èãðîêè ïðîâîäÿò ïåðåãîâîðû, â õîäå
êîòîðûõ âûáèðàþòñÿ ñòðàòåãèè, è äàëåå, îáúåäèíÿÿñü â êîàëèöèè, ïîëó÷àþò âûèãðûø, êàê åäèíàÿ ãðóïïà. Ïðèíöèïû äåëåíèÿ ýòîãî âûèãðûøà è
ÿâëÿþòñÿ ðåøåíèåì êîîïåðàòèâíîé èãðû. Ñòîèò òàêæå îòìåòèòü, ÷òî íàñ
íå èíòåðåñóåò ïðîöåññ ïåðåãîâîðîâ, à òîëüêî åãî êîíå÷íûé ðåçóëüòàò.
Íà ïðàêòèêå ó÷àñòíèêè êîíôëèêòîâ ÷àñòî ñîâåðøàþò ñâîé âûáîð
íå îäèí ðàç è íàâñåãäà, à ïîñëåäîâàòåëüíî âî âðåìåíè, â çàâèñèìîñòè îò
ðàçâèòèÿ êîíôëèêòà. Ìàòåìàòè÷åñêèå ìîäåëè êîíôëèêòîâ, îïèñûâàþùèå
ïðîöåññû ïîñëåäîâàòåëüíîãî ïðèíÿòèÿ ðåøåíèé èãðîêàìè â èçìåíÿþùèõñÿ
óñëîâèÿõ, ò.å. ó÷èòûâàþùèå äèíàìèêó, èññëåäóþòñÿ â êëàññå ïîçèöèîííûõ
èãð. Îñíîâû òåîðèè ïîçèöèîííûõ èãð çàëîæåíû Õ. Êóíîì [8].
Íàèáîëåå ïðîñòûì òèïîì ïîçèöèîííûõ èãð ÿâëÿåòñÿ êëàññ êîíå÷íîøàãîâûõ èãð ñ ïîëíîé èíôîðìàöèåé. Èãðàìè ñ ïîëíîé èíôîðìàöèåé ÿâëÿþòñÿ èãðû, â êîòîðûõ ëþáîìó èãðîêó ìîæåò áûòü äîñòóïíà èíôîðìàöèÿ î
ñîñòîÿíèè èãðû â äàííûé ìîìåíò è âñ¼ ïðåäûäóùåå ðàçâèòèå èãðû. Åñëè
ïîðÿäîê õîäîâ îïðåäåë¼í ïðàâèëàìè è íå çàâèñèò îò õàðàêòåðèñòèê èãðîêîâ (íàïðèìåð ñêîðîñòü ðåàêöèè èëè ñêîðîñòü ïðèíÿòèÿ ðåøåíèÿ), à òàêæå
êàæäûé èãðîê èìååò èíôîðìàöèþ î âñåõ âîçìîæíûõ õîäàõ äðóãèõ èãðîêîâ,
òî ïðàêòè÷åñêè ìîæíî ñ÷èòàòü òàêóþ èãðó èãðîé ñ ïîëíîé èíôîðìàöèåé.
Áîëüøèíñòâî íàñòîëüíûõ èãð ÿâëÿþòñÿ èãðàìè ñ ïîëíîé èíôîðìàöèåé, íàïðèìåð: øàøêè, øàõìàòû, ãî, êðåñòèêè-íîëèêè. Ê èãðàì ñ íåïîëíîé
èíôîðìàöèåé ìîæíî îòíåñòè áîëüøóþ ÷àñòü êàðòî÷íûõ èãð.
4
Ïîñòàíîâêà çàäà÷è
 äàííîé ðàáîòå ââîäèòñÿ â ðàññìîòðåíèå íåñòàíäàðòíûé ñïîñîá çàäàíèÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè â ìíîãîøàãîâûõ äèñêðåòíûõ èãðàõ,
ïîçâîëÿþùèé óòâåðæäàòü ñèëüíóþ äèíàìè÷åñêóþ óñòîé÷èâîñòü ïîëó÷åííîãî ðåøåíèÿ.
 êà÷åñòâå ïðèìåðà ñòðîèòñÿ ìàòåìàòè÷åñêàÿ ìîäåëü íåòðèâèàëüíîé
ìíîãîøàãîâîé äèñêðåòíîé èãðû, êàæäûé óçåë êîòîðîé ÿâëÿåòñÿ áèìàòðè÷íîé èãðîé. Äëÿ äàííîé èãðû íåîáõîäèìî ïðîàíàëèçèðîâàòü âîçìîæíîñòü
ïîñòðîåíèÿ ðàâíîâåñèÿ ïî Íýøó, êîòîðîå áóäåò ïîääåðæèâàòü êîîïåðàöèþ.
Òàêæå íåîáõîäèìî ïðåäñòàâèòü ïðîãðàììíûé ïðîäóêò (êîìïüþòåðíóþ ðåàëèçàöèþ), ïîçâîëÿþùèé íàéòè ðåøåíèå îïðåäåëåííîé âûøå ìíîãîøàãîâîé äèñêðåòíîé èãðû äëÿ êîíêðåòíîãî ïðèìåðà. Ñ åãî ïîìîùüþ ìîæíî
íàãëÿäíî ñðàâíèòü çíà÷åíèÿ "íîâîé"è "ñòàðîé" õàðàêòåðèñòè÷åñêèõ ôóíêöèé.
5
Îáçîð ëèòåðàòóðû
 ýòîì ðàçäåëå ïðåäñòàâëåí îáçîð ëèòåðàòóðû, èñïîëüçîâàííîé ïðè
íàïèñàíèè âûïóñêíîé êâàëèôèêàöèîííîé ðàáîòû.
Îñíîâíûå îïðåäåëåíèÿ è òåîðåìû âçÿòû èç êíèã:
"Òåîðèÿ èãð" Èçä. ÁÕÂ-Ïåòåðáóðã Ïåòðîñÿí Ë. À., Çåíêåâè÷ Í.À.,
Øåâêîïëÿñ Å.Â. [5]; "Èãðû â ðàçâåðíóòîé ôîðìå: îïòèìàëüíîñòü è óñòîé÷èâîñòü" Ïåòðîñÿí Ë.À., Êóçþòèí Ä. [6]; "×àñòü 2. Êîîïåðàòèâíûå èãðû
è èãðû â ïîçèöèîííîé ôîðìå: ó÷åáíîå ïîñîáèå." Ãðèãîðüåâà Ê. [3].
Äëÿ ðàçðàáîòêè ïðîãðàììû èñïîëüçîâàëñÿ ïàêåò ïðèêëàäíûõ ïðîãðàìì "MATLAB" è îäíîèìåííûé ÿçûê ïðîãðàììèðîâàíèÿ. Ðóêîâîäñòâîì
ïî èñïîëüçîâàíèþ áûëî èçäàíèå [4].
Äëÿ ëó÷øåãî ïîíèìàíèÿ îòäåëüíûõ ðàçäåëîâ ìàòåìàòèêè, à èìåííî
äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ è òåîðèè ãðàôîâ, áûëè èçó÷åíû [1], [7].
6
Ãëàâà 1. Íåîáõîäèìûå ñâåäåíèÿ è îñíîâíûå
îïðåäåëåíèÿ
×òîáû íàèáîëåå ïîëíî îïèñàòü ðàññìàòðèâàåìóþ ñèñòåìó óïîìÿíåì
ñâåäåíèÿ èç òåîðèè ãðàôîâ è ââåäåì îñíîâíûå îïðåäåëåíèÿ èç òåîðèè èãð.
1.1. Çàäàíèå ìíîãîøàãîâîé äèñêðåòíîé èãðû íà
äðåâîâèäíîì ãðàôå
Ãðàôîì íàçûâàåòñÿ ïàðà (X, F ), ãäå X - íåêîòîðîå êîíå÷íîå ìíîæåñòâî, à F - îòîáðàæåíèå, ñòàâÿùåå â ñîîòâåòñòâèå êàæäîé òî÷êå x ∈ X
ïîäìíîæåñòâî Fx ⊂ X [7].
Ïàðó ýëåìåíòîâ (zk , zk+1 ), ãäå zk+1 ⊂ Fzk áóäåì íàçûâàòü äóãîé èëè
îðèåíòèðîâàííûì ðåáðîì. Äëÿ äóãè p = (zk , zk+1 ) âåðøèíû zk è zk+1 íàçûâàþòñÿ áîêîâûìè âåðøèíàìè äóãè.
Ïóòåì â ãðàôå (X, F ) áóäåì íàçûâàòü òàêóþ ïîñëåäîâàòåëüíîñòü
p = (p1 , p2 , ..., pk , ...) äóã, ÷òî áîêîâàÿ âåðøèíà êàæäîé ñëåäóþùåé äóãè
ãðàíè÷èò ñ áîêîâîé âåðøèíîé ïðåäûäóùåé. Äëèíà ïóòè p = (p1 , ..., pk )
- ýòî ÷èñëî äóã ïîñëåäîâàòåëüíîñòè l(p) = k . Ïîñëåäîâàòåëüíîñòü ðåáåð
p1 , ..., pk , ...,(çäåñü îðèåíòàöèÿ íå âàæíà) ãäå ó êàæäîãî pk îäíà èç áîêîâûõ
âåðøèí ÿâëÿåòñÿ òàêæå áîêîâîé äëÿ pk−1 , à äðóãàÿ - áîêîâîé äëÿ pk+1 ,
íàçûâàåòñÿ öåïüþ.
Åñëè ìåæäó ëþáîé ïàðîé âåðøèí ýòîãî ãðàôà ñóùåñòâóåò öåïü, ñîåäèíÿþøàÿ ýòè âåðøèíû, òî òàêîé ãðàô ìû íàçûâàåì ñâÿçíûì.
Äåðåâî èëè äðåâîâèäíûé ãðàô - êîíå÷íûé ñâÿçíûé ãðàô áåç öèêëîâ,
èìåþùèé íå ìåíåå äâóõ âåðøèí è åäèíñòâåííóþ íà÷àëüíóþ âåðøèíó.
Îáîçíà÷èì ãðàô (X, F ) êàê G = (X, F )
Äàäèì îïðåäåëåíèå ìíîãîøàãîâîé èãðû Γ ñ ïîëíîé èíôîðìàöèåé íà
ãðàôå G.
Îïðåäåëåíèå 1 Ïóñòü G = (X, F ) - äðåâîâèäíûé ãðàô. Ðàññìîòðèì ðàç-
áèåíèåSìíîæåñòâà âåðøèí
X íà n + 1 ìíîæåñòâî X1 , ..., Xn , Xn+1 :
T
n+1
Xl = ∅, k 6= l. Fx = ∅ äëÿ x ∈ Xn+1 .
i=1 Xi = X , Xk
Íà ìíîæåñòâå îêîí÷àòåëüíûõ ïîçèöèé Xn+1 îïðåäåëåíû n âåùåñòâåííûõ ôóíêöèé H1 (x), ..., Hn (x), x ∈ Xn+1 . Ôóíêöèþ Hi (x) i = 1, .., n
áóäåì íàçûâàòü ôóíêöèåé âûèãðûøà èãðîêà n. Ìíîæåñòâî Xi , ãäå i =
1, .., n áóäåì íàçûâàòü ìíîæåñòâîì î÷åðåäíîñòè èãðîêà i.
Ðàññìîòðèì, êàê ïðîèñõîäèò ìíîãîøàãîâàÿ èãðà, çàäàííàÿ íà äðåâîâèäíîì ãðàôå èãðû.
Ìíîæåñòâî N èãðîêîâ ïðîíóìåðîâàíî íàòóðàëüíûìè ÷èñëàìè îò 1
äî n (â ñòàíäàðòíîì îáîçíà÷åíèè N = {1, 2, ..., n}). Äîïóñòèì, âåðøèíà
z0 ∈ Xi1 , ýòî îçíà÷àåò, ÷òî â ïîçèöèè z0 ñîâåðøàåò õîä èãðîê i1 è âûáèðàåò
7
ñëåäóþùóþ âåðøèíó z1 ∈ Fz0 . Åñëè z1 ∈ Xi2 , òî õîä ñîâåðøàåò èãðîê i2 . Îí
âûáèðàåò ñëåäóþùóþ ïîçèöèþ z2 ∈ Fz1 . Òàêèì îáðàçîì, êîãäà íà k -ì øàãå
ðåàëèçóåòñÿ ïîçèöèÿ zk ∈ Xik , òî â íåé ñîâåðøàåò õîä èãðîê ik è, ñîîòâåòñòâåííî, äåëàåò ñâîé âûáîð â ïîëüçó ñëåäóþùåé ïîçèöèè zk+1 ∈ Fzk . Èãðà
ïðîäîëæàåòñÿ, ïîêà ìû íå äîñòèãíåì âåðøèíû zl ∈ Xn+1 (îêîí÷àòåëüíîé
ïîçèöèè), ãäå âûïîëíÿåòñÿ óñëîâèå Fzl = ∅.
 ðåçóëüòàòå òàêîãî çàäàíèÿ èãðû íåêîòîðàÿ ïîñëåäîâàòåëüíîñòü âåðøèí z0 , ..., zl , êîòîðàÿ îïðåäåëÿåò ïóòü â ãðàôå G, çàäàåòñÿ îäíîçíà÷íî è
òî÷íî îïðåäåëÿåò îêîí÷àòåëüíóþ ïîçèöèþ zl . Òàêæå ýòî îçíà÷àåò, ÷òî çíàÿ
îêîí÷àòåëüíóþ ïîçèöèþ zl , ìû ìîæåì îäíîçíà÷íî îïðåäåëèòü âñþ ñûãðàííóþ ïàðòèþ (ïàðòèåé òàêæå íàçûâàþò ïóòü, ðåàëèçîâàííûé íåêîé ïîñëåäîâàòåëüíîñòüþ âåðøèí). Ýòî âîçìîæíî áëàãîäàðÿ äðåâîâèäíîñòè ãðàôà,
îïèñûâàþùåãî èãðó.
Òàêèì îáðàçîì, òåîðåòè÷åñêè, â èãðàõ ñ ïîëíîé èíôîðìàöèåé, åñòü
âîçìîæíîñòü ïðåäñêàçàòü èñõîä ïàðòèè ïóòåì ïðîñ÷åòà âñåâîçìîæíûõ õîäîâ èãðîêîâ è óñòàíîâèòü òó ïîñëåäîâàòåëüíîñòü õîäîâ, êîòîðàÿ ïðèâåäåò
ê íóæíîìó ðåçóëüòàòó. Òî åñòü, ó íàñ âñåãäà åñòü âîçìîæíîñòü çàäàòü àëãîðèòì, êîòîðûé îáåñïå÷èò õîòÿ áû îäíîìó èãðîêó âûèãðûø, èëè â êðàéíåì
ñëó÷àå íè÷üþ. Îäíàêî, äëÿ áîëüøåé ÷àñòè èãð ïîñòðîèòü ýòîò àëãîðèòì
íåâîçìîæíî, ïîñêîëüêó íà ïðàêòèêå äåðåâî âñåâîçìîæíûõ âàðèàíòîâ ñëèøêîì âåëèêî, ÷òîáû áûëî âîçìîæíûì ïðîèçâåñòè ðàñ÷åò è ñäåëàòü àíàëèç
çà êàêîå-òî îïðåäåëåííîå âðåìÿ.
Ðàñìîòðèì ïîíÿòèå ïîäãðàôà, òåñíî ñâÿçàííîå ñ ïîíÿòèåì ïîäûãðû.
Ïîäãðàô Gz = (Xz , F ) äðåâîâèäíîãî ãðàôà G - ýòî ãðàô ñ íà÷àëüíîé
âåðøèíîé z (z ∈ X ), êîòîðûé âëîæåí â äåðåâî ãðàôà G è ñîäåðæèò âñå
âåðøèíû, â êîòîðûå ìîæíî ïîïàñòü èç âåðøèíû z .
Câÿæåì ñ ïîäãðàôîì Gz ïîäûãðó Γz ñëåäóþùèì îáðàçîì. Ìíîæåñòâî î÷åðåäíîñòè èãðîêîâ â ïîäûãðå Γz îïðåäåëÿåòñÿ ïî ïðàâèëó Yiz =
z
= Xn+1 ∩ Xz ,
Xi ∩ Xz , i = 1, .., n. Ìíîæåñòâî îêîí÷àòåëüíûõ ïîçèöèé Yn+1
z
âûèãðûø Hi (x) èãðîêà i â ïîäûãðå Γz ïîëàãàåì ðàâíûì
z
Hiz (x) = Hi (x), x ∈ Yn+1
, i = 1, ..., n
Íà ðèñ.1 èçîáðàæåí ïðèìåð äðåâîâèäíîãî ãðàôà G ñ ïîäãðàôîì Gz
Îïðåäåëåíèå 2 Îäíîçíà÷íîå îòîáðàæåíèå ui , êîòîðîå êàæäîé âåðøèíå
(ïîçèöèè) x ∈ Xi ñòàâèò â ñîîòâåòñòâèå íåêîòîðóþ âåðøèíó (ïîçèöèþ)
y ∈ Fx , íàçûâàåòñÿ ñòðàòåãèåé èãðîêà i.
Ìíîæåñòâî Ui - ìíîæåñòâî ñòðàòåãèé èãðîêà i. Óïîðÿäî÷åííûé íàáîð (âåêòîð) u = (u1 , ..., ui , ..., un ), ãäå ui ∈ Ui íàçûâàåòñÿ ñèòóàöèåé â èãðå, à
Q
äåêàðòîâî ïðîèçâåäåíèå U = ni=1 Ui - ìíîæåñòâîì ñèòóàöèé.
8
Ðèñ. 1
1.2 Êîîïåðàöèÿ â ìíîãîøàãîâûõ èãðàõ
Ïóñòü êîëè÷åñòâî èãðîêîâ n, N = {1, ..., n}. Ëþáîå íåïóñòîå ïîäìíîæåñòâî S ⊂ N íàçûâàåòñÿ êîàëèöèåé.
 äàëüíåéøåì ìû áóäåì ïîäðàçóìåâàòü, ÷òî âûèãðûøè îïðåäåëåíû
íå òîëüêî íà ìíîæåñòâå îêîí÷àòåëüíûõ ïîçèöèé Xn+1 , íî è äëÿ êàæäîãî
x ∈ X.
Òàêèì îáðàçîì, â ýòîì ñëó÷àå äëÿ êàæäîãî x ∈ X îïðåäåëåíû n
ïîëîæèòåëüíûõ âåùåñòâåííûõ ÷èñåë hi (x), i = 1, ..., n è äëÿ êàæäîãî ïóòè
èãðû z = (z0 , z1 , ..., zl ), zl ∈ Xn+1 ìîæíî îïðåäåëèòü âûèãðûø èãðîêà i êàê
ñóììó:
l
X
hi (zk ), hi ≥ 0.
Hi (z0 ) =
k=0
Ðàññìîòðèì, êàê ïðîèñõîäèò êîîïåðàòèâíàÿ èãðà. Ïåðåä íà÷àëîì èãðû ó÷àñòíèêè ñîãëàøàþòñÿ âûáðàòü òàêîé âåêòîð ñòðàòåãèé
ū(·) = (ū1 (·), ..., ūi (·), ..., ūn (·)),
êîòîðûé ìàêñèìèçèðóåò èõ ñóììàðíûé âûèãðûø.
Îïðåäåëåíèå 3 Êîîïåðàòèâíîé òðàåêòîðèåé, âäîëü êîòîðîé ðàçâèâàåòñÿ èãðà Γ, áóäåì íàçûâàòü òðàåêòîðèþ z̄ = (z̄0 , ..., z̄k , ..., z̄l ), z̄l ∈ Xn+1 ,
ðåàëèçîâàííóþ ñèòóàöèåé ū(·) = (ū1 , ..., ūi , ..., ūn ):
max
z0 ,...,zi ,...,zl
n X
l
X
hi (zk ) =
i=1 k=0
n X
l
X
hi (z̄k )
i=1 k=0
Î÷åâèäíî, ÷òî â èãðå Γ ìû ìîæåì èìåòü öåëîå ìíîæåñòâî êîîïåðàòèâ9
íûõ òðàåêòîðèé, êàæäàÿ èç êîòîðûõ äàñò íàì îäèíàêîâûé ìàêñèìàëüíûé
îáùèé âûèãðûø. Äëÿ ïðîñòîòû ìû ïðåäïîëîæèì, ÷òî â èãðå Γ ñóùåñòâóåò
åäèíñòâåííàÿ êîîïåðàòèâíàÿ òðàåêòîðèÿ.
Îïðåäåëåíèå 4 Õàðàêòåðèñòè÷åñêîé ôóíêöèåé èãðû n ëèö áóäåì íàçû-
âàòü âåùåñòâåííóþ ôóíêöèþ V , îïðåäåëåííóþ íà êîàëèöèÿõ S ⊂ N , ïðè
ýòîì äëÿ ëþáûõ íåïåðåñåêàþùèõñÿ êîàëèöèé T, S (T ⊂ N, S ⊂ N ) âûïîëíÿåòñÿ íåðàâåíñòâî
V (T ) + V (S) ≤ V (S ∪ T ), V (∅) = 0, S ∩ T = ∅
Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ îïèñûâàåò âåëè÷èíó ãàðàíòèðîâàííîãî ìàêñèìàëüíîãî âûèãðûøà, êîòîðóþ äàííîå ïîäìíîæåñòâî èãðîêîâ ìîæåò ïîëó÷èòü ïðè îáúåäèíåíèè â êîàëèöèþ. Èñõîäÿ èç ðàçìåðà âûïëàò, èãðîêè
ïðèíèìàþò ðåøåíèå î ñîçäàíèè êîàëèöèè.
Ïðè çàäàíèè õàðàêòåðèñòè÷åñêîé ôóíêöèè â ìíîãîøàãîâûõ èãðàõ
âàæíûì ÿâëÿåòñÿ âûïîëíåíèå óñëîâèÿ
V (N ) =
n X
l
X
hi (z̄k ), N = {1, .., n}
i=1 k=0
10
Ãëàâà 2. Óñòîé÷èâîñòü ïðèíöèïîâ îïòèìàëüíîñòè
 êëàññè÷åñêîé òåîðèè êîîïåðàòèâíûõ èãð èãðîêàì íåâûãîäíî îòêëîíÿòüñÿ îò âûáðàííûõ çàðàíåå ñòðàòåãèé, òàê êàê ýòî ìîæåò ïðèâåñòè
ê óìåíüøåíèþ îáùåãî âûèãðûøà. Â ïîçèöèîííûõ èãðàõ âñòàåò âîïðîñ îá
óñòîé÷èâîñòè (ñîñòîÿòåëüíîñòè âî âðåìåíè) âûáðàííûõ ïðèíöèïîâ îïòèìàëüíîñòè - áóäóò ëè èãðîêè ïðèäåðæèâàòüñÿ ñòðàòåãèé, îïðåäåëåííûõ ïåðåä èãðîé, ó÷èòûâàÿ åå äèíàìèêó, ò.å èçìåíÿþùèåñÿ âî âðåìåíè óñëîâèÿ. Â
ñëó÷àå äèíàìè÷åñêîé íåóñòîé÷èâîñòè ìû ìîæåì ïðèéòè ê ñîñòîÿíèþ, êîãäà îäíà èç ñòîðîí çàèíòåðåñîâàíà íàðóøèòü ñîãëàøåíèå, èç-çà ïîÿâëåíèÿ
ëó÷øåé â äàííûé ìîìåíò äëÿ ñåáÿ àëüòåðíàòèâû.
Çàäàíèå õàðàêòåðèñòè÷åñêîé ôóíêöèè ïîçâîëÿåò íàì îïðåäåëèòü ìíîæåñòâà äåëåæåé
C = {ξ = (ξi ) :
n
X
ξi = V (N ), ξi ≥ V ({i}), i = 1, ..., n},
i=1
C -ÿäðî
M = {ξ = (ξi ) :
X
ξi = V (S), S ∈ N } ⊂ C,
i∈S
âåêòîð Øåïëè
X
Shi = ξi =
{i}∈S,S:S⊂N
(s − 1)!(n − s)!
[V (S) − V (S\{i})]
n!
(ãäå s - ÷èñëî ýëåìåíòîâ ìíîæåñòâà S ⊂ N , n - ÷èñëî ýëåìåíòîâ ìíîæåñòâà N ), N M -ðåøåíèå è äðóãèå ïðèíöèïû îïòèìàëüíîñòè êëàññè÷åñêîé
òåîðèè êîîïåðàòèâíûõ èãð. ×åðåç M áóäåì îáîçíà÷àòü ëþáîé èç âûøåóïîìÿíóòûõ ïðèíöèïîâ îïòèìàëüíîñòè.
Íàïîìíèì, ÷òî ÷åðåç z̄ = (z̄0 , ..., z̄k , ...z̄l ), zl ∈ Xn+1 , ìû îáîçíà÷èëè
êîîïåðàòèâíóþ òðàåêòîðèþ.
 ïîäûãðå Γz̄k , k = 1, ..., n ââåäåì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ
V (z̄k , {S}), S ⊂ N òàêèì æå îáðàçîì, êàêèì îíà áûëà ââåäåíà â èñõîäíîé èãðå Γ = Γ(z0 ). Îñíîâûâàÿñü íà ýòîé õàðàêòåðèñòè÷åñêîé ôóíêöèè
ìîæíî àíàëîãè÷íûì îáðàçîì îïðåäåëèòü ìíîæåñòâî äåëåæåé
C(z̄k ) = {ξ = (ξi ) :
n
X
ξi = V (z̄k , {N }), ξi ≥ V (z̄k , {i}), i = 1, ..., n},
i=1
C -ÿäðî
M = {ξ = (ξi ) :
X
ξi = V (z̄k , {S}), S ∈ N } ⊂ C(z̄k ),
i∈S
11
âåêòîð Øåïëè
Shki = ξik =
X
{i}∈S,S:S⊂N
(s − 1)!(n − s)!
[V (z̄k , {S}) − V (z̄k , S\{i})]
n!
(ãäå s - ÷èñëî ýëåìåíòîâ ìíîæåñòâà S ⊂ N , n - ÷èñëî ýëåìåíòîâ ìíîæåñòâà N ), N M -ðåøåíèå è äðóãèå ïðèíöèïû îïòèìàëüíîñòè òåîðèè êîîïåðàòèâíûõ èãð. Îáîçíà÷èì M (z̄k ) ⊂ C(z̄k ) êàê ïðèíöèï îïòèìàëüíîñòè,
ðàññìàòðèâàåìûé â ïîäûãðå Γz̄k .
Îïðåäåëåíèå 5 Ïóñòü ξ = {ξ1 , ..., ξi , ..., ξn } ∈ M (z0 ). Ëþáàÿ ìàòðèöà
β = {βik }, ãäå βik ≥ 0, i = 1, ...., n k = 1, ..., l òàêàÿ, ÷òî:
ξi =
l
X
βik ,
k=0
Íàçûâàåòñÿ ïðîöåäóðîé ðàñïðåäåëåíèÿ äåëåæà (ÏÐÄ).
Pk−1
Îáîçíà÷èì βk = (β1k , ..., βnk ), à β(k) = m=0
βm .
Èíòåðïðåòèðîâàòü ÏÐÄ β ìîæíî ñëåäóþùèì îáðàçîì: βik - ýòî âûïëàòà èãðîêó i íà k øàãå èãðû Γz0 (íà ïåðâîì øàãå ïîäûãðû Γz̄k ). βk âåêòîð, ñîñòîÿùèé èç âûïëàò êàæäîìó èãðîêó íà k øàãå èãðû Γz0 , à βi (k)
- ýòî ñóììà, êîòîðóþ èãðîê i ïîëó÷àåò íà ïåðâûõ k øàãàõ èãðû Γz0 .
Îïðåäåëåíèå 6 Ïðèíöèï îïòèìàëüíîñòè M (z0 ) íàçûâàåòñÿ äèíàìè÷å-
ñêè óñòîé÷èâûì, åñëè äëÿ êàæäîãî ξ ∈ M (z0 ) ñóùåñòâóåò ÏÐÄ β , òàêàÿ
÷òî
ξ k = ξ − β(k) ∈ M (z̄k ), k = 1, ..., l
Òàêèì îáðàçîì, ïðèíöèï îïòèìàëüíîñòè M áóäåò äèíàìè÷åñêè óñòîé÷èâûì, åñëè äëÿ êàæäîãî äåëåæà ξ ∈ M ñóùåñòâóåò òàêàÿ ÏÐÄ β , ÷òî åñëè
âûïëàòû â êàæäîé ïîçèöèè z̄k îïòèìàëüíîé òðàåêòîðèè z̄ áóäóò ñäåëàíû
ñîãëàñíîé ýòîé ÏÐÄ β , òî â êàæäîé ïîäûãðå Γz̄k èãðîêè ìîãóò îæèäàòü
âûïëàò ξ¯k , êîòîðûå áóäóò îïòèìàëüíûìè â ïîäûãðå Γz̄k â òîì æå ñìûñëå,
â êàêîì îíè áûëè îïòèìàëüíû â èñõîäíîé èãðå Γz0
Îïðåäåëåíèå 7 Ïðèíöèï îïòèìàëüíîñòè M (z0 ) íàçûâàåòñÿ ñèëüíî äè-
íàìè÷åñêè óñòîé÷èâûì, åñëè äëÿ êàæäîãî ξ ∈ M (z0 ) ñóùåñòâóåò ÏÐÄ
β , òàêàÿ, ÷òî âûïîëíÿåòñÿ β(k) ⊕ M (z̄k ) ⊂ M (z0 ), k = 1, ..., l, ãäå a ⊕ A =
{a + â : â ∈ A, a ∈ Rn , A ⊂ Rn }.
Ñèëüíàÿ äèíàìè÷åñêàÿ óñòîé÷èâîñòü ïîäðàçóìåâàåò, ÷òî åñëè âûïëàòû ñäåëàíû â ñîîòâåòñòâèå ñ ÏÐÄ β , òî çàðàáîòàâ íà ïåðâûõ k øàãàõ ñóììó
β(k) è ïåðåñìàòðèâàÿ îïòèìàëüíûé äåëåæ â ýòîé ïîäûãðå (òî åñòü çàìåíÿÿ
12
îäèí îïòèìàëüíûé äåëåæ äðóãèì), èãðîêè âñå ðàâíî ïîëó÷àò â ðåçóëüòàòå
â èãðå Γz0 âûïëàòû â ñîîòâåòñòâèè ñ íåêîòîðûì äåëåæîì, îïòèìàëüíûì â
ïðåäûäóùåì ñìûñëå, ò.å. äåëåæîì, ïðèíàäëåæàùèì ìíîæåñòâó M (z0 ).
2.1. Ðåãóëÿðèçàöèÿ êëàññè÷åñêèõ ïðèíöèïîâ
îïòèìàëüíîñòè
Ïðîâåäåì òàêóþ ðåãóëÿðèçàöèþ êëàññè÷åñêèõ ïðèíöèïîâ îïòèìàëüíîñòè, êîòîðàÿ ïðèâåäåò íàñ ê ñèëüíîé äèíàìè÷åñêîé óñòîé÷èâîñòè [6].
Çàäàäèì ÏÐÄ êàê β̄ k = {βik , i = 1, ..., n}, k = 0, .., l, ãäå N = {1, ..., n}
ìíîæåñòâî âñåõ èãðîêîâ. Ôóíêöèè βik îïðåäåëåíû ñëåäóþùèì îáðàçîì:
Pn
0
ξ
hi (z0 )
βi0 = i i=1
, ξ0 ∈ C(z0 );
(1)
V (z0 , {N })
βi1
P
ξi1 ni=1 hi (z̄1 )
=
, ξ1 ∈ C(z̄1 );
V (z̄1 , {N })
...
P
ξik ni=1 hi (z̄k )
=
, ξk ∈ C(z̄k );
V (z̄k , {N })
...
P
ξil ni=1 hi (z̄l )
l
βi =
, ξl ∈ C(z̄l );
V (z̄l , {N })
βik
Î÷åâèäíî, ÷òî äëÿ ðàçëè÷íûõ äåëåæåé ξk ∈ C(z̄k ) ïîëó÷àþòñÿ ðàçëè÷íûå
ÏÐÄ β̄ k . Îáîçíà÷èì ìíîæåñòâî âñåâîçìîæíûõ β̄ k êàê B k .
Ìíîæåñòâî
C̃(z0 ) = {ξ¯ : ξ¯ =
l
X
β̄ k , β̄ k ∈ B k }
(2)
k=0
áóäåì íàçûâàòü ðåãóëÿðèçîâàííûì ïðèíöèïîì îïòèìàëüíîñòè (ÏÎ) C̃(z0 ).
Ìíîæåñòâî
¯k
¯k
C̃(zk ) = {ξ : ξ =
l
X
β̄ m , β̄ m ∈ B m }
(3)
m=k
áóäåì íàçûâàòü ðåãóëÿðèçîâàííûì ïðèíöèïîì îïòèìàëüíîñòè (ÏÎ) C̃(zk ).
Òåîðåìà 1 Åñëè ÏÐÄ β îïðåäåëåíà êàê β̄, k = 1, ..., l (1) òî âñåãäà âûïîë-
íÿåòñÿ β(k) ⊕ C̃(z̄k ) ⊂ C̃(z0 ), òî åñòü ÏÎ C̃(z0 ) ñèëüíî äèíàìè÷åñêè
13
óñòîé÷èâûé. Ìíîæåñòâî
⊕ C̃(z̄k ) ýòî ìíîæåñòâî âñåõ âåêòîðîâ âèPk−1 m β(k)
k
k
¯
¯
äà β(k) + ξ = m=0 β̄ + ξ , ãäå ξ¯k ∈ C̃(z̄k ).
Ââåä¼ì â ðàññìîòðåíèå íîâóþ ôóíêöèþ:
P
l
X
V (z̄m , {S}) ni=1 hi (z̄m )
, S ⊂ N, k = 1, ..., l
Ṽ (z̄k , {S}) =
V (z̄m , {N })
(4)
m=k
Óòâåðæäåíèå 1 Ôóíêöèÿ, çàäàâàåìàÿ ôîðìóëîé (4) îáëàäàåò ñâîéñòâîì
ñóïåðàääèòèâíîñòè.
Äîêàçàòåëüñòâî. Äîêàæåì, ÷òî âûïîëíÿåòñÿ íåðàâåíñòâî
Ṽ (z̄k , T ) + Ṽ (z̄k , S) ≤ Ṽ (z̄k , S ∪ T ),
ãäå Ṽ (∅) = 0 è S ∩ T = ∅
Ðàññìîòðèì êëàññè÷åñêóþ õàðàêòåðèñòè÷åñêóþ ôóíêöèþ. Ïî îïðåäåëåíèþ, äëÿ íåå âûïîëíÿåòñÿ íåðàâåíñòâî V (zm , {T }) + V (zm , {S}) ≤
V (zm , {S ∪ T }), äëÿ ëþáîãî zm ∈ X .
Òàê êàê õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ è ôóíêöèÿ âûèãðûøà íåîòðèöàòåëüíû, òî ìû èìååì:
Pn
Pn
V (z̄m , {T }) i=1 hi (z̄m ) V (z̄m , {S}) i=1 hi (z̄m )
+
≤
V (z̄m , {N })
V (z̄m , {N })
P
V (z̄m , {S ∪ T }) ni=1 hi (z̄m )
≤
V (z̄m , {N })
Ïðîñóììèðîâàâ ëåâóþ è ïðàâóþ ÷àñòè íåðàâåíñòâà ïî m îò k äî l ìû
ïîëó÷èì:
P
P
l
X
V (z̄m , {T }) ni=1 hi (z̄m ) V (z̄m , {S}) ni=1 hi (z̄m )
+
≤
V (z̄m , {N })
V (z̄m , {N })
m=k
P
l
X
V (z̄m , {S ∪ T }) ni=1 hi (z̄m )
≤
,
V (z̄m , {N })
m=k
P
P
l
l
X
V (z̄m , {T }) ni=1 hi (z̄m ) X V (z̄m , {S}) ni=1 hi (z̄m )
+
≤
V (z̄m , {N })
V (z̄m , {N })
m=k
m=k
P
l
X
V (z̄m , {S ∪ T }) ni=1 hi (z̄m )
≤
V (z̄m , {N })
m=k
Ṽ (z̄k , T ) + Ṽ (z̄k , S) ≤ Ṽ (z̄k , S ∪ T )
×òî è òðåáîâàëîñü äîêàçàòü.
14
Äëÿ äîêàçàòåëüñòâà ñëåäóþùåãî óòâåðæäåíèÿ íàì ïîòðåáóåòñÿ òåîðåìà î íåîáõîäèìîì è äîñòàòî÷íîì óñëîâèè ïðèíàäëåæíîñòè äåëåæà C -ÿäðó.
Ïðèâåäåì åå ôîðìóëèðîâêó.
Òåîðåìà 2 Äëÿ òîãî, ÷òîáû äåëåæ α = (α1 , .., αi , .., αn ), N = {1, ..., n}
ïðèíàäëåæàë C -ÿäðó, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû äëÿ âñåõ S ⊂ N
âûïîëíÿëèñü íåðàâåíñòâà
X
V (S) ≤ α(S) =
αi
i∈S
Óòâåðæäåíèå 2 Åñëè õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ â èãðå çàäàåòñÿ ôîðìóëîé (4), òî äåëåæè, îïðåäåëåííûå ôîðìóëàìè (2)(3) âñåãäà ïðèíàäëåæàò Ñ-ÿäðó.
Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ òåîðåìîé î íåîáõîäèìîì è äîñòàòî÷íîì
óñëîâèè ïðèíàäëåæíîñòè äåëåæà C -ÿäðó. Äîêàæåì, ÷òî âûïîëíÿåòñÿ ñëåäóþùåå íåðàâåíñòâî:
X
Ṽ (zk , {S}) ≤
ξ¯ik
i∈S
Ïðåîáðàçóåì ïðàâóþ ÷àñòü íåðàâåíñòâà. Òàê êàê
ξ¯k =
l
X
m
β̄ =
m=k
l
X
{βim , i = 1, ..., n},
m=k
òî â ïðàâîé ÷àñòè íàøåãî íåðàâåíñòâà ìû èìååì
X
i∈S
ξ¯ik =
l X
X
m=k i∈S
βim =
l X m
X
ξi
Pn
j=1 hj (z̄m )
V (N, z̄m )
m=k i∈S
, ξ m ∈ C(z̄m )
 ñèëó òîãî, ÷òî ξ m ∈ C(z̄m )
V (z̄m , {S}) ≤
X
ξim
i∈S
Çíà÷èò, äëÿ êàæäîãî îòäåëüíîãî ñëàãàåìîãî íà ïðîèçâîëüíîì øàãå ñóììèðîâàíèÿ m áóäåò âûïîëíÿòüñÿ
Pn
P
V (z̄m , {S}) n hi (z̄m ) X ξim j=1 hj (z̄m )
i=1
≤
V (z̄m , {N })
i∈S
V (z̄m , {N })
Î÷åâèäíî, ÷òî ëåâàÿ è ïðàâàÿ ÷àñòè ýòîãî íåðàâåíñòâà íåîòðèöàòåëüíû.
Ñëåäîâàòåëüíî, ïðîñóììèðîâàâ èõ ïî m = k, ..., l ìû ïîëó÷èì íåðàâåíñòâî
âèäà
15
Pn
P
l
l
X
V (z̄m , {S}) ni=1 hi (z̄m ) X X ξim j=1 hj (z̄m )
≤
,
V
(z̄
,
{N
})
V
(z̄
,
{N
})
m
m
m=k
m=k i∈S
X
ξ¯ik
Ṽ (zk , {S}) ≤
i∈S
×òî è òðåáîâàëîñü äîêàçàòü.
Òàêèì îáðàçîì, åñëè ñ÷èòàòü â èãðå Γ(z0 ) ïðèíöèïîì îïòèìàëüíîñòè ðåãóëÿðèçîâàííûé ÏÎ C̃(z0 ), çàäàâàòü õàðàêòåðèñòè÷åñêóþ ôóíêöèþ
è ÏÐÄ β ôîðìóëàìè (4) è (2)-(3) ñîîòâåòñòâåííî , òî íà îñíîâàíèè òåîðåìû (1) è äîêàçàííûõ óòâåðæäåíèé ìîæíî ãàðàíòèðîâàòü, ÷òî ïîëó÷åííîå
ðåøåíèå áóäåò ñèëüíî äèíàìè÷åñêè óñòîé÷èâûì.
16
Ãëàâà 3. Ïîñòðîåíèå ìíîãîøàãîâîé èãðû, êàæäûé
óçåë êîòîðîé ÿâëÿåòñÿ áèìàòðè÷íîé èãðîé
Îïðåäåëåíèå 8 Ñèñòåìà
Γ = (N, {Xi }i∈N , {Hi }i∈N )
â êîòîðîé N = {1, 2, ..., n} ìíîæåñòâî èãðîêîâ, Xi - ìíîæåñòâî ñòðàòåãèé èãðîêà i, Hi - ôóíêöèÿ âûèãðûøà èãðîêà i, îïðåäåëåííàÿ
Qn íà äåêàðòîâîì ïðîèçâåäåíèè ìíîæåñòâ ñòðàòåãèé èãðîêîâ X = i=1 Xi (ìíîæåñòâî ñèòóàöèé èãðû) íàçûâàåòñÿ áåñêîàëèöèîííîé èãðîé.
Êîíå÷íàÿ áåñêîàëèöèîííàÿ èãðà äâóõ ëèö íàçûâàåòñÿ áèìàòðè÷íîé èãðîé.
Ôóíêöèè âûèãðûøà ìîæíî çàïèñàòü â âèäå äâóõ ìàòðèö:
α11 . . . α1n
β11 . . . β1n
..
.
..
.
...
..
.. , H2 = B = ...
H1 = A = .
.
αm1 . . . αmn
βm1 . . . βmn
Ãäå ýëåìåíòû ìàòðèö αij è βij áóäóò ñîîòâåòñòâåííî âûèãðûøàìè 1 è 2
èãðîêîâ â ñèòóàöèè (i, j), i ∈ {1, ..., m}, j ∈ {1, ..., n}. Áèìàòðè÷íàÿ èãðà
ïðîèñõîäèò ñëåäóþùèì îáðàçîì. Ïåðâûé èãðîê âûáèðàåò íîìåð i ñòðîêè,
à âòîðîé íîìåð j ñòîëáöà. Âûèãðûøàìè èãðîêîâ ÿâëÿþòñÿ: αij = H1 (xi , yj )
è βij = H2 (xi , yj ), ñîîòâåòñòâåííî.
Ðàññìîòðèì êîíå÷íóþ ìíîãîøàãîâóþ êîîïåðàòèâíóþ èãðó Ḡ äâóõ èãðîêîâ, N = {1, 2}, ãäå êàæäûé óçåë ýòî áèìàòðè÷íàÿ èãðà Γ.  êàæäîé
âåðøèíå ìíîãîøàãîâîé èãðû Ḡ çàäàþòñÿ ðàçëè÷íûå áèìàòðè÷íûå èãðû,
òî åñòü â îáùåì ñëó÷àå Γz 6= Γz 0 , ãäå z, z 0 - âåðøèíû èãðû Ḡ.
Ïåðåõîä èç âåðøèíû z â âåðøèíó z 0 îïèñûâàåòñÿ êàê z 0 = T (z, (i, j)),
ãäå T (z, (i, j)) îïåðàòîð, êîòîðûé ñòàâèò â ñîîòâåòñòâèå âåðøèíå z âåðøèíó z 0 â çàâèñèìîñòè îò ïàðû (i, j), i ∈ {1, ..., m}, j ∈ {1, ..., n}, âûáðàííîé
èãðîêàìè â âåðøèíå z . Ìíîæåñòâà ñòðàòåãèé êàæäîãî èãðîêà â èãðàõ Γz
(ñîîòâåòñòâåííî âåðøèíàõ èãðû Ḡ) ìîãóò áûòü ðàçëè÷íû.
Âûèãðûøè êàæäîãî èãðîêà â âåðøèíå z âûãëÿäÿò ñëåäóþùèì îáðàz
çîì: h1 (z) = αij
, h2 (z) = βijz .
Ïîñòðîèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ â èãðå Γz .
z
V (z, {1}) = max min αij
i
j
V (z, {2}) = max min βijz
j
i
z
V (z, {1, 2}) = max[αij
+ βijz ]
i,j
17
Ïóñòü z̄ = (z̄0 , ..., z̄k , ..., z̄n ) - êîîïåðàòèâíàÿ òðàåêòîðèÿ, ãäå z̄n - êîíå÷íàÿ âåðøèíà.
Îáúåäèíÿÿñü â êîàëèöèþ, èãðîêè ñòðåìÿòñÿ ìàêñèìèçèðîâàòü ñâîé
ñóììàðíûé âûèãðûø.
Ïîñòðîèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ â èãðå Ḡ. Ðàññìîòðèì Ḡz̄n .
zn
W (zn , 0, {1, 2}) = max[αij
+ βijzn ]
i,j
zn
W (zn , 0, {1}) = max min αij
i
j
W (zn , 0, {2}) = max min βijzn
j
i
Òàê êàê ïåðåõîä â ñëåäóþùóþ âåðøèíó çàâèñèò îò òîãî, êàêîé âûáîð áûë
ñäåëàí èãðîêàìè íà ïðåäûäóùåì øàãå, äëÿ òîãî ÷òîáû ïîëó÷èòü ìàêñèìàëüíûé ñóììàðíûé âûèãðûø â êîíöå èãðû Ḡ íàì íåäîñòàòî÷íî ïðîñòî
èñêàòü ìàêñèìóì ñóììû âûèãðûøåé íà êàæäîì øàãå. Èíà÷å ãîâîðÿ, ìàêñèìàëüíûé ñóììàðíûé âûèãðûø íå ðàâåí ñóììå ìàêñèìàëüíûõ âûèãðûøåé. Èñïîëüçóÿ ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ [1] ìîæíî ëåãêî
ïîêàçàòü, ÷òî èìåþò ìåñòî ñëåäóþùèå ñîîòíîøåíèÿ.
Ðàññìîòðèì Ḡz̄n−1 :
z
z
W (zn−1 , 1, {1, 2}) = max[αijn−1 + βijn−1 + W (T (z̄n−1 , (i, j)), 0, {1, 2})]
i,j
z
W (zn−1 , 1, {1}) = max min[αijn−1 + W (T (z̄n−1 , (i, j)), 0, {1})]
i
j
z
W (zn−1 , 1, {2}) = max min[βijn−1 + W (T (z̄n−1 , (i, j)), 0, {2})]
j
i
Ïðîäîëæàÿ ïî àíàëîãèè, ïîëó÷èì äëÿ Ḡz0 :
z0
W (z0 , n, {1, 2}) = max[αij
+ βijz0 + W (T (z0 , (i, j)), n − 1, {1, 2})]
i,j
z0
W (z0 , n, {1}) = max min[αij
+ W (T (z0 , (i, j)), n − 1, {1})]
i
j
W (z0 , n, {2}) = max min[βijz0 + W (T (z0 , (i, j)), n − 1, {2})]
j
Ḡ:
i
Çíàÿ õàðàêòåðèñòè÷åñêóþ ôóíêöèþ, ìîæåì ïîñòðîèòü C -ÿäðî â èãðå
C(z0 ) = {α = (α1 , α2 ) : α1 + α2 = W (z0 , n, {1, 2})},
α1 ≥ W (z0 , n, {1})
α2 ≥ W (z0 , n, {2})
Ôîðìóëû äëÿ âû÷èñëåíèÿ íîâîé õàðàêòåðèñòè÷åñêîé ôóíêöèè (4) W̃
18
áóäóò âûãëÿäåòü ñëåäóþùèì îáðàçîì:
W̃ (z̄k , n + 1 − k, {1}) =
z̄k
n
X
W (z̄m , n + 1 − m, {1})(αij
+ βijz̄k )
m=k
W̃ (z̄k , n + 1 − k, {2}) =
W (z̄m , n + 1 − m, {1, 2})
z̄k
n
X
W (z̄m , n + 1 − m, {2})(αij
+ βijz̄k )
m=k
W (z̄m , n + 1 − m, {1, 2})
, k = 0, ..., n
, k = 0, ..., n
Î÷åâèäíî, ÷òî äëÿ ñëó÷àÿ äâóõ èãðîêîâ çíà÷åíèÿ ñëåäóþùèõ õàðàêòåðèñòè÷åñêèõ ôóíêöèé ñîâïàäàþò W (z̄k , n + 1 − k, {1, 2}) = W̃ (z̄k , n + 1 −
k, {1, 2}), k = 0, ...n.
Ôóíêöèè, çàäàþùèå ÏÐÄ β , i ∈ {1, 2}, k = 0, .., n ïðèìóò âèä:
βi0
z0
ξi0 (αij
+ βijz0 )
=
, ξ0 ∈ C(z0 );
W (z0 , {1, 2})
..
.
βik
z̄k
ξik (αij
+ βijz̄k )
, ξk ∈ C(z̄k );
=
W (z̄k , {1, 2})
..
.
Íà ðèñ. 2 ïðåäñòàâëåíà ñõåìà èãðû â ïðîñòåéøåì ñëó÷àå, åñëè â êàæäîé âåðøèíå, i ∈ {1, 2}, j ∈ {1, 2}. Âåðøèíû ïåðåíóìåðîâàíû íàòóðàëüíûìè ÷èñëàìè îò 1 äî 21, äâîéíûìè èíäåêñàìè â êðóãëûõ ñêîáêàõ îáîçíà÷åíà
ïàðà ñòðàòåãèé, âûáðàííàÿ íà ïðåäûäóùåì øàãå. Òàêèì îáðàçîì, åñëè â
âåðøèíå 1 ðåàëèçóåòñÿ ñèòóàöèÿ (2,1), òî èãðà ïåðåõîäèò â âåðøèíó 4. Åñëè,
íàïðèìåð, â âåðøèíå 4 ðåàëèçóåòñÿ ñèòóàöèÿ (1,1), òî êîíå÷íîé âåðøèíîé
â èãðå áóäåò âåðøèíà 14.
Ðèñ. 2
19
Ðèñ. 3: Çíà÷åíèÿ
W (z0 ) è W̃ (z0 ) äëÿ èãðîêà
1
Ðèñ. 5: Çíà÷åíèÿ
èãðîêà 1
Ðèñ. 4: Çíà÷åíèÿ
W (z0 ) è W̃ (z0 ) äëÿ èãðîêà
2
ξ1 ∈ C( z0 ) è ξ1 ∈ C̃( z0 ) äëÿ
Ðèñ. 6: Çíà÷åíèÿ
ξ2 ∈ C( z0 ) è ξ2 ∈ C̃( z0 ) äëÿ
èãðîêà 2
Ðåøåíèå ïîäîáíûõ èãð ïðîöåññ òðóäîåìêèé èç-çà îáøèðíîñòè äðåâîâèäíîãî ãðàôà, îïèñûâàþùåãî èãðó, è, êàê áûëî ñêàçàíî âûøå, íå âñåãäà ñóùåñòâóåò âîçìîæíîñòü ÷èñëåííî ðåàëèçîâàòü àëãîðèòì, ïîçâîëÿþùèé íàéòè ðåøåíèå è ïðîâåñòè àíàëèç.
 ïàêåòå ïðèêëàäíûõ ïðîãðàìì MATLAB (ñì. ïðèëîæåíèå), áûëà
ðåàëèçîâàíà ïðîãðàììà, ïîçâîëÿþùàÿ íàéòè ðåøåíèå â ïðîñòîì ñëó÷àå,
åñëè êîëè÷åñòâî øàãîâ (óðîâíåé äðåâîâèäíîãî ãðàôà) ðàâíî òðåì.
Äëÿ òîãî, ÷òîáû îöåíèòü (ñðàâíèòü) çíà÷åíèÿ ôóíêöèé W (z0 ) è W̃ (z0 ),
äëÿ êàæäîãî èãðîêà, áûëà ïðîâåäåíà ñåðèÿ ýêñïåðèìåíòîâ èç äåñÿòè èãð.
Ìàòðèöû âûèãðûøåé èãðîêîâ çàïîëíÿëèñü ñëó÷àéíûìè öåëûìè ÷èñëàìè
â èíòåðâàëå [0;10].
Íà ðèñ.(3)-(4) èçîáðàæåíû çíà÷åíèÿ W (z0 ) è W̃ (z0 ) â ðàçíûõ èãðàõ.
Ñåðûì öâåòîì îáîçíà÷åíû çíà÷åíèÿ W̃ (z0 ), ÷¼ðíûì - W (z0 ).
20
Íà ðèñ.(5)-(6) èçîáðàæåíû çíà÷åíèÿ äåëåæåé, êîòîðûå ïîëó÷àþò èãðîêè â ðàçíûõ èãðàõ. Ñåðûì öâåòîì îáîçíà÷åíû çíà÷åíèÿ äåëåæåé, â ñëó÷àå èñïîëüçîâàíèÿ êëàññè÷åñêîãî ÏÎ C(z0 ), ÷¼ðíûì - ðåãóëÿðèçîâàííîãî
ÏÎ C̃(z0 ).
Î÷åâèäíî, ÷òî ìû íå ìîæåì óòâåðæäàòü ÿâíûé âèä ñîîòíîøåíèÿ
ìåæäó ïîëó÷åííûìè çíà÷åíèÿìè, ðàâíî êàê è îïðåäåëèòü, îò ÷åãî çàâèñÿò ýòè ñîîòíîøåíèÿ.
21
Ãëàâà 4. Ñòðàòåãè÷åñêàÿ ïîääåðæêà
Ïîñòðîèì èãðó Ḡ∞ , íà îñíîâå èãðû Ḡ, ðàññìîòðåííîé â ïðåäûäóùåé
ãëàâå. Îïèøåì êàê ïðîèñõîäèò èãðà.
 èãðå Ḡ∞ áåñêîíå÷íîå ÷èñëî øàãîâ.  äàííîé ãëàâå ðàññìîòðèì íàèáîëåå ïðîñòîé ñëó÷àé, êîãäà îïåðàòîð T (z) íå çàâèñèò îò ïðåäûäóùåãî ðàçâèòèÿ èãðû. Ïåðåõîä èç âåðøèíû z â âåðøèíó z 0 çàäàåòñÿ êàê z 0 = T (z),
ãäå T (z) - îïåðàòîð, êîòîðûé ñòàâèò â ñîîòâåòñòâèå âåðøèíå z âåðøèíó
z 0 . Îïåðàòîð T (z) íå çàâèñèò îò ïàðû (i, j), âûáèðàåìîé íà ïðåäûäóùåì
øàãå, òàêèì îáðàçîì èãðà äâèæåòñÿ ïî îïðåäåëåííîé, çàäàâàåìîé èçíà÷àëüíî òðàåêòîðèè (z0 , z1 , ..., zk , ...). Èãðà Ḡ∞ ýòî ïîñëåäîâàòåëüíîñòü èãð
{Γz0 , Γz1 , ..., Γzk , ...}. Ïåðåîáîçíà÷èì Γz1 êàê Γ1 , Γz2 êàê Γ2 è òàê äàëåå. Òàêèì îáðàçîì ìû ïîëó÷èëè èãðó
Ḡ∞ = {Γz0 , Γz1 , ..., Γzk , ...} = {Γ1 , Γ2 , ..., Γk , ...},
k
ãäå Γk = {Ak , B k }, Ak = {αij
}, B k = {βijk } äëÿ ∀k .
Ïîäûãðà Ḡ∞
k çàäàåòñÿ êàê
Ḡ∞
k = {Γk , Γk+1 , ...}.
Íà êàæäîì øàãå èãðû Ḡ∞ èãðîêè ïîìíÿò âñå âûáðàííûå èìè è ïàðòíåðàìè ñòðàòåãèè äî äàííîãî øàãà. Òî åñòü íà øàãå k êàæäûé èç èãðîêîâ
çíàåò "èñòîðèþ"
(i0 , i1 , ..., ik−1 , j0 , j1 , ..., jk−1 )
Îïðåäåëèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ â èãðàõ Γk :
k
Vk ({1}) = max min αij
i
j
Vk ({2}) = max min βijk
j
i
k
Vk ({1, 2}) = max[αij
+ βijk ]
i,j
Âûèãðûø êàæäîãî èãðîêà â èãðå Ḡ∞ :
H01
=
∞
X
δ l αill jl , 0 < δ < 1
l=0
H02
=
∞
X
δ l βill jl , 0 < δ < 1
l=0
22
Âûèãðûø êàæäîãî èãðîêà â ïîäûãðå Ḡ∞
k :
Hk1
∞
X
=
δ l−k αill jl , 0 < δ < 1
l=k
Hk2
=
∞
X
δ l−k βill jl , 0 < δ < 1
l=k
Òåïåðü ïîñòðîèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ â èãðå Ḡ∞ . Òàê êàê ïîñëåäîâàòåëüíîñòü èãð Γk îïðåäåëåíà çàðàíåå è íå çàâèñèò îò âûáîðà èãðîêîâ
â òå÷åíèå èãðû Ḡ∞ , òî ïðîöåññ ïîñòðîåíèÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè
çíà÷èòåëüíî óïðîùàåòñÿ: ÷òîáû ïîëó÷èòü ìàêñèìàëüíûé âûèãðûø íà âñåé
èãðå Ḡ∞ , äîñòàòî÷íî ìàêñèìèçèðîâàòü âûèãðûø â êàæäîé èãðå Γk . Òàêèì
îáðàçîì
max(H01
i,j
W0 ({1, 2}) =
= max
i,j
W0 ({1, 2}) =
∞
X
l
(αij
+
βijl )
∞
∞
X
X
l l
= max(
δ αij +
δ l βijl ) =
i,j
=
∞
X
δ
l
l
(max(αij
i,j
W0 ({1}) =
δ
l
l=0
+
βijl ))
i,j
=
∞
X
δ l Vl ({1, 2}), 0 < δ < 1
l=0
= max min
i
l=0
l
δ l (max(αij
+ βijl )),
l=0
max min H01
i
j
∞
X
l=0
∞
X
l=0
l=0
W0 ({1}) =
δ
l
+
H02 )
j
l
(max min αij
)
i
j
∞
X
l
δ l αij
l=0
=
=
∞
X
l=0
∞
X
l
δ l (max min αij
)
i
j
δ l Vl ({1}), 0 < δ < 1
l=0
Àíàëîãè÷íî äëÿ W0 ({2})
W0 ({2}) =
∞
X
δ
l
l=0
(max min βijl )
j
i
=
∞
X
δ l Vl ({2}), 0 < δ < 1
l=0
Ïîñòðîèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ â èãðå Ḡ∞
k , èñïîëüçóÿ òå æå ðàññóæäåíèÿ:
Wk ({1}) =
∞
X
l=k
δ
l−k
l
(max min αij
)
i
j
23
=
∞
X
l=k
δ l−k Vl ({1}), 0 < δ < 1
Wk ({2}) =
∞
X
δ
l−k
l=k
Wk ({1, 2}) =
∞
X
l=k
δ
l−k
(max min βijl )
j
i
l
(max(αij
i,j
+
=
βijl ))
∞
X
δ l−k Vl ({2}), 0 < δ < 1
l=k
=
∞
X
δ l−k Vl ({1, 2}), 0 < δ < 1
l=k
Ðàâíîâåñèå ïî Íýøó ïîääåðæèâàåò êîîïåðàöèþ, åñëè ïðè åãî ðåàëèçàöèè
ìû ïîëó÷àåì êîîïåðàòèâíóþ òðàåêòîðèþ.
Ðàññìîòðèì ñèòóàöèþ, äàþùóþ íàì êîîïåðàòèâíóþ òðàåêòîðèþ
(ī0 , ī1 , ..., j̄0 , j̄1 , ...).
 ñëó÷àå, åñëè îäèí èç èãðîêîâ îòêëîíÿåòñÿ îò êîîïåðàòèâíîé òðàåêòîðèè, òî âòîðîé èãðîê íà÷èíàåò èãðàòü ïðîòèâ íåãî. Âòîðîé èãðîê ñòðåìèòñÿ ìèíèìèçèðîâàòü âûèãðûø îòêëîíèâøåãîñÿ èãðîêà, ïðèìåíÿÿ ñòðàòåãèè íàêàçàíèÿ. Cìûñë ñòðàòåãèé íàêàçàíèÿ çàêëþ÷àåòñÿ â òîì, ÷òî èãðîê
âûíóæäàåò ñâîåãî ïàðòíåðà ïðèäåðæèâàòüñÿ îïðåäåëåííîãî ïóòè â èãðå,
èñïîëüçóÿ ïîñòîÿííóþ óãðîçó ïåðåõîäà íà ñòðàòåãèþ, îïòèìàëüíóþ â èãðå
ïðîòèâ ïàðòíåðà [3].
Ïóñòü íà k -îì øàãå ïåðâûé èãðîê îòêëîíèëñÿ îò êîîïåðàòèâíîé òðàåêòîðèè, âûáðàâ ik âìåñòî īk . Âòîðîé èãðîê óçíàåò îá ýòîì íà øàãå (k + 1)
è íà÷èíàåò èãðàòü ïðîòèâ íåãî.
Ïðåäïîëîæèì, ÷òî çà ïðèíöèï îïòèìàëüíîñòè èãðîêè ïðèíèìàþò âåêòîð Øåïëè.
Sh1 = ξ1 =
(1 − 1)!(2 − 1)!
(2 − 1)!(2 − 2)!
W ({1}) +
[W ({1, 2}) − W ({2})]
2!
2!
W ({1, 2} − W ({1}) − W ({2}))
2
Àíàëîãè÷íî äëÿ âòîðîé êîìïîíåíòû
Sh1 = ξ1 = W ({1}) +
Sh2 = ξ2 = W ({2}) +
W ({1, 2} − W ({1}) − W ({2}))
2
Äëÿ ïîäûãðû Ḡ∞
k
Shk1 = ξ1k = Wk ({1}) +
Wk ({1, 2} − Wk ({1}) − Wk ({2}))
2
Wk ({1, 2} − Wk ({1}) − Wk ({2}))
2
Ðàññìîòðèì âûèãðûø, êîòîðûé ïîëó÷èò îòêëîíèâøèéñÿ íà k -îì øàãå èãShk2 = ξ2k = Wk ({2}) +
24
ðîê íà âñåé èãðå Ḡ∞ , êîãäà âòîðîé èãðîê åãî "íàêàçûâàåò":
k−1
X
δ s αis¯s j¯s
k
+ āk δ + δ
∞
X
k+1
s=0
k
δ s−(k+1) Vs ({1}), āk = max αij
, (4.1)
i,j
s=k+1
ãäå āk ìàêñèìàëüíûé âûèãðûø êîòîðûé ìîæåò ïîëó÷èòü ïåðâûé èãðîê
íà øàãå k â ñëó÷àå îòêëîíåíèÿ.
Äëÿ ïîñòðîåíèÿ ðàâíîâåñèÿ ïî Íýøó íàëîæèì îãðàíè÷åíèÿ íà èãðó.
Ïóñòü supk Vk ({1}) = Vm ({1}) = V̂ ({1}) è supk Vk ({2}) = Vm ({2}) =
V̂ ({2}). Ïîòðåáóåì, ÷òîáû âûïîëíÿëèñü ñëåäóþùèå íåðàâåíñòâà:
V̂ ({1}) < ∞, V̂ ({2}) < ∞
min
k
Wk ({1, 2} − Wk ({1}) − Wk ({2}))
=b>0
2
āk < b
Äîêàæåì, ÷òî âåëè÷èíà (4.1) ìåíüøå âûèãðûøà, ïîëó÷àåìîãî ïåðâûì
èãðîêîì â ñëó÷àå êîîïåðàöèè íà âñåé èãðå Ḡ∞ . Òî åñòü ïîêàæåì, ÷òî ìû
ìîæåì ñòðàòåãè÷åñêè ïîääåðæàòü êîìïîíåíòó âåêòîðà Øåïëè.
Òàê êàê íà ïåðâûõ k − 1 øàãàõ èãðîê ïðèäåðæèâàëñÿ êîîïåðàòèâíîé
òðàåêòîðèè, òî íàì äîñòàòî÷íî îöåíèòü íåðàâåíñòâî:
k
āk δ + δ
∞
X
k+1
δ s−(k+1) Vs ({1}) < ξ1k
s=k+1
Ïðåîáðàçóåì åãî.
k
āk δ + δ
k+1
∞
X
δ s−(k+1) Vs ({1}) < Wk ({1}) +
Wk ({1,2}−Wk ({1})−Wk ({2}))
2
s=k+1
k
āk δ + δ
k+1
∞
X
δ s−(k+1) Vs ({1}) < Wk ({1}) + b
s=k+1
Çàìåíèì Vs ({1}) íà V̂ ({1}) (ïðåäïîëàãàåì íàèëó÷øèé âàðèàíò äëÿ îòêëîíèâøåãîñÿ èãðîêà) è ïðèìåíèì ôîðìóëó ñóììû áåñêîíå÷íîé ãåîìåòðè÷åñêîé ïðîãðåññèè
k
āk δ + δ
k+1
∞
X
δ s−(k+1) V̂ ({1}) < Wk ({1}) + b
s=k+1
āk δ k + δ k+1
1
V̂ ({1}) < Wk ({1}) + b
1+δ
25
Îáîçíà÷èì
ˆ
inf Vk ({1}) = V̂ ({1})
k
Wk ({1}) =
∞
X
δ
l−k
Vl ({1}) >
∞
X
ˆ
δ l−k V̂ ({1})
l=k
l=k
∞
k
āk δ + δ
k+1
X
1
ˆ
δ l−k V̂ ({1}) + b
V̂ ({1}) <
1+δ
l=k
1
1 ˆ
V̂ ({1}) + b
V̂ ({1}) <
1+δ
1+δ
ˆ
δ k+1 V̂ ({1}) − V̂ ({1})
< b − āk δ k
1−δ
ˆ
V̂ ({1}) − δ k+1 V̂ ({1})
> āk δ k − b
1−δ
Ñ ó÷åòîì ââåäåííûõ îãðàíè÷åíèé,î÷åâèäíî, ÷òî ïðàâàÿ ÷àñòü íåðàâåíñòâà âñåãäà îòðèöàòåëüíà. Òàê êàê 0 < δ < 1, ìû âñåãäà ìîæåì ïîäîáðàòü òàêîå δ , ïðè êîòîðîì ÷èñëèòåëü â ëåâîé ÷àñòè ïîëîæèòåëåí. À çíà÷èò
íåðàâåíñòâî âåðíîå.
Àíàëîãè÷íûå ðàññóæäåíèÿ ìîæíî ïðèâåñòè äëÿ ñëó÷àÿ, êîãäà îòêëîíÿåòñÿ âòîðîé èãðîê.
Òàêèì îáðàçîì ìû óáåäèëèñü, ÷òî ïðè îãðàíè÷åíèÿõ âèäà
āk δ k + δ k+1
sup Vk ({1}) = Vm ({1}) = V̂ ({1}) = V̂ ({1}) < ∞
k
sup Vk ({2}) = Vm ({2}) = V̂ ({2}) = V̂ ({2}) < ∞
k
min
k
Wk ({1, 2} − Wk ({1}) − Wk ({2}))
=b>0
2
āk < b
ðàâíîâåñèå ïî Íýøó â ñòðàòåãèÿõ íàêàçàíèÿ ïîääåðæèâàåò êîîïåðàöèþ, òî
åñòü ïðè åãî ðåàëèçàöèè ìû ïîëó÷àåì êîîïåðàòèâíóþ òðàåêòîðèþ.
26
Âûâîäû
 äàííîé ðàáîòå áûë ðàññìîòðåí íîâûé ñïîñîá çàäàíèÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè. Äîêàçàíû óòâåðæäåíèÿ, ïîçâîëÿþùèå ãîâîðèòü î ñèëüíîé äèíàìè÷åñêîé óñòîé÷èâîñòè ïðèíöèïîâ îïòèìàëüíîñòè â ìíîãîøàãîâûõ äèñêðåòíûõ èãðàõ. Ïîñòðîåíà ìàòåìàòè÷åñêàÿ ìîäåëü íåòðèâèàëüíîé
ìíîãîøàãîâîé äèñêðåòíîé èãðû, êàæäûé óçåë êîòîðîé ÿâëÿåòñÿ áèìàòðè÷íîé èãðîé.
Ðåàëèçîâàí ïðîãðàììíûé ïðîäóêò â ñðåäå MATLAB äëÿ ðåøåíèÿ âûøåîïèñàííîé èãðû, ñ ïîìîùüþ êîòîðîãî ïîëó÷åíû ðåøåíèÿ íåñêîëüêèõ
èãð. Ýòè äàííûå ïîçâîëèëè íàì ïðîâåñòè íàãëÿäíûé ñðàâíèòåëüíûé àíàëèç ñ ïîìîùüþ ãðàôèêîâ. Òàêæå óäàëîñü ïîñòðîèòü ðàâíîâåñèå ïî Íýøó â
ñòðàòåãèÿõ íàêàçàíèÿ äëÿ ðàññìàòðèâàåìîé ìíîãîøàãîâîé èãðû, ÷òî îáåñïå÷èâàåò ñòðàòåãè÷åñêóþ ïîääåðæêó êîîïåðàöèè.
Èñõîäÿ èç ïîëó÷åííûõ ðåçóëüòàòîâ, ìîæíî ñäåëàòü âûâîä, ÷òî çàäà÷è, ïîñòàâëåííûå â íà÷àëå ðàáîòû, âûïîëíåíû.
27
Çàêëþ÷åíèå
 çàêëþ÷åíèå ìîæíî äîáàâèòü âîçìîæíûå äàëüíåéøèå ïóòè ðàçâèòèÿ äàííîé âûïóñêíîé êâàëèôèêàöèîííîé ðàáîòû:
• Îáîáùåíèå ðàññìàòðèâàåìîé ìíîãîøàãîâîé èãðû è ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè íà ñëó÷àé n ëèö.
• Àíàëèòè÷åñêîå îáîñíîâàíèå ðåçóëüòàòîâ, ïîëó÷åííûõ ýìïèðè÷åñêèì ïóòåì
• Ðåàëèçàöèÿ ïðîãðàììíîãî ïðîäóêòà, ïîçâîëÿþùåãî íàéòè ðåøåíèÿ äëÿ
áîëüøåãî ÷èñëà øàãîâ
28
Ñïèñîê ëèòåðàòóðû
[1] Áåëëìàí Ð. Äèíàìè÷åñêîå ïðîãðàììèðîâàíèå. Ì.: Èíîñòðàííàÿ ëèòåðàòóðà, 1960. 400 ñòð.
[2] Âîðîáüåâ Í.Í. Òåîðèÿ èãð äëÿ ýêîíîìèñòîâêèáåðíåòèêîâ. Ì.: Íàóêà,
1985. 272 ñ.
[3] Ãðèãîðüåâà Ê.Â. ×àñòü 2. Êîîïåðàòèâíûå èãðû è èãðû â ïîçèöèîííîé
ôîðìå: ó÷åáíîå ïîñîáèå. Ì.: ÑÏá. ãîñ.àðõèò.-ñòðîèò.óí-ò.,2009.141 ñ.
[4] Êîëïàê Å.Ï., Áàëûêèíà Þ.Å. Ââåäåíèå â Matlab. Ñîëî, 2013. 302 ñ.
[5] Ïåòðîñÿí Ë. À., Çåíêåâè÷ Í. À., Øåâêîïëÿñ Å. Â. Òåîðèÿ Èãð. Ì.: ÁÕÂÏåòåðáóðã, 2012. 424 ñ.
[6] Ïåòðîñÿí Ë.À., Êóçþòèí Ä.Â. Èãðû â ðàçâåðíóòîé ôîðìå: îïòèìàëüíîñòü è óñòîé÷èâîñòü. ÑÏá.: ÑÏáÃÓ, 2000.292 ñ.
[7] Õàðàðè Ô. Òåîðèÿ ãðàôîâ. Ì.: ÊîìÊíèãà, 2006. 296ñ.
[8] Kuhn H. W. Extensive games and the problem of information // Annals of
Mathematics Studies, 1953
29
Ïðèëîæåíèå
y=Creatematrix(3)
y2=Cmat(2)
[y2 V3 h1 h2 k1 k2]=v3(y)
[y2 V1]=v1(y, k1, k2)
[y2 V2]=v2(y, k1, k2)
vtilde1=vtilde(V1,V3,h1,h2)
vtilde2=vtilde(V2,V3,h1,h2)
[c1]=core(V1(1),V2(1),V3(1))
[c2]=core(V1(2),V2(2),V3(2))
[c3]=core(V1(3),V2(3),V3(3))
core1=[c1(1) c2(1) c3(1)]
core2=[c1(2) c2(2) c3(2)]
ctilde1=ctilde(core1,h1, h2, V3)
ctilde2=ctilde(core2,h1, h2, V3)
filename='diploma.xls'
xlswrite=(filename, V1,'B1')
xlswrite=(filename, vtilde1,'B2')
xlswrite=(filename, V2,'B3')
xlswrite=(filename, vtilde2,'B4')
xlswrite=(filename, ctilde1,'B2')
xlswrite=(filename, V2,'B2')
function [ y2, V3, h1, h2, k1, k2 ] = v3( y )
y2=Cmat(2)
V3=zeros(1,3)
h1=zeros(1,3)
h2=zeros(1,3)
for k=1:16 %%Äëÿ V3
for m=1:2
for n=1:2
h=y(3).mat(m,n,1,k)+y(3).mat(m,n,2,k)
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
30
i=2, j=2
end
if y2(2).mat(i,j,3,round((k+1)/4))<h
y2(2).mat(i,j,3,round((k+1)/4))=h
end
end
end
y2(2).mat(i,j,3,round((k+1)/4))=y2(2).mat(i,j,3,round((k+1)/4))+
y(2).mat(i,j,1,round((k+1)/4))+y(2).mat(i,j,2,round((k+1)/4))
end
for k=1:4
for m=1:2
for n=1:2
h=max(max(y2(2).mat(:,:,3,k)))
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
i=2, j=2
end
y2(1).mat(i,j,3,1)=h+y(1).mat(i,j,1,1)+y(1).mat(i,j,2,1)
end
end
end
V3(1)=max(max(y2(1).mat(:,:,3,1)))
[i j]=mm3(y2(1).mat(:,:,3,:))
h1(1)=y(1).mat(i,j,1,:)
h2(1)=y(1).mat(i,j,2,:)
V3(2)=max(max(y2(1).mat(:,:,3,:)))y(1).mat(i,j,1,:)-y(1).mat(i,j,2,:)
if i==1 & j==1
k1=1;
end
if i==1 & j==2
k1=2;
end
31
if i==2 & j==1
k1=3;
end
if i==2 & j==2
k1=4;
end
[i1 j1]=mm3(y2(2).mat(:,:,3,k1))
h1(2)=y(2).mat(i1,j1,1,k1)
h2(2)=y(2).mat(i1,j1,2,k1)
V3(3)=max(max(y2(2).mat(:,:,3,k1)))-y(2).mat(i1,j1,1,k1)y(2).mat(i1,j1,2,k1)
[i3 j3]=mm3(y2(2).mat(:,:,3,k1))
if i3==1 & j3==1 & k1==1
k2=1;
end
if i3==1 & j3==2 & k1==1
k2=2;
end
if i3==2 & j3==1 & k1==1
k2=3;
end
if i3==2 & j3==2 & k1==1
k2=4;
end
if i3==1 & j3==1 & k1==2
k2=5;
end
if i3==1 & j3==2 & k1==2
k2=6;
end
if i3==2 & j3==1 & k1==2
k2=7;
end
if i3==2 & j3==2 & k1==2
k2=8;
end
if i3==1 & j3==1 & k1==3
k2=9;
end
if i3==1 & j3==2 & k1==3
k2=10;
end
32
if i3==2 & j3==1 & k1==3
k2=11;
end
if i3==2 & j3==2 & k1==3
k2=12;
end
if i3==1 & j3==1 & k1==4
k2=13;
end
if i3==1 & j3==2 & k1==4
k2=14;
end
if i3==2 & j3==1 & k1==4
k2=15;
end
if i3==2 & j3==2 & k1==4
k2=16;
end
[i4 j4]=mm3(y(3).mat(:,:,1,k2)+y(3).mat(:,:,2,k2))
h1(3)=y(3).mat(i4,j4,1,k2)
h2(3)=y(3).mat(i4,j4,2,k2)
end
function [ y2, V2 ] = v2(y, k1, k2)
V2=zeros(1,3)
for k=1:16 %%Äëÿ V2
h=maxmin2(y(3).mat(:,:,2,k))
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
i=2, j=2
end
y2(2).mat(i,j,2,round((k+1)/4))=h+y(2).mat(i,j,2,round((k+1)/4))
end
for k=1:4
h=maxmin2(y2(2).mat(:,:,2,k))
33
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
i=2, j=2
end
y2(1).mat(i,j,2,1)=h+y(1).mat(i,j,2,1)
end
V2(1)=maxmin2(y2(1).mat(:,:,2,1))
V2(3)=maxmin2(y(3).mat(:,:,2,k2))
A(1,1)=maxmin2(y(3).mat(:,:,2,4*(k1-1)+1))+y(2).mat(1,1,2,k1)
A(1,2)=maxmin2(y(3).mat(:,:,2,4*(k1-1)+2))+y(2).mat(1,2,2,k1)
A(2,1)=maxmin2(y(3).mat(:,:,2,4*(k1-1)+3))+y(2).mat(2,1,2,k1)
A(2,2)=maxmin2(y(3).mat(:,:,2,4*k1))+y(2).mat(2,2,2,k1)
V2(2)=maxmin2(A)
end
function [ y2, V1 ] = v1( y, k1, k2 )
V1=zeros(1,3)
for k=1:16 %%Äëÿ V1
h=maxmin1(y(3).mat(:,:,1,k))
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
i=2, j=2
end
y2(2).mat(i,j,1,round((k+1)/4))=h+y(2).mat(i,j,1,round((k+1)/4))
end
for k=1:4
h=maxmin1(y2(2).mat(:,:,1,k))
34
if rem(k,4)==1
i=1, j=1
end
if rem(k,4)==2
i=1, j=2
end
if rem(k,4)==3
i=2, j=1
end
if rem(k,4)==0
i=2, j=2
end
y2(1).mat(i,j,1,1)=h+y(1).mat(i,j,1,1)
end
V1(1)=maxmin1(y2(1).mat(:,:,1,1))
V1(3)=maxmin1(y(3).mat(:,:,1,k2))
A(1,1)=maxmin1(y(3).mat(:,:,1,4*(k1-1)+1))+y(2).mat(1,1,1,k1)
A(1,2)=maxmin1(y(3).mat(:,:,1,4*(k1-1)+2))+y(2).mat(1,2,1,k1)
A(2,1)=maxmin1(y(3).mat(:,:,1,4*(k1-1)+3))+y(2).mat(2,1,1,k1)
A(2,2)=maxmin1(y(3).mat(:,:,1,4*k1))+y(2).mat(2,2,1,k1)
V1(2)=maxmin1(A)
end
function [ core ] = core(v1,v2,v3)
core=zeros(1:2)
core(1)=v1+(v3-(v1+v2))/2
core(2)=v2+(v3-(v1+v2))/2
if ((v1+v2)>v3);
core=zeros(1:2);
end
end
function [ ctilde ] = ctilde(core, h1,h2,V3)
ctilde=zeros(1,3)
beta=zeros(1,3)
beta(3)=core(3)*(h1(3)+h2(3))/V3(3)
beta(2)=core(2)*(h1(2)+h2(2))/V3(2)
beta(1)=core(1)*(h1(1)+h2(1))/V3(1)
ctilde(3)=beta(3)
ctilde(2)=beta(2)+beta(3)
ctilde(1)=beta(1)+beta(2)+beta(3)
end
function y = Creatematrix(n)
y = struct('mat',zeros(2,2,2,1));
35
for k=1:n
if(k~=1)
y(k).mat=zeros(2,2,2,4^(k-1));
end
for j=1:4^(k-1)
y(k).mat(:,:,1,j)=floor(10*rand(2,2));
y(k).mat(:,:,2,j)=floor(10*rand(2,2));
end
end
end
function [ vtilde ] = vtilde(V,V3,h1,h2)
vtilde=zeros(1,3)
vtilde(3)= V(3)*(h1(3)+h2(3))/V3(3)
vtilde(2)= V(2)*(h1(2)+h2(2))/V3(2)+vtilde(3)
vtilde(1)= V(1)*(h1(1)+h2(1))/V3(1)+vtilde(3)+vtilde(2)
end
36
Отзывы:
Авторизуйтесь, чтобы оставить отзыв