Понятие чистых и смешанных стратегий

Если в игре каждый из противников применяет одну и ту же стратегию, то про эту игру говорят, что она происходит в чистых стратегиях, а стратегии игроков А и В будут называться чистыми стратегиями. В антагонистической игре пара стратегий называется равновесной (устойчивой), если ни одному из игроков невыгодно отступать от своих стратегий.Применять чистые стратегии имеет смысл, если игроки знают о действиях противника. Если этого нет, то идея равновесия нарушается и игра может вестись как получится.Стратегии А1 В1 – устойчивы по отношению к информации о поведении противника.Признаком устойчивости пары стратегий это равенство верхней и нижней цены игры. И случай А1 В1 будет

ν = α = β. ν > 0, то игрок А будет в выигрыше, если ν < 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Теорема: каждая игра с полной информацией имеет седловую точку и следовательно решает в чистых стратегиях, т.е. имеется пара устойчивых стратегий, дающих устойчивый выигрыш равный ν.Если матрица не имеет седловую точку, то цена игры лежит α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии. Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

Задать смешанную стратегию это значит задать те вероятности, с которыми используются чистые стратегии.

S_A = || p₁, p₂ …. p_m ||,S_B = || q1, q2 …. q_m ||, A: ∑ pi = 1,B: ∑ qi = 1

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

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

Предположим что и игрок А и игрок В придерживаются смешанной стратегии. Необходимо определить А: ∑∑ a_ijp_iq_j

Для игрока В ожидаемый проигрыш равен ожидаемому выигрышу игрока А. Выигрыш первого игрока и средний проигрыш второго игрока равны друг другу.

18.Методы решения конечной игры двух лиц порядка m*n.

Предположим, что все элементы платёжной матрицы 0≤aij. Тогда α≤ν≤β. Согласно основной теореме матричных игр, любая матричная игра имеет 2 оптимальные смешанные стратегии.

S_A = (p₁, p₂, …, p_n)

S_B = (p₁, p₂, …, p_n)

Решаем игру для игрока А, при этом предполагая что игрок В использует только чистые стратегии. Тогда

a₁₁p₁ + a₂₁p₂ + … + a_m1p_m ≥ ν: B₁

a₁₂p₁ + a₂₂p₂ + … + a_m2p_m ≥ ν: B₂ (1)

a_1np₁ + a_2np₂ + … + a_mnp_m ≥ ν: B_n

X₁ = P₁/ν, X₂ = P₂/ν … X_m = P_m/ν

a₁₁X₁… + a_m1p_m ≥ 1

a_1nX₁… + a_m1p_m ≥ 1 (2)

p₁+p₂+…+p_m=1

X₁+X₂+…+X_m = 1/ν (3)

max ν!

L(x) = X₁+X₂+…+X_m -> min (4)

Определим задачу линейного программирования.

X₁⁰…X_m⁰

ν = 1/(X₁⁰+X₂⁰…X_m⁰) (5)

p1 = X₁⁰*ν_опт

p2 = X₂⁰*ν_опт (6)

….

min L(x) = ∑x_i

∑a_ij: 1≤x_i (7) (прямая задача)

0≤x_i (i=1,2..)

В:

a₁₁q₁ + a₂₁q₂ + … + a_m1q_m < ν: A₁

a₂₁q₁ + a₂₂q₂ + … + a_m2q_m < ν: A₂ (8)

a_m1q₁ + a_m2q₂ + … + a_mnq_m < ν: A_m

Y₁ = q₁/ν, Y₂ = q₂/ν … Y_m = q_m/ν

q₁+q₂+…+q_n=1

y₁+y₂+…+y_n=1/ν

L(y)=∑y_j -> max

∑a_ij, y_i≤1 (i=1,2…) (9) (двойственная задача)

0≤y_i

y₁⁰+y₂⁰…y_m⁰ = 1/ν_опт

ν_опт = 1/∑y_m⁰

q1 = y₁⁰*ν_опт

q2 = y₂⁰*ν_опт

….

ν=1/∑x_i = 1/∑y_i = 1/min L(x) = 1/ max L(y) (11)

1) α = 1, β = 3

2) Нет упрощений.

3) Прямая задача

L(x)=x₁+x₂+x₃ => min

x₁+3x₂+x₃ >= 1

2x₁+x₂+x₃>=1

3x₁+x₂+x₃>=1

x_i>=0

x₁=2/9, x₂=2/9, x₃=1/9

max L(x)=5/9

ν=1/(2/9+2/9+1/9)=9/5

p₁=x₁*ν=2/5

p₂=2/5

p₃=1/5

S_A=(2/5, 2/5, 1/5)

двойственная задача

L(y) = y₁+y₂+y₃ => max

y₁+2y₂+3y₃≤ 1 y₁=2/9

3y₁+y₂+y₃≤1 => y₂=2/9 max L(y) = 5/9

y₁+3y₂+y₃≤1 y₃=1/9

y_j>=0

y₁=a₁/ν

ν=1/(2/9+2/9+1/9)=9/5

q₁=y₂*ν=(2/9)*(9/5)=2/5

q₂=(2/9)*(9/5)=2/5

q₃=(1/9)*(9/5)=1/5

ν_опт=9/5

S_B=(2/5, 2/5, 1/5)

Задача mxn сводится к задаче линейного программирования.

Приближённый метод решения матричных игр mxn (Браун-Робинсон).

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

Сделано 20 шагов.

Подсчитав количество звёздочек суммарных выигрышей р₁ => 7, p₂ =>8, p₃ => 5. S_A: p₁=7/20, p₂=8/20/, p₃=5/20

S_B: q₁=8/20, q₂=8/20, q₃=4/20

β_∑=37

α_∑=36

ν=(α+β)/∑ = (α_∑/20 + β_∑/20)/∑ = (36/20 + 37/20)/2 =1,82

ν=1,8