Методы решения задач

Антагонистическая игра

Антагонистические игры — игры, в которых участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла.

Антагонистическая игра в нормальной форме это совокупность {X, Y, F (x, y)}, где Х-это множество стратегий игрока 1, Y-множество стратегий игрока 2. Функция F (x, y) представляет собой выигрыш игрока 1 в ситуации (x, y), когда игрок 1 выбирает стратегию x? X, а 2 выбирает стратегию y? Y, при этом выигрыш игрока 2 равен F (x, y).

Стратегии (x, y) чистые стратегии игроков. В антогонистической игре игрок 1 стремиться по возможности maxF (x, y), а 2 min.

Границы возможностей игроков определяются значениями нижней и верхней цены игры. Нижней ценой игры в чистых стратегиях называется величина ?=max (x?X) min (y?Y). Верхней ценой игры в чистых стратегиях называется величина ?=min (y?Y) max (x?X). Смысл величин? заключается в следующем: игрок 1 может гарантировать себе выигрыш не меньше нижнего независимо от действий игрока 2; игрок 2 может гарантировать себе проигрыш не больше верхнего независимо от действия игрока 1 (в чистых стратегиях).

Матричная игра

Матричные игры — игры, в которых участвуют два игрока (I и II) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий. Если игрок I имеет m стратегий, а игрок II — n стратегий, то игра может быть задана (m n) — мaтрицей, А = ||a_ij||, где a_ij есть выигрыш игрока I, если он выберет стратегию i (i = -1,…, m), а игрок II — стратегию j (j = 1,…, n).

Критерий Лапласа L основан на гипотезе равновероятности и содержательно может быть сформулирован следующим образом: «поскольку мы ничего не знаем о состояниях среды, их надо считать равновероятными». Иногда этот принцип называется также принципом недостаточного основания. При принятии данной гипотезы в качестве оценки стратегии i надо брать соответствующий ей средний выигрыш, то есть.

Оптимальная по данному критерию стратегия L0 находится из условия.

(2).

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

Критерий вальда V основан на гипотезе крайней осторожности (крайнего пессимизма), которая формулируется так: «При выборе той или иной стратегии надо рассчитывать на худший из возможных вариантов». Если принять эту гипотезу, то оценкой стратегии i является число.

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

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

Критерий Гурвица G связан с введением числа 0? б?1, называемого «показателем пессимизма-оптимизма». Гипотеза о поведении среды состоит в том, что наихудший вариант реализуется с вероятностью б, а наилучший — с вероятностью 1-б. Тогда оценкой стратегии i является число поставка автомобиль теория игра.

.

а оптимальная стратегия i0 находится из условия. Ясно, что при б=1 данный критерий превращается в критерий крайнего пессимизма (то есть в критерий Вальда), а при б=0 — в критерий крайнего оптимизма. Содержательная трудность при использовании критерия Гурвица — назначение показателя пессимизма б.

Критерий Сэвиджа (критерий минимакса риска)

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

Критерий Сэвиджа определяется так:

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

Игры 2Ч2

Когда в матричной игре оба участника имеют по две стратегии (игры размерности 2Ч2). Такая игра задается матрицей вида.

Пусть (х1, х2) — оптимальная стратегия игрока 1, (у1, у2) — оптимальная стратегии игрока 2. Тогда, исключая тривиальный случай (наличие чистой оптимальной стратегии хотя бы у одного из игроков), имеем:

Получаем:

Приравнивая левые части уравнений и подставляя.

.

Получаем.

, где.

Аналогично находим.

, где .

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

Игры 2Чm

Теперь пусть матрицаАматричной игры имеет размерность 2Чm. Рассмотрим графический метод решения такой игры.

Представим матрицу в виде.

Каждую смешанную стратегию первого игрока можно задать таким образом:

.

Оптимальная стратегия первого игрока.

=().

определяется из условия.

Значение удобно определять графически. Для этого введем обозначения.

j=1,…, m,.

Здесь, j=1,…, m, — линейные функции, ц (x) — вогнутая функция (ее график, выделенный на рисунке пунктиром, называется нижней огибающей), — точка, в которой достигается максимум функции ц (x). Построив график данных функций получим: если =0 или =1, то для второго игрока оптимальной будет чистая стратегия, соответствующая функции, график которой проходит через точку (0,?(0)) или (1,ц (1)) и имеет соответственно наибольший отрицательный или наибольший положительный наклон среди всех прямых, проходящих через эту точку; если максимум функции ц (x)достигается во внутренней точке и существует функция, график которой проходит через точку (параллельно оси абсцисс, то оптимальной для второго игрока являетсяя чистая стратегия; если максимум функции ц (x) достигается во внутренней точке и нет прямой, проходящей через точку (параллельно оси абсцисс, то оптимальная смешанная стратегия второго игрока имеет вид, график функции проходит через точку (и имеет наибольший положительный наклон среди всех прямых, проходящих через эту точку;

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

был параллелен оси абсцисс. Цена игры подсчитывается по формуле.

или .

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

Рисунок 1. График игры 2Чm.