Теорема. Для того, чтобы в матричной игре существовали минимаксы, необходимо и достаточно, чтобы равны были минимаксы:
max min аij = min max аij
Оптимальные смешанные стратегии и их свойства.
Если матричная игра не имеет седловой точки ( ситуации равноыесия), то ее решение в чистых стратегиях становится непредсказуемым: каждому игроку можно только гарантировать, что его выигрыш при разумном поведении будет не менее нижней границы и не более верхней границы, цены игры.
Матричная игра без седловой точки приводит к неустойчивости использования стратегий при многократном повторении игры.
Смешанной стратегией игрока в матричной игре называется полный набор вероятностей x = ( x1, x2 ... xm) и y = ( y1, y2 ... yn) применения его чистых стратегий. (чистые стратегии - исходные).
Свойства смешанных стратегий.
1 свойство. Если x" = ( x1, x2, ... xm ) и y" = ( y1, y2,...yn ) - оптимальные смешанные стратегии игроков в матричной игре, то для произвольных стратегий x и y справедливо
Н ( А, x", y) = å aij xi" ³ v для всех j=1:n, так как это равносильно использованию вторым игроком чистой j-той стратегии: y = ( 0, 0,...yj=1,... 0, 0 )
Н ( А, x, y") = å aij yj" £ v для всех i=1:m, так как это равносильно использованию первым игроком чистой i-той стратегии: x = ( 0, 0,...xi=1,... 0, 0 )
2 свойство. Если в матричной игре с матрицей А и ценой игры v стратегии x" и y" - оптимальные, то
если å aij xi" > v, то yj" = 0
если å aij yj" < v, то xi" = 0
если неравенства обращаются в равенства, то соответственно:
xi" ¹ 0, yj" ¹ 0.
На приведенных свойствах основано решение матричных игр в смешанных стратегиях.
2.6. Доминирование в матричных играх.
Решение в матричных играх, особенно если матрица большая, получается путем громоздких вычислений и преобразований. Поэтому необходимо по возможности сократить матрицу и упростить решение, не в ущерб результату. В качестве такого сокращения используется понятие доминирования стратегий.
Пусть задана матричная игра с платежной матрицей А, а смешанные стратегии игроков представлены в виде x = ( x1, x2,... xm ) и y = ( y1, y2,... yn). Вектор х' строго доминирует вектор х"( вектор x" строго доминируется вектором x' ), если справедливо: xi' > xi" , i=1:m. Если неравенство нестрогое, то и доминирование является нестрогим.
Теорема. Если строка с номером r в матрице А строго доминируется выпуклой линейной комбинацией всех остальных строк, то она входит с нулевой вероятностью в любую оптимальную смешанную стратегию первого игрока.
Если x~, y~- пара оптимальных смешанных стратегий игры с матрицей A, то удалив из вектора x~ нулевую координату с номером r получим пару оптимальных смешанных стратегий x`~,y~ игры с матрицей A`, полученной из матрицы A вычеркиванием строки с номером r.
Обратное утверждение тоже верно. Если x`~,y~- пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве r-той коодинаты вектора x`~ ноль и сдвинув на одно место вправо все координаты вектора x~ с номерами r, r+1... m-1, получим пару оптимальных смешанных стратегий x~,y~ игры с матрицей A.
Теорема. Если строка с номером r в матрице А нестрого доминируется выпуклой линейной комбинацией всех остальных строк, то существует оптимальная смешанная стратегия первого игрока x~, у которой r-тая координата равна нулю.
Любая пара x`~,y~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой координаты с номером r в вектор x`~ и сдвигом координат этого вектора с номерами r, r+1,...m-1 на одно место вправо.
Во всех этих случаях значение игры с матрицей А совпадает со значением игры с матрицей А~.
Теорема. Если столбец с номером s в матрице А строго доминирует выпуклую линейную комбинацию всех остальных столбцов, то он входит с нулевой вероятностью в любую оптимальную смешанную стратегию второго игрока.
Если x~,y~ - пара оптимальных смешанных стратегий в игре с матрицей А, то удалив из вектора y~ нулевую координату с номером s, получим пару оптимальных смешанных стратегий x~,y`~ игры с матрицей A`, полученной из матрицы А вычеркиванием столбца с номером s.
Обратное: если x~,y`~ - пара оптимальных смешанных стратегий игры с матрицей A`, то добавив в качестве координаты с номером s вектора y`~ ноль и сдвинув все координаты с номерами s, s+1,... n-1 на одно место вправо получим пару x~,y~ оптимальных смешанных стратегий в игре с матрицей А.
Теорема. Если столбец с номером s в матрице А нестрого доминирует выпуклую линейную комбинацию всех остальных столбцов, то существует такая оптимальная смешанная стратегия y~ второго игрока, в которой координата с номером s равна нулю и любая пара x~,y`~ оптимальных смешанных стратегий игры с матрицей А` преобразуется в пару оптимальных смешанных стратегий x~,y~ игры с матрицей А добавлением нулевой s-той координаты и сдвигом координат с номерами s, s+1,... n-1 вектора y`~ вправо на одно место.
Таким образом, если строка матрицы А доминируется какой-либо другой (то есть она меньше) или линейной выпуклой комбинацией всех остальных строк, то ее можно вычеркнуть и решать задачу с меньшей матрицей, а решение исходной задачи получить добавив нули вместо недостающих координат в векторе первого игрока.
Если столбец матрицы А доминирует какой-либо другой (то есть он больше) или выпуклую линейную комбинацию всех остальных столбцов, то ее можно вычеркнуть, решить игру с меньшим количеством столбцов и получить оптимальные смешанные стратегии добавлением нулей вместо невостающих координат в векторе второго игрока.
Метод приближенного определения цены игры.
Способ отыскания приближенного решения прямоугольных игр был сформулирован в работе Г.В.Брауна, а сходимость процесса была доказана Джулией Робинсон в 1951 году.
Этот метод, называемый еще итеративным, опирается на традиционный статистический принцип: основывать будущие решения на соответствующей предыстории.
Заключается он в последовательной процедуре "сближения" вержней и ниждей цены игры с заданной точностью.
Глава . Биматричные игры
Функция выигрыша биматричной игры представляет собой две платежные матрицы : А - определяет выигрыш первого игрока, а В - выигрыш второго игрока. Первый игрок имеет m чистых стратегий ( m строк в матрицах А и В ) Второй игрок имеет n чистых стратегий ( n столбцов в матрицах А и В ).
В результате выбора первым игроком i-той стратегии, а вторым игроком j-той стратегии, первый игрок получает выигрыш aij, а второй - bij .
Решение биматричных игр сводится к отысканию ситуаций равновесия и равновесных (оптимальных) стратегий игроков.
В биматричной игре ситуация i*j называется приемлемой для первого игрока, если его выигрыш в этой ситуации не меньше, чем в любой другой:
аi*j ³ аij j=1:n
Для второго игрока ситуация ij* приемлема, если его выигрыш в этой ситуации не меньше, чем в любой другой:
bi*j ³ bij i=1:m
Tаким образом, приемлемые ситуации для первого игрока - это максимальные элементы встолбцах матрицы А, а для второго игрока - максимальные (тоже!) элементы в строках матрицы В.
Ситуация i*j* в биматричной игре называется равновесной, если она приемлема для обоих игроков, то есть если любое отклонение от нее как для первого игрока, так и для второго только лишь уменьшает их выигрыш:
аi*j* ³ аij*
bi*j* ³ bi*j
Множество ситуаций равновесия G образуется как пересечение множеств приемлемых ситуаций первого и второго игроков.
Пример.
| 3 | 0 | 2 | 3 | 1 | 0 | ||
| А: | 1 | 2 | 0 | В: | 2 | 0 | 2 |
| 0 | 3 | 2 | 0 | 2 | 1 |
G1={(1,1),(1,3),(3,2),(3,3)}
G2={(1,1),(2,1),(2,3),(3,2)} G = {(1,1),(3,2)}
I v(1,1)= 3 II v(1,1)= 3
v(3,2)= 3 v(3,2)= 2
Таким образом, если в биматричной игре несколько равновесных ситуаций, то по выгодности они не равнозначны, в отличие от матричных игр.
Из примера хорошо видно, что хотя (1,1) и (3,2) - ситуации равновесия, ситуации (1,2) и (3,1) таковыми не являются, в отличие от матричных игр.
Принципиальным отличием биматричных игр от матричных является отсутствие в них антагонизма.В матричных играх переговоры между игроками были бессмысленны, так как их интересы были прямо противоположны, в биматритчных играх договоры между участниками имеют реальное основание.
Так, в рассматриваемом примере второй игрок заинтересован в том, чтобы первый выбрал i=1, так как при этом v(II)= 3. Первому же игроку с точки зрения выгоды безразлично какую стратегию выбрать - первую или третью - в любом случае его выигрыш составляет 3. Если первый игрок доброжелательно настроен по отношению к противнику, то он выберет первую стратегию, чтобы и второй игрок получил максимальный выигрыш. В противном случае первый потребует за выбор более выгодной для второго стратегии дополнительную плату, и если эта плата будет меньше единицы, то очевидно, что второй игрок согласится на эту сделку.Такая игра называется игрой с побочными платежами.
Если в биматричной игре ситуаций равновесия нет, но игроки имеют возможность договориться между собой, то обычно применяют такой искусственный прием: находится i*j* такая,что:
max ( aij + bij ) = ( ai*j* + bi*j* )