4. Основные понятия, принципы и классификация игр.

Теория игр – раздел ИСО, изучающий конфликтные ситуации, возникающие при взаимодействии двух или более сторон, имеющих несовпадающие интересы.

Опр. Математическая модель конфликтной ситуации наз-ся игрой.

Игры в ИСО, в отличии от реальных, происходят по определенным правилом. Для того, чтобы задать игру необход. определить следующие элементы:

1) Конфликтующие стороны (игроки) – лиц, принимающих решения и имеющих несовпадающие интересы.

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

3) Точно определенный набор конечных состояний (выигрыш, проигрыш, ничья).

4) Платежи, соответствуют каждому возможному состоянию.

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

Следует различать понятия «игры» и «партии»

Игра – совокупность правил, а партия – однократная реализация. Ход в игре – это выбор и реализация одного из предусмотренных правилами способа действия.

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

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

Все рекомендации теории игр даются для многократного повторения игры.

Классификация игр.

• в зависимости от количества стратегий у игроков:

• конечные (у которого игрока конечное число стратегий);

• бесконечные (хотя бы одного игрока бесконечное число стратегий);

• по характеру предварительной договоренности между играми:

• коалиционные (игроки объединяются);

• бескоалиционные (игроки, не могут объединяются);

• по количеству участников:

• парная;

• множественная;

• в зависимости от объема информации, которой обладают игроки

• игры с полной информацией;

• игры с неполной информацией;

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

Основные принципы теории игр.

1. Принцип рационального выбора действий: каждый игрок считает противника таким же умным как и он сам и не рассчитывает на его промахи;

II) Принцип гарантированного результата: каждый игрок является достаточно осторожным и придерживаться той линии поведения, которая ,гарантирует ему средний результат наилучший, независимо от поведения противника.

Антагонистические игры. Платежная матрица.

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

Пусть в антагонистической игре игрок имеет стратегий , а игрок имеет стратегий .

Платежной матрицей (матрицей игры) наз-ся, матрица элементы которой , ; соответствуют выигрышу игрока (проигрышу игрока ) когда игрок выбрал ую стратегию , а игрок ответил той стратегией . Строки этой матрицы соотв-ют стратегиям игрока , а столбцы этой матрицы соответствуют стратегиям игрока .

			…
			…
			…
…	…	…	…	…
			…

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

Принцип минимакса. Нижняя и верхняя цена игры.

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

Сначала предположим, что мы выступаем на стороне игрока . Если мы выбираем стратегию , то второй игрок,

		…
		…
		…
…	…	…	…	…

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

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

Естественно, что из всех стратегий , мы выбираем ту, которая максимизирует, наш гарантируемый выигрыш, равный .

Величину – наз. нижней ценой игры, а соответствующую стратегию наз. максиминной.

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

т.е .

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

Докажем, что , , ;

; .

Седловая точка матрицы.

Игры в которых, нижняя цена равна верхней наз-ют игры с седловой точкой.

В платежной матрице такой игры существует элемент такой что ; ; (1)

такой элемент наз-тся седловой точкой. Заметим, что седловая точка может быть и не единственной. В играх с седловой точкой, общее значение нижней и верхней цены: наз-ся чистой ценой игры.

Если в платежной матрицы есть седловая точка, то игра имеет решение: .

Теорема1. Матричная игра платежной матрицы , имеет седловую точку, тогда и только тогда, когда

(2)

Д-во. Докажем, что из (1) следует (2)

Так как , то .

Докажем, что из (2) следует (1).

Обозначим через и те и , на которых достигаются внешние максимумы и минимумы на (2), т.е.

Откуда,

Получили неравенство, соответствующее (1). Доказано.

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

Док-во. 1) Докажем, что множества оптимальных стратегий игры с платежными матрицами и совпадают. Пусть – мн-во оптимальных стратегий для игры с платежной матрицей . – седловая точка матрицы . Рассм. .

– седловая точка м-цы . Аналогично можно показать справедливость обратного утверждения.

2) Нужно показать, что выполняется равенство .

Доказано.