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.