Принятие решения в условиях неопределенности

Рассмотрим пример. Игроки А и В одновременно и независимо друг от друга записывает каждый одно из трёх чисел: 1, 2 или 3. Если сумма записанных чисел оказывается четной, то игрок В платит игроку А эту сумму; если же сумма чисел оказывается нечетной, то эту сумму выплачивает игрок А игроку В.

У игрока А три стратегии:

А1 – записать 1; А2 – записать 2; А3 – записать 3.

Стратегии игрока В аналогичны. Рассматриваемая игра есть игра 3´3. Платёжная матрица имеет три строки и три столбца. Эта матрица представлена таблицей 2.

Таблица 2. Исходная платёжная матрица

B         A	В1	В2	В3
А1	2	-3	4
А2	-3	4	-5
А3	4	-5	6

В таблице 2 одни элементы являются положительными, а другие отрицательными. Преобразуем полученную матрицу, прибавив к каждому её элементу значение 6. Преобразованная матрица представлена таблицей 3. С точки зрения анализа оптимальных стратегий эта матрица эквивалентна исходной.

Таблица 3 Преобразованная платёжная матрица

B A	В1	В2	В3
А1	8	3	10
А2	3	10	1
А3	10	1	12

Принцип максимина

Естественный принцип  оптимальности для антагонистической игры — принцип максимина (минимакса). Будем анализировать эту игру, используя платёжную матрицу, показанную на табл. 3. Предположим, что игрок А выбирает стратегию А₁. Тогда в зависимости от того, какую стратегию изберёт противник, наш выигрыш будет равен либо 8, либо 3, либо 10. Итак, выбирая стратегию А₁, мы в худшем случае получаем выигрыш 3. Если же выберем стратегию А₂ или А₃, то будем  иметь в худшем случае выигрыш 1. Запишем минимальные возможные выигрыши для разных стратегий Аi в виде дополнительного столбца платёжной матрицы (табл. 4). Ясно, что следует выбирать ту стратегию, где минимальный возможный выигрыш оказывается наибольшим (по сравнению с остальными стратегиями). В данном случае это стратегия А₁. Выигрыш 3 является максимальным в тройке минимальных выигрышей (в тройке 3, 1, 1). Его называют максиминным выигрышем или, проще, максимином. У него ещё одно название – нижняя цена игры.

Табл. 4. Нижняя и верхняя  цена игры

B A	В1	В2	В3	αi
А1	8	3	10	3
А2	3	10	1	1
А3	10	1	12	1
βi	10	10	12

Аналогичным образом  рассуждает противник. Если он выберет  стратегию В₁, то в худшем для себя случае позволит нам получить выигрыш 10. То же можно сказать и о стратегии В₂. При выборе стратегии В₃ худший (для противника) случай соответствует нашему выигрышу, равному 12. Числа 10, 10, 12 – максимальные значения наших выигрышей, отвечающие стратегиям противника В₁, В₂, В₃ соответственно. Выпишем эти значения в виде дополнительной строки платёжной матрицы (см. табл. 4). Ясно, что противник должен выбрать ту стратегию, где наш выигрыш оказывается наименьшим. Это есть либо стратегия В₁, либо В₂. Обе стратегии являются минимаксными, обе они дают противнику гарантию, что наш выигрыш не превысит минимакса, или, иначе, верхней цены игры, равной в данном случае 10.

Верхняя и нижняя цены игры.

Величина a=  называется нижней ценой игры.

Величина b=   называется верхней ценой игры.

 

Наша максиминная стратегия, равно как и минимаксная стратегия  противника, является наиболее осторожной, "перестраховочной" стратегией. Принцип осторожности, диктующий игрокам выбор таких стратегий, называют принципом минимакса.

Подведём  итоги. Антагонистические игры, в которых каждый игрок имеет конечное множество стратегий, называются матричными играми. Для задания такой игры достаточно выписать так называемую платежную матрицу, в которой строки соответствуют стратегиям первого игрока, а столбцы - стратегиям второго игрока. Элементами матрицы служат выигрыши первого игрока.

Означает ли всё это, что теория игр рекомендует придерживаться только минимаксных (максиминных) стратегий? Ответ на этот вопрос зависит от того, имеет или не имеет платёжная матрица игры седловую точку.

Игра  с седловой точкой

В теории игр седловая точка (седловой элемент) — это наибольший элемент столбца матрицы игры, который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С. т. есть точка равновесия.

Рассмотрим некоторую  игру 3´3, платёжная матрица которой дана табл. 5. Здесь как максиминный, так и минимаксный выигрыши равны 4. Иными словами, в данной игре нижняя и верхняя цена игры совпадают, обе равны 4. Выигрыш 4 является одновременно и максимальным из минимальных выигрышей для стратегий А₁, А₂, А₃ и минимальным из максимальных выигрышей для стратегий В₁, В₂, В₃. В геометрии точку на поверхности, являющуюся одновременно минимумом по одной оси координат и максимумом по другой, называют седловой точкой (см. рис. 1). По аналогии с геометрией элемент а₂₂=4 рассматриваемой здесь платёжной матрицы называют седловой точкой матрицы, а об игре говорят, что она имеет седловую точку.

Рис. 1. Пример поверхности с седловой точки

Достаточно посмотреть внимательно на матрицу (см. табл. 5), чтобы понять, что каждый из игроков должен придерживаться максиминной (минимаксной) стратегии. Эти стратегии являются оптимальными в игре с седловой точкой. Любое отклонение от них будет невыгодно для игрока, допустившего отклонение.

Если же игра не имеет  седловой точки (см. табл. 4), то ни одна из стратегий Аi или Вi не является оптимальной.

 

 

 

Табл. 5. Платёжная матрица  с седловой точкой

B A	В1	В2	В3	Минимумы строк, ai
А1	2	3	7	2
А2	5	4	6	4
А3	6	2	1	1
Максимумы   столбцов, bj	6	4	7

Как быть, если игра не имеет  седловой точки? Если каждый игрок вынужден выбирать одну-единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно свои стратегии "смешивать", чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он "передоверяет" свой выбор случайности, "бросает жребий", и берёт ту стратегию, которая выпала.

Смешанные стратегии в теории игр представляют модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведёт себя противник в данной партии. Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх.

3. Решение игр в смешанных стратегиях

Если игра не имеет  седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в таблице 4, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

Необходимость случайного изменения стратегии  в игре  
без седловой точки

Допустим, что мы и  наш противник многократно играем в игру, матрица которой дана на рис. 4. Если мы выберем определённую стратегию, например максиминную стратегию A₁, и будем придерживаться её от игры к игре, то противник, поняв это, будет выбирать каждый раз стратегию B₂, в результате чего наш выигрыш не превысит нижней цены игры, т.е. будет равен 3. Если, однако, мы внезапно (для противника) сменим стратегию A₁ на стратегию A₂, то получим выигрыш 10. Разгадав нашу новую стратегию, противник тут же сменит стратегию B₂ на стратегию B₃, уменьшив наш выигрыш до 1. И так далее. Здесь проявляется общее правило для игр без седловой точки: игрок, играющий по определённой (детерминированной) стратегии, оказывается в более худшем положении по сравнению с игроком, который меняет стратегию случайным образом.

Впрочем, случайные изменения  стратегии надо делать не как попало, а с умом. Пусть A₁, A₂, …, An — возможные стратегии игрока A. Для получения наибольшего эффекта он должен использовать все или некоторые из этих стратегий случайным образом, но не с одинаковыми, а с разными (специально вычисленными) вероятностями. Пусть стратегия A₁,используется с вероятностью p₁, стратегия A₂,с вероятностью p₂ и т. д.

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂, ..., A_n с вероятностями p₁, p₂, ..., p_i, ..., p_n причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы

,

или в виде строки S_A=(p₁, p₂, …, p_n). В отличие от смешанных стратегий S_A стратегии Aj называют чистыми. При надлежащем подборе вероятностей p_j смешанная стратегия может оказаться оптимальной. При этом выигрыш игрока A будет не меньше некоторого значения v, называемого ценой игры. Это значение больше нижней цены игры, но меньше верхней.

Аналогичны образом  должен вести себя игрок B. Его оптимальная стратегия также есть некоторая смешанная стратегия

или в виде строки S_B=(q₁, q₂, …,q_m), где q_j — специально подобранные вероятности, с которыми игрок B использует стратегии B_j. Сумма вероятностей равна 1: При выборе игроком B оптимальной смешанной стратегии выигрыш игрока A будет не больше цены игры v.

Чистые стратегии можно  считать частным случаем смешанных. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*_A , S*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству α≤v≤β, где α и β — нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S*_A = (p*₁, p*₂, ..., p*_i, ..., p*_m) и S*_B = (q*₁, q*₂, ..., q*_i, ..., q*_n) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

Решением игры называется такая пара стратегий — в общем случае смешанных, систематическое применение которых обеспечивает каждой стороне максимально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптимальной стратегии (в то время как другая продолжает придерживаться своей), то это ни в коем случае не может быть выгодно для отступающего; это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конечная игра имеет решение (возможно, в области смешанных стратегий). Это положение называется основной теоремой теории игр.

Эта теорема имеет  большое практическое значение — она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.

4. Приведение матричной игры к задаче линейного программирования

Обозначим через S_A=(p₁, p₂, …, p_n) оптимальную смешанную стратегию игрока A. Требуется найти вероятности и определить цену игры при условии, что известна платёжная матрица игры. Допустим, что игрок B выбирает чистую стратегию B₁. Тогда средний выигрыш для игрока A будет равен a₁₁p₁+a₂₁p₂+…+a_n1p_n. Этот выигрыш должен быть не меньше цены игры v, следовательно, a₁₁p₁+a₂₁p₂+…+a_n1p_n≥v.

Если игрок B выберет стратегию B₂, то и в этом случае средний выигрыш игрока A должен быть не меньше цены игры v, следовательно, a₁₂p₁+a₂₂p₂+…+a_n2p_n≥v.