Мінімаксна матриця гри.

Табл. 5.16

Вj Аi	В1	В2	В3	В4	αі
А1	60	90	30	70	α1 =30
А2	80	30	20	60	α2 =20
А3	20	30	80	10	α3 =10
βj	β1 =80	β2 =90	β3 =80	β4 =70

Нижня ціна гри :

1⁰ . Мінімальні виграші для кожної стратегії гравця А

;

2⁰ . Максимальний з мінімальних виграшів:

Тобто, поставка на ринок товару сорту А₁ може як мінімум забезпечити фірмі а прибуток у розмірі 30 ($тис).

Верхня ціна гри:

1⁰ . Максимальні програші для кожної стратегії гравця В:

2⁰ . Мінімальний програш:

Фірма В, обравши у конкурентній боротьбі стратегію поставок на ринок товару сорту В₄ не втратить більше 70($тис). При інших стратегіях програші фірми В можуть бути більшими.

4. Ідентифікація ігрової стратегії та вибір методу рішення гри.

Оскільки нижня ціна гри не дорівнює верхній, гра не має сідлової точки та оптимального рішення у чистих стратегіях. Тобто, поставка на ринок товарів тільки одного сорту не забезпечує стійкості рішення.

Пошук оптимальних стратегій залежить від реальних умов задачі. Немає підстав вважати, що кожна фірма обмежується поставкою на ринок тільки одного сорту товару. Комбінація у певній пропорції різних сортів може забезпечити фірмі А прибуток, більший за нижню ціну гри, але, очевидно, менший за верхню ціну. Тобто, оптимальне рішення може бути знайдено шляхом фізичного поєднання стратегій.

Важливе зауваження Фізичне поєднання стратегій передбачає поєднання чистих стратегій Аі у пропорціях, які визначаються ймовірностями

Оскільки конфліктна ситуація формалізується грою , яка не має наочної геометричної інтерпретації, знаходження оптимальних стратегій можливо або шляхом приведення матричної гри до задачі лінійного програмування, або ітераційним методом.

Необхідні теоретичні відомості.

Нехай гра задана платіжною матрицею=1, 2,…,;

=1, 2,…,ГравецьА має у своєму розпорядженні стратегії А₁, А₂,…, А_m, гравець В – стратегії В₁, В₂,…, В_n . Необхідно визначити оптимальні стратегії та, де- ймовірності застосування відповідних чистих стратегійА_і, В_j (пропорції поєднання у випадку фізичного поєднання стратегій). При цьому

Застосування оптимальної стратегії за визначенням забезпечує гравцюА середній виграш не менший при будь-якій стратегії гравцяВ, та виграш, рівний ціні гри , при оптимальній стратегії гравцяВ.

Це твердження формалізується системою нерівностей

(5.7)

У загальному випадку можна припустити позитивність значення , це досягається через невід’ємність елементів платіжної матриці .

Цього завжди можна домогтися, якщо додати до всіх елементів матриці деяку позитивну величину; при цьому ціна гри збільшиться на, а рішення не зміниться.

Кожну з нерівностей (5.7) можна поділити на позитивну величину та ввести позначення:

(5.8)

Тоді система (5.7) запишеться у вигляді

, (5.9)

де –невід’ємні змінні.

Мета гравця А – максимізувати свій гарантований виграш, тобто ціну гри . Якщо поділити рівністьна, отримуємо, що змінні (=1, 2, …,) задовольняють умові:

(5.10)

Максимізація ціни гри рівносильна мінімізації величини, тому задача може бути сформульована наступним чином:

Визначити невід’ємні значення змінних, які б задовольняли лінійним обмеженням (5.9) та мінімізували лінійну функцію цих змінних: (5.11)

Маємо типову задачу лінійного програмування, яка може бути вирішена одним з відомих методів.

Для знаходження оптимальних стратегій слід вважати на те, що гравець В намагається мінімізувати виграш, тобто максимізувати величину, при виконанні умови:

(5.12)

де , які задовольняють умові:

Таким чином гра зводиться до наступної задачі:

Визначити значення змінних , які задовольняють систему нерівностей (5.12) та максимізують лінійну функцію (5.13)

Рішення задачі лінійного програмування (ЛП) (5.9)-(5.11) та (5.12)-(5.13) визначають відповідні оптимальні стратегії та .При цьому ціна гри:

(5.14)

Приведемо задачу вибору фірмою А стратегії конкурентної боротьби на ринку до задачі ЛП:

(5.15)

(5.16)

Рішення задачі за допомогою Microsoft Excel дає наступні значення(звіт за результатами наведений нижче):

Тобто: 0,0115;0,0019;0,0077

Вважаючи, що та

визначимо ймовірності стратегій гравця А, застосування яких забезпечить середній виграш близько 47,4 $ тис., що більше за нижню ціну гри , яка дорівнює 30 $ тис.: 0,55; 0,09;0,036;

Відповідно задача вибору стратегії фірмою В:

(5.17)

(5.18)

Рішення задачі ЛП у надбудові "Пошук рішення" Microsoft Excel дає наступні результати:

0,007; 0;0,01;0,004

0,021; 47,4;

0,33; 0;0,48;0,19

Важливе зауваження У практичних задачах часто немає потреби знаходити точне рішення гри, достатнім виявляється приблизне рішення, яке забезпечує середній виграш, близький до ціни гри. Приблизне рішення гри можна отримати методом ітерацій (Метод Брауна-Робинсона)

.

Необхідні теоретичні відомості.

В основі методу ітерацій лежить імітаційний експеримент, основний принцип якого можна сформулювати наступним чином.

На кожному кроці (циклі) ітераційного процесу кожний гравець відповідає на черговий крок іншого тією самою стратегією, яка є оптимальною відносно всіх попередніх ходів супротивника.

Попередні ходи супротивників розглядаються як деякі змішані стратегії, в які чисті стратегії входять у пропорціях, що визначаються частотою їх застосування.

Ідея цього методу полягає в імітації поведінки гравців А та В, коли вони застосовують один проти іншого свої стратегії, та визначенні основних характеристик цих стратегій.

Алгоритм ітераційного методу з необхідними коментарями розглянемо при розв’язанні проблеми вибору стратегії конкурентної боротьби.

1⁰. Сформуємо таблицю ітераційного методу (табл.5.17), стовпчики якого містять:

• Перший – , номер ітераційного експерименту (ітерації).

• Другий – , номер обраної стратегії гравцяА.

• Третій, четвертий, п’ятий та шостий – В₁, В₂, В₃, В₄ , “накопичений виграш” за перші ітерацій при тих стратегіях, які застосовували гравці в попередніх циклах експерименту та при стратегіях відповідноВ₁, В₂, В₃, В₄ в даному циклі. Ці значення отримуються шляхом додавання елементів відповідного рядка до значень, які були рядком вище. З усіх накопичених виграшів знаком «*»позначений мінімальний, тобто найбільш прийнятний для гравця В.

Таким чином позначене число визначає вибір-відповідь гравця В в даному циклі експерименту, (якщо їх декілька, позначаються всі та у відповідь приймається будь-яка стратегія); номер відповідної стратегії заноситься у наступний (сьомий) стовпчик.

Важливе зауваження Значення накопиченого виграшу використовуються замість значень середнього виграшу. Це обумовлено лише спрощенням розрахунків та не впливає на кінцевий результат.

• Сьомий стовпчик –, номер відповідної оптимальної стратегії гравцяВ.

• Восьмий, дев’ятий, десятий – А₁, А₂, А₃ , “накопичений виграш” за циклів (ітерацій) відповідно при стратегіяхА₁, А₂, А₃ гравця А.

Ці значення отримуються шляхом додавання елементів -го рядка до значень, які були отримані за перші-1 ітерацій.

З цих значень «*» позначено максимальне; це найбільш прийнятна стратегія для гравця А у наступному циклі (- у наступному рядку таблиці).

• Одинадцятий – – середній мінімальний “накопичений виграш” (мінімальний з виграшів, поділений на кількість ітерацій) – нижня оцінка ціни гри.

• Дванадцятий - – середній максимальний “накопичений виграш”, (максимальний з виграшів, поділений на кількість ітерацій –) – верхня оцінка ціни гри.

• Тринадцятий - - приблизна оцінка ціни гри.

2⁰. У першому циклі експерименту довільно обирається одна зі стратегій гравця А, (наприклад, А₁), та заповнюються (у подальших циклах - обчислюються) рядки 3-6 табл. 5.17.

3⁰. У відповідь обирається та стратегія гравця В (рядок 7), яка найменш вигідна для гравця А (позначена «*»), тобто обертає виграш за стратегією А_і до мінімуму, та заповнюються (у подальших циклах - обчислюються) рядки 8-10 табл.5.17.

4⁰. У рядки 10-12 заповнюється (у подальших циклах – обчислюються) значення

5⁰. Стратегія гравця А відповідає найбільшому з можливих виграшів (позначення «*»). Номер цієї стратегії заноситься у рядок 2 наступного циклу експерименту.

6⁰. Наступний цикл експерименту.

Стратегія – відповідь на два ходи гравця А (=1,=2): гравецьВ обирає у відповідь ту зі своїх стратегій (позначення «*»), яка дає найменший накопичений виграш за попередні цикли.

7⁰. Ітераційний процес продовжується за наведеним алгоритму певну кількість циклів, після чого визначаються частоти появи різних стратегій гравців, яки визначаються діленням кількості застосування стратегій на загальну кількість ітерацій . Після 50 ітерацій маємо наступні результати:

Стратегія А₁ застосовувалась 29 разів, А₂ -3 рази, А₄ -18 разів.

Ймовірності застосування стратегій гравця А:

Стратегія В₁ застосовувалась 18 разів, В₂ -0, В₃ -24, В₄- 8 разів.

Ймовірності застосування стратегій гравця В:

Середня ціна гри 47,3 (останній рядок табл.5.17).

Важливе зауваження За ціну гри можна прийняти середню цінуколи всі виграші гравцяА (В) приблизно дорівнюють один одному А1≈А2≈А3 (В1≈В2≈В3≈В4). Збіжність ітераційного методу дуже повільна, проте часто результати прийнятні для практичних цілей можна отримати за обмежену кількість ітерацій (15-20). При цьому середня ціна гри коливається біля точної цини гри.

Таблиця ітераційного методу.

Таб. 5.17

№	i	В1	В2	В3	В4	j	A1	A2	A3	νmin	νmax	ν*
1	2	3	4	5	6	7	8	9	10	11	12	13
	1	60	90	30*	70	3	30	20	80*	30	80	55
	3	80*	120	110	80*	1	90	100*	100*	40	50	45
	3	100	150	190	90*	4	160*	160*	110	30	53,3	41,7
	1	160*	240	220	160*	1	220	240*	130	40	60	50
	2	240	270	240	220*	4	290	300*	140	44	60	52
	2	320	300	260*	280	3	320*	320*	220	43,3	53,3	48,3
	1	380	390	290*	350	3	350*	340	300	41,4	50	45,7
	1	440	480	320*	420	3	380*	360	380*	40	47,5	43,8
	3	460	510	400*	430	3	410	380	460*	44,4	51,1	47,8
	3	480	540	480	440*	4	480*	420	470	44	48	46
	1	540	630	510*	510*	3	510	440	550*	46,3	50	48,2
	3	560	660	590	520*	4	580*	500	560	43,3	48,3	45,8
	1	620	750	620	590*	4	650*	560	570	45,4	50	47,7
	1	680	840	650*	660	3	680*	580	650	46,4	48,6	47,5
	1	740	930	680*	730	3	710	600	730*	45,3	48,7	47,0
	3	760	960	760	740*	4	780*	660	740	46,3	48,8	47,6
	1	820	1050	790*	810	3	810	680	820*	46,5	48,2	47,4
	3	840	1080	870	820*	4	880*	740	830	45,6	48,9	47,3
	1	900	1170	900	890*	4	950*	800	840	46,8	50	48,4
	1	960	1260	930*	960	3	980*	820	820	46,5	49,0	47,8
	1	1020	1350	960*	1030	3	1010*	840	900	45,7	48,1	46,9
	1	1080	1440	990*	1170	3	1040*	860	980	45	47,3	46,1
	1	1140	1330	1020*	1240	3	1070*	880	1060	44,4	46,5	45,5
	1	1200	1420	1050*	1310	3	1100	900	1140*	43,8	47,5	45,7
	3	1220	1450	1130*	1320	3	1130	920	1220*	45,2	48,8	47,0
	3	1240	1480	1210*	1330	3	1160	940	1300*	46,5	50	48,3
	3	1260*	1510	1290	1340	1	1220	1020	1320*	46,7	48,9	47,8
	3	1280*	1540	1370	1350	1	1280	1100	1340*	45,7	47,9	46,8
	3	1300*	1570	1450	1360	1	1340	1180	1360*	44,8	46,9	45,9
	3	1320*	1600	1530	1370	1	1400*	1240	1380	44	46,7	45,3
	1	1380*	1690	1560	1440	1	1460*	1320	1400	44,5	47,1	45,8
	1	1440*	1780	1590	1510	1	1520*	1400	1420	45	47,5	46,3
	1	1500*	1870	1620	1580	1	1580*	1480	1440	45,5	47,9	46,7
	1	1560*	1960	1650	1650	1	1640*	1560	1460	45,9	48,2	47,0
	1	1620*	2050	1680	1720	1	1700*	1640	1480	46,3	48,6	47,4
	1	1680*	2040	1710	1790	1	1760*	1740	1500	46,7	48,9	47,8
	1	1740*	2130	1740*	1860	1	1820*	1820*	1520	47	49,2	48,1
	1	1800	2220	1770*	1930	3	1850*	1840	1600	46,6	48,7	47,7
	1	1860	2310	1800*	2000	3	1880*	1860	1680	46,2	48,2	47,2
	1	1920	2400	1830*	2070	3	1910*	1880	1760	45,8	47,8	46,8
	1	1980	2490	1860*	2140	3	1940*	1900	1840	45,4	47,3	46,4
	1	2040	2580	1890	2210	3	1970*	1920	1920	45	46,9	46,0
	1	2100	2670	1920*	2280	3	2000*	1940	2000*	44,7	46,5	45,6

Продовження таблиці 5.17

1	2	3	4	5	6	7	8	9	10	11	12	13
	3	2120	2700	2000*	2290	3	2030	1960	2080*	45,5	47,3	46,4
	3	2140	2730	2080*	2300	3	2060	1990	2160*	46,2	48	47,1
	3	2160	2760	2160*	2310	1	2120	2070	2180*	47	47,4	47,2
	3	2180*	2790	2240	2320	1	2180	2150	2200*	46,4	46,8	46,6
	3	2200*	2820	2320	2330	1	2240*	2230	2220	45,8	46,7	46,2
	1	2260*	2910	2350	2400	1	2300	2310*	2240	46,1	47,1	46,6
	2	2340*	2940	2370	2460	1	2360	2390*	2260	46,8	47,8	47,3

5. Вибір рішення.

Очевидно, що результати отримані обома методами розрізняються не набагато.

Важливе зауваження. Застосування сучасних програмних продуктів, зокрема Microsoft Excel мабуть робить більш простим та доступним метод вирішення таких задач шляхом приведення їх до задач лінійного програмування.

Якщо задача допускає фізичне поєднання стратегій, то рішення може трактуватися наступним чином.

Для забезпечення середнього прибутку у розмірі не менше 47.4 ($тис) фірмаА повинна поставляти на ринок товари у наступній пропорції ( у дужках подані значення отримані ітераційним методом):

Сорт А1	=55(58) %
Сорт А2	=9 (6) %
Сорт А3	=36 (36)%

Відповідно поставка фірмою В товарів повинна здійснюватись у наступній пропорції:

Сорт В1	=33(36)%
Сорт В2	=0(0)%
Сорт В3	=48 (48)%
Сорт В4	=19(16)%

Це дозволить фірмі не втратити в середньому більше, ніж менше

47.4 ($тис)

У випадку, коли фізичне поєднання стратегій не можливе, ймовірності таможуть інтерпретуватися як характеристики змішаних стратегій гравців.

Припускаючи, що з тих чи інших причин можлива поставка на ринок тільки одного сорту товару рішення може трактуватися наступним чином.

Для забезпечення середнього прибутку у розмірі не менше 47.4 ($тис) фірмаА повинна поставляти на ринок

Сорт А1	=55(58) %	випадків
Сорт А2	=9 (6) %	випадків
Сорт А3	=36 (36)%	випадків

Відповідно трактуються складові змішаної стратегії фірми В.