Критерии Вальда, Лапласа, Гурвица, Сэвиджа в частном случае принятия решений в условиях неопределенности

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

, где

			….
x1	L11			L1k
x2
….
xn	Ln1			Lnk

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

 

 

Где . Множество предполагается неизвестным.

В этом случае рассмотренные выше критерии для выбора оптимальной стратегии принимают следующий вид.

Критерий Вальда:

Критерий Гурвица:

Критерий Лапласа:

Критерий Сэвиджа: , где

 

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

 

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

Упрощенная математическая модель конфликтных ситуаций представляет собой игру.

Игра может быть определена следующим образом:

· Имеются n конфликтных сторон (лиц), принимающих решения, интересы которых не совпадают.

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

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

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

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

Характерным примером является довольно распространенная ситуация, когда несколько фирм добиваются права у заказчика на получение выгодного заказа или конфликтуют из-за обладания новыми рынками сбыта.

Развернутая форма игры

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

Наши представления об играх связаны с карточными или “салонными ” играми, шахматами, шашками.

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

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

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

Т.о. наше представление об игре определяется наличием 3-х элементов:

1. Чередованием ходов, которые могут быть как личными, так и случайными.

2. Возможной недостаточностью информации.

3. Наличием функция выигрыша.

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

Где А - начальная вершина (позиция), В, С - промежуточные вершины (позиции), Х - окончательная.

Определение. Под позиционной игрой n лиц понимают следующее:

1. Топологическое дерево Г с выделенной вершиной А, называемой начальной позицией игры.

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

3. Разбиение множества всех неокончательных позиций (т.е. неокончательных вершин) дерева Г на n+1 множество , , …, , которые называют множествами очередности. Множество соответствует началу (может быть связано со случайностью), – множество очередности для 1-го игрока (1-ый уровень от А - см. рис. *), и т.д.

4. Вероятное распределение для каждой позиции из на множестве непосредственно следующих за ней позиций (т.е. из каждой позиции следуют варианты позиций с некоторой вероятностью).

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

6. Для каждого информационного множества множество индексов вместе с взаимно однозначными отображениями множества на множества альтернатив каждой позиции из .

В этом определении перечислены все элементы игры: условие (1) устанавливает, что имеется начальная позиция; (2) задает функцию выигрыша; (3) разделяет множество неокончательных позиций на позиции с ходом случая () и личные позиции, соответствующие каждому из игроков: (, …, ) (из позиции очередь хода принадлежит игроку ); (4) задает схему рандомизации в каждой позиции случая; (5) разбивает позиции каждого игрока на информационные множества: игрок знает лишь, в каком информационном множестве он находится, но не знает, в какой именно позиции этого множества.

Такая форма задания игры называется развернутой формой.

Нормальная форма игры

В интуитивном понимании стратегия есть некоторый план развертывания игры.

Определение. Стратегия i -го игрока есть некоторая функция, которая ставит в соответствие каждому информационному множеству этого игрока некоторый индекс из .

Будем обозначать множество всех стратегий i -го игрока через . Вообще говоря, игрок принимает решение о своем ходе в игре обычно в тот момент, когда надо делать этот ход. Однако с чисто теоретической точки зрения можно абстрагироваться от такого практического ограничения и предполагать, что уже до начала игры каждый игрок решил, что он будет делать в каждом случае. Т.е. предполагаем, что каждый игрок выбрал некоторую стратегию уже до начала игры.

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

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

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

Функцию на множестве всех взаимных значений , …, можно выразить либо в форме соотношения, либо в виде n - мерной таблицы n -мерных векторов. В случае n =2 эта запись сводится к матрице, элементами которой являются пары вещественных чисел. Такая n -мерная таблица называется нормальной формой игры.

Пример⁰. Для игры в “Орлянку” нормальной формой игры является матрица

	“Р”	“О”
Р”	(−1, 1)	(1, −1)
О”	(1, −1)	(−1, 1)

Здесь каждая строка представляет стратегию игрока 1, а столбец − стратегию игрока 2.

Пример⁰. Рассмотрим следующую игру. Случайно выбирается целое число z с возможными значениями 1, 2, 3, 4, каждое с вероятностью . Игрок I не зная результата этого хода, выбирает целое число x. Игрок II, не зная ни z, ни х, выбирает целое число у.

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

В этой игре каждый игрок имеет 4 стратегии: 1, 2, 3, 4, так как от других чисел мало проку. Если игрок I выбирает 1, а, игрок II − 3, то выигрыш будет равен (2, -2) с вероятностью , (0,0) - с вероятностью и (-2, 2) с вероятностью . Ожидаемый выигрыш тогда равен:

.

Подсчитав все значения, получим таблицу:

	(0, 0)	(−1/2, 1/2)	(−1/2, 1/2)	(0, 0)
	(1/2, −1/2)	(0, 0)	(0, 0)	(1/2, −1/2)
	(1/2, −1/2)	(0, 0)	(0, 0)	(1/2, −1/2)
	(0, 0)	(−1/2, 1/2)	(−1/2, 1/2)	(0, 0)

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

Ситуации равновесия

Определение. Пусть дана игра Г. Говорят, что ситуация (т.е. какой-нибудь n -набор стратегий) равновесна, или, что она является ситуацией равновесия, если для любого и для любого имеет место неравенство

.

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

 

Пример ⁰. Для игры в нормальной форме

 

как , так и являются ситуациями равновесия.

 

К сожалению, не каждая игра обладает ситуациями равновесия. Например, игра в “Орлянку” такой ситуации не имеет.

 

	“Р”	“О”
“Р”	(−1, 1)	(1, −1)
“О”	(1, −1)	(−1, 1)

 

 

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

Действительно, справедлива следующая теорема:

Теорема: Любая конечная игра n лиц с полной информацией имеет ситуацию равновесия.