Принцип минимакса (осторожности)

Предположим, что противник всеведущ и угадывает все ходы! Первый игрок предполагает, что второй все знает и для хода i первого игрока выберет j (i): a_ij (i) £ a_ij," j = 1,…, n. Обозначим α_i=a_ij(i)=min a_ij, j=1,…,n; i=1,...,m

Тогда лучшей стратегией для первого игрока является выбор i ₀ такой, что

α=max_ia_i=max_i min_ja_ij=α_i0

Величину a назовем нижней ценой игры в чистых стратегиях.

Второй игрок из соображений осторожности считает, что первый " j выберет i (j) так, что a_ij (j) ³ a_ij, " i, т.е. β_j=max a_ij,j=1,…,m и выбирает j с минимальным b_j, т.е.

Β=min_j max_i a_ij=β_j0

Величину b назовем верхней ценой игры в чистых стратегиях.

Пример 1. a = –1, b = +1, a £ b

Пример 2. α=max{0.5, 0.7, 0.5}=0.7;

β=min{0.9, 0.7, 0.8}=0.7.

α=β.

Лемма. Для любой функции f (x, y), x Î X, y Î Y, справедливо неравенство

в предположении, что эти величины существуют.

Доказательство. Введем обозначения:

Тогда

Теорема. Необходимым и достаточным условием равенства верхней и нижней цен игры в чистых стратегиях является существование седловой точки в матрице (a_ij).

Доказательство. Необходимость. Пусть a = b. По определению

т.е. α≤α_i0j0≤β. Так как a = b, то α_ij0≤α_i0j0≤ α_i0j, , т.е. является седловой точкой.

Достаточность. Пусть седловая точка (i ₀ j ₀) существует, т.е.

то α_ij0≤α_i0j0≤ α_i0j, .

Тогда но по лемме верно обратное, т.е. . Следовательно a = b.

Дата добавления: 2014-01-04