Игровые модели. Теория игр. Стратегия. Классификация видов игр, в зависимости от причин, вызывающих неопределенность. Платежная матрица.

Понятие об игровых моделях

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

ТЕОРИЯ ИГР

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

Игра – это совокупность правил, описывающих сущность конфликтной ситуации. Эти правила устанавливают:

− выбор образа действий игроков на каждом этапе игры;

− информацию, которой обладает каждый игрок при осуществлении

таких выборов;

− плату для каждого игрока после завершению любого этапа игры.

Если в качестве противоположности выступает, неактивная, пассивная сторона, которая явно активно не противодействует достижению намеченной цели, то такие игры называются играми с «природой». Такой стороной являются неизвестность поведения участников ВЭД при взаимодействии с таможенными органами, таможенно-тарифная политика других государств, неясность погодных условий при перевозке товаров,итд

Конфликтующие стороны называются игроками, одна реализация игры – партией, исход игры – выигрышем или проигрышем. Развитие игры во времени происходит последовательно, по этапам или ходам. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действия и его реализацию. Ходы бывают личные и случайные. Личным ходом называют сознательный выбор игроком одного из возможных вариантов действия и его осуществление. Случайным ходом называют, выбор, осуществляемый не волевым решением игрока, а каким- либо механизмом случайного выбора (бросание монеты, пасовка, сдана карт)

СТРАТЕГИЯ

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

Классификация видов игр, в зависимости от причин, вызывающих неопределенность

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

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

Если в игре участвуют два игрока, игра называется парной, если число игроко больше двух – множественной. Участники множественной игры могут образовывать коалиции (постоянные или временные). Различают игры и по сумме выигрыша. Игра называется игрой с нулевой суммой, если каждый игрок выигрывает за счет других, а сумма выигрыша одной стороны равна проигрышу другой. В парной игре с нулевой суммой интересы игроков прямо противоположны. Парная игра с нулевой суммой называется антагонистической игрой

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

Игра называется конечной, если у каждого игрока имеется конечное число стратегий. Игра называется бесконечной, если хотя бы у одного игрока имеется бесконечное число стратегий.

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

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

ПЛАТЕЖНАЯ МАТРИЦА

Принцип минимакса (осторожности)

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m альтернатив (А1, А2, ..., Аm), а игрок II – n стратегий (B1, В2, ..., Вn). Такая игра называется игрой размерностью m⋅n. Пусть каждая сторона выбрала определенную стратегию: игрок I – Аi, (i=l, 2,..., m), игрок II – Bj (j = 1,2,..., n). Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой.

Пусть аij – выигрыш игрока I в ситуации, когда игрок выбрал стратегию Аi, а игрок II выбрал стратегию Bj. Выигрыш игрока II в данной ситуации обозначим через bij.

Рассматриваем игру с нулевой суммой, следовательно, аij=–bij Для любых i и j и для проведения анализа достаточно знать выигрыш только одного из игроков.

Если игра состоит только из личных ходов, тo выбор стратегии (Аi, Bj) однозначно определяет исход игры, например выигрыш игрока I. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (Ai, Bj) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш – это среднее значение (математическое

ожидание). Предположим, что значения аij известны для каждой пары стратегий (Аi, Bj). Составим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы – стратегиям игрока II. Такая таблица называется платежной матрицей. Каждый элемент (аij > 0) матрицы

определяет величину выигрыша игрока I и проигрыш игрока II при применении соответствующих стратегий (Ai, Bj). Цель игрока I – максимизировать свой выигрыш, а игрока II – минимизировать свой проигрыш.

Будем считать, что все аij > 0. Этого всегда можно добиться прибавлением достаточно большого положительного числа ко всем строкам и столбцам матрицы. Такое изменение матрицы не повлияет на результат.

Таким образом, платежная матрица имеет вид:



I / II B1 B2 … Bj … Bn …i

A1 a11 a12 … a1j … a1n 1

A2 a21 a22 … a2j … a2n 2

… … … … … … … …

Ai ai1 ai2 … aij … ain i

… … … … … … … …

Am am1 am2 … amj … amn m

j 1 2 … j … n

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий Ai, A2, ..., Am;

2) наилучшей (оптимальной) стратегии игрока II из стратегий В1, В2, …, Вn.

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

Методы и модели решения игровых задач. Принцип минимакса. Верхняя и нижняя цена игры. Чистые стратегии. Седловая точка. Доминирующие стратегии.

Принцип минимакса (осторожности)

Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m альтернатив (А1, А2, ..., Аm), а игрок II – n стратегий (B1, В2, ..., Вn). Такая игра называется игрой размерностью m*n. Пусть каждая сторона выбрала определенную стратегию: игрок I – Аi, (i=l, 2,..., m), игрок II – Bj (j = 1,2,..., n). Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой.

Пусть аij – выигрыш игрока I в ситуации, когда игрок выбрал стратегию Аi, а игрок II выбрал стратегию Bj. Выигрыш игрока II в данной ситуации обозначим через bij.

Рассматриваем игру с нулевой суммой, следовательно, аij=–bij Для любых i и j и для проведения анализа достаточно знать выигрыш только одного из игроков.

Если игра состоит только из личных ходов, тo выбор стратегии (Аi, Bj) однозначно определяет исход игры, например выигрыш игрока I. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (Ai, Bj) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш – это среднее значение (математическое

ожидание). Предположим, что значения аij известны для каждой пары стратегий (Аi, Bj). Составим таблицу, строки которой соответствуют стратегиям игрока I, а столбцы – стратегиям игрока II. Такая таблица называется платежной матрицей. Каждый элемент (аij > 0) матрицы

определяет величину выигрыша игрока I и проигрыш игрока II при применении соответствующих стратегий (Ai, Bj). Цель игрока I – максимизировать свой выигрыш, а игрока II – минимизировать свой проигрыш.

Будем считать, что все аij > 0. Этого всегда можно добиться прибавлением достаточно большого положительного числа ко всем строкам и столбцам матрицы. Такое изменение матрицы не повлияет на результат.

Таким образом, платежная матрица имеет вид:

I / II B1 B2 … Bj … Bn …i

A1 a11 a12 … a1j … a1n 1

A2 a21 a22 … a2j … a2n 2

… … … … … … … …

Ai ai1 ai2 … aij … ain i

… … … … … … … …

Am am1 am2 … amj … amn m

j 1 2 … j … n

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий Ai, A2, ..., Am;

2) наилучшей (оптимальной) стратегии игрока II из стратегий В1, В2, …, Вn.

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

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

Чистые стратегии

Характерные оценки

Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию А1, то игрок II может выбрать такую стратегию Вj, при которой выигрыш игрока I будет равен наименьшему из чисел а1j:

а₁=min_j*a_1j

т.е. 1 – минимальное значение из всех чисел первой строки.

Тогда, по аналогии справедливо записать выражение для любой стратегии Аi

а_i=min_j*a_ij

Выбирая стратегию Аi, игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем i. Поэтому игрок I должен выбрать ту ситуацию, для которой это число i –максимально

=max_ia_i

т.е. - максимальное значение из всех чисел столбца i (i=1, …, m).

Подставив вместо i выражение а_i=min_j*a_ij получим:

=max_imin_ja_ij

Величина – гарантированный выигрыш, который может обеспечить себе игрок I при любом поведении игрока П. Величина называется нижней ценой игры, или максимином, а стратегия А, игрока I, обеспечивающая получение нижней цены игры, называется максиминной чистой перестраховочной стратегией, при этом игрок I при любом поведении игрока II обеспечивает себе выигрыш не меньше :

а_i а(i=1,m) *1,m-сверху черточка!

Игрок II заинтересован в том, чтобы уменьшить свой проигрыш, т.е. обратить выигрыш игрока I в минимум. Для выбора оптимальной стратегии он должен найти максимальное значение выигрыша в каждом столбце и среди этих значений выбрать наименьшее. Обозначим через j, максимальное значение в каждом столбце:

_j=max_ia_ij

Наименьшее значение j обозначим через :

=min_j_j

С учетом _j=max_ia_ij получим:

=min_jmax_ia_ij

называется верхней ценой игры, или минимаксом. Стратегия игрока II, обеспечивающая получение верхней цены игры, называется минимаксной чистой стратегией. Применяя ее, игрок II проиграет не больше при любых действиях игрока I:

_j(j=1,2,…n)

Справедливо неравенство .

Таким образом, придерживаясь максиминной стратегии Ai, игрок I желает получить выигрыш не менее независимо от действий игрока II, придерживаясь минимаксной стратегии Bj гарантирует себе проигрыш не больше .

Принцип, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр называется принципом минимакса – принцип гарантированного результата. Этот принцип был впервые сформулирован Дж.фон Нейманом в 1928 г.

Седловая точка

Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. =. Такие игры называют играми с седловой точкой, в этом случае ==называется чистой ценой игры, а стратегии игроков A*j и B*j, позволяющие достичь этого значения, – оптимальными. Пара (A*j , B*j) называется седловой точкой матрицы, так как одновременно является минимальным в j-м столбце. Оптимальные стратегии A*j и B*j и чистая цена являются решением игры в чистых стратегиях, т.е. без привлечения механизма случайного выбора.

ДОМИНИРУЮЩАЯ СТРАТЕГИЯ

При постановке задач необходимо иметь в виду некоторые преобразования, которые помогают упростить сложную задачу путем изменения – уменьшения размерности платежной матрицы посредством выделения и исключения доминирующих и дублирующих стратегий. Стратегия игрока Аi доминирует над стратегией игрока Ak, если при любом поведении противника даст не меньший выигрыш, а если такой же, то дублирует Ak. В таком случае все элементы строки I больше (доминируют) или равны (дублируют) всех элементов строки k.

Решение игр в смешанных стратегиях. Условия применения смешанных стратегий. Теорема теории игр Дж. фон Неймана. Формализованное решение игровой задачи со смешанными стратегиями.

Условия применения смешанных стратегий.

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

Как мы отмечали выше, если матричная игра содержит седловую точку (матричные игры, для которых нижняя цена игры равна верхней), то ее решение находится по принципу минимакса. Если же платежная матрица не имеет седловой точки, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше , а игрок II обеспечит себе проигрыш не больше . Так как < , то игрок I стремится увеличить выигрыш, а игрок II – уменьшить проигрыш.

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

повторении игры в одних и тех же условиях с заданными вероятностями.

Для применения смешанных стратегий требуются следующие условия:

1) в игре отсутствует седловая точка;

2) игроками используется случайная смесь чистых стратегий с

соответствующими вероятностями;

3) игра многократно повторяется в одних и тех же условиях;

4) при каждом из ходов один игрок не информирован о выборе

стратегии другим игроком.

Теорема теории игр Дж. Фон Неймана.

Основная теорема теории игр Дж. фон Неймана: каждая конечная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях. Следствие: каждая конечная игра имеет цену, являющуюся математическим ожиданием выигрыша игрока I и проигрыша игрока II, причем выигрыш, соответствующий оптимальному решению, называется ценой игры – , удовлетворяющий условию < < . Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно.

Чистые стратегии игроков в их оптимальных смешанных стратегиях называются активными. В теории игр доказывается следующая теорема об активных стратегиях.

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

Решение матричных игр в смешанных стратегиях может быть найдено либо графически, либо методами линейного программирования.

Графический метод применим для решения игр, в которых хоть один игрок имеет две чистые стратегии. Этот метод интересен в том плане, что графически объясняет понятие седловой точки. Методами линейного программирования может быть решена любая игра двух лиц с нулевой суммой.

Решения игр в смешанных стратегиях: графический метод, метод линейного программирования.

Решение матричных игр в смешанных стратегиях может быть найдено либо графически, либо методами линейного программирования.

Графический метод применим для решения игр, в которых хоть один игрок имеет две чистые стратегии. Этот метод интересен в том плане, что графически объясняет понятие седловой точки. Методами линейного программирования может быть решена любая игра двух лиц с нулевой суммой.

Графический метод

Рассмотрим игру 2хn, в которой игрок А имеет две стратегии.

	y1	y2	…	yn
	B1	B2	…	Bn
x1:A1	a11	a12	…	a1n
1-x1: A2	a21	a22	…	A2n

Игра предполагает, что игрок А смешивает стратегии А1 и А2 с соответствующими вероятностями x1 и 1-x1, . Игрок B смешивает стратегии B1, B2,…,Bn с вероятностями y1, y2, …, yn, где , j=1, 2,…,n, и. В этом случае ожидаемый выигрыш игрока А, соответствующий j-й чистой стратегии игрока В, вычисляется в виде, или, j=1, 2,…,n. Следовательно, игрок А ищет величину x1, которая максимизирует

минимум ожидаемых выигрышей.

Метод линейного программирования

Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Еще в 1947 г. создателем теории игр Дж.фон Нейманом была установлена эта взаимосвязь, а также концепция двойственности в линейном программировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования. Оптимальные значения вероятностей xi, i=1,2,…,m, игрока А могут быть определены путем решения следующей максиминной задачи.

max{min(сверху m снизу i=1 *a_i1*x_i*сверху m снизу i=1 *a_i2*x_i,…, сверху m снизу i=1 *a_in*x_i)},

x₁+x₂+…+x_m=1

x_i0, i=1,2,…,m.

Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим:

=min(сверху m снизу i=1 *a_i1*x_i*сверху m снизу i=1 *a_i2*x_i,…, сверху m снизу i=1 *a_in*x_i).

Отсюда вытекает, что

сверху m снизу i=1 *a_ij*x_i, j=1,2,…,n.

Следовательно, задача игрока А может быть записана в виде Максимизировать z=при ограничениях

сверху m снизу i=1 *a_ij*x_i,, j=1,2,…,n.

x₁+x₂+…+x_m=1

x_i0, i=1,2,…,m.

не ограничено в знаке.

Отметим последнее условие, что цена игры может быть как положительной, так и отрицательной.

Оптимальные стратегии y1, y2=,…,yn игрока В определяются путем решения задачи

Min_yi { max (сверху n снизу j=1 *a_1j*x_j*сверху n снизу j=1 *a_2j*x_j,…, сверху n снизу j=1 *a_mj*x_j)},

y₁+y₂+…+y_n=1

y_j0, j=1,2,…,n.

Используя процедуру, аналогичную приведенной выше для игрока А, приходим к выводу, что задача для игрока В сводится к следующему. Минимизировать w= при ограничениях

сверху n снизу j=1 *a_ij*y_j,

y₁+y₂+…+y_n=1, j=1,2,…,n.

не ограничено в знаке.

Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную , которая является ценой игры. Причиной этого является то, что задача игрока В является двойственной к задаче игрока А. Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.