Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Матричная игра двух лиц с нулевой суммойСодержание книги
Поиск на нашем сайте
В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 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.2.191 (0.01 с.) |