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

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

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

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

 

Таблица 6.1

	В1	…	Вj	…	Вп
А1	a11	…	a1j	…	a1n
…	…	…	…	…	…
Аi	ai1		aij		ain
…	…	…	…	…	…
Ат	am1	…	amj	…	amn

 

Рассмотрим два примера.

Пример 6.1. Пусть двое игроков, одновременно и не зная выбора противника, кладут на стол по монете. При совпадении сторон обе монеты забирает первый игрок, при несовпадении обе монеты забирает второй игрок. У каждого из игроков по две стратегии и . Число возможных ситуаций - четыре. Пусть выигрыш первого игрока (+1), его проигрыш (-1). Тогда матрица игры имеет вид:

	Г	Р
Г		-1
Р	-1

 

где слева выписаны стратегии первого игрока, над матрицей – стратегии второго.

Пример 6.2. В город можно войти только по двум мостам. Город обороняют 3 роты, на город нападают 2 роты, город будет взят, если на одном из мостов наступающие окажутся в численном превосходстве. Надо построить матрицу игры для обороняющихся, считая, что успешная оборона дает выигрыш (+1), потеря города дает (-1). Стратегии первого игрока таковы: выделить на защиту первого моста 0, 1, 2, 3 роты (остальные отправить защищать второй мост); стратегии второго игрока: атаковать первый мост силами 0, 1, 2 рот (остальные отправить атаковать второй мост). Матрица игры будет иметь вид:

	В1	В2	В3
А1			-1	-1
А2				-1
А3		-1
А4		-1	-1

 

где слева от матрицы – стратегии защитников, над матрицей – стратегии нападающих.

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

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

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

Нижней чистой ценой игры (максимином) называется число α, определяемое по формуле

. (6.1)

Верхней чистой ценой игры (минимаксом) называется число β, определяемое по формуле

. (6.2)

Стратегии игроков, соответствующие максимину (минимаксу), называются максиминными (минимаксными).