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

Элементы теории игр и принятия решений.

Лекция 7,8

Вопросы:

1. Основные понятия.

2. Теоремы теории игр.

3. Способы решения задач теории игр.

4. Методы принятия решений: в условиях определенности; в условиях риска; в условиях неопределенности.

Теория игр принадлежит к наиболее молодым математическим дисциплинам, её возникновение относится к концу II-й Мировой войны.

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

Ситуация называется конфликтной, если в ней сталкиваются интересы нескольких лиц, преследующих противоположные цели.

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

Упрощенная, формализованная модель конфликтной ситуации, называется игрой, а конфликтующие 7стороны - игроками.

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

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

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

Личный ход представляет собой выбор игроком одного из данного множества вариантов.

Например, в шахматах каждый ход - личный, причем 1-й - выбор из 20 вариантов. Решение, принятое игроком при личном ходе, называется выбором.

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

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

Исходом игры является выигрыш или проигрыш. Величина этого выигрыша или проигрыша называется ценой игры.

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

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

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

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

В зависимости от числа возможных стратегий игры делятся на конеч­ные и бесконечные. В игре могут сталки-ваться интересы двух или более противников. В 1-м случае игра называется парной, во 2-м - множественной. Ограничимся рассмотрением только парных игр.

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

Рассмотрим парную игру с нулевой суммой. 1-й игрок имеет m воз­можных стратегий, а 2-й - n возможных стратегий. Не зная выбора друг друга, 1-й игрок выбирает i-ю стратегию, а 2-й игрок -j-ю стратегию. В результате игры 1-й игрок выигрывает величину , а 2-й - проигрывает эту же величину. Из чисел составляют матрицу, которая называется платежной или матрицей игры, .

Строки матрицы соответствуют стратегиям 1-го игрока, а столбцы - стратегиям 2-го. Это чистые стратегии.

Игра, определяемая матрицей А, имеющей m строк и n столбцов, называется конечной игрой размерности mхn.

Чтобы описание игры было законченным, необходимо указать цели, которыми руководствуются игроки при выборе своих стратегий. Эти цели просты: 1-й игрок стремится обеспечить себе наибольший вы­игрыш, а 2-й - наименьший проигрыш. Специфической трудностью является то, что ни один из игроков не контролирует полностью значение , т.к. 1-й игрок распоряжается только выбором i, а 2-й - j. Преодоление этой трудности, т.е. определение наиболее рационального способа ведения игры каждым игроком, и представляет собой существо теории игр.

Для того, чтобы понять принципы, которые лежат в основе выбо­ра каждым игроком своей стратегии, рассмотрим игру со следующей матрицей А

y₁ y₂ y₃ А(х)

х₁ 7 2 5 2

А = х₂ 2 2 3 2

х₃ 3 5 4 3

В(y) 7 5 5

При выборе 1-м игроком, например, 1-й стратегии, х₁, его вы­игрыш может быть равен 7, 2 или 5. Может ли 1-й игрок рассчитывать на максимальный выигрыш ? Да, если 2-й игрок выберет 1-ю свою стратегию, y₁. Однако он может выбрать и 2-ю стратегию, y₂, и вы­игрыш будет равен 2. Но уже меньше 2 выигрыш не может быть ни при какой стратегии 2-го игрока. Поэтому число 2, являющееся минималь­ным элементом стратегии х₁, есть гарантированный выигрыш 1-го игрока при стратегии х₁. Аналогично можно определить гарантирован­ные выигрыши для любой стратегии 1-го игрока - А(х). Предполагает­ся, что игроки избегают необоснованного риска и выбирают ту стра­тегию, которая дает максимальный из всех гарантированных выигрышей.

Число называется нижней ценой игры или максимином.

А соответствующая стратегия - максиминной.

Также можно рассуждать и в отношении 2-го игрока. Только в А указаны его проигрыши, которые он стремится минимизировать. Нап­ример, стратегия y₁ может принести 2-му игроку проигрыш 7, 2 или 3. Но уже больше 7 он не проиграет. Следовательно, число 7, являющееся максимальным элементом стратегии y₁, есть гарантированный проигрыш2-го игрока при y₁. Определим все гарантированные проигрыши - В(y). Каким же проигрышем может ограничиться 2-й игрок ?

Числоназывается верхней ценой игры или минимаксом.

А соответствующая стратегия - минимаксной.