Игра в развернутой форме с несовершенной информацией

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

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 10.04.2014
Размер файла 19,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

математический модель множество динамический

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

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

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

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

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

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

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

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

* давать предсказания, согласующиеся с эмпирическими наблюдениями и интуицией;

* быть достаточно универсальной и приложимой к широкому кругу практически интересных ситуаций;

* предсказывать в большинстве случаев единственный исход.

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

1. Игры в развернутой форме

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

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

2. Дерево игры

Во-первых, нам (как и в статической игре) нужно определить множество игроков. Для того, чтобы моделировать случайные события, влияющие на выигрыш игроков, нам необходимо определить еще одного игрока природу. Таким образом, мы имеем I = {1, · · ·, N} ? {природа}.

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

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

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

3. Игра в развернутой форме с несовершенной информацией

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

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

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

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

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

Заключение

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

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

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

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

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

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

1. Зенкевич Н.А., Петросян Л.А., Янг Д.В.К. Динамические игры и их приложения в менеджменте: учеб. пособие / Н.А. Зенкевич, Л.А. Петросян, Д.В.К. Янг; Высшая школа менеджмента СПбГУ.СПб.: Изд-во Высшая школа менеджмента, 2009. 415 с.

2. Трояновский В.М. Математическое моделирование в менеджменте. Учебное пособие. 2-е изд., испр. и доп. - М.: Издательство РДЛ. 2003.

3. Костевич Л., «Математическое программирование» Изд-во «Новое знание», 2003.

Размещено на Allbest.ru

...

Подобные документы

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

    реферат [46,6 K], добавлен 06.05.2010

  • Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

    дипломная работа [81,0 K], добавлен 08.08.2007

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

    курсовая работа [318,4 K], добавлен 17.08.2013

  • Принцип минимакса как основа целесообразного поведения игроков в антагонистической игре. Порядок разыгрывания в некооперативной игре в нормальной форме. Принцип оптимальности стратегий для нее. Представление игры в развернутой и в нормальной форме.

    реферат [241,5 K], добавлен 20.10.2012

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

    реферат [49,5 K], добавлен 29.12.2010

  • Определение матричных игр в чистых стратегиях. Смешанные стратегии и их свойства. Решения игр матричным методом. Метод последовательного приближения цены игры. Отыскание седлового элемента. Антагонистические игры как первый класс математических моделей.

    контрольная работа [855,7 K], добавлен 01.06.2014

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

    курсовая работа [862,0 K], добавлен 28.05.2013

  • Игры, повторяемые многократно, их отличительные свойства и этапы. Смешанные стратегии, условия и возможности их использования на практике. Аналитический метод решения игры типа 2 x 2. Основные теоремы для прямоугольных игр. Алгебраические решения.

    презентация [893,5 K], добавлен 23.10.2013

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

    курсовая работа [1,4 M], добавлен 17.10.2014

  • Составление платежной матрицы, поиск нижней и верхней чисты цены игры, максиминной и минимаксной стратегии игроков. Упрощение платежной матрицы. Решение матричной игры с помощью сведения к задаче линейного программирования и надстройки "Поиск решения".

    контрольная работа [1010,3 K], добавлен 10.11.2014

  • Процесс выбора или построения модели для исследования определенных свойств оригинала в определенных условиях. Стадии процесса моделирования. Математические модели и их виды. Адекватность математических моделей. Рассогласование между оригиналом и моделью.

    контрольная работа [69,9 K], добавлен 09.10.2016

  • Содержание математики как системы математических моделей и инструментов для их создания. Возникновение "теории идей". Натуральные числа, множество целых чисел, рациональное число, вещественное или действительное число. Существующая теория чисел.

    реферат [81,7 K], добавлен 13.01.2011

  • Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.

    курсовая работа [1,0 M], добавлен 26.09.2013

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

    курсовая работа [1,1 M], добавлен 23.11.2010

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

    курсовая работа [3,0 M], добавлен 14.06.2011

  • Основные определения теории биматричных игр. Пример биматричной игры "Студент-Преподаватель". Смешанные стратегии в биматричных играх. Поиск "равновесной ситуации". 2x2 биматричные игры и формулы для случая, когда у каждого игрока имеется две стратегии.

    реферат [84,2 K], добавлен 13.02.2011

  • Постановка задач принятия решений в условиях неопределенности, генерация и оценки альтернативных вариантов их решения для хорошо и слабо структурированных проблем. Аналитическая иерархическая процедура Саати, метод порогов несравнимости "Электра".

    курсовая работа [38,3 K], добавлен 10.04.2011

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

    лабораторная работа [32,1 K], добавлен 21.06.2013

  • Теория малых упругопластических деформаций. Метод последовательных приближений. Метод упругих решений. Подход, основанный на методе дополнительных нагрузок. Теория пластического течения. Упругость объемной деформации. Критерий упрочнения Д. Дракера.

    презентация [264,1 K], добавлен 17.07.2015

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

    реферат [368,2 K], добавлен 13.06.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.