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

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

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

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

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

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

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

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

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

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

Г= < I, >, где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

=-2( -1)=0

получим

, то есть

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

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

. (см. рис. 1)

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

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

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

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

= Argmax

М1

Х1

0, 50

1, 50

Рис.1

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

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

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

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

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

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

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

Итак, пусть

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

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

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

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

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

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

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

Пусть

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

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

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

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

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

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

= Argmax

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

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

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

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

Г=

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

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

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

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

Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша.

Концепция равновесия Нэша впервые использована не Нэшем; Антуан Огюст Курно показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Соответственно, некоторые авторы называют его равновесием Нэша-Курно.

Однако Нэш первым показал в своей диссертации Некооперативные игры (1950), что равновесия Нэша должны существовать для всех конечных игр с любым числом игроков. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

Игра может иметь равновесие Нэша в чистых стратегиях или в смешанных. Нэш доказал, что если разрешить смешанные стратегии, тогда в каждой игре 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) – продавец обманул покупателя, а тот решил проверить продавца.

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

х₁^а
х₂

х₂^а = 2

х₂^а
x₁

х₁^а = 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) – в данном случае в выигрыше оказывается жена, так как они пошли на балет вместе.

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

жена:

х₁^а
х₂

х₂^а= 2

муж:

х₁
х₂^а

х₁^а = 1

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

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

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

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

Реклама

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

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

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

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

Фирма

реклама не реклама

реклама 4, 4 9, 0

Фирма

не реклама 0, 9 5, 5

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

(4, 4) – обе фирмы потратятся на рекламу и тогда поровну распределится объем рынка, их продукцию будут покупать, так как она разрекламирована, фирмы получат выигрыш M₁= M₂ = 4.

(9, 0) – если 1-я фирма потратит деньги на рекламу, а вторая не будет этого делать, тогда в выигрыше будет 1-я фирма, так как ее товар все будут покупать: ее выигрыш M₁= 9, а вторая фирма ничего не получит M₂ = 0.

(0, 9) – наоборот, первая фирма не рекламирует свой товар, а вторая – рекламирует, тогда вторая фирма будет в выигрыше, займет весь оставшийся объем рынка M₂ = 9, а первая ничего не получит M₁= 0.

(5, 5) – обе фирмы ничего не рекламируют и в результате делят объем рынка пополам M₁= M₂ = 5.

В этой игре ситуация равновесна – точка (4, 4), когда товар обеих фирм хорошо разрекламирован (ситуация равновесия по Нэшу).

Однако, есть точка (5, 5) – это Паретовская точка (т.е. обе фирмы могут получить больше на одинаковое количество). Эта ситуация возможна тогда, когда никто не будет друг друга обманывать, а для этого необходимы дополнительные переговоры.

Итак, ситуация равновесия в этом примере существует и единственна, но она не устраивает обоих игроков.

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒