91

10.Элементы теории игр.

10.1Основные понятия и определения.

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

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

Область приложения теории игр включает математику, экономику, политику, военную стратегию.

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

Выигрыш каждого игрока определяется платежной функцией.

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

Ход игры - это действие игрока , заключающееся в выборе одного из вариантов.

Партия - это некоторая определенная совокупность ходов, сделанная игроками.

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

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

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

10.2Классификация игр.

Игры классифицируются:

• по числу игроков;

• по числу стратегий;

• по свойствам платежных функций;

• по характеру предварительных переговоров между игроками до игры.

Классификация игр по числу игроков.

Различают игры с двумя, тремя и более участниками.

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

Классификация игр по количеству стратегий.

Различают конечные и бесконечные игры. Мы будем рассматривать конечные игры.

Классификация игр по свойствам платежных функций.

Различают:

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

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

Классификация игр по характеру предварительной договоренности.

Различают кооперативные и некооперативные игры.

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

Игра, в которой игроки не могут координировать свои стратегии подобным образом, называется некооперативной.

10.3 Описание игр.

Существует ряд способов описания и анализа игр:

1. описание в виде дерева игры для игры в развернутой форме.

При таком описании игры указывается:

1. какие ходы могут делать игроки;

2. какой информацией во время игры они располагают;

3. какие варианты можно выбирать;

4. какими могут быть предельные размеры платежей в конце игры.

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

Пример .

Дерево игры для игры в развернутой форме - на примере упрощенной игры двух лиц в покер.

В этой игре ставка каждого игрока равна 5 у.е. Набор карт в руках игроков может быть «старшим» (С) или «младшим» (М) .

У игрока 1 имеются две возможности: либо раскрыть карты (Р), либо повышать игру (В). При раскрытых картах старшая выигрывает банк, если карты игроков равны, то банк делится пополам. Если игрок повышает игру, то он вкладывает в банк еще 5 у.е.

Игрок 2 либо пасует(П) , либо уравнивает(У). Если он пасует, то игрок 1 выигрывает банк при любых картах. Если игрок уравнивает(вносит еще 5 у.е.),то, если одинаковые карты, то банк делится пополам, если нет- то банк достается тому, у кого «старшая».

Ход 1 - определение ставок и сдача карт(случайный ход).

Ход 2 - игрок 1 либо раскрывает карты, либо повышает игру.

Ход 3 - игрок 2 либо пасует , либо уравнивает.

10.3.1Игра в нормальной форме.

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

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

Игрок 2 выбирает стратегию

Платежная матрица имеет размерность m x n, где

m - число стратегий игрока 1,

n - число стратегий игрока 2,

- выигрыш первого игрока при выборе первым стратегии , а вторым - стратегии .

- выигрыш второго игрока при выборе вторым стратегии , а первым - стратегии .

10.3.2Игры двух участников с нулевой суммой.

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

Платежная матрица для игры двух участников с нулевой суммой.

Е сли игрок 1 выбирает стратегию , а игрок 2 выбирает стратегию , то игрок 1 получает , а игрок 2 получает .

Игры такого типа называют матричными. В такой игре игрок 1 стремится выбрать строку, чтобы выигрыш был максимален, а игрок 2 выбирает столбец, чтобы был минимален проигрыш.

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

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

, где .

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

Оптимальная стратегия игрока 1 будет состоять в выборе строки с самым высоким из таких минимальных платежей

.

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

Игрок 2 стремится обеспечить себе наименьшее значение платежа своему противнику вне зависимости от стратегии, избираемой первым игроком.

Игрок 2 стремится к гарантированному результату, выбирая минимаксную стратегию.

.

Если игрок 1придерживается максиминной стратегии, то его выигрыш будет

.

Если игрок 2 избирает минимаксную стратегию, то его проигрыш

.

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

Пример:

минимальные элементы строк

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

Однако не все игры двух участников с нулевой суммой являются вполне определенными .В общем случае

.

Игры, в которых строгое неравенство, называются не полностью определенными играми без седловой точки .

Пример:

минимальные элементы строк

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

Смешанная стратегия представляет собой вероятностную комбинацию чистых стратегий.

Смешанную стратегию для игрока 1 можно указать с помощью вектора вероятностей , где - вероятность выбрать i - ую стратегию первым игроком, .

( * )

( Условие () можно записать в ином виде: ,

где - единичный вектор размерности m : .

Для игрока 2 вектор , где - вероятность выбора j - стратегии, .