Все Лекции по Оптимизации (g10)

Посмотреть архив целиком

91



  1. Элементы теории игр.

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

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

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

Область приложения теории игр включает математику, экономику, политику, военную стратегию.

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

Выигрыш каждого игрока определяется платежной функцией.

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

Ход игры - это действие игрока , заключающееся в выборе одного из вариантов.

Партия - это некоторая определенная совокупность ходов, сделанная игроками.


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

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

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

    1. Классификация игр.

Игры классифицируются:

  • по числу игроков;

  • по числу стратегий;

  • по свойствам платежных функций;

  • по характеру предварительных переговоров между игроками до игры.


Классификация игр по числу игроков.

Различают игры с двумя, тремя и более участниками.

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


Классификация игр по количеству стратегий.

Различают конечные и бесконечные игры. Мы будем рассматривать конечные игры.


Классификация игр по свойствам платежных функций.

Различают:

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


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


Классификация игр по характеру предварительной договоренности.

Различают кооперативные и некооперативные игры.


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

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

    1. Описание игр.

Существует ряд способов описания и анализа игр:

  1. описание в виде дерева игры для игры в развернутой форме.


При таком описании игры указывается:

  1. какие ходы могут делать игроки;

  2. какой информацией во время игры они располагают;

  3. какие варианты можно выбирать;

  4. какими могут быть предельные размеры платежей в конце игры.


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


Пример .

Дерево игры для игры в развернутой форме - на примере упрощенной игры двух лиц в покер.


В этой игре ставка каждого игрока равна 5 у.е. Набор карт в руках игроков может быть «старшим» (С) или «младшим» (М) .

У игрока 1 имеются две возможности: либо раскрыть карты (Р), либо повышать игру (В). При раскрытых картах старшая выигрывает банк, если карты игроков равны, то банк делится пополам. Если игрок повышает игру, то он вкладывает в банк еще 5 у.е.


Игрок 2 либо пасует(П) , либо уравнивает(У). Если он пасует, то игрок 1 выигрывает банк при любых картах. Если игрок уравнивает(вносит еще 5 у.е.),то, если одинаковые карты, то банк делится пополам, если нет- то банк достается тому, у кого «старшая».


Ход 1 - определение ставок и сдача карт(случайный ход).


Ход 2 - игрок 1 либо раскрывает карты, либо повышает игру.


Ход 3 - игрок 2 либо пасует , либо уравнивает.


      1. Игра в нормальной форме.

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

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


Игрок 2 выбирает стратегию

Платежная матрица имеет размерность m x n, где

m - число стратегий игрока 1,

n - число стратегий игрока 2,

- выигрыш первого игрока при выборе первым стратегии , а вторым - стратегии .

- выигрыш второго игрока при выборе вторым стратегии , а первым - стратегии .


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

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


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

Если игрок 1 выбирает стратегию , а игрок 2 выбирает стратегию , то игрок 1 получает , а игрок 2 получает .

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

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

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

, где .

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

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

.

Стратегия, соответствующая максимальному значению минимумов строк, называется максиминной стратегией.

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

Игрок 2 стремится к гарантированному результату, выбирая минимаксную стратегию.

.

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

.

Если игрок 2 избирает минимаксную стратегию, то его проигрыш

.

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


Пример:

минимальные элементы строк





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

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

.

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


Пример:

минимальные элементы строк






Стратегии, рассмотренные выше, называются чистыми . m - строк платежной матрицы являются чистыми стратегиями игрока 1 , n - столбцов являются чистыми стратегиями игрока 2. В этом примере результат оказывается неожиданным для обоих игроков. То есть в таких играх принцип решения в той форме, как он изложен выше, оказывается непригодным. Однако этот принцип решения остается верным, если расширить понятие стратегии за счет смешанных(случайных) стратегий.

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

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

( * )

( Условие () можно записать в ином виде: ,

где - единичный вектор размерности m : .

Для игрока 2 вектор , где - вероятность выбора j - стратегии, .

, где - единичный транспонированный вектор размерности n.

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

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


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

Не полностью определенная игра имеет решение возможно не единственное, при котором хотя бы один из игроков применяет случайное комбинирование стратегий. Так, ожидаемый выигрыш( математическое ожидание ) игрока 1 в предположении , что он использует вектор вероятностей , а игрок 2 применяет свою j - ую стратегию, равен

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

( 10.3.0)

где

.

Цель игрока 2 - достичь

( 10.3.0)


Теорема о минимаксе утверждает, что существует хотя бы одна пара стратегий , при которых

.

,

где - цена игры, - решение ( 10.3 .0), - решение ( 10.3 .0).

При любых векторах выполняются соотношения

.

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

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

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

В некооперативных играх игроки принимают решения независимо друг от друга либо потому , что:

  1. координация запрещена;

  2. осуществление соглашения невозможно.


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

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

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


для .


,


где

- матрица выигрыша первого игрока,


- матрица выигрыша второго игрока.


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


Пример.

Двое подростков едут навстречу друг другу на автомобилях. Проигравшим считается тот, кто первым свернет в сторону.




Если один свернул в сторону, а другой нет, то «выигравший»получает 5, а проигравший получает -5. Если оба свернули, то ничья, каждый выиграл 0.

Если оба не свернули, то катастрофа(авария).

В данном случае, когда ни один из игроков не отказывается от своей стратегии независимых действий, существуют две точки равновесия ( 5 , -5 ) и ( -5 , 5 ).


Случайные файлы

Файл
91630.rtf
157181.rtf
ref_tolling.doc
1349.rtf
26309-1.rtf