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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


реферат Антагонистические и матричные игры

Информация:

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

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


 

      Содержание

 

      Введение

 
     Реальные  конфликтные ситуации приводят к  различным видам игр. Игры различаются  по целому ряду признаков: по количеству участвующих в них игроков, по количеству возможных игроков, по количеству возможных стратегий, по характеру взаимоотношений между игроками, по характеру выигрышей, по виду функций выигрышей, по количеству ходов, по характеру информационной обеспеченности игроков.
     Для матричных игр доказано, что любая  из них имеет решение, и оно может быть легко найдено путем сведения игры к задаче линейного программирования), биматричные игры (это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока А, столбец - стратегии игрока В, на пересечении строки и столбца в первой матрице находится выигрыш игрока А, во второй матрице - выигрыш игрока В.
     Для биматричных игр также разработана  теория оптимального поведения игроков, однако решать такие игры сложнее, чем обычные матричные непрерывные игры (Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения), и т.д.
     Возможны  также и другие подходы к разбиению  игр. Теперь вернёмся непосредственно  к теме исследования, а именно к  Теории игр. Для начала дадим определение  этому понятию.
     Теория  игр - раздел математики, изучающий  формальные модели принятия оптимальных  решений в условиях конфликта. При  этом под конфликтом понимается явление, в котором участвуют различные  стороны, наделённые различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений (например, на основе недостаточных данных) можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому теория игр рассматривается также, как теория принятия оптимальных решений в условиях неопределённости. Она позволяет систематизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии и других науках. Участвующие в конфликте стороны называются коалициями действия; доступные для них действия - их стратегиями; возможные исходы конфликта - ситуациями.
     Задача  теории состоит в том, что является:
     1) оптимальным поведением в игре.
     2) исследование свойств оптимального  поведения
     3) определение условий, при которых  его использование осмысленно (вопросы  существования, единственности, а  для динамических игр и вопросы  именной состоятельности).
     4) построение численных методов  нахождения оптимального поведения. 
     Теория  игр, созданная для математического  решения задач экономического и  социального происхождения, не может  в целом сводиться к классическим математическим теориям, созданным для решения физических и технических задач. Однако в различных конкретных вопросах теория игр широко используются весьма разнообразные классические математические методы.
 

      Глава 1. Игровые модели

     1.1. Теория игр

 
    Экономист математик должен уметь принимать решение в условиях неопределенности, уметь использовать математический инструментарий, отражающийся на ключевые понятия вероятности, матрицы, основы линейного программирования.
    В природе, в обществе часто встречаются явления, в которых те или иные участники имеют несовпадающие интересы и располагают различными путями для конфликта, и они являются предметом изучения теории игр. Под конфликтом будем понимать всякое явление, применительно к которому можно говорить, кто и как в этом явлении участвует, каковы могут быть у этого явления исходы, кто в этих исходах заинтересован и в чем эта заинтересованность состоит.
    Ход событий в конфликте зависит  от решений, принимаемых каждой из сторон, и поэтому поведение любого участника  конфликта, если оно в том или  ином смысле разумно, должно определяться с учетом возможного поведения всех его участников.
    Для конфликта характерно то, что ни один из его участников заранее не знает решений, принимаемых остальными участниками, т.е. вынужден действовать в условиях неопределенности. Неопределенность исхода может проявляться не только в результате сознательных действий других участников, но и как результат действия тех или иных «стихийных сил» (неопознанной природы). Важно лишь то, что в наличии двух или более сторон с различными целями (в том числе сознательных индивидуумов или природы) исключает априорную оценку каких-либо вероятностных распределений того или иного исхода, которая, тем самым предопределяется конфликтностью явления. Конфликт может возникнуть также из различия целей, которые отражают не только несовпадающие интересы различных сторон, но и многосторонние интересы одного и того же лица. Например, конструктор обычно преследует многосторонние - интересы, согласуя противоречивые технико-экономические требования, предъявляемые и конструируемому изделию (минимизации габаритов и стоимости, максимизация надежности и т.п.).
    Наконец, прямо противоположные интересы различных сторон явно проявляются  в непосредственной борьбе (военной, дипломатической, экономической, спортивной и т.д.).
    Формализация  содержательного описания конфликта  представляет собой его математическую модель, которую называют игрой. Участников конфликта называют игроками. При  этом в качестве единого игрока может  выступать целый коллектив, имеющий  некоторые общие интересы (фирма, предприятие, спортивная команда, воюющая сторона и т. д.). Теория игр изучает оптимальное поведение игроков в играх в том или ином смысле.
    По  традиции изложение теории антагонистических  игр, моделирующих антагонистические  конфликты, т. е. конфликты двух лиц, интересы которых прямо противоположны. Поэтому антагонистическом конфликте у сторон нет почвы для согласования действий. Исход антагонистической игры оценивается вещественным числом, которая одна из сторон старается максимизировать, а другая – минимизировать. Отсюда выигрыш (в самом широком смысле) одной из сторон в антагонистическом конфликте составляет проигрыш (потери) противной стороны и является одним из разделов программ - теория конечных антагонистических игр1. В этих играх игроки, для достижения своих целей, располагают лишь конечным числом возможных действий (стратегий), которые они выбирают независимо друг от друга.
    Рассматривая бесконечные, которые отличаются от матричных лишь тем, что один или оба игрока имеют бесконечное число стратегий. Концептуально эти игры ничем не отличаются от матричных. Педагогически их разделение связанно преимущественно с тем, что вводится основные и первоначальные, возможно, трудноуспеваемые понятия и концепции теории антагонистических игр. В этом случае хотелось использовать минимум необходимого математического аппарата.
    Значительная  часть теории игр посвящена многошаговым играм. Поэтому, например, общие динамические игры, требующих более тонких математических конструкций, нами не рассматриваются. Все игры характеризуются тем, что игроки совершают свои выборы не раз и навсегда, а последовательно по времени. Поэтому они располагают той или иной информацией о развитии игры в прошлом. Существует также теория многошаговых игр n лиц.
    Бескоалиционные игры описывают конфликты, в которых интересы игроков не являются диаметрально противоположными (в частности, эти интересы могут совпадать). В этих играх игроки стремятся к ситуациям равновесия, т. е. к таким ситуациям, отклонение от которых отдельного игрока, если остальные игроки не изменяют своих стратегий, может привести разве лишь к его проигрышу.
    Конфликты, в которых принимают участие  очень большое число участников, моделируются играми с бесконечным  числом игроков. Мы затрагиваем только некоторые вопросы этой теории – игры, в которых выигрыш игрока определяется лишь его собственным выбором и «мерой» множества остальных игроков, сделавших такой же выбор2.
    Антагонистические и бескоалиционные игры, составляют основное содержание теории стратегических игр. При этом участникам антагонистической игры нет никакой выгоды, как отклоняться от своих оптимальных стратегий, так и договариваться до игры  о выборе совместного плана действий. В бескоалиционных играх игрок, отклоняющийся от ситуации равновесия, может лишь проиграть при условии, что остальные игроки будут стараться ее сохранить. Однако если от ситуации равновесия отклониться несколько игроков, то они могут и выиграть. Поэтому в бескоалиционных играх правила игры не предусматривают вступление игроков в коалиции. В реальных конфликтах такие ограничения возникают иногда из-за «физической» невозможности объединения или в силу законодательных актов.
    Вместе  с тем природой ряда конфликтов между  участниками допускается сотрудничество (кооперирование, согласование способов действий, обмен информацией и т. п.). В результате сторон могут использовать совместную стратегию. В этом случае исход игры определяется множеством их возможных выигрышей или выигрышей отдельных групп (коалиций) игроков. Поэтому модели этих игр, не имея стратегического аспекта, называются нестратегическими. Кооперативная теория, как раз и рассматривает вопросы, связанные с нестратегическими играми.
    Основная  проблема теории кооперативных игр  состоит в том, чтобы «разумно»  разделить выигрыш, который может получить коалиция из всех игроков, между этими игроками или указать множество возможных дележей выигрышей. В последнем случае выбор конкретного дележа может быть произведен по соображениям, не отраженным в теоретико-игровой модели. Естественно, что распределение выигрыша должно производиться «разумно». Различные понятия «разумности» приведет к различным решениям.
    Практика  создания и функционирования различных  организационных (в том числе  и эколого-экономических) систем показывает, что процедуры управления в них должны быть построены по иерархическому принципу. Задачи анализа и синтеза иерархических систем не укладываются в рамки обычной теории оптимального управления, так как в условиях взаимодействия подсистем становится неоднозначным само понятие оптимальности. Современная теория иерархических систем, получившая название информационной теории иерархических систем, возникла и сформировалась за последние 10 лет на стыке общей теории управления и теории игр. Параллельно развивалась близкая к ней по идеологии теория активных систем.
    Именно  наличие неопределенности приводит к образованию иерархических  структур и разделению полномочий по принятию решений. Если плановый орган  неточно знает параметры контролируемых им подразделений (подсистем), то ему  может быть выгодно, предоставить им определенную самостоятельность. При этом важно так обеспечить информационный обмен, чтобы эффективность управления не снижалась от децентрализации.
    Исследуется такая ситуация, когда создание высшего (коллективного) органа необходимо для обеспечения информацией нижнего уровня. Эта ситуация принятия решений в условиях ассиметрий информации в системе управления.

     1.2. Классификация игровых моделей

 
     Игровую модель можно определить, как совокупность (x,y) правил поведения при конфликтной ситуации и функции платежа Н(x,y) для каждого игрока на любом этапе игры.
     Ввиду того, что теория игр квалифицируется  как некоторый раздел математики, описание ее предмета также должно формулироваться достаточно четким, математическим образом. Если не говорить о понятиях модели вообще и модели математической, то теория игр содержит три нуждающихся в точном понимании термина:
      принятие решения,
      конфликт,
      оптимальность решения
     Дадим однозначное толкование каждому  из этих терминов на языке теории множеств.
     Принятие  решений (или стратегия игрока - совокупность рекомендаций по ведению игры от начала и до конца): Принятие субъектом К некоторого своего решения можно понимать просто как выбор некоторого элемента(решения) xиз множества всех допустимых решений gk.
     Конфликты: Содержательно конфликт рассматривается как явление, в котором решаются вопросы о том, кто и как в этом явлении участвует, какие у этого явления могут быть исходы, а также кто и как в этих исходах заинтересован. Во-первых, необходимо фиксировать, что в конфликте участвуют те или иные стороны, являющиеся принимающими решения субъектами. Эти стороны естественно называть коалициями действия. Здесь термин коалиция употреблен для подчеркивания возможной сложности, структурности принимающего решения субъекта3. В его роли может выступать целый коллектив, причем коллективы, составляющие различные коалиции действия, могут, вообще говоря, пересекаться. Заметим, что в конфликте может участвовать и лишь одна коалиция действия, причем этот случай с теоретико-правовой точки зрения оказывается, отнюдь не тривиальным. Множество всех коалиций действия будет обозначаться через W. Во -вторых, необходимо отразить возможности участников конфликта, т.е указать, какие именно решения может принимать каждая из коалиций действия КIW. Эти решения называются (коалиционными) стратегиями коалиции К. Множество всех стратегий коалиции действия К будем обозначать через gк. Исход конфликта определяется исходя из осуществимости результатов выбора всеми коалициями действия своих стратегий с учетом всех обусловленных между ними связей (если таковые предусмотрены) и называются ситуацией. Т.о., множество всех ситуаций можно понимать  как некоторое заданное подмножество g декартова произведения  (пары стратегий). В-третьих, необходимо указать стороны, отстаивающие некоторые интересы. Их естественно называть коалициями интересов. Множество таких коалиций интересов конструируемого конфликта будем обозначать через Wu   .
     В-четвертых, необходимо описать сами интересы (цели) сторон. Это значит, что для каждой коалиции интересов из  Wu и на множестве всех ситуаций g должно быть указано бинарное отношение предпочтения Rk  , понимаемое как отношение нестрогого предпочтения. Как обычно отношение нестрогого предпочтения  порождает отношение безразличия   Ik=RkCRk-1  , а также отношение строгого предпочтения  Pk=Rk\Ik (=Rk\Rk-1) .
     На  основе сказанного формальным представлением о конфликте можно считать  систему
     Г=<W, >, где
     W, и Wu произвольные множества             
       и  Rk I g?g ,  K I Wu
     Системы такого вида будем называть играми.
     Остается  математически сформулировать представление  об оптимальности принимаемых решений. Это, однако, оказывается существенно  более трудным, чем обрисованная выше математизация понятия принятия решений и конфликта. Основная причина этого состоит в том, что пока еще не выработано достаточно содержательных представлений об оптимальности. Начнем с того почти тривиального соображения, что всякое содержательное представление об оптимальности в условиях конфликта состоит в правиле выбора для каждого конфликта (из определенного класса) некоторого множества его исходов, которые при этом и объявляются оптимальными. В математической форме это выглядит следующим образом: оптимальность это отображение j, которое каждой игре Г принадлежащей некоторому классу игр G, ставит в соответствие некоторое подмножество множества ее исходов g:  

                                        jГ I g , ГI G
     Соответствие  j при этом называется принципом оптимальности для класса игр G      , а множество исходов jГ- реализацией этого принципа для игры  Г  , или решением игры    в смысле принципа оптимальности.  Другими словами можно сказать, что оптимальной считается такая ситуация, в которой каждый игрок получает свой “максимальный” выигрыш, а именно: когда один игрок получает максимальный выигрыш, а второй - минимизирует свой проигрыш.
     В наиболее чистом виде сущность теории игр, как теории математических моделей принятия оптимальных решений в условиях конфликтов, воплощается в теории бескоалиционных игр, в которых множества коалиций действия и коалиций интересов совпадают; те и другие в этом случае называются игроками.
     В свою очередь в классе бескоалиционных  игр присутствуют свои подклассы. Рассмотрим некоторые важные подклассы бескоалиционных игр.
     Бескоалиционная игра Г называется конечной, если конечны все множества стратегий gi игроков iII. Конечные игры составляют простейший, но важный класс игр.
     Конечная  бескоалиционная игра называется биматричной, если множество I в ней состоит из двух игроков (т.е. I={1,2}). Такое название объясняется возможностью следующего естественного описания игр этого класса. Если составить две таблицы, в которых входы по строкам будут соответствовать стратегиям игрока 1, а входы по столбцам - стратегиям игрока 2, то в этих таблицах клетки будут соответствовать ситуациям игры. Если заполнить клетки первой таблицы значениями функции выигрыша игрока 1, а клетки второй таблицы - значениями функции выигрыша игрока 2, то получим пару матриц, полностью описывающих игру. Эти матрицы называются матрицами выигрышей в биматричной игре4.
     Биматричная игра с m?n - матрицами выигрышей игроков называется m?n - биматричной. Биматричную игру с матрицами выигрышей А и В будем обозначать через Г(А,В) или ГА,В, i - я строка любой матрицы обозначается через Мi. , j - ый столбец - М.j .
     Бескоалиционная игра Г называется игрой с постоянной суммой, если для каждой ее ситуации xIg будет выполняться условие
      , где  Hi - функция выигрыша или платежа.
     Игра  Г называется игрой с нулевой суммой, если константа с =0 (модель в которой стороны ведут расчеты только между собой и платежи не поступают со стороны и не уходят на сторону).
     Бескоалиционная игра с нулевой суммой, в которой имеется только два игрока (первый игрок выбирает стратегию в множестве Х, второй  - в множестве Y, при этом каждый не знает, что выбирает другой) I={1,2} называется антагонистической. Цель первого игрока: Н ® max, цель второго игрока: Н ® min. Таким образом, в любой антагонистической игре выигрыш одного из игроков численно равен проигрышу другого:  H1(x1,x2)=-H2(x1,x2). Цена игры определяется, как суммарный платеж каждому игроку.
        Антагонистическая биматричная игра называется матричной.
     Неантагонистические игры - модели,  в которых присутствуют частично противоположные и частично совпадающие интересы “играющих” сторон.
     Дискретные  игры - игры, в которых множество стратегий дискретно.
     Игры  с полной информацией - игры, в которых все ходы противника заранее известны.
     Определение: Пара (x0,y0) I X?Y называется седловой точкой, если F(x,y0) ?
                                                                                                                             "xIX
     F(x0,y0) ? F(x0,y)
      "yIY
     Или по-другому: sup F(x,y0)=F(x0,y0)=inf F(x0,y),
                                      xIX                            yIY
     или max F(x,y0)=F(x0,y0)=minF(x0,y).
              xIX                             yIY
     Игровой смысл понятия седловой точки: игроки выбрали стратегии x0, y0, следовательно 1-ому игроку невыгодно отклоняться от x0, 2-ому игроку невыгодно отклоняться от y0. Т.е. это устойчивая точка.
     Определение: Г имеет решение, если функция  выигрыша F имеет седловую точку  на произведении X?Y. При этом x0,y0 называются оптимальными стратегиями.
 

      Глава 2. Антагонистические и матричные игры

     2.1. Антагонистические игры

 
     Задача  принятия решения, рассматриваемая  в рамках системного подхода, содержит три основные компоненты: в ней  выделены система, управляющая подсистема и среда. Теперь мы переходим к изучению задач принятия решения, в которых на систему воздействует не одна, а несколько управляющих подсистем, каждая из которых имеет свои цели и возможности действий. Такой подход к принятию решений называется теоретико-игровым, а математические модели соответствующих взаимодействий называются играми. Ввиду различия целей управляющих подсистем, а также определенных ограничений на возможности обмена информацией между ними, указанные взаимодействия носят конфликтный характер. Поэтому всякая игра представляет собой математическую модель конфликта. Ограничимся случаем, когда управляющих подсистем две. Если цели систем противоположны, конфликт называется антагонистическим, а математическая модель такого конфликта называется антагонистической игрой.5
     В теоретико-игровой терминологии 1-я  управляющая подсистема называется игроком 1, 2-я управляющая подсистема - игроком 2, множества их альтернативных действий называются множествами стратегий этих игроков. Пусть Х - множество стратегий игрока 1, Y - множество стратегий игрока 2. Состояние системы однозначно определяется выбором управляющих воздействий подсистемами 1 и 2, то есть выбором стратегий x?X и y?Y. Пусть F(x,y)- оценка полезности для игрока 1 того состояния системы, в которое она переходит при выборе игроком 1 стратегии х и игроком 2 стратегии у. Число F(x,y) называется выигрышем игрока 1 в ситуации (x,y), а функция F - функцией выигрыша игрока 1. Выигрыш игрока 1 одновременно является проигрышем игрока 2 , то есть величиной, которую первый игрок стремится увеличить, а второй – уменьшить. Это и есть проявление антагонистического характера конфликта: интересы игроков полностью противоположны (то, что выигрывает один, проигрывает другой).
     Антагонистическую игру естественно задать системой Г=(Х, Y, F).
     Заметим, что формально антагонистическая  игра задается фактически так же, как  и задача принятия решения в условиях неопределенности - если отождествить управляющую подсистему 2 со средой. Содержательное различие между управляющей  подсистемой и средой состоит в том, что поведение первой носит целенаправленный характер. Если при составлении математической модели реального конфликта у нас есть основание (или намерение) рассматривать среду как противника, цель которого - принести нам максимальный вред, то такую ситуацию можно представить в виде антагонистической игры. Другими словами, антагонистическую игру можно трактовать как крайний случай ЗПР в условиях неопределенности, характеризуемый тем, что среда рассматривается как противник, имеющий цель. При этом мы должны ограничить виды гипотез о поведении среды.
     Наиболее  обоснованной здесь является гипотеза крайней осторожности, когда, принимая решение, мы рассчитываем на самый худший для нас возможный вариант  действий среды.
     Антагонистические игры, в которых один или оба игрока имеют бесконечное множество стратегий называются бесконечными. С теоретической точки зрения это отличие малосущественно, т.к. игра остается антагонистической, и проблема состоит в использовании более сложного аппарата исследования.
     Пример .(Одновременная игра преследования  на плоскости.)
     Пусть S1 и S2 - множества на плоскости. Игра Г заключается в следующем. Пусть 1-ый игрок выбирает некоторую точку хIS1, а игрок 2 - точку yIS2. При совершении выбора игроки 1 и 2 не имеют информации о действиях противника, поэтому подобный выбор удобно интерпретировать как одновременный. Точки хIS1, yIS2 являются в этом случае стратегиями игроков 1 и 2 соответственно. Таким образом, множества стратегий игроков совпадают с множествами S1 и S2 на плоскости.
     Целью игрока 2 является минимизация расстояния между ним и вторым игроком (игрок 1 преследует противоположную цель). Поэтому под выигрышем H(x,y) игрока 1 в этой игре будем понимать евклидово  расстояние r(x,y) между точками xIS1 и yIS2, т.е. H(x,y)= r(x,y), xIS1 и yIS2. Выигрыш игрока 2 полагается равным выигрышу игрока 1, взятому с противоположным знаком(т.к. игра антагонистическая).
     Отдельно  надо отметить специальный класс  антагонистических бесконечных  игр, в которых X=Y=[0, 1]. В этих играх ситуациями являются пары чисел (x,y), где x, yI[0, 1]. Эти пары задают точки единичного квадрата. Поэтому такие игры называются играми на единичном квадрате. Класс игр на единичном квадрате во многом характеризует бесконечные антагонистические игры и поэтому является базовым при исследовании бесконечных игр.
     Пример. (Поиск на отрезке.)
     Игрок 2 (прячущийся) выбирает точку yI[0, 1], а игрок 1 (ищущий) выбирает одновременно и независимо точку xI[0, 1]. Точка y считается “обнаруженной”, если ?x - y?? l, где 0< l <1. В этом случае игрок 1 выигрывает величину +1, во всех остальных случаях его выигрыш полагается равным 0. Игра антагонистическая. Функция выигрыша имеет вид
и т.д.................


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


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


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


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


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