12. Классификация игр. Определение седловой точки.

I В зависимости от количества игроков различают игры двух (парная игра) и более (множественная игра) игроков.

II По количеству стратегий игры делятся на:

1) Конечные - все игроки имеют конечное число возможных стратегий

2) Бесконечные - хотя бы один из игроков имеет бесконеч.кол-во возможных стратегий

III По характеру взаимодействия игры делятся на:

1) бескоалиционные: игроки не имеют права вступать в соглаш-я, образовывать коалиции;

2) коалиционные (кооперативные) – участники множественной игры могут вступать в коалиции. В кооперативных играх коалиции наперёд определены.

IV По характеру выигрышей игры делятся на:

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

2) игры с ненулевой суммой.

V По виду функций выигрыша:

1) Матричная игра – это конечная игра двух игроков с нулевой суммой, в к-рой задаётся выигрыш игрока 1 в виде платежной матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2).

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

3) Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной в зависимости от стратегий.

4) Если функция выигрышей является выпуклой, то такая игра называется выпуклой.

VI Ходы бывают личные (игрок сознательно выбирает и осуществляет действие) и случайные (выбор осущ-ся на волей игрока, а механизмом случайного выбора -монетка).

«Чисто азартные» игры состоят только из случ.ходов, Стратегические игры - игры, в которых конфликт отражает интересы актив.участников, которые осущ-т личные ходы.

Ситуации равновесия (седловые точки).

Рассмотрим матричную игру: два игрока А и В имеют противоположные интересы: выигрыш одного равен проигрышу другого. А хочет максимизировать, В -минимизировать. A имеет m стратегий, В- n. По максиминному критерию (максимальный из минимальных выигрышей ) определяем гарантированный выигрыш λ для А (меньше этого не получим). Этот выигрыш- нижняя цена игры. По минимаксному критерию (минимальный из максимальных выигрышей ) определяем β для B (больше этого не отдаст). Этот выигрыш- верхняя цена игры. Если нижняя цена игры равна верхней цене игры и совпадают номера индексов то есть седловая точка. Минимаксные стратегии игроков устойчивы, общее значение λ и β называется ценой игры, а выигрыш, достигаемый при этой паре стратегий называется Седловой точкой матрицы (на них достигается max по первой координате и min по второй).

Пара чистых стратегий (Ai, Вj) игроков А и В, образующая седловую точку и седловой элемент a_ij , называется решением игры и обладает свойством равновесия. Ai, Вj _-оптимальные чистые стратегии.

13.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях.

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

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

Смешанной стратегией SA игрока А называется применение чистых стратегий A1, A2, ..., Am с вероятностями p1, p2, ..., pi, ..., pm причем . Аналогично смешанные стратегии игрока В SB = (q1, q2, ..., qi, ..., qn).

Если мы подберем такой набор P*_i , который обеспечивает max-й выигрыш независимо от действий 2-ой стороны, то этот набор - оптимальная смешанная стратегия стороны А. - оптимальная смешанная стратегия стороны B.

Рассмотрим игру размера 2×2. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.

Если отсутствует, то оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2). Пусть задана платежная матрица:

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию , а игрок В — чистую стратегию B1 (1-ый столбец матрицы Р), равен цене игры v: a11 * p*1+ a21 * p*2= v. Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию B2, т.е. a12 * p*1+ a22 * p*2= v. Учитывая, что p*1+ p*2= 1, получаем систему уравнений для определения оптимальной стратегии и цены игры v:

аналогично находим для В:

Графический метод: .

На оси OX отложим отрезок единичной длины А1,А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (p,1-p). Точке А1(0;0) соответствует стратегия A1, точке А2(1,0)-А2. В точках А1 и А2 восстановим перпендикуляры, на которых будем откладывать выигрыши игроков. Если игрок выберет А1 стратегию, то выиграет при стратегии В1 игрока 2 а11, при стратегии В2-а12. Если А2, то при В1 его выигрыш –а21, при В2-а22.

Л оманая линия, составленная из частей отрезков, расположенная ниже всех отрезков, наз-ся нижней границей выигрыша игрока А (мин выигрыш). Эта мин.величина максимальна в точке К, то есть этой точке соотв-т оптим.стратегия А*=(р,1-р), а ее ордината равна цене игры v.

13*.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях.(ответ на вопрос по методичке)

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

Для каждого игрока можно задать следующие компоненты:

Pia – вероятность применения i-ой стратегии со стороны А.

Если подобрать такой набор Pia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {p_1a , p_2a , …, p_ma } = S_A и будет называться смешанной стратегией.

S^*_A = {p^*_1a , p^*_2a , …, p^*_ma } – оптимальная смешанная стратегия.

{ S_A } – множество смешанных стратегий со стороны А, из которых нужно выбрать оптимальную.

Игра 2*2 в смешанных стратегиях.

Е

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

а11	а12
а21	а22

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

a₁₁ p^*_1a + a₂₁ p^*_2a = γ - при игре против первой чистой стратегии стороны В.

a₁₂ p^*_1a + a₂₂ p^*_2a = γ – против второй чистой стратегии стороны В.

p^*_1a + p^*_2a = 1

Аналогично для В:

a₁₁ p^*_1b + a₁₂ p^*_2b = γ - при игре против первой чистой стратегии стороны В.

a₂₁ p^*_1b + a₂₂ p^*_2b = γ – против второй чистой стратегии стороны В.

p^*_1b + p^*_2b = 1

Решение системы уравнений:

Для того, чтобы полученные решения имели смысл необходимо требовать следующие соотношения:

или

Если выполняется либо одно, либо другое, то вероятности от 0 до 1.

Д

γ

ля стороны А: Для стороны В: