Лекция 5

Формализация основных понятий Теории Игр.

Принцип Оптимальности

Принятие решений

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

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

Но что такое «наиболее предпочтительное» решение, а тем более, «оптимальное» решение. Опять мы сталкиваемся со сложной задачей, формальные методы решения которой весьма ограничены. Далее мы введем понятие «принципа оптимальности» - правила, определяющего выбор 2оптимального» решения. Но этих принципов оптимальности можно изобрести в достаточно большом количестве. Задача исследователя операций (ИО) – сформулировать правила, принципы выбора решения, приводящие к формулировке соответствующего принципа оптимальности, предоставив решение о выборе конкретного принципа оптимальности. Далее ИО определяет множество оптимальных выборов, соответствующего этому принципу, а ЛПР выбирает из этого множества конкретное решение, которое его устраивает и за которое он полностью отвечает.

Введем необходимые для дальнейшего изложения понятия из теории игр.

Игроком (лицом, стороной или коалицией) называется субъект, отстаивающий в игре свою совокупность интересов. Если данную совокупность интересов отстаивает несколько участников игры, то они рассматриваются как один игрок.

Игроки, имеющие противоположные по отношению друг к другу интересы, называются противниками.

Схематически игра может быть записана в виде:

Г= <I,>, где

I – множество игроков {1,…..n}или (,…,)

- управление i- го игрока ,

- множество выборов ,

Х=- множество исходов,

- функция выигрыша ,

,

- информационное множество , описывающее информацию, на основании которой игроки выбирают свои стратегии,-множество стратегий .

Принцип Оптимальности

Принцип оптимальности – это понятие определяющее

решение игры.

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

Пример 1. Задача оптимизации

В этом случае I= {1}- изучается поведение единственного игрока, максимизирующего свою функцию выигрыша.

Пусть, например,

Из необходимого условия оптимальности

=-2(-1)=0

получим

, то есть

Пусть теперь функция выигрыша имеет вид:

то есть прежнюю функцию мы «срезали» прямой.

. (см. рис. 1)

В этом случае, очевидно, при

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

Замечание. Везде далее будет использовано обозначение Argmax- множество точектаких,что

Тогда в рассматриваемом выше примере имеем:

= Argmax

М1
						Х1
0	0,50	1	1,50	2
	Рис.1

Пример2.Многокритериальная задача.

В этомслучае имеем одного игрока

I={1}, но m функций , которые он желает максимизировать

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

F(), а затем как в предыдущем примереопределяем= Argmax.

Пример. 3. Антагонистическая игра.

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

Итак, пусть

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

,

которая по определению удовлетворяет условию

Седловая точка удовлетворяет принципу устойчивости (равновесия интересов).Если один из игроков выбрал свое управление , соответствующее седловой точке, то противнику не целесообразно отклоняться от неё.

Например, для матричной игры

,

не трудно проверить, что элемент =3-наименьший во второй строке и наибольший в третьем столбце, то есть=3соответствует седловой точке в этой игре.

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

Пример.4. Максимально гарантированный результат(МГР)

Пусть

-управление игрока, а-неконтролируемые им факторы.

Тогда игрок гарантированно может рассчитывать на получение результата

Управление , удовлетворяющее условию

называется гарантирующим и может служить в качестве оптимального решения.

Пусть -управление партнера и игрок 1 знаетего принципоптимальности, чтопозволяет ему оценить его «отклик» на свое управление , то есть знать, что игрок 2 выберет.

Например, если мы знаем , то

= Argmax

Тогда МГР игрока1 оценивается величиной

Отметим, что в следствие получаем неравенство.

Пример.5. Бескоалиционная игра n лиц.

Эта игра общего вида

Г=

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

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

Самым распространенным принципом оптимальности для этой игры является ситуация равновесия по Нэшу

, удовлетворяющаяусловиям

Здесь

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

Ситуация - называется ситуацией сильного равновесия, если от неё не выгодно отклоняться любой коалиции

(При получаем ситуацию, эффективную по Парето).

Как мы покажем далее, равуновесные ситуации далеко не всегда Парето-оптимальны.

Далее будем анализировать игры двух лиц и соответственно использовать запись .

Определение: Стратегия называетсяабсолютно оптимальной, если для любыхимеет место равенство:

Для любого х₂первый игрок, используя такую стратегию, максимизирует свой выигрыш.

Определим x₂= х₂^а - оптимальный ответ второго игрока из условия:

M₂(x₁^а(x₂),x₂) =M₂(x₁^а(x₂^а),x₂^а)

Симметрично определяется абсолютно оптимальная стратегия второго игрока.

Тогда ситуация равновесия в исходной игре определяется из условия

x₁^a(x₂^а) = x₂^a(x₁^a)

Замечание.

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

Исследуем свойства ситуаций равновесия по Нэшу в следующих биматричных играх.

Покупатель -продавец.

Стратегии:

продавец = {честно взвесил или обманул}={1,2}

покупатель = {поверил или проверил}={1,2}

Эта игра имеет вид:

Покупатель

Верить проверить

Честно взвесить 0,0 0, -1/2

Продавец

Обмануть 1,-1 -1,1

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

(0,0) – в данном случае продавец честно взвесил товар, а покупатель ему верит, не проверяя.

(1,-1) – в данном случае продавец обманул покупателя, а покупатель не поверил ему.

(0,-1/2) – покупатель честно взвесил товар, но покупатель ему не поверил и решил проверить.

(-1,1) – продавец обманул покупателя, а тот решил проверить продавца.

Для этой игры построим абсолютно оптимальные стратегии:

х1 а	2	1
х2	1	2

х₂^а = 2

х2 а	1	2
x1	1	2

х₁^а = 1

Итак, имеем:

х₁^а(x₂) :

обманул	честно взвесил
верит	не верит

х₂^а(x₁) :

честно взвесил	обманул
верит	не верит

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

Действительно:

(0,0) – выгодно отклониться продавцу,

(1,-1) – покупателю,

(0,-1/2) – покупателю,

(-1,1) – продавцу.

Таким образом, ситуации равновесия не всегда существуют.

Семейный спор.

Рассмотрим биматричную игру вида:

Жена

Футбол балет

Футбол 2,1 0,0Муж

Балет 0,0 1,2

Матрицы выигрышей имеют следующий смысл:

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

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

(0,0) – опять оба не в выигрыше.

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

Для этой игры абсолютно оптимальные стратегии имеют вид:

жена:

х1 а	1	2
х2	1	2

х₂^а = 2

муж:

х1	1	2
х2 а	1	2

х₁^а= 1

Эти стратегии пересекаются в двух точках;

То есть в данном случае существует две ситуации равновесия: (1,2) и (2,1). Вопрос в том, кто берет на себя инициативу установления равновесия. Этот вопрос решается только обсуждениями в динамике или учитывая, кто в семье главный.

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

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

Реклама

Пусть две фирмы выпускают однотипный товар. Объем рынка как показал маркетинг – 10 ед. товара.

Управление игроков(фирм) – {рекламировать , не рекламировать} ={1,2}

Реклама обходиться в 1 ед. товара.

Биматричная игра имеет вид: