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

Размещено на 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