Принцип доминирования стратегий игроков

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

Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак, конечно, не скажется, но зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

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

41. Критерий цены игры и оптимальных смешанных стратегий в терминах множеств смешанных стратегий игроков. (28 баллов)

42. Основная теорема теории матричных игр. (22 балла)
Основная теорема теории игр — теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть S* _A = (p* ₁ ,p* ₂ ,...,p* _i ,...,p* _m ) и S* _B = (q* ₁ ,q* ₂ ,...,q* _i ,...,q* _n ) — пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

43. Экономическая интерпретация максиминного и минимаксного принципов матричной игры. (28 баллов).
показателем эффективности стратегии А_i назовем минимальный выигрыш при этой стратегии: α_i=min a_ij, i=1,2..m, 1≤j≤n.

Максимином, или нижней ценой игры в чистых стратегиях, называется наибольший из показателей эффективности стратегий А_i, i=1,2..m,

α=max α_i=maxmin a_ij, 1≤j≤n 1≤i≤m

Стратегия А_к, показатель эффективности которой совпадает с максимином α_к =α, называется максиминной стратегией игрока А. множество всех (чистых) стратегий максиминных стратегий игрока А обозначим через (S_a^c)^{max min}

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

показателем неэффективности стратегий В_j назовем максимальный проигрыш игрока В при этой стратегии: В_j=max a_ij, j=1,2..n, 1≤i≤m.

Минимаксом, или верхней ценой игры в чистых стратегиях, называется наименьший из показателей неэффективности стратегий В_j, j=1,2..n: β=min β_j = minmax a_ij 1≤j≤n 1≤i≤m

Стратегия В_l, показатель неэффективности которой совпадает с минимаксом β_l = β_, называется минимаксной стратегией игрока В. Множество всех (чистых) минимаксных стратегий игрока В обозначим через (S_в^c) ^{min max} . принцип выбора игроком В минимаксной стратегии в качестве эффективной называется минимаксным принципом. Если игрок В придерживается минимаксного принципа выбора стратегий, то он при любой игре противника А не может проиграть больше минимакса β.

8. Теорема Дж. фон Неймана. (25 баллов) и, что тоже самое

44. Теорема о существовании решения игры в смешанных стратегиях. (22 балла)

Любая матричная игра имеет решение в смешанных стратегиях, т. е. существует цена игры в смешанных стратегиях V и оптимальные смешанные стратегии P⁰ и Q⁰ соответственно игроков A и B.

Иными словами: