Теория игр как теория математических моделей принятия решений в условиях столкновения, когда игрок располагает информацией о множестве возможных ситуаций. Понятие и отличительные особенности динамической игры, составление и структура его дерева.
Аннотация к работе
Теория игр - теория математических моделей принятия решений в условиях неопределенности, в условиях столкновения, конфликтных ситуациях, когда принимающий решение субъект (игрок), располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится во множестве решений, которые он может принять, и о количественной мере того выигрыша, который он мог бы получить, выбрав в данной ситуации данную стратегию. Игры - это математические модели ситуаций принятия решений, включающих взаимодействие нескольких действующих лиц - игроков. В зависимости от действий, предпринятых игроками, реализуется некоторый исход; у игроков имеются предпочтения на этих исходах и обычно существует конфликт интересов, поскольку различные игроки предпочитают различные исходы. Следовательно, игрок должен делать предсказания по поводу того, что будут делать другие игроки. Во-первых, это последовательность действий игроков при возможных сценариях развития событий в игре, а также выигрыши, получаемые игроками в зависимости от произошедших в игре событий.В основе теории игр лежат ситуации принятия стратегических решений. Результат зависит для каждого из игроков и от того, какие стратегии выберут его партнеры по игре. Интересны ситуации, когда кооперация выгодна для всех, но каждый из игроков пытается выиграть за счет другого (других), не вступая в кооперацию. Награждение нобелевской премией 1994 года в области экономики Харшаньи, Нэша и Штерна за работу в области теории игр указывает на то, что здесь в последние годы было достигнуто очень много. Дополнительно к тем составляющим, которые были указаны в прежнем определении, требуется также перечислить информационные множества, которые задают разбиение множества вершин (кроме конечных).
Введение
математический модель множество динамический
Теория игр - теория математических моделей принятия решений в условиях неопределенности, в условиях столкновения, конфликтных ситуациях, когда принимающий решение субъект (игрок), располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится во множестве решений, которые он может принять, и о количественной мере того выигрыша, который он мог бы получить, выбрав в данной ситуации данную стратегию.
Теория игр пытается математически объяснить явления, возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.
Теория игр была основана Джоном фон Нейманом и Оскаром Моргенштерном в их первой работе «The Theory of Games and Economic Behavior», изданной в 1944 году. В 1928 году в математических анналах фон Нейманом была опубликована статья «О теории общественных игр» в которой впервые было применено понятие «теория игр». Использование этого понятия объясняется схожестью логики принятия решений в таких играх, как шахматы, скат или покер, и в некоторых ситуациях общественной жизни, прежде всего в экономике и военном деле. Характерным для таких ситуаций является то, что результат для принимающего решение зависит не только от его решения, но и от того, какое решение примут другие. Поэтому оптимальный исход не может быть получен в результате принятия решения одним лицом.
Игры - это математические модели ситуаций принятия решений, включающих взаимодействие нескольких действующих лиц - игроков. Игроки совместно определяют результат, и каждый старается получить тот результат, который является с его точки зрения наилучшим.
В зависимости от действий, предпринятых игроками, реализуется некоторый исход; у игроков имеются предпочтения на этих исходах и обычно существует конфликт интересов, поскольку различные игроки предпочитают различные исходы. Поэтому каждый игрок сталкивается с вопросом о том, какие действия являются для него наилучшими. Поскольку игроки взаимозависимы, то ответ на этот вопрос будет зависеть не только от собственных предпочтений игрока, но и от того, как действуют другие игроки. Следовательно, игрок должен делать предсказания по поводу того, что будут делать другие игроки.
Человек, который в игре не участвует, может поставить перед собой близкий вопрос о предсказании общего исхода игры. Основываясь на предположении о рациональном поведении всех участвующих игроков, теория игр дает набор инструментов и концепций, с помощью которых можно получить ответы на эти вопросы.
Ситуации, которые можно описать как взаимодействие нескольких игроков, каждый из которых действует в соответствуии со своими целями, возникают в самых разных областях - в салонных играх (шахматах, карточных играх), в экономике, политике, военном деле, биологии. Теория игр предлагает набор формальных моделей и концепций, которые можно использовать для анализа подобных ситуаций.
При этом основной целью теории игр является предсказание поведения игроков и отыскание некоторого наиболее правдоподобного исхода (или множества исходов) игры. Концепцией решения (не путать с принятием решений!) называют правило, которое позволяет по данному описанию игры получить такие предсказания. По-видимому, концепция решения должна удовлетворять следующим условиям: * давать предсказания, согласующиеся с эмпирическими наблюдениями и интуицией;
* быть достаточно универсальной и приложимой к широкому кругу практически интересных ситуаций;
* предсказывать в большинстве случаев единственный исход.
По-видимому, не существует концепции, удовлетворяющей одновременно всем этим условиям, и любая используемая концепция будет лишь компромиссным вариантом.
1. Игры в развернутой форме
Динамическая игра более сложный объект, чем статическая игра. Для того чтобы описать динамическое игровое взаимодействие нескольких субъектов, нам необходимо знать две вещи.
Во-первых, это последовательность действий игроков при возможных сценариях развития событий в игре, а также выигрыши, получаемые игроками в зависимости от произошедших в игре событий. Во-вторых, необходимо знать, что каждому игроку может быть известно относительно ходов, уже сделанных другими игроками. В первом случае, мы говорим о дереве игры; во втором об информационных множествах игроков.
2. Дерево игры
Во-первых, нам (как и в статической игре) нужно определить множество игроков. Для того, чтобы моделировать случайные события, влияющие на выигрыш игроков, нам необходимо определить еще одного игрока природу. Таким образом, мы имеем I = {1, · · ·, N} ? {природа}.
Во-вторых, нужно определить, в каком порядке игроки ходят, и какие действия им доступны на каждом ходе. Например, в игре хулиган с гранатой первый ход делает прохожий; ему доступны действия отдать и не отдавать. В случае, если выбрано действие не отдать, делает ход хулиган; его возможные действия - взорвать и не взорвать. Эту информацию мы можем изобразить в виде следующего дерева (или графа) игры, изображенного на рисунке.
Дерево игры состоит из вершин и соединяющих их отрезков. Каждая вершина означает либо момент принятия решения одним из игроков, либо момент окончания игры. Моменты принятия решения обозначены жирными точками; их на нашем дереве два: принятие решения прохожим, и принятие решения хулиганом. Всего существует три варианта окончания игры: если прохожий отдает кошелек, если прохожий не отдает кошелек и хулиган взрывает гранату, и если прохожий не отдает кошелек, и хулиган не взрывает. В дереве игры всегда существует одна вершина, соответствующая началу игры. В нашем случае, это вершина, в которой делает ход прохожий.
Наконец, в-третьих, нам надо определить, как выигрыши игроков зависят от ходов, которые были сделаны. Формально, для каждой конечной вершины дерева игры мы определяем выигрыши для каждого игрока. В нашем случае, мы предполагаем, что выигрыш каждого игрока равен -1 в случае взрыва гранаты, 0 в случае, если взрыва нет, но игрок остался без кошелька, и 1, если взрыва не было, и кошелек остался у игрока.
3. Игра в развернутой форме с несовершенной информацией
Каждой вершине в развернутой форме игры соответствует единственная предыстория-то есть последовательность действий, которая приводит из начальной вершины в данную вершину. Особенностью рассматриваемых в предыдущей главе игр с совершенной информацией является то, что каждый игрок перед тем, как сделать ход, полностью знает предысторию игры - действия, выбранные ранее им и другими игроками. Другими словами, игрок знает, в какой вершине дерева он оказался. В этом разделе мы рассмотрим класс игр, называемых играми с несовершенной информацией, в которых игроки могут не знать полностью предысторию игры.
Чтобы отобразить ограниченность информации на дереве игры, используют так называемые информационные множества. Информационное множество отображает тот факт, что игрок не знает, в какой вершине дерева находится (т.е. не знает точно, какова была предыстория игры). Если игрок не может отличить две вершины дерева, то они принадлежат одному и тому же информационному множеству. Используя понятие информационного множества, мы можем дать формальное определение игр с совершенной (и полной) информацией: в играх с совершенной информацией в каждом информационном множестве находится только одна вершина.
Примером игры с несовершенной информацией служит любая статическая игра. Ее можно искусственно динамизировать., задав произвольным образом порядок ходов и определив подходящим образом информационные множества. Предположим, что первый игрок ходит первым, второй - вторым. Есть две вершины, в которых ход принадлежит второму игроку, однако сам он не может различить, выбирая свои действия, в какой вершине он находится; другими словами, эти две вершины находятся в одном и том же информационном множестве.
По сравнению с развернутой формой игр с совершенной (и полной) информацией, в развернутой форме игр с несовершенной информацией появляется еще один элемент - информационное множество. Какие требования накладываются на дерево игры, содержащее информационные множества с более чем одной вершиной? Во-первых, каждая вершина дерева игры (кроме конечных) должна принадлежать одному и только одному информационному множеству. Во-вторых, по смыслу определения информационного множества, в каждой вершине информационного множества ход должен принадлежать одному и тому же игроку. В-третьих, множества возможных действий во всех вершинах одного и того же информационного множества должны быть одинаковыми (в противном случае игрок мог бы по тому, какие альтернативы ему доступны, определить, в какой именно вершине он находится).
Еще один вид требований к дереву игры появляется, если предположить, что игроки не забывают ту информацию, которой они обладают. Это так называемые игры с идеальной памятью. Игра в развернутой форме называется игрой с идеальной памятью, если игроки всегда помнят то, что они ранее знали, и то, что они ранее делали.
Вывод
В основе теории игр лежат ситуации принятия стратегических решений. Результат зависит для каждого из игроков и от того, какие стратегии выберут его партнеры по игре. Интересны ситуации, когда кооперация выгодна для всех, но каждый из игроков пытается выиграть за счет другого (других), не вступая в кооперацию. Когда все ведут себя, таким образом, тогда все оказываются в худшем положении по сравнению с тем, которое было бы достигнуто при кооперировании. Многие экономические, военные, политические, биологические ситуации могут быть представлены в виде подобных игр.
Таким образом, теория игр стала одним из ведущих математических методов экономики и других областей науки. Награждение нобелевской премией 1994 года в области экономики Харшаньи, Нэша и Штерна за работу в области теории игр указывает на то, что здесь в последние годы было достигнуто очень много.
Как видим, развернутая форма игр с несовершенной информацией несколько более сложна, чем развернутая форма игр с совершенной информацией. Дополнительно к тем составляющим, которые были указаны в прежнем определении, требуется также перечислить информационные множества, которые задают разбиение множества вершин (кроме конечных). Информационные множества должны быть заданы так, чтобы каждая вершина, кроме конечных, принадлежала одному и только одному из них. Кроме того, по смыслу определения информационного множества, во всех его вершинах ход должен принадлежать одному и тому же игроку.
Используя понятие информационного множества, мы можем дать формальное определение игр с совершенной информацией: в играх с совершенной информацией в каждом информационном множестве находится только одна вершина.
Список литературы
1. Зенкевич Н.А., Петросян Л.А., Янг Д.В.К. Динамические игры и их приложения в менеджменте: учеб. пособие / Н.А. Зенкевич, Л.А. Петросян, Д.В.К. Янг; Высшая школа менеджмента СПБГУ.СПБ.: Изд-во Высшая школа менеджмента, 2009. 415 с.
2. Трояновский В.М. Математическое моделирование в менеджменте. Учебное пособие. 2-е изд., испр. и доп. - М.: Издательство РДЛ. 2003.