Понятие игры, виды игр

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

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

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

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

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

Если сумма выигрышей игроков равна нулю, то игру называют игрой с нулевой суммой. В случае парной игры это означает, что выигрыш одного игрока равен проигрышу другого.

1.1.2. Решение матричных игр в чистых стратегиях
(принцип минимакса)

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

Пусть игроки А и В располагают конечным числом возможных действий – чистых стратегий. Обозначим их соответственно А₁, А₂, …, А _m и В₁, В₂, …, В _n. Игрок А может выбрать любую чистую стратегию А _i , а игрок В может выбрать любую чистую стратегию В _j . Пара стратегий (А _i, В _j) однозначно определяет результат игры a_ij (a_ij – выигрыш игрока А или проигрыш игрока В при условии, если игрок A придерживается своей чистой стратегии A _i, а игрок B – чистой стратегии B _j)_. Если известны значения исхода игры a_ij для каждой пары (А _i, В _j) чистых стратегий, то можно составить платежную матрицу выигрышей игрока А (проигрышей игрока В) (рис. 1.1).

Рис. 1.1. Платежная матрица игры

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

Используя этот принцип, найдем наилучшую стратегию игрока A. Выбирая стратегию A _i, мы должны рассчитывать, что игрок B ответит на нее той из своих стратегий B _j, для которой выигрыш игрока A будет минимальным. Найдем минимальное число a_ij в каждой строке матрицы:

.

Эта величина есть гарантированный (самый малый) выигрыш игрока A при выборе им чистой стратегии A _i. Значения a _i обычно записываются в правом столбце платежной матрицы (см. рис. 1.1). Очевидно, что желающий перестраховаться игрок A должен предпочесть другим стратегиям ту, для которой гарантированный выигрыш a _i максимален.

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

Аналогичные рассуждения могут быть проведены по поводу действий игрока В. С его точки зрения, в платежной матрице приведены проигрыши. В каждом из столбцов он должен найти максимальное значение проигрыша при выборе стратегии B _j:

.

Значения b _j записываются в дополнительной строке платежной матрицы (см. рис. 1.1).

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

Можно показать, что максимин не превосходит минимакс, т. е. a £ b. Если в игре нижняя цена равна верхней (a = b), то говорят, что игра имеет седловую точку и чистую цену игры g = a = b. Пару чистых стратегий (, ), соотвествующих g, называют седловой точкой матричной игры, а элемент a_ij ^*платежной матрицы, стоящий на пересечении i ^*-й строки и j ^*-го столбца, – седловым элементом платежной матрицы. Он одновременно является минимальным в своей строке и максимальным в своем столбце. Стратегии и , образующие седловую точку, являются оптимальными. Значения ; ;g называют решением игры.

Пример. В игре принимают участие два игрока. Каждый из игроков может записать независимо от другого цифру 4, 5 или 6. Если разность между цифрами, записанными игроками А и В положительна, то игрок А выигрывает количество очков, равное этой разности. Если разность отрицательна, то выигрывает игрок В. Если разность равна нулю, то игра заканчивается вничью. Составить платежную матрицу и найти решение игры.

Решение. Составим платежную матрицу игры. Чистыми стратегиями игрока А будут: А1 – записать число 4; А2 – записать число 5; А3 – записать число 6. У игрока В чистыми будут аналогичные стратегии. Элемент матрицы а₁₁ = 0, так как в ситуации (А1; В1) оба игрока записывают цифру 4 и выигрыш игрока А равен 4 – 4 = 0. В ситуации (А1; В2) выигрыш игрока А составит а₁₂ = 4–5 = –1. Аналогичным образом вычисляются остальные элементы платежной матрицы (рис. 1.2).

Рис. 1.2. Платежная матрица примера

Определим минимальные гарантированные выигрыши игрока А, равные при выборе им стратегий А _i. Так, если игрок А записал цифру 4, то его минимальный выигрыш при выборе данной стратегии составит a₁ = min(0; –1; –2) = –2. Аналогично находим a₂ = min(1; 0; –1)= –1, если игрок А записал цифру 5 и a₃ =
= min(2; 1; 0) = 0, если им записана цифра 6. Найдем нижнюю цену игры игрока А, воспользовавшись “принципом максимина”, т. е. . Нижняя цена игры для игрока А составит
a = max(–2; –1; 0) = 0. Таким образом, максиминному выбору игрока А будет отвечать третья стратегия, гарантирующая выигрыш, равный нулю.

Для игрока В значения элементов составят соответственно = 2, = 1, = 0. Верхняя чистая цена игры для игрока В по “принципу минимакса” составит = min (2; 1; 0) = 0. Следовательно, минимаксному выбору игрока В будет отвечать третья стратегия, гарантирующая минимальный проигрыш, равный нулю.

Так как a = b, то данная игра имеет седловую точку, т. е. третья чистая стратегия игрока А и третья чистая стратегия игрока В образуют седловую точку со значением 0 и данная матричная игра имеет решение (A₃; B₃; 0).