Теория игр и её практическое применение

Муниципальное образовательное учреждение 
средняя общеобразовательная школа №___

городского округа  - город  Волжский  Волгоградской  области 
 
 

Городская  конференция  творческих  и  исследовательских  работ обучающихся

«С  математикой  по  жизни» 
 
 
 

Научное направление  –  математика 
 
 
 
 

«Теория игр и её практическое применение» 
 
 
 
 
 
 
 

                                        Автор: Гойдина Н.А.,

                                        обучающаяся 9б класса

                                        МОУ СОШ №2

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

                                        учитель математики Григорьева Н.Д.

2010  год

Оглавление 
 

     Введение 

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

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

    Цель  проекта предопределила его задачи:

• ознакомиться с историей зарождения теории игр;
• определить понятие и сущность теории игр;
• дать характеристику основным типам игр;
• рассмотреть возможные сферы применения данной теории на практике.

    Объектом проекта выступила теория игр.

    Предмет исследования – сущность и применение теории игр на практике.

    Теоретической основой написания работы явилась  экономическая литература таких  авторов, как  Дж. фон Нейман, Оуэн Г., Васин А.А., Морозов В.В., Замков О.О., Толстопятенко А.В., Черемных Ю.Н. 
 

.

     1. Введение в теорию игр

    1.1 История

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

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

    Принято считать монографию Дж. Неймана и  О. Моргенштерна “Теория игр и  экономическое поведение”, моментом рождения теории игр. После её публикации в 1944 г., многие ученые предсказали революцию в экономических науках благодаря использованию нового подхода. Эта теория описывала рациональное поведение принятия решений во взаимосвязанных ситуациях, помогая решать многие актуальные проблемы в разных научных областях. Монография подчеркивала, что стратегическое поведение, конкуренция, кооперация, риск и неопределенность, являются главными элементами в теории игр и непосредственно связаны с задачами управления.

    Начальные работы по теории игр отличались простотой предположений, что делало их менее пригодными для практического использования. За последние 10 – 15 лет положение резко изменилось. Прогресс в промышленности показал плодотворность методов игр в прикладной деятельности.

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

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

    В 1958-1959 гг. к 1965-1966 гг. была создана советская школа в теории игр, для которой была характерно скопление усилий в области антагонистических игр и строго военных приложений. Изначально это стало причиной отставания от американской школы, так как в то время основные открытия в антагонистических играх уже были сделаны. В СССР математиков до середины 1970-х гг. не допускали в область управления и экономики. И даже тогда, когда советская экономическая система начала рушиться, экономика не стала главным направлением для теоретико-игровых исследований. Профильный институт, занимавшийся и сейчас занимающийся теорией игр - Институт системного анализа РАН.  

    1.2 Определение теории игр

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

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

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

    Данный  раздел науки анализирует конфликты, используя математические методы. Теория получила своё название, так как простейшим примером конфликта является игра (например, шахматы или крестики-нолики). Как в игре, так и в конфликте каждый игрок имеет свои цели и пытается их достигнуть, принимая разные стратегические решения. [1] 

    1.3 Виды конфликтных ситуаций

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

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

    Игра  – математическая модель описания конфликта.

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

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

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

    а) множество заинтересованных сторон. В случае, если число игроков ограниченно (конечно), они различаются по своим номерам или по присваиваемым им именам;

    б) возможные действия каждой из сторон, именуемые также стратегиями или ходами;

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

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

    2 Виды игр

    2.1 Дилемма заключенного 

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

      Рассмотрим такую ситуацию. Двое  подозреваемых находятся под  следствием. У следствия недостаточно  улик, поэтому разделив подозреваемых, каждому из них предложили сделку. Если один из них будет по-прежнему молчать, а другой свидетельствовать против него, то первый получит 10 лет, а второго отпустят за содействие следствию. Если они оба будут молчать, то получат по 6 месяцев. Наконец, если они оба заложат друг друга, то они получат по 2 года. Вопрос: какой выбор они сделают?

    Таблица 1 – Матрица выигрышей в игре «Дилемма заключенного» 

    Предположим, что эти двое - рациональные люди, которые хотят минимизировать свои потери. Тогда первый может рассуждать так: если второй меня заложит, то мне  лучше тоже его заложить: так мы получим по 2 года, а иначе я получу 10 лет. Но если второй меня не будет закладывать, то мне всё равно лучше его заложить - тогда меня отпустят сразу. Поэтому не зависимо от того, что будет делать другой, мне выгоднее его заложить. Второй также понимает, что в любом случае ему лучше заложить первого. В результате оба из них получают по два года. Хотя если бы они не свидетельствовали друг против друга, то получили бы только по 6 месяцев.

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

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

    Конфликты, подобные этой дилемме, часто встречаются в жизни, например, в экономике (определение бюджета на рекламу), политике (гонка вооружений), спорте (использование стероидов). Поэтому дилемма заключенного и грустное предсказание теории игр получили широкую известность, а работа в области теории игр - единственная возможность для математика получить Нобелевскую премию.[2] 

    2.2 Классификация игр

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

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

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

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

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

    2.3 Типы игр

    Симметричные  и несимметричные

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

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

    С нулевой суммой и  с ненулевой суммой

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

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

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

    Кооперативные и некооперативные

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

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

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

    Гибридные игры включают в себя элементы кооперативных  и некооперативных игр.

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

    Параллельные  и последовательные

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

    С полной или неполной информацией

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

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

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

    Игры  с бесконечным  числом шагов

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

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

    Дискретные  и непрерывные  игры

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

     3. Применение теории игр 

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

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

    Двумя основными областями применения являются военное дело и экономика. Теоретико-игровые разработки применяются при проектировании автоматических систем управления для ракетного/противоракетного оружия, выборе форм аукционов по продаже радиочастот, прикладном моделировании закономерностей денежного обращения в интересах центральных банков, и т.п. Международные отношения и стратегическая безопасность обязаны теории игр (и теории принятия решений) в первую очередь концепцией гарантированного взаимного уничтожения. Это заслуга плеяды блестящих умов (в том числе связанных с RAND Corporation в Санта Монике, Калиф.), дух которой до высших руководящих постов дошел в лице Роберта Макнамары. Следует, правда, признать, что сам Макнамара теорией игр не злоупотреблял.