Матричные игры

Матричные игры Содержание лекции  Оптимальные стратегии игроков  Принцип максимина  Смешанные стратегии  Условия применения смешанных стратегий  Оптимальные смешанные стратегии  Основная теорема теории матричных игр (теорема Дж. Фон Неймана)  Устойчивость оптимальных стратегий  Теорема об активных стратегиях РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА • Кремлёв, А. Г. Теория игр: основные понятия : учебное пособие для вузов / А. Г. Кремлёв ; под научной редакцией А. М. Тарасьева. — Москва : Издательство Юрайт, 2020. — 141 с. — (Высшее образование). — ISBN 978-5-534-03414-1. — URL : https://urait.ru/bcode/453797 • Шиловская, Н. А. Теория игр : учебник и практикум для вузов / Н. А. Шиловская. — Москва : Издательство Юрайт, 2020. — 318 с. — (Высшее образование). — ISBN 978-5-9916-8264-0. — URL : https://urait.ru/bcode/451420 Пример В платежной матрице указано, какую долю рынка выиграет предприятие у своего единственного конкурента, если оно будет действовать согласно каждой из возможных трех стратегий, а конкурент — согласно каждой из своих возможных трех стратегий. Задача игрока А – максимизировать свой выигрыш. Задача игрока В (конкурента) – минимизировать проигрыш (минимизировать выигрыш игрока А). Необходимо найти решение игры. Если первый игрок будет действовать со второй стратегией A2 , а второй игрок — со второй стратегией B2 , то игроки могут гарантировать себе: первый — выигрыш не менее ν=α=β=0.3=30% рынка, а второй — что первый выиграет не более ν=30% рынка Принцип построения стратегии игрока A, основанный на максимизации минимальных выигрышей, называется принципом максимина (maxmin) Принцип построения стратегии игрока B, основанный на минимизации максимальных выигрышей, называется принципом минимакса (minmax)  В этом случае элемент aij  называется ценой игры, является одновременно минимальным в i–й строке и максимальным в j–м столбце. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях. Оптимальная стратегия первого игрока – A2 , второго – B2 . Видно, что отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш, а отклонение второго игрока от B2 увеличивает его проигрыш. Пример Задана платёжная матрица игры A = Необходимо найти решение игры. В данной игре =3 =4 Поскольку – выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует. Очевидно, что для данной игры рассмотренный выше подход к нахождению оптимального решения неприменим, а максиминная и минимаксная стратегия игроков не являются решением игры. Применение максиминного (минимаксного) принципа каждым из игроков обеспечивает: Если    , то игра не имеет седловой точки. Если платежная матрица не имеет седловой точки, т.е. , то поиск решения игры проводится в смешанных стратегиях. СМЕШАННЫЕ СТРАТЕГИИ Смешанные стратегии Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm, причем сумма вероятностей равна 1: m  pi  1 i 1 Смешанные стратегии игрока А записываются в виде матрицы  A1 S A    p1 A2  Ai  Am   p2  pi  pm  или в виде строки SA = (p1, p2, ..., pi, ..., pm), либо  р  ( р1,......рm ), рi  0 (i  1, m) Смешанные стратегии Аналогично смешанные стратегии игрока В обозначаются  B1 S B    q1 B2  B j  Bn   q2  q j  qn  или SB = (q1, q2, ..., qj, ..., qn), либо  q  (q1,......qn ), q j  0 ( j  1, n), где сумма вероятностей появления стратегий равна 1: n qj 1 j 1 Условия применения смешанных стратегий      игра без седловой точки; игроки используют случайную смесь чистых стратегий с заданными вероятностями; игра многократно повторяется в сходных условиях; при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком; допускается усреднение результатов игр Выигрыш игрока А (проигрыш игрока В) Пусть игроки  А и В применяют смешанные стратегии p и q , т.е. игрок А использует стратегию Аi с вероятностью рi, а игрок В – стратегию Вj с вероятностью qj При использовании смешанных стратегий игра приобретает случайный характер, случайными становятся и величины выигрышей игроков. В матричной игре, зная матрицу А можно определить выигрыш игрока А (проигрыш игрока В), определяемый математическим ожиданием: m n   M ( A, p, q )   aij pi q j i 1 j 1 Эта функция называется платежной функцией игры Пример Определить выигрыши игрока А в ситуациях Решение: Если ,, то при данных значениях платежная функция игры равна 2 3 2 M ( A, P, Q)   aij pi q j   pi ai1q1  ai 2q2  ai 3q3   i 1 j 1 i 1  p1a11q1  a12q2  a13q3   p2 a21q1  a22q2  a23q3   Таким образом, выигрыш игрока А в ситуации (P,Q) M ( P, Q)  0.612 Ответ: выигрыши игрока А в ситуациях M ( P, Q)  0.612 ; M ( P, B1 )  0.62 ; M ( P, B2 )  0.65 ; M ( P, B3 )  0.606 Оптимальные смешанные стратегии * Определение. Векторы p * и q называют оптимальными смешанными стратегиями, если они образуют седловую точку платежной   функции игры M ( A, p, q ) , то есть удовлетворяют неравенству:  *  * * *  M ( A, p, q )  M ( A, p , q )  M ( A, p , q ) (1)  * * В этом случае M ( A, p , q ) называется ценой игры и обозначается через  (      )  * * ( p , q ) платежная функция В седловой   точке M ( A, p, q ) достигает максимума по смешанным  стратегиям p игрока А и минимума по смешанным стратегиям q игрока В Оптимальные смешанные стратегии Первое из неравенств (1) означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств (1) означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.   max  M ( A, p, q )   A  min q p   min  max  M ( A, p, q )   B q p 2) Основная теорема теории матричных игр (теорема Дж. Фон Неймана)  * * ( p ,q )  * *   M ( A, p , q ) Отсюда следует, что при выборе оптимальных стратегий игроку А всегда будет гарантирован средний выигрыш, не меньший, чем цена игры, при любой фиксированной стратегии игрока В (и, наоборот, для игрока В) Устойчивость оптимальных стратегий Это свойство называется условием устойчивости. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Теорема об активных стратегиях Если один из игроков придерживается своей оптимальной смешанной стратегии, то его выигрыш остается неизменным и равным цене игры, не зависимо от того, какую стратегию принимает второй игрок, если только тот не выходит за пределы своих активных стратегий. Эта теорема имеет большое практическое значение – она дает конкретные методы нахождения оптимальных стратегий при отсутствии седловой точки.