Основні визначення. Ціна гри

Основні визначення. Ціна гри.

У випадку, коли нижня ціна гри   й верхня ціна гри  не збігаються, 

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

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

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

2)               1.По-перше, забезпечується найбільша скритність вибору стратегії (результат вибору не може стати відомим супротивникові, оскільки він невідомий самому гравцеві),

2. По-друге, при розумній побудові механізму випадкового вибору стратегій, останні виявляються оптимальними.

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

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

Основні визначення

Розглянемо довільну m ´ п гру, задану т ´ n-матрицею

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

сума яких дорівнює 1,

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

сума яких також дорівнює 1.

Зауваження. Кожна чиста стратегія є часткою случаємо змішаної стратегії: зокрема, чиста стратегія  є змішаною стратегією, описуваної набором чисел , у якому

Підкреслимо, що для дотримання таємності кожний із гравців застосовує свої стратегії незалежно від іншого гравця.

Таким чином, задавши два набори

ми виявляємося в ситуації в змішаних стратегіях.

У цих умовах кожна звичайна ситуація (у чистих стратегіях) {А_i, В_k} по визначенню є випадковою подією й, через незалежність наборів Р и Q, реалізується з імовірністю p_iq_k. У цій ситуації {А_i, В_k} гравець А одержує виграш . Тим самим, математичне очікування виграшу гравця А в умовах ситуації в змішаних стратегіях (Р, Q) дорівнює

Це число й приймається за середній виграш гравця А при змішаних стратегіях

Визначення.

Стратегії

називаються оптимальними змішаними стратегіями гравців А и В відповідно, якщо виконано наступне співвідношення

Пояснення. Виписані нерівності означають наступне:

ліва нерівність – відхилення гравця А від оптимальної стратегії Р° за умови, що гравець У дотримується стратегії Q°, приводить до того, що виграш гравця, що відхилився, А може тільки зменшитися,

права нерівність – відхилення гравця У від оптимальної стратегії Q° за умови, що гравець А дотримується стратегії Р°, приводить до того, що виграш гравця А може тільки зрости, і виходить, виграш гравця В – тільки зменшитися.

Наведена умова оптимальності рівносильна тому, що

Величина

обумовлена останньою формулою, називається ціною гри.

Набір (Р°, Q°, v), що складається з оптимальних змішаних стратегій гравців А и В і ціни гри, називається рішенням матричної гри.

Виникають два ключових питання:

1-й - які матричні ігри мають рішення в змішаних стратегіях?

2-й - як знаходити рішення матричної гри, якщо воно існує?

Відповіді на ці питання дають наступні дві теореми.