Лекции в печатном виде (990087), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

1. Ситуация с полной информацией.

B₃(+) - игрок В действует также, как и игрок А.

Вводятся две величины:

max min a_ij =  нижняя оценка цены игры

i j

min max a_ij =  верхняя оценка цены игры

i j

Докажем, что  <=

a_ij’ =  <=a_ij<= a_i’j’ 

Если  = = V, то говорят, что игра имеет седловую точку, а решением игры является пара чистых стратегий A_i*,B_j* , дающая максимальный выигрыш и минимальный проигрыш равный V равный цене игры.

Теорема 1.

Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях, причём это решение обладает свойством устойчивости.

Пример:

max min a_ij =  max min a_ij = 

i j i j

min max a_ij =  min max a_ij = 

i j i j

Седловой точки нет (A₁ ,B₄) = (A₂ ,B₄) = V = 5

Если нет седловой точки:

1. Однократно, следовательно, необходимо использовать наиболее осторожный метод maxmin.

2. Многократно – используются смешанные стратегии.

то есть каждой стратегии соответствует вероятноть:

A_i , p_i p_i

B_j , q_j q_j

Решением будет смешанная стратегия

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

S_B =( q₁, q₂…, q_N)

Теорема 2. (Основная теорема теории игр)

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

 <=V<=

S_A - чистая стратегия, следовательно S_A = (0, …, 0, 1, 0, …. ,0)

Методы решения матричных игр.

1. Проверить на наличии седловой точки.

2. Если нет седловой точки, то матрицу игры упрощают.

Из матрицы игры исключают доминируемые и дублируемые стратегии.

Задача: найти стратегии S_A =( p₁, p₂…, p_N) и S_B =( q₁, q₂…, q_N), дающие максимальный средний выигрыш.

Игра mxn, число активных стратегий будет равняться min(m,n)

Определение.

Стратегия A_i доминирует ( ) A_k, то есть A_i A_k, значит:

j a_ij a_kj

Определение.

Стратегия A_i дублирует (=) A_k, то есть A_i = A_k, значит:

j a_ij = a_kj

Стратегия B_j B_r, i a_ij a_rj

Стратегия B_j = B_r, i a_ij = a_rj

Пример: игра (5x5)

A₁ A₄

A₂ = A₅

B₁ B₂

B₁ B₅

A₂₁ = A₅

Получим S_A = (p₁, p₂, 0, 0, 0)

S_B = (q₁, 0, q₂, 0, 0)

Метод Лагранжа

Этот метод используется в играх с квадратной матрицей игры G(m,m).

S_A=(p₁,p₂) - вектор вероятностей выбора стратегий игроком А.

S_B=(q₁,q₂) - вектор вероятностей выбора стратегий игроком В.

Пусть игрок А использует смешанные стратегии, а В чистые, тогда выигрыш составит:

V₁=a₁₁*p₁+a₂₁*p₂

V₂=a₁₂*p₁+a₂₂*p₂

если же В также использует смешанные стратегии, то выигрыш составит:

V=( a₁₁*p₁+a₂₁*p₂)*q₁+( a₁₂*p₁+a₂₂*p₂)*q₂

Строится функция Лагранжа:

L=(a₁₁*p₁+a₂₁*p₂)*q₁+(a₁₂*p₁+a₂₂*p₂)*q₂+₁*(p₁+p₂-1)+ ₂*(q₁+q₂-1)

q₁ , q₂

p₁ , p₂

p₂ =1- p₁

q₂ =1- q₁

Получим

;

;

;

Пример.

G(2,2)

Метод линейного программирования

Этот метод используется в играх с произвольной матрицей игры G(m,n).

S_A=(p₁,p_2,…, p_i,…, p_n) - вектор вероятностей выбора стратегий игроком А.

S_B=(q₁,q_2,…, q_j,…, q_n) - вектор вероятностей выбора стратегий игроком B.

Требование, накладываемое на матрицу - i , j a_ij>0

Характеристики

Список файлов лекций