рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Матричная игра двух лиц с нулевой суммой - раздел Философия, Общее понятие имитационного моделирования экономических процессов В Игре Двух Лиц С Нулевой Суммой (Такую Игру Называют Также Антагон...

В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 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.

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

– Конец работы –

Эта тема принадлежит разделу:

Общее понятие имитационного моделирования экономических процессов

Основные понятия... Объектно ориентированное моделирование ООМ предполагает поддержку классов и... Класс определяет некоторый шаблон или прототип блока например бассейн вообще Оперируя с классом например Бассейн...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Общее понятие имитационного моделирования экономических процессов.
Имитационная модель можно рассмотреть как специальную форма математической модели, в которой: декомпозиция системы на компоненты производится с учетом структуры проектируемого или из

Пакеты визуального моделирования
  Пакеты визуального моделирования позволяют пользователю вводить описание моделируемой системы в естественной для прикладной области и преи

Численное решение
Традиционная технология численного моделирования требует весьма аккуратного выбора и настройки численного метода (иногда даже несколько раз по ходу решения) и тщательного исследования погрешности р

Существующие подходы к визуальному моделированию сложных динамических систем
В настоящее время существует великое множество визуальных средств моделирования. Договоримся не рассматривать в этой работе пакеты, ориентированные на узкие прикладные области (электроника, электро

Оптимизация заданной целевой функции.
Модели экономических процессов разрабатываются с целью оптимизации заданной целевой функции при некоторой совокупности ограничений. Термин “оптимизация” обычно используется для обозначения процессо

Этапы исследования экономических процессов.
Работа, выполняемая в процессе исследования, состоит из следующих этапов: 1) идентификации проблемы; 2) построения модели; 3) решения поставленной задачи с помощью модели

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

Правила построения сетевой модели.
Правило 1. Каждая операция в сети представляется одной и только одной дугой(стрелкой). Ни одна из операций не должна появляться в модели дважды. При этом следует различать случай, к

Моделирование экономических процессов в виде системы массового обслуживания
В системах массового обслуживания различают три основных эта­па, которые проходит каждая заявка: 1) появление заявки на входе в систему; 2) прохождение очереди; 3) процес

Имитационное моделирование управления запасами
Существует проблема классификации имеющихся в наличии запасов. Для решения этой задачи используется методика адми­нистративного наблюдения. Цель ее заключается в определении той части запасов фирмы

Простейшая модель оптимального размера заказа.
Предположим, что: 1) темп спроса на товар известен и постоянен; 2) получение заказа мгновенно; 3) закупочная цена не зависит от размера заказа; 4) дефицит не доп

Модель оптимального размера заказа с фиксированным вре­менем его выполнения.
Предположим, что: 1) темп спроса на товар известен и постоянен; 2) время выполнения заказа известно и постоянно; 3) закупочная цена не зависит от размера заказа;

Модель оптимального размера заказа с производством.
Предположим, что: 1) темп спроса на товар известен и постоянен; 2) темп производства товара известен и постоянен; 3) время выполнения заказа известно и постоянно;

Модель оптимального размера заказа с дефицитом.
Предположим, что: 1) темп спроса на товар известен и постоянен; 2) время выполнения заказа известно и постоянно; 3) закупочная цена не зависит от размера заказа.

Модель оптимального размера заказа с количественными скидками.
Предположим, что: 1) темп спроса на товар известен и постоянен; 2) время выполнения заказа известно и постоянно. Исходные данные: темп спроса, издержки заказа, изд

Дискретная стохастическая модель оптимизации начально­го запаса.
Мы отказываемся от предположения о постоянстве и детерми­нированности величины спроса на товар и предполагаем извест­ным распределение величины спроса. Пусть S — размер запаса на на

Основы теории матричных игр
Методы, основанные на теории игр, используются для принятия решений в условиях неопределенности. Игра — это матема­тическая модель конфликтной ситуации, которая предполагает наличие следующи

Матричная игра двух лиц с ненулевой постоянной суммой
Конечная игра, в которой сумма выигрышей обоих игроков не равна нулю и постоянна для всех сочетаний их чистых стратегий, называется матричной игрой двух лиц с ненулевой постоянной сум­мой. Пусть

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги