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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


реферат Игры с ненулевой суммой и кооперативные

Информация:

Тип работы: реферат. Добавлен: 30.04.2012. Сдан: 2011. Страниц: 8. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Содержание 

     Введение……………………………………………………………………..…3
    Игры с ненулевой суммой и кооперативные……………………………..5
      Игры с ненулевой суммой…………………………………………..5
      Кооперативные игры………………………………………………...9
    Практическая часть……………………………..………………………...
    Заключение………………………………………………………………..
     Список использованной литературы……………………………………… 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

       В экономике, например, оказался  недостаточным аппарат математического  анализа, занимающийся определением  экстремумов функций. Появилась  необходимость изучения так называемых  оптимальных минимаксных и максиминных  решений. Следовательно, теорию игр можно рассматривать как новый раздел оптимизационного подхода, позволяющего решать новые задачи при принятии решений.
     Целью курсового проекта является изучение теории игр.
     В соответствии с поставленной целью  предстоит решить следующие задачи:
      рассмотреть игры с ненулевой суммой;
      рассмотреть кооперативные игры;
      решение задачи.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    Игры  с ненулевой суммой и кооперативные
      Игры с ненулевой суммой
 
     Теория игр - раздел математики, предметом которого является анализ принятия оптимальных решений в условиях конфликта. Возникнув из задач классической теории вероятностей, теория игр превратилась в самостоятельный раздел в 1945-1955. Таким образом, теория игр - один из новейших разделов математики. Наиболее полное изложение идей и методов теории игр впервые появилось в 1944 в труде Теория игр и экономическое поведение (Theory of Games and Economic Behavior) математика Дж. фон Неймана (1903-1957) и экономиста О. Моргенштерна (1902-1977). Фон Нейман опубликовал несколько работ по теории игр в 1928 и 1935; другим предшественником теории игр по праву считается французский математик Э. Борель (1871-1956). Некоторые фундаментальные идеи были независимо предложены А. Вальдом (1902-1950), заложившим основы нового подхода к статистической теории принятия решений.
     Область приложения теории игр выходит, конечно, далеко за рамки таких игр и включает, например, математику, экономику, политику, военную стратегию. Однако в терминологии теории игр много заимствований из терминологии общеизвестных игр.
     Так лица, принимающие решения, называются игроками, а целевая функция — платежной функцией. Под игроками могут подразумеваться отдельные лица или группы лиц (как например, партнеры по игре в бридж), фирмы, страны и т.д. Выигрыш каждого игрока определяется платежной функцией. Таким образом, игра представляет собой совокупность известных всем игрокам правил, которые определяют, что может делать игрок и каковы последствия и выигрыши в результате каждого отдельного их действия [6].
     Ходэто момент игры, когда игроки должны произвести выбор одного из возможных вариантой. Партией игры называется некоторая определенная совокупность ходов и выборов. Существенной чертой любой игры является то, что выигрыш каждого игрока зависит обычно не только от сделанного им самим выбора, но и от выбора других игроков.
     Каждый игрок должен учитывать эту зависимость от остальных игроков при выборе стратегии. Стратегия - это набор правил, формулируемых до игры, которые определяют выбор варианта в любой из могущих возникнуть ситуаций. Так как понятие стратегий является в теории игр нейтральным, то эту дисциплину нередко называют «стратегическими играми».
     Одним из важных типов платежных функций является платежная функция в игре с нулевой суммой когда общая сумма выигрышей игроков равна нулю. В игре двух участников с нулевой суммой выигрыш одного из партнеров равен проигрышу другого, т. е. налицо прямой конфликт между игроками. Прямой противоположностью играм такого типа являются игры двух участников с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща. В общей игре с ненулевой суммой имеют место, как правило, и конфликты, и согласованные действия игроков.
     В игре с ненулевой суммой необязательно, чтобы один из участников выигрывал, а другой проигрывал; напротив, они могут и выигрывать и проигрывать совместно. Поскольку интересы игроков теперь не являются полностью противоположными, то имеется возможность угрожать противнику, блефовать, сообщать друг другу о своих намерениях, накапливать опыт игры. Так, например, если в игре с нулевой суммой игрокам не выгодно открывать друг другу свои стратегии, то в игре с ненулевой суммой иной раз желательно координировать свои действия с партнером или каким-либо способом влиять на его действия [5].
     Потребность в сообщении между партнерами и в координировании их действий совершенно очевидна в координированных играх, в которых платежи обоих игроков либо одинаковы, либо в более общем случае различаются на постоянную величину, так что игроки и выигрывают, и проигрывают совместно. Предположим в качестве примера, что два человека оказались в горящем доме. Дверь так сильно захлопнута, что ее можно открыть только совместными усилиями. Платежи показаны на рис. 1 Действуя вместе, оба человека могут спастись —  выигрыш каждого в этом случая равен 100: в противном случае могут пострадать оба   -   выигрыш каждого равен 0. Очевидно, что для них лучше всего действовать сообща.
                                                                     Второй человек 

           Толкать    Не толкать
                                                                     дверь        дверь
      Первый      Толкать дверь                  (100, 100)   (0, 0)
     человек      Не толкать дверь   (0, 0)         (0, 0) 

     Рис. 1  Платежная матрица игры «двое в горящем доме» 

     В качестве примера игры с ненулевой суммой рассмотрим еще одну игру. Двое подростков едут навстречу друг другу на автомобилях: проигравшим считается тот, кто первым свернет в сторону. Платежи указаны на рис. 2. Если один свернул в сторону, а другой нет, то «выигравший» игрок получает 5, а «проигравший» (свернувший с дороги) получает —5. Если же сворачивают оба, то состязание заканчивается вничью и выигрыши равны нулю. Если же никто из них не свернул в сторону, то игра завершается аварией выигрыш каждого равен —100. Здесь ни один из игроков не располагает доминирующей стратегией, которая является наилучшей при любых предположениях о поведении другого игрока. Если бы каждый из них мог убедить другого, что он намеревается свернуть, то они сыграли бы вничью, однако каждый испытывает желание выиграть, нарушив любое подобное соглашение. Если нарушают договоренность оба, то исходом является катастрофа.
                                                                                  

                                                                                    Водитель 2 

                                                                     Сворачивать      Не сворачивать
                                 Сворачивать                   (0, 0)                 (-5, 5)
     Водитель 1
                               Не сворачивать                (5, -5)               (-100, -100) 
 

     Рис. 2 Игра подростков на автомобилях
     Игры с ненулевой суммой могут быть кооперативными или некооперативными. В некооперативных играх игроки принимают решения независимо друг от друга либо потому, что координация запрещена, либо потому, что осуществление соглашения невозможно. Примером первой ситуации могут служить антитрестовские законы, запрещающие некоторые виды соглашений между фирмами, а примером второй заключение международных торговых соглашений, навязать которые трудно или невозможно.
     Один из подходов к решению некооперативных игр состоит в определении точки [точек) равновесия игр, т.е. точки (точек), где ни один из игроков не имеет никаких причин отказываться от своей стратегии независимых действий*. В игре двух подростков существуют две точки равновесия: (5. —5) и (— 5,5), где один игрок сворачивает в сторону, а другой нет.
     Для того чтобы дать точное определение понятию точки 
равновесия, используя понятие смешанной стратегии, предположим, что если игрок 1 выбирает стратегию Si1, а игрок 2 — стра- 
тегию Si2, то выигрыш первого игрока равен Пij1
а выигрыш второго Пij2. Если вероятность того, что игрок 1 
выберет i-ю чистую стратегию Si1, равна рi1 (i = 1,2,…,т), то смотанная стратегия первого игрока выражается вектором

     p1 = (p11,p21,….,pm1),  где p11'=1,    p1? 0
     Аналогично, если рj2   -   вероятность выбора j-й чистой стратегии
Sj2 игроком 2 (j = 1,2, …,п). то смешанная стратегия второго игрока выражается вектором
     p2 = (p12,p22,….,pn2)',   где   1p2=1,    p2? 0
     Точкой равновесия является пара векторов р1*, р2*. определяющих оптимальные смешанные стратегии каждого из игроков, т. е. стратегии, приводящие данного игрока к максимальному ожидаемому выигрышу при условии, что противник применяет свою (оптимальную) смешанную стратегию. Следовательно,
                                  р1П1р2* ? р11 р2*   для всех р1,
     р1П2 р2 ? р12 р2*        для всех  р2 .
     В каждой конечной игре двух лиц существует пара векторов смешанных стратегий, приводящих к точке равновесия. Такая пара векторов может быть не единственной, и может оказаться, что различным парам соответствуют различные значения (ожидаемого) выигрыша. Вообще говоря, в каждой игре п лиц с конечным числом стратегий существуют смешанные стратегии, приводящие к равновесию. Равновесие - это набор таких смешанных стратегий, которые невыгодно самостоятельно изменять ни одному из игроков.
      Кооперативные игры
     Кооперативной игрой называется игра с непостоянной суммой, в которой игрокам разрешается обсуждать перед игрой свои стратегии и договариваться о совместных действиях: иначе говоря, игроки могут образовывать коалиции. Основная задача в кооперативной игре состоит в дележе общего выигрыша между членами коалиции. Следует различать кооперативные игры с побочными платежами, в которых платежи являются переводимыми, и игры без побочных платежей, в которых платежи непереводимы.
     Один из принципов кооперативной игры без побочных платежей для двух игроков известен как решение Нэша. Игроки достигают некоторого соглашения о согласовании своих стратегий, причем если бы им не удалось скоординировать свои действия, то каждый игрок получил бы некоторый фиксированный платеж. Этот платеж называется платежом при угрозе. Так например, в соответствующей некооперативной игре точкой угрозы могли бы быть максиминные платежи.
     
     Нэш указал ряд разумных допущений, при которых решение игры с торгом является единственным.
     Первое допущение симметрия: предполагается, что решение не зависит от того, какие номера присвоены игрокам.
      Второе допущение - инвариантность относительно линейных преобразований: решение не зависит от монотонных линейных преобразований платежей.
     Третье допущение независимость от не имеющих отношения к делу альтернатив: решение не изменится, если исключить из рассмотрения те возможные выборы, которые не использованы в решении.
     Четвертое допущение оптимальность по Парето: не может быть решением такой набор платежей, помимо которого существует какой-нибудь другой набор платежей, более выгодный хотя бы для одного игрока. Если эти условия выполнены, то единственным решением является пара платежей (П1*2*), которые максимизируют произведение превышений этих платежей над платежами при угрозе
     max (П11) (П22)
                                                  П12
     Здесь П1, П2 - выигрыш каждого игрока; Т1, Т2 выигрыши каждого игрока в точке угрозы. На рис. 3 решение представлено в геометрической форме. Заштрихованная часть плоскости соответствует множеству возможных платежей это множество выпукло, так как игроки могут применять смешанные стратегии.
     Прямой линией на границе множества отмечена «передовая линия» платежей, т.е. множеству всех пар платежей, которые удовлетворяют допущению оптимальности по Парето. Точкой угрозы является точка Т, а решением Нэша является точка S, в которой передовая линия платежей достигает линии наибольшего уровня. Линии уровня в данном случае - это равносторонние гиперболы с центром в Т. Решение является единственным: оно принадлежит переговорному множеству, т.е. множеству всех точек на передовой линии платежей, в которых выигрыши игроков больше, чем в точке угрозы. 

      П2 Выигрыш игрока 2
       (П1 –Т1)(П22) = const
       Направление наискорейшего роста
      ……..
      Т2      S
      ………… Т точка угрозы                 Решение Нэша
      …………………..
      ……... Т1 П1
                       …….                                               Выигрыш игрока 1 

     Рис. 3 Решение Нэша в задаче торгов
     Кооперативными играми с побочными платежами называются игры, в которых допускается заключение взаимнообязывающих соглашений о стратегиях, а платежи могут перераспределяться между игроками. Поскольку разрешены побочные платежи, то следует рассматривать только общие выигрыши любых возможных коалиций. Игры такого типа можно анализировать, пользуясь характеристической функцией игры, с помощью которой описываются все возможные коалиции, а именно указывается, какой максимальный общий выигрыш может гарантировать себе каждая из коалиций. Если известно множество игроков в игре n лиц
N = {1,2,..,п},
то любое подмножество S множества N является коалицией; характеристическая функция указывает, чему равен гарантированный выигрыш для S. Таким образом, характеристическая функция представляет собой вещественную функцию, область определения которой состоит из 2n возможных подмножеств множества N*. Запишем эту функцию в виде
     v(S),     где   S С N.
                v( O) = 0;
                v(1) = 0,      v(2) = 0, v (3) = 0;
                v (l,2) = 0,   v (1,3) = 0,2,   v (2,3) = 0,2;
                 v ( 1,2,3) = v (N) = 1
     Рис. 4. Характеристическая функция для игры трех участников
     Пример характеристической функции для игры трех лиц представлен на рис. 4. Здесь каждая из четырех строк соответствует значениям характеристической функции для коалиций, число игроков в которых равно соответственно 0, 1, 2, 3. Первая строка отражает предположение, что максимальный выигрыш для пустого множества равен нулю. Вторая строка показывает, что выигрыш любого игрока, действующего в одиночку, равен нулю. В третьей строке указаны выигрыши трех коалиций, которые могут быть составлены из двух игроков. Если игроки 1 и 2 действуют совместно, они могут гарантировать себе выигрыш в размере 0,1: коалициям игроков 1 и 3 или 2 и 3 гарантирован выигрыш, равный 0.2. Наконец последняя строка показывает, что если все игроки объединяются в «большую коалицию», то выигрыш равен 1. Рассматриваемая игра представлена в нормализованной форме 0-1:
                            v(i) = 0,    при любом i € N.
v(N) = 1.    где N = {1,…, n},
     т.е выигрыш самостоятельно действующего игрока равен нулю, а выигрыш большой коалиции, включающей всех игроков, равен единице. Если для всех непересекающихся подмножеств А и В выполняется равенство
v(А?В)? v (А) + v(В),
     то характеристическая функция является супераддитивной. Это значит, что если нет ни одного игрока, который входил бы в обе коалиции А и В. то коалиция, составленная как объединение этих двух подмножеств, будет иметь выигрыш не меньший, чем сумма выигрышей А и В. Предположение о супераддитивности характеристической функции вполне приемлемо, поскольку создание коалиций было бы бессмысленным, если бы величина выигрыша уменьшалась с увеличением числа участников коалиции.
     Вектор П n-мерного евклидова пространства, компонентами которого являются суммарные выигрыши каждого отдельного игрока, называется «дележом»:
П = (П1, П2 ,..Пn),
     где Пi    -   выигрыш i-го игрока (i  = 1,2, …п).
       Примером дележа для игры, изображенной на рис. 4, является вектор (0,3;0,2;0,5). т. е. игрок 1 получает 0,3. игрок 2 получает 0,2. а игрок 3 — 0,5. Предположим, что если мы учтем всех игроков и все платежи, то величина суммарного выигрыша игроков будет равна выигрышу большой коалиции, включающей всех игроков, т. е.
                             n
v(N) =   ? Пi = ? Пi
        i€N                 i=0
     Это допущение называется условием групповой рациональности. Вполне обосновано также предположение, что участвуя в коалиции, каждый игрок получает по меньшей мере столько, сколько он мог бы получить, действуя независимо, т.е.
Пi ? v({i}) при любом   i N.
     Это допущение называется условием индивидуальной рационалъности. Укачанные предположения ограничивают чисто возможных дележей. Так например, в играх, представленных в формализованной форме, единственными приемлемыми дележами являются векторы с неотрицательными компонентами, сумма которых равна единице. Однако и при таких ограничениях множество дележей остается чрезвычайно большим. Поэтому, для того чтобы еще дополнительно сузить это множество, приходится вводить какой-либо критерий допустимости или доминирования на множестве дележей.
     Одним из слабых критериев доминирования на множестве 
дележей является критерий, называемый решением по фон Ней- 
манну-Моргенштерну. Множество игроков называется эффек- 
тивным при данном дележе, если их общий выигрыш после 
объединения в коалицию будет по меньшей мере равен сумме 
выигрышей, получаемых каждым игроком в отдельности. Следовательно, коалиция S является эффективной при дележе П = 
= (П1, …Пn), если

v(S) ? ?Пi.
            i€S
     В качестве примера рассмотрим игру, изображенную на рис. 4. 
В этой игре множество, состоящее из игрока 2 и игрока 3 является эффективным при дележе (0,95; 0; 0,05). Действительно, если 
они образуют коалицию, то их общий выигрыш составит 0,2. 
а это больше того, что можно получить согласно данному де- 
лежу. Дележ П1 = (П11, П12, .. ,П1nдоминирует, над дележом П2 = (П11, П22, .. ,П2n)  , если существует такая коалиция игроков, эффективная при П1, что каждый из игроков, вступивших в коалицию, получает при П1 больше, чем при П2. Иначе говоря, имеется некоторая коалиция S, такая, что

v(S) ? ?П1 i.
         все  i€S
     причем каждый член этой коалиции получает при П1 больше, чем при П2
П1 i> П2 i при всех i€S
     Так, например, в игре, изображенной на риc. 4. дележ П1 = (0,1;0,8;0,1) доминирует над П2 = (0.05:0.9:0,05). Действительно, коалиция (1,3) является эффективной при П1 и оба игрока 1 и 3 получают при П1 больше, чем при П2. Если удастся воспрепятствовать независимым действиям игроков, то возможность образования коалиции (1,3) служит гарантией того, что дележ (0,05;0,9;0,05) может никогда не использоваться в игре.
     Решением игры по фон Нейману и Моргенштерну называется множество дележей со следующими свойствами: ни один из дележей этого множества не доминирует над другим дележом из того же множества; для любого дележа, не входящего в множество, существует доминирующий дележ, принадлежащий данному множеству. Этот слабый критерий доминирования обычно несколько сужает множество дележей, однако он не приводит, как правило, к множеству, состоящему из одного дележа. В действительности, решение фон Неймана - Моргенштерна часто содержит бесконечное число дележей. В игре более чем с двумя участниками даже и число решений фон Неймана- Моргенштерна (т.е. число множеств дележей, каждое из которых является решением фон Неймана Моргенштерна) может быть либо очень большим, либо бесконечным. Кроме того, существует ряд примеров игр, которые не обладают решениями фон Неймана-Моргенштерна [5].
     Более сильный критерий доминирования на множестве де- 
лежей можно задать с помощью понятия «ядра» игры. Ядро — 
это некоторое подмножество каждого решения фон Неймана- 
Моргенштерна (если такие решения существуют). Число дележей, входящих в ядро, значительно меньше, чем в решении 
фон Неймана-Моргенштерна, поскольку дележи, входящие в 
ядро, должны удовлетворять следующему условию: каждая из 
коалиций при данном дележе получает по меньшей мере столько, сколько могли бы получить в сумме входящие в нее игроки, 
действуя самостоятельно. Ядром называется множество всех недоминируемых дележей, т.e. таких дележей П= (П1, .. ,Пn) , которые удовлетворяют условию

      i ? v(S)   для любого подмножества S из N.
                                                    i€S
     Следовательно, множество дележей, входящих в ядро, удовлетворяет условию «коалиционной рациональности». Это условие включает более частные условия «индивидуальной рациональности» (когда рассматриваются подмножества, состоящие из отдельных игроков), «групповой рациональности» (когда подмножеством является большая коалиция, включающая всех игроков) и условие рациональности любой коалиции промежуточного размера. Ядро описанной на рис. 4 игры трех участников показано в геометрической форме на рис. 5.  

       П3
                                               (0;0;1)
                                                  (0,1;0;0,9) (0;0,1;0,9)
     
       Ядро
                             (0,8;0;0,2)…………………..……  (0;0,8;0,2)
                   (1;0;0)             (0;1;0)
       П1 (08;0,2;0) (0,2;0,8;0) П2
     Рис. 5 Ядро игры
     Изображенный на рисунке равносторонний треугольник является границей симплекса в пространстве Е3, т.е. границей множества дележей (П1
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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