Решение матричных игр

Решение матричных игр Содержание лекции •Аналитическое решение матричных игр 2 × 2 в смешанных стратегиях •Графическое решение матричных игр 2 × 2 в смешанных стратегиях •Решение матричных игр 2хn РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА • Кремлёв, А. Г. Теория игр: основные понятия : учебное пособие для вузов / А. Г. Кремлёв ; под научной редакцией А. М. Тарасьева. — Москва : Издательство Юрайт, 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 Аналитический метод решения игры 2х2 Рассмотрим игру размера 2х2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответствующих этой точке. Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S *A   p1* , p2*  и S B*  q1* ,q2*  Для того, чтобы их найти, воспользуемся теоремой об активных стратегиях.  a11 a12  Пусть игра задана платежной матрицей P     a21 a22  S *A  A1   *  p1 a11 p1* A2   * p2   a21 p2*  a12 p1*  a22 p2*   * * p  p Учитывая, что 1 2  1 , получим систему уравнений для определения оптимальной стратегии S *A и цены игры  :  a11 p1*  a21 p2*    * * a p  a p  12 1 22 2    p*  p*  1 1 2  Решая эту систему, получим оптимальную стратегию p1* a22  a21 ,  a11  a22  a21  a12 и цену игры p2* a11  a12  a11  a22  a21  a12 a22a11  a12a21  a11  a22  a21  a12 Применяя теорему об активных стратегиях при отыскании S B* – оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А средний проигрыш игрока В равен цене игры  , т.е.  a11q1*  a12q2*    * * a q  a q  21 1 22 2    q*  q*  1 1 2  * * * Тогда оптимальная стратегия S B  q1 ,q2  определяется формулами a a  a q1*  * q2 22 12 a11  a22  a21  a12  12 a11  a12 a11  a21 a11    a11  a22  a21  a12 a11  a12 Пример В городе N имеются две конкурирующие компании («Сладкий мир» и «Сладкоежка»), которые занимаются производством шоколада. Обе компании могут производить молочный шоколад и горький шоколад. Стратегию компании «Сладкий мир» обозначим Аi, компании «Сладкоежка» - Вi. Пусть платежная матрица игры имеет вид В1 В2 A1 5 4 A2 3 6 Найти решение игры аналитическим методом. 5 4  A   3 6 min 4 max4;3  4  4 3 min 5;6  5  5 max 5 6    , при этом цена игры   4;5 Игра не имеет седловой точки, следовательно, не решается в чистых стратегиях Каждый из игроков А и В обладает единственной оптимальной смешанной стратегией S *A  p1* , p2* и S B*  q1* ,q2*  a22  a21 63 3    a11  a22  a21  a12 5  6  3  4 4 1 * * p2  1  p1  4 p1* q1* a22  a12 64 1    a11  a22  a21  a12 4 2 q2*  1  q1* 1  2 a22a11  a12a21 30  12 9    a11  a22  a21  a12 4 2    Оптимальной смешанной стратегией игрока * S А является стратегия A  0.75;0.25 , а * S игрока В - стратегия B  0.5;0.5 Цена игры   4.5 Т.о., компании «Сладкий мир» следует распределить производство шоколада следующим образом: 75% от общего объема производства отдать производству молочного шоколада, а 25% производству горького шоколада. Компания «Сладкоежка» должна поровну производить молочный и горький шоколад Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число С, то оптимальные смешанные стратегии игроков не изменятся, а только цена игры увеличится (уменьшится) на это число С. Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k. Эти свойства матричных игр применяются: 1) чтобы исключить отрицательные числа в матрице игры; 2) чтобы все выигрыши были целыми числами, т.е. исключить дробные числа в матрице игры Пример Решить матричную игру 2х2 с платежной матрицей вида: Bj Ai A1 A2 B1 B2 0.5 0.1 -0.2 0.3 Решение: Умножая все элементы Bj платежной матрицы на 10, Ai а затем прибавляя к ним A1 число 2, получаем игру с платежной матрицей A 2 B1 B2 7 3 5 Решая эту игру алгебраическим методом, получаем 53 2 p1   ; 7 530 9 50 5 ; q1   7 530 9 7 p2  ; 9 4 q2  ; 9 7  5  0  3 35 v  7530 9 В соответствии со свойствами 1 и 2, исходная матричная игра имеет те же оптимальные смешанные стратегии: 5 4 2 7 SB   ;  SA   ;  9 9 9 9 и А для получения исходной цены игры необходимо из полученной цены игры вычесть 2, а затем разделить на 17  10. Т.о., получаем цену исходной игры:  35   2  : 10  90  9  . Графический метод решения игры 2х2 Решение матричных игр 2хn и mх2 Графические решения матричных игр Графический метод применим к тем играм, в которых хотя бы один игрок имеет две стратегии. Рассмотрим игру 2хn. Пусть игра не имеет седловой точки. Графические решения матричных игр Цена игры определяется следующим образом: Графические решения матричных игр Максимум функции найдем, построив ее график. Для этого поступаем следующим образом. Построим графики прямых для каждого k=1,2,…,n в системе координат p0w Графические решения матричных игр На каждой из построенных прямых определяются и отмечаются наименьшие значения. Полученная ломаная огибает снизу все семейство построенных прямых и называется нижней огибающей семейства. Рис. 1 Графические решения матричных игр Цену игры  определяет верхняя точка построенной нижней огибающей. Координаты этой точки являются оптимальной стратегией игрока А: Рис. 1 Графические решения матричных игр Цену игры  определяет верхняя точка построенной нижней огибающей. Координаты этой точки являются оптимальной стратегией игрока А: Рис. 1 Графические решения матричных игр Рис. 2 Графические решения матричных игр Оптимальная смешанная стратегия игрока В получается, если положить где q находят из уравнения Рис. 2 Пример 1. Один из игроков в данной игре, представленной матрицей имеет 2 стратегии, следовательно, к этой игре применим графический метод. Найдем решение игры графическим и аналитическим методами. Решение p1* q1* 47 1    0.5 2 457 2 45 1    0.17 2 457 6 p2*  1  p1*  0.5 q2*  1  q1*  5  0.83 6 8  35   4.5 2 457 Оптимальные смешанные стратегии S *A  0.5; 0.5 и при цене игры S B*  0.17; 0.83; 0   4.5 Следовательно, предприятие должно выпускать 50% продукции А1 и 50% продукции А2. Оптимальный спрос в 17% находится в состоянии В1 и в 83% - в состоянии В3