Принятие решений на основе теории игр

⇐ ПредыдущаяСтр 5 из 7Следующая ⇒

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.

Стратегии – доступные для игроков действия (набор правил и ограничений). Фактически – это альтернативы.

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

Антагонистические игры – игры двух игроков, в которых выигрыш одного из игроков равен проигрышу другого в любой ситуации, ещё их называют играми с нулевой суммой. Антагонистические игры, в которых каждый игрок имеет конечное число стратегий, называются матричными играми. Для задания такой игры выписывают платёжную матрицу, в которой строки соответствуют стратегиям первого игрока, а столбцы второго. Элементами матрицы a_ij являются выигрыши первого игрока.

Bj Ai	B1	B2	…	Bn
A1	a₁₁	a₁₂	…	a_1n
A2	а₂₁	а₂₂	…	а₂_n
…	…	…	…	…
Am	а_m1	а_m₂	…	а_mn

Оценки стратегий матричной игры.

Если есть матрица выигрышей, состоящая из n столбцов и m строк, то это означает, что у первого игрока есть m различных стратегий, а у второго n. В каждой ячейке с номером строки iи номером столбцаj записан выигрыш или проигрыш, который получит первый игрок, если применит стратегию с номером i, а второй при этом будет действовать в соответствии со своей j-ой стратегией. А у второго игрока выигрыш или проигрыш равен выигрышу или проигрышу первого с обратным знаком.

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

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

Чистая цена игрыg - цена игры, если верхняя и нижняя цены совпадают, то есть g=a=b. В этом случае игра называется игрой с седловой точкой.

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

Вj Ai	B1	B2	B3	ai
A1	1	2	3	1
A2	4	5	6	4
bj	4	5	6

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

Вj Ai	B1	B2	B3	B4	ai
A1	2	7	6	10	2
A2	8	4	9	5	4
bj	8	7	9	10

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

В игре без седловой точки, если игрок 1 осведомлён о том, что игрок 2 будет придерживаться минимаксной стратегии, то он может выбрать оптимальную стратегию, которая не совпадает с максиминной. Пример: А=

Вj Ai	В1	В2	В3	В4	В5
А1	3	5	8	6	11
А2	8	4	12	7	9

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

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

Дата добавления: 2018-05-12; просмотров: 795; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒

Мы поможем в написании ваших работ!