Реферат Курсовая Конспект
Матричная игра двух лиц с нулевой суммой - раздел Философия, Общее понятие имитационного моделирования экономических процессов В Игре Двух Лиц С Нулевой Суммой (Такую Игру Называют Также Антагон...
|
В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 1 и игрок 2. В распоряжении каждого из них имеется множество стратегий. Под стратегией понимают совокупность правил (принципов), определяющих выбор варианта действий при каждом ходе игрока в зависимости от сложившейся ситуации. Пусть А = {а1, а2,...} — множество стратегий игрока 1, В = {b1, b2,...} — множество стратегий игрока 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,..., п. Строки этой матрицы соответствуют стратегиям a1, а2, ..., аm игрока 1, столбцы — стратегиям b1, b2, ..., 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 в смешанной стратегии своих чистых стратегий a1, a2, ..., am; q1, q2, ..., qn — вероятности использования игроком 2 в смешанной стратегии своих чистых стратегий b1, b2, ..., 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 складывается из стратегий a1, a2,..., am с вероятностями соответственно p1, p2,..., pm (, ). Оптимальная смешанная стратегия игрока 2 складывается из стратегий b1, b2,..., bn с вероятностями q1, q2,..., qn (, ). Условия игры определяются платежной матрицей , , i = 1,..., m; j = 1,..., n.
Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 — чистую стратегию bj, то средний выигрыш игрока 1 (математическое ожидание выигрыша) составит р1a1j + р2a2j + ... + рmamj, j = 1,..., n.
Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры v и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования:
v ® max (игрок 1 стремится максимизировать свой выигрыш),
или, обозначив хi = рi/v, имеем
Причем
Поведению игрока 2 соответствует двойственная задача:
Задача (1) всегда имеет решение. Получив ее оптимальное решение , можно найти цену игры оптимальные значения и, следовательно, оптимальную стратегию игрока 1. Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры v* нужно уменьшить на d.
Справедливо и обратное положение: любую задачу линейного программирования можно свести к решению соответствующей игры двух лиц с нулевой суммой.
– Конец работы –
Эта тема принадлежит разделу:
Основные понятия... Объектно ориентированное моделирование ООМ предполагает поддержку классов и... Класс определяет некоторый шаблон или прототип блока например бассейн вообще Оперируя с классом например Бассейн...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Матричная игра двух лиц с нулевой суммой
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов