Необходимые условия максимина. Различные формы их представления

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

Кафедра «информационной и техносферной безопасности»

Реферат

по дисциплине «Теория игр»

на тему «Необходимые условия максимина. Различные формы их представления»

Выполнила: студентка 2 курса

Специальности «экономика»

Москалева О. С.

Проверил: к.ф.м.н., доцент Погосян С. Л.

Курск – 2012

Содержание

Введение……………………………………………………………………… …..3

1.     Предмет и задачи теории игр…………………………….……………  ….4

2.     Терминология и классификация игр……………………………..…  ……6

3.     Принцип максимина (минимакса)…………………………………  ……10

Заключение…………………………………………………………………….....14 Список литературы……………………………………………………………....15

Введение

   Первую попытку создать математическую теорию игр предпринял в 1921 г. Э.Борель. Как самостоятельная область науки впервые теория игр была систематизировано изложена в монографии Дж.фон Неймана и О.Моргенштерна “Теория игр и экономическое поведение” в 1944 г. С тех пор многие разделы экономической теории (например, теория несовершенной конкуренции, теория экономического стимулирования и др.) развивались в тесном контакте с теорией игр. Теория игр с успехом применяется и в социальных науках (например, анализ процедур голосования, поиск равновесных концепций, определяющих кооперативные и некооперативные поведения лиц). Как правило, избиратели отводят кандидатов, представляющих крайние точки зрения, но при избрании одного из двух кандидатов, предлагающих различные компромиссные решения, возникает борьба. Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке зрения на кооперацию.

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

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

Предмет и задачи теории игр

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

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

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

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

    Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника, неизвестно лишь то, каким именно из них он воспользуется в данной партии. В реальном конфликте это обычно не так: перечень всех возможных стратегий противника как раз и неизвестен, а наилучшим решением в конфликтной ситуации нередко будет именно выход за пределы известных противнику стратегий, “ошарашивание” его чем-то совершенно новым, непредвиденным.
   Теория игр не включает элементов риска, неизбежно сопровождающего разумные решения в реальных конфликтах. Она определяет наиболее осторожное, “перестраховочное” поведение участников конфликта.
   Кроме того, в теории игр находятся оптимальные стратегии по одному показателю (критерию). В практических ситуациях часто приходится принимать во внимание не один, а несколько числовых критериев. Стратегия, оптимальная по одному показателю, может быть неоптимальной по другим.
   Сознавая эти ограничения и потому, не придерживаясь слепо рекомендаций, даваемых теорий игр, можно все же выработать вполне приемлемую стратегию для многих реальных конфликтных ситуаций.

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

Терминология и классификация игр

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

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

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

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

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

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

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

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

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

конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).

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

7. Если любая возможная партия некоторой игры имеет нулевую сумму

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

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

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

Принцип максимина (минимакса)

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

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

.

Величину

  (1)

принято обозначать через  (или просто v) и называть нижним значением (нижней ценой) игры, а соответствующую этому значению стратегию i° игрока I — максиминной стратегией. Если игрок I придерживается данной стратегии, то его выигрыш будет не меньше максиминного значения, то есть

(2)

Аналогично стратегия j°, определяемая равенством

называется минимаксной стратегией игрока II, а соответствующее значение  (или просто ) — верхним значением (верхней ценой) игры.

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

  (3)

Полагая, что в неравенстве (2) j = j°, а в выражении (3) i = i°, получим:

(4)

Принцип, которого придерживается игрок I, называется принципом максимина, так как его гарантированный выигрыш равен величине (1). Игрок II также придерживается этого принципа, так как

.

Из неравенства (4) следует, что во всякой матричной игре .При этом возможны два следующих случая:

.                                             (5)

В первом случае игрок I может обеспечить себе выигрыш , игрок II в состоянии ему  не дать больше, чем .

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

Пример.

.

Нахождение  и  матрицы Н может быть проведено по следующей схеме:

 = 3,  = 4, ; 2-я строка — максиминная стратегия; 1-й столбец - минимаксная стратегия. Применение максиминной и минимаксной стратегий приводит к выигрышу игрока I, равному  (разность  достается игроку II, но можно привести пример, когда эта разность достается игроку I). Однако игрок I в игре , отклоняясь от максиминной и выбирая первую стратегию, может выиграть 4>3 (при условии, что игрок II придерживается минимаксной стратегии). Но игрок II, разгадав намерения игрока I, может выбрать свою четвертую стратегию и тем самым наказать его (даст ему 2<3). Игрок I в свою очередь может изменить решение и выбрать такую стратегию, при которой будет наказан игрок II, и т. д. И это будет происходить во всех играх, в которых .

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

Заключение

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

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

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

Список литературы

1.  Оуэн Г. Теория игр. - М.: Наука, 1971.

2.  Венцель Е.С. Элементы теории игр. -М, 1961.

3.  Мак-Кинси Дж. Введение в теорию игр. М., Физматгиз,1966

4.  А.Д.Школьников Основы теории игр. Л, Изд.горного института, 1970

5.  Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб.пособие. – 2-е изд., испр. – М.: Дело, 2002.

6.  Карлин С. Математические методы в теории игр, программировании и экономике. - М.: Мир, 1964.