Теория игр: история и применение. Теория игр: классические примеры в картинках и конкретных игровых модулях

В результате изучения данной главы студент должен:

знать

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

уметь

Различать игры в стратегической и развернутой формах, строить "дерево игры"; формулировать игровые модели конкуренции для различных типов рынков;

владеть

Методами определения исходов игры.

Игры: основные понятия и принципы

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

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

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

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

Теория игр – это математическая теория конфликтных ситуаций.

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

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

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

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

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

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

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

В литературе встречаются следующие определения элементов, составляющих игру.

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

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

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

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

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

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

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

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

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

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

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

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

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

Повторим, что задача теории игр – нахождение оптимальных стратегий.

Классификация игр представлена на рис. 8.1.

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

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

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

Рис. 8.1.

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

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

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

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

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

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

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

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

Приведем следующий пример. Игра "Зачет". Пусть игрок 1 – студент, готовящийся к зачету, а игрок 2 – преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: A1 – хорошо подготовиться к зачету; A 2 – не подготовиться. У преподавателя имеется тоже две стратегии: B1 – поставить зачет; B 2 – не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей:

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

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

Еще один пример хорошо известной биматричной игры "Дилемма заключенного".

Каждый из двух игроков располагает двумя стратегиями: A 2 и B 2 – стратегии агрессивного поведения, a A i и B i – миролюбивое поведение. Предположим, что "мир" (оба игрока миролюбивы) лучше для обоих игроков, чем "война". Случай, когда один игрок агрессивный, а другой миролюбивый, выгоднее агрессору. Пусть матрицы выигрышей игроков 1 и 2 в данной биматричной игре имеют вид

Для обоих игроков агрессивные стратегии A2 и B2 доминируют мирные стратегии Ах и B v Таким образом, единственное равновесие в доминирующих стратегиях имеет вид (А2, B 2), т.е. постулируется, что результатом некооперативного поведения является война. В то же время исход (A1, B1) (мир) дает больший выигрыш для обоих игроков. Таким образом, некооперативное эгоистическое поведение вступает в противоречие с коллективными интересами. Коллективные интересы диктуют выбор мирных стратегий. В то же время, если игроки не обмениваются информацией, война является наиболее вероятным исходом.

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

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

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

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

На рис. 8.2 представлена экстенсивная форма игры, а в табл. 8.1 – стратегическая форма.

Рис. 8.2.

Таблица 8.1. Игра с одновременным принятием решений в стратегической форме

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

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

Воробьев Η. Н. Теория игр для экоиомистов-кибериетиков. М.: Наука, 1985.
Вентцель Е. С. Исследование операций. М.: Наука, 1980.

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

Слово «игра» не должно вводить в заблуждение. Это понятие в теории игр трактуется шире, чем в повседневной жизни. Ситуация стратегического взаимодействия может быть описана в виде модели, которую и называют игрой. Таким образом, в теории игр игрой будет считаться не только игра в шахматы, но и голосование в Совете Безопасности ООН, и торг продавца с покупателем на рынке.

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

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

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

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

С помощью разных теоретико-игровых концепций можно решать разные классы игр. Один из самых красивых теоретических результатов теории игр доказывает, что в некотором очень широком классе моделей можно гарантированно найти решение. Я имею в виду результат Джона Нэша, полученный им в 1950 году: в любой конечной игре в нормальной форме можно всегда найти по крайней мере одно равновесие в смешанных стратегиях. Хронологически это была первая универсальная теоретико-игровая концепция, которая позволяет гарантированно найти решение в очень широком классе моделей.

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

Конечно, Джон Нэш не является единоличным автором теории игр. Теория игр как самостоятельная наука начала развиваться чуть раньше, в начале ХХ века. Первые попытки формально определить игры, стратегии игроков и концепции решения игр восходят к именам Эмиля Бореля и Джона фон Неймана. Однако именно Нэш предъявил концепцию равновесия, которая позволяет гарантированно найти решение в конечных играх. В честь автора теоремы о существовании равновесия в смешанных стратегиях в конечных играх это равновесие стали называть равновесием Нэша.

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

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

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

И Оскар Моргенштерн стали основателями нового интересного направления математики, которое получило название "теория игр". В 1950-е годы этим направлением заинтересовался молодой математик Джон Нэш. Теория равновесия стала темой его диссертации, которую он написал, будучи в возрасте 21 год. Так родилась новая стратегия игр под названием «Равновесие по Нэшу», заслужившая Нобелевскую премию спустя много лет - в 1994 году.

Долгий разрыв между написанием диссертации и всеобщим признанием стал испытанием для математика. Гениальность без признания вылилась в серьезные ментальные нарушения, но и эту задачу Джон Нэш смог решить благодаря прекрасному логическуму разуму. Его теория "равновесие по Нэшу" удостоилась премии Нобеля, а его жизнь экранизации в фильме «Beautiful mind» («Игры разума»).

Кратко о теории игр

Поскольку теория равновесия Нэша объясняет поведение людей в условиях взаимодействия, поэтому стоит рассмотреть основные понятия теории игр.

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

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

Дилемма заключенного и научный прорыв

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

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

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

Пример дилеммы заключенного

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

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

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

Цепь логических умозаключений

Итак, преступник А рассматривает следующие варианты:

Я молчу и молчит мой напарник — мы оба получим по 1 году тюрьмы.
Я сдаю напарника и он сдает меня — мы оба получим по 2,5 года тюрьмы.
Я молчу, а напарник меня сдает — я получу 5 лет тюрьмы, а он свободу.
Я сдаю напарника, а он молчит - я получаю свободу, а он 5 лет тюрьмы.

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

Таблица вероятных исходов дилеммы заключенного.

Вопрос состоит в том, что выберет каждый участник?

«Молчать, нельзя говорить» или «молчать нельзя, говорить»

Чтобы понять выбор участника, нужно пройти по цепочке его размышлений. Следуя рассуждениям преступника А: если я промолчу и промолчит мой напарник, мы получим минимум срока (1 год), но я не могу узнать, как он себя поведет. Если он даст показания против меня, то мне также лучше дать показания, иначе я могу сесть на 5 лет. Лучше мне сесть на 2,5 года, чем на 5 лет. Если он промолчит, то мне тем более нужно дать показания, поскольку так я получу свободу. Точно так же рассуждает и участник B.

Нетрудно понять, что доминирующая стратегия для каждого из преступников - это дача показаний. Оптимальная точка этой игры наступает тогда, когда оба преступника дают показания и получают свой «приз» — 2,5 года тюрьмы. Теория игр Нэша называет это равновесием.

Неоптимальное оптимальное решение по Нэшу

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

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

Рассматривая вариант, когда оба преступника молчат и получают всего по 1 году, можно назвать него Парето-оптимальным вариантом. Однако он возможен, только если преступники смогли бы сговориться заранее. Но даже это не гарантировало бы этого исхода, поскольку соблазн отступить от уговора и избежать наказания велик. Отсутствие полного доверия друг к другу и опасность получить 5 лет вынуждает выбрать вариант с признанием. Размышлять о том, что участники будут придерживаться варианта с молчанием, действуя согласованно, просто нерационально. Такой вывод можно сделать, если изучать равновесие Нэша. Примеры только доказывают правоту.

Эгоистично или рационально

Теория равновесия Нэша дала потрясающие выводы, опровергнувшие существующие до этого принципы. Например, Адам Смит рассматривал поведение каждого из участников как абсолютно эгоистичное, что и приводило систему в равновесие. Эта теория носила название «невидимая рука рынка».

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

Чисто мужской эксперимент

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

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

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

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

Вся наша жизнь игра

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

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

Смешанные стратегии

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

Рассмотрим два вида стратегии:

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

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

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

Пенальти и смешанная стратегия

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

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

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

"ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ"

Кафедра информатики и методики преподавания информатики

Квалификационная работа

ТЕОРИЯ ИГР В НАЧАЛЬНОЙ ШКОЛЕ

Исполнитель:

Новикова Ксения Сергеевна,

студентка группы 591

Научный руководитель:

Дмитриева О.А.,

ассистент кафедры ИМПИ

Зав. кафедрой:

Матрос Д. Ш.,

докт. пед. наук, профессор

Дата допуска к защите:

Челябинск 2007

Введение

1.2 Решение матричной игры в чистых стратегиях

1.3 Решение матричной игры в смешанных стратегиях

1.4 Решение игр графическим методом

1.5 Сведение матричной игры к задаче линейного программирования

1.6 Игры с природой

Выводы по I главе

Глава II Разработка элективного курса “Элементы теории игр в начальной школе”

2.1 Место компьютера в начальной школе

2.3 Игра как метод обучения в начальной школе

2.4 Анализ программ и стандарта по информатике в начальной школе

2.5 Элективный курс

2.6 Педагогический эксперимент

2.7 Описание программного продукта

Выводы по II главе

Заключение

Список использованной литературы

Приложения

Введение

Теория игр была основана Джоном фон Нейманом и Оскаром Моргенштерном в их первой работе "The Theory of Games and Economic Behavior", изданной в 1944 году. В 1928 году в математических анналах фон Нейманом была опубликована статья "О теории общественных игр", в которой впервые было применено понятие "теория игр". Использование этого понятия объясняется схожестью логики принятия решений в таких играх, как шахматы и покер. Характерным для таких ситуаций является то, что результат для принимающего решение зависит не только от его решения, но и от того, какое решение примут другие. Поэтому оптимальный исход не может быть получен в результате принятия решения одним лицом.

Другим предшественником теории игр по праву считается французский математик Э. Борель (1871-1956). Некоторые фундаментальные идеи были независимо предложены А. Вальдом (1902-1950), заложившим основы нового подхода к статистической теории принятия решений.

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

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

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

Цель: изучение теоретических положений по теории игр и создание элективного курса "Элементы теории игр в начальной школе" с методической поддержкой.

Объект исследования: Теория игр

Предмет исследования: Обучение теории игр в начальной школе.

Задачи исследования:

изучить теоретический материал

отобрать задачи для практической реализации

разработать алгоритмы решения задач

программно реализовать отобранные задачи

разработать элективный курс

создать электронное пособие

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

Новизна работы заключается в следующем:

На данный момент не существует школьного курса по теме теории игр в начальной школе.

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

Разработан элективный курс “Элементы теории игр в начальной школе" и программно-методическая поддержка к нему.

Глава I Основные положения Теории игр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Такая стратегия - это, скорее, не ложь, а умалчивание.

Пример

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

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

В чём ошиблась эта пара? Мужчина, верно просчитав ситуацию с экономической точки зрения, не учёл психологического фактора. Жест с квартирой женщина восприняла как несерьёзность намерений. Но она не подумала о том, что её ухажёр - экономист, стало быть, принимает решения в первую очередь с позиции «выгодно - невыгодно». Таким образом, эта игра была проиграна обоими участниками.

Что делать

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

2. Игра на 90 баллов

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

Пример

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

Профессор согласился. На следующий день он рассадил студентов в разные аудитории и раздал по листку, где было лишь два вопроса. Первый стоил всего 10 баллов, а второй - 90 и звучал так: «Какое колесо спустило?»

Если опираться на логику, то ответ будет «Правое переднее колесо»: именно справа, ближе к обочине чаще всего валяется всякий мусор, на который в первую очередь наезжает передняя шина. Но не спешите.

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

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

Можно рассуждать так: есть ли у студентов что-то «общее» с одним из колёс? Возможно, год назад им вместе приходилось уже менять какое-то колесо. Или одна шина измазана краской, и оба студента знают об этом. Если такой момент будет найден, именно этот вариант и стоит выбрать. Даже если другой студент не знаком с теорией игр, он может вспомнить этот случай и указать нужное колесо.

Что делать

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

3. Игра с собой

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

Пример

Некая Ольга решает, пробовать ей курить или нет.

Дерево игры

На рисунке представлено так называемое дерево игры: его полезно рисовать каждый раз, когда вам нужно принять какое-либо решение. Ветви этого дерева - варианты развития событий. Цифры (0, 1 и -1) - выигрыш, то есть будет ли игрок победителем, если изберёт тот или иной вариант.

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

Предположим, что Ольга решила попробовать курить. Что дальше? Бросит она или нет? Это уже будет решать Будущая Ольга, на рисунке она вступает в игру по ветке «Попробовать». Если у неё уже сформировалась зависимость, то бросать курить она не захочет, поэтому варианту «Продолжать» ставим выигрыш 1 (вторая цифра правой нижней ветки).

Что мы получаем? Нынешняя Ольга будет в выигрыше в том случае, если попробует курить, но не попадёт в зависимость. А это, в свою очередь, зависит от Будущей Ольги, для которой выгоднее курить (она уже курит довольно давно, значит, у неё есть зависимость, стало быть, бросать она не захочет). Так стоит ли так рисковать? Может, сыграть вничью: получить выигрыш 0 и вообще не пробовать курить?

Что делать

Просчитывать стратегию можно не только в игре с кем-то, но и в игре с самим собой. Попробуйте нарисовать дерево игры, и вы увидите, приведёт ли ваше нынешнее решение к выигрышу.

4. Игра в аукцион

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

Пример

В эпизоде с аукционом из «Двенадцати стульев» Остап Бендер допустил стратегическую ошибку. Вслед за предложением в 145 рублей за лот он поднял цену сразу до двухсот.

С точки зрения теории игр Остапу следовало повышать ставку, но минимально до тех пор, пока не останется конкурентов. Таким образом, он смог бы сэкономить деньги и не попасть впросак: Остапу не хватило 30 рублей, чтобы оплатить комиссионный сбор.

Что делать

Есть игры, такие как аукцион, в которые нужно играть только головой. Заранее определитесь с тактикой и подумайте о максимальной сумме, которую вы готовы отдать за лот. Дайте себе слово не превышать лимит. Этот шаг поможет справиться с азартом, если он вдруг вас настигнет.

5. Игра на обезличенном рынке

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

Пример

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

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

Что делать

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

Теория игр - новая наука, но её уже изучают в лучших университетах мира. В издательстве «МИФ» вышел учебник «Стратегические игры». Он пригодится, если вы хотите научиться анализировать каждое своё действие, принимать взвешенные решения, лучше понимать не только других, но и себя.