Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Матричная игра двух лиц с нулевой суммой

Поиск

В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 1 и иг­рок 2. В распоряжении каждого из них имеется множество стра­тегий. Под стратегией понимают совокупность правил (принци­пов), определяющих выбор варианта действий при каждом ходе игро­ка в зависимости от сложившейся ситуации. Пусть А = { а 1, а 2 ,... } множество стратегий игрока 1, В = { b 1, b 2 ,... } множество стра­тегий игрока 2. Элементы множества А — возможные стратегии (действия) игрока 1, элементы множества В — стратегии игрока 2. Условия игры представлены так называемой функцией выигрыша игрока 1: H (ai, bj), где аi Î А — i -я стратегия игрока 1, bj Î В — j -я стратегия игрока 2. В игре с нулевой суммой выигрыш игрока 2 равносилен проигрышу игрока 1 и равен поэтому — H (ai, bj). Пред­полагается, что функция выигрыша обоим игрокам известна. По­скольку игроков всего двое и игра антагонистическая, коалиции невозможны.

Игра, в которой множества А и В стратегий игроков конечны, т.е. | А | < ¥, | В |< ¥, называется матричной. В этом случае функ­ция выигрышей игрока 1 имеет вид матрицы, называемой матри­цей игры (матрицей выигрышей, платежной матрицей) Н = { аij } m,n, i = 1,..., т; j = 1,..., п. Строки этой матрицы соответствуют стра­тегиям a 1, а 2 ,..., аm игрока 1, столбцы — стратегиям b 1, b 2 ,..., bn игрока 2. Элемент матрицы aij = H (ai, bj) выигрыш игрока 1 в случае, когда он применит стратегию аi, а его противник — стра­тегию bj, i = 1,..., т; j = 1,..., п.

Элементы матрицы могут быть положительными, отрицатель­ными или равными нулю. Случай, когда данный элемент матри­цы положителен, означает, что игрок 2 в определенной ситуа­ции должен уплатить игроку 1 сумму, равную значению этого эле­мента. Если данный элемент отрицателен, игрок 1 уплачивает игроку 2 сумму, равную абсолютному значению этого элемента. И наконец, если этот элемент равен нулю, никакой выплаты не производится. Таким образом, в игре двух лиц с нулевой суммой один игрок выигрывает столько же, сколько проигрывает другой (все выплаты производятся из «карманов» противников). Это и объясняет название — игра с нулевой суммой.

Игрок 1 стремится к максимальному выигрышу, игрок 2 — к минимальному проигрышу. Решить игру — значит найти опти­мальные стратегии игроков и их выигрыши.

В игре двух лиц с нулевой суммой, как и в любой другой стра­тегической игре, исход зависит от поведения обоих игроков, ко­торое основывается на так называемых правилах игры. Допустим, что по правилам игры игрок 1 может выбрать произвольную стро­ку матрицы и, следовательно, может выбрать одно из чисел 1, 2,..., т. Аналогично игрок 2 имеет возможность выбора произ­вольного столбца матрицы выигрышей и, следовательно, одного из чисел 1, 2,..., п. Исход (результат) игры и, следовательно, сум­му, которую игрок 2 должен уплатить игроку 1, определяет эле­мент матрицы выигрышей, находящийся на пересечении строки, выбранной игроком 1, и столбца, выбранного игроком 2. Ни один из партнеров не знает, какую стратегию применит его противник. Таким образом, имеет место ситуация полной неопределенности, при которой теория вероятностей не может помочь игрокам в выборе решения.

Рассмотрим процесс принятия решений обеими сторонами более детально, предполагая, что игроки действуют рационально.

Если игрок 1 не знает, как поступит его противник, то, дей­ствуя наиболее целесообразно, не желая рисковать и считая, что противник также будет действовать целесообразно, он выберет такую стратегию, которая гарантирует ему наибольший из наи­меньших выигрышей при любой стратегии противника. Принято говорить, что при таком образе действий игрок 1 руководству­ется принципом максиминного выигрыша. Этот выигрыш определя­ется формулой a = aij. Величина a называется нижней ценой игры, максиминным выигрышем, или сокращенно — максимином.

В свою очередь игрок 2, действуя рационально, выберет такую стратегию, которая гарантирует ему наименьший из возможных проигрышей при любых действиях противника. Принято гово­рить, что игрок 2 руководствуется принципом минимаксного проиг­рыша. Этот проигрыш определяется выражением b = . Величина b называется верхней ценой игры или минимаксом.

Принцип осторожности, который определяет выбор партнера­ми стратегий, соответствующих максиминному выигрышу или минимаксному проигрышу, часто называют принципом минимакса, а стратегии, вытекающие из этого принципа, — минимаксны­ми стратегиями. Доказано, что всегда а 5 р, чем и объясняются названия «нижняя цена» и «верхняя цена». В случае когда ниж­няя цена игры равняется ее верхней цене, их общее значение на­зывается ценой игры. При этом результат стратегической игры двух лиц с нулевой суммой можно определить, не приступая к факти­ческой игре: вполне реален сценарий, когда партнеры, взглянув на матрицу, рассчитываются, пожимают друг другу руки и рас­ходятся. Очевидно, что исход такой игры не изменится, если она будет повторена многократно, поскольку ни одному из игроков невыгодно отклоняться от своих минимаксных стратегий. Си­туация, в которой нижняя и верхняя цены игры совпадают, на­зывается седловой точкой. Формальное определение: ситуация (ai *, bj *) Î A ´ В называется седловой точкой, если

В седловой точке элемент матрицы аij * = H (ai *, bj *) является од­новременно наименьшим в строке и наибольшим в столбце и, сле­довательно, соответствует цене игры. Однако существуют матри­цы игры двух лиц с нулевой суммой (и таких игр большинство), для которых a ¹ b, т.е. седловая точка отсутствует. Исход такой игры определить труднее, поскольку какой-либо одной так назы­ваемой чистой оптимальной стратегии ни для одного игрока не существует. В таких случаях говорят, что решение игры в чистых стратегиях отсутствует, и рассматривают так называемое смешан­ное расширение игры, решение которой ищут в смешанных страте­гиях. Смешанная стратегия игрока — это случайная величина, зна­чениями которой являются его чистые стратегии. Для того чтобы задать смешанную стратегию игрока, необходимо указать вероят­ности (частоты), с которыми выбираются его первоначальные (чи­стые) стратегии. При этом предполагается, что игра повторяется многократно.

Здесь р 1, р 2 ,..., рm вероятности использования игроком 1 в смешанной стратегии своих чистых стратегий a 1, a 2,..., am; q 1, q 2 ,..., qn вероятности использования игроком 2 в смешан­ной стратегии своих чистых стратегий b 1, b 2 ,..., bn.

Математическое ожидание выигрыша игрока 1:

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

Пусть Р* — смешанная стратегия игрока 1, Q * — смешанная стратегия игрока 2. Ситуацию (P*,Q*), при которой М (Р, Q*М (Р*, Q*) £ М (Р*, Q), называют седловой точкой смешанного расширения игры, а математическое ожидание выигрыша v = М (Р*, Q *) — ценой игры, причем всегда a £ v £ b.

Доминирование стратегий. Если платежная матрица такова, что каждый элемент некоторой строки i не меньше соответствующе­го элемента строки k и по меньшей мере один ее элемент строго больше соответствующего элемента строки k, то говорят, что стра­тегия а, игрока 1 доминирует его стратегию аi. Доминируемая стра­тегия не может быть оптимальной чистой стратегией игрока 1 и даже не может войти в его оптимальную смешанную стратегию с ненулевой вероятностью, поэтому ее можно исключить из рас­смотрения, вычеркнув из матрицы строку k. Аналогично: если каждый элемент некоторого столбца j не больше соответству­ющего элемента столбца r и по меньшей мере один его элемент строго меньше соответствующего элемента столбца r, то гово­рят, что стратегия bj игрока 2 доминирует его стратегию br. Поэтому столбец r матрицы можно вычеркнуть.

Сведение игры двух лиц с нулевой суммой к задаче линейного программирования. Если седловая точка отсутствует, то общим методом решения игры любой (конечной) размерности является сведение игры двух лиц с нулевой суммой к задаче линейного профаммирования. Из основного положения теории стратегичес­ких игр следует, что при использовании смешанных стратегий существует по меньшей мере одно оптимальное решение с ценой игры v, причем a £ v £ b, т.е. цена игры находится между ниж­ним и верхним значениями игры. Величина v неизвестна, но мож­но предположить, что v > 0. Это условие выполняется, поскольку путем преобразования матрицы всегда можно сделать все ее эле­менты положительными. Таким образом, если в исходной платеж­ной матрице имеется хотя бы один неположительный элемент, то первым шагом в процедуре сведения игры к задаче линейного программирования должно быть ее преобразование в матрицу, все элементы которой строго положительны. Для этого достаточ­но увеличить все элементы исходной матрицы на одно и то же число d > | aij |, где аij £0. При таком преобразовании мат­рицы оптимальные стратегии игроков не изменяются.

Допустим, что смешанная стратегия игрока 1 складывается из стратегий a 1, a 2,..., am с вероятностями соответственно p 1, p 2, ..., pm ( , ). Оптимальная смешанная стратегия игрока 2 скла­дывается из стратегий b 1, b 2, ..., bn с вероятностями q 1, q 2, ..., qn (, ). Условия игры определяются платежной матрицей , , i = 1,..., m; j = 1,..., n.

Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 — чистую стратегию bj, то средний выигрыш игрока 1 (математическое ожидание выигрыша) составит р 1 a 1 j + р 2 a 2 j + ... + рmamj, j = 1,..., n.

Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры v и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования:

v ® max (игрок 1 стремится максимизировать свой выигрыш),

или, обозначив хi = рi /v, имеем

Причем

Поведению игрока 2 соответствует двойственная задача:

Задача (1) всегда имеет решение. Получив ее оптимальное решение , можно найти цену игры оптимальные значения и, следовательно, оптималь­ную стратегию игрока 1. Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры v* нужно умень­шить на d.

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



Поделиться:


Последнее изменение этой страницы: 2016-09-05; просмотров: 267; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.218.213.240 (0.01 с.)