Быстрый поиск

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

В игре могут сталкиваться интересы двух противников (игра парная или игра двух лиц), интересы n (n > 2) противников (игра множественная или игра n лиц). Существуют игры с бесконечным множеством игроков.

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

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

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

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

в которой I и – множества, – функции на множестве принимающие вещественные значения.

Бескоалиционная игра называется игрой с постоянной суммой, если существует такое постоянное C, что для всех ситуаций .

Ситуация s в игре называется приемлемой для игрока i, если этот игрок, изменяя в ситуации s свою стратегию si на какую-либо другую si', не может увеличить своего выигрыша.

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

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

Матричные игры

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

Каждая фиксированная стратегия, которую может выбрать игрок, называется его чистой стратегией.

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

Пусть первый игрок имеет m чистых стратегий, а второй – n.

Парная игра с нулевой суммой задается ' формально системой чисел – матрицей, элементы которой определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю строку (i-ю стратегию), а второй игрок j-й столбец (j-ю стратегию). Матрица называется платежной матрицей или матрицей игры.

Задача первого игрока – максимизировать свой выигрыш.

Задача второго игрока – максимизировать свой выигрыш – сводится к минимизации проигрыша второго, что эквивалентно задаче минимизации выигрыша первого игрока.

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

Гарантированный выигрыш первого игрока, применяющего чистую i-ю стратегию,

Число называется нижним значением игры, а соответствующая чистая стратегия i0, при которой достигается называется максиминной стратегией первого игрока. Аналогично, называется верхним значением игры а j0 – минимаксной стратегией второго игрока.

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

Любая пара (i0, j0), обладающая свойством (10.1), называется седловой точкой.

Смешанные стратегии

Если обозначить через x1, x2, …, xm вероятности (частоты), с которыми первый игрок выбирает соответственно первую, вторую, . . ., m-ю чистую стратегию, так что через ; через y1, y2, …, yn вероятности, с которыми второй игрок выбирает первую, вторую, ,.., n-ю свою чистую стратегию, причем , то наборы чисел x=( x1, x2, …, xm) и y=(y1, y2, …, yn) называются смешанными стратегиями первого и второго игроков соответственно. Каждый игрок имеет бесчисленное множество смешанных стратегий. Множество смешанных стратегий первого игрока обозначим через s1 и множество смешанных стратегий второго игрока – через s2.

Задача первого игрока состоит в выборе такой стратеги чтобы при отсутствии информации о выборе другого максимизировать свой выигрыш. Задача второго игрока состоит в выборе такой стратегии , чтобы при отсутствии информации о поведении первого игрока минимизировать выигрыш первого.

Если первый игрок применяет стратегию, а второй – стратегию то средний выигрыш M(x, y) первого игрока равен

Выигрыш M(x, y) называют функцией игры.

Например, в задаче с матрицей

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

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