Основные понятия теории игр. Примеры решения задач

смешанных стратегиях (или функцией игры) или платежной функцией игры с матрицей, заданной табл. 4.

- Функцию М(Р, q) можно задать в матричной форме М(Р, q ) = РАq^T, где Р = (р₁, р₂, …, р_m) – вектор строка размера [1´m],

                          – матрица выигрышей игрока А в чистых стратегиях (матрица размер [m´n]), 

– вектор столбец размер [n ´1].

 Проигрыш игрока В в ситуации (A_k,q) определяется по формуле  .

- Выигрыш игрока А в ситуации (р, В_k) определяется по формуле .

- Для функции М (р, q) можно вывести и некоторые другие формулы:

.

- Показатель эффективности смешанной стратегии  р  игрока А относительно множества `S_B смешанных стратегий игрока В определяется по формуле  

- Показатель эффективности смешанной стратегии  р  игрока А относительно множества S_B чистых стратегий игрока В  определяется по формуле  

- Показатель неэффективности смешанной стратегии q игрока В относительно множества `S_A смешанных стратегий игрока А определяется по формуле   .

-  Показатель неэффективности смешанной стратегии q игрока В относительно множества S_A чистых стратегий игрока А определяется по формуле   .

- Нижней ценой (или максимином) матричной игры в смешанных стратегиях называется величина  , где a_р – показатель эффективности смешанной стратегии  р  игрока А.

- Верхней ценой (или минимаксом) матричной игры в смешанных стратегиях называется величина , где b_q – показатель неэффективности смешанной стратегии  q  игрока В.

Теорема 2. Нижняя цена игры a и верхняя цена игры В в чистых стратегиях, нижняя цена игры `a  и верхняя цена игры `b в смешанных стратегиях удовлетворяют следующим неравенствам a £`a £`b £ b.

11.6. Седловая точка в смешанных стратегиях

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение `g =`a =`b называется ценой игры в смешанных стратегиях, а стратегии p<sup>0</sup> и q<sup>0</sup>, для которых выполняется равенство `g =`a<sub>р0</sub> =`b_q0 (и тогда это общее значение равно M(p⁰,q⁰), т.е. M(p⁰,q⁰) = `g ), называются оптимальными смешанными стратегиями соответственно игрока А и В.

Теорема 3. (Основная теорема матричных игр Фон Неймана).

Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях `g и оптимальные смешанные стратегии p⁰ и q⁰ соответственно игроков А и В, т.е.

.

Теорема 4. Пусть `g – цена игры, М(р, q) – функция выигрыша,  `S_А,`S_В – множества смешанных стратегий соответственно игроков А и В.

1). Для того чтобы стратегия p⁰ игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство для любого qÎ`S<sub>B</sub>, т.е. выбор игроком А оптимальной стратегии p<sup>0</sup> гарантирует ему выигрыш M(p<sup>0</sup>,q), не меньший цены игры`g  при любой стратегии q игрока В.

2). Для того чтобы стратегия q⁰ игрока B была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство  для любого рÎ`S<sub>А</sub>, т.е. выбор игроком В одной из своих оптимальных стратегий q<sup>0</sup> гарантирует ему проигрыш, не больший цены игры`g при любой стратегии р игрока А.

Теорема 5. Пусть `g – цена игры, M(p,q)  – функция выигрыша, A_i и B_j, i = 1, 2, …, m,  j = 1, 2, …, n – чистые стратегии соответственно игроков А и В.

1). Для того чтобы стратегия p⁰ игрока А была оптимальной, необходимо и достаточно, чтобы  M(p⁰,В_j) ³`g , j = 1, 2, …, n.

2). Для того чтобы стратегия q⁰ игрока B была оптимальной, необходимо и достаточно, чтобы (A_i, q⁰) £`g, i = 1, 2, …, m.

Теорема 6. Для того чтобы `g была ценой игры, а p<sup>0</sup> и q<sup>0</sup> – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства M(p, q<sup>0</sup>) £`g = M(p⁰,q⁰) £ М(p⁰,q) для любых рÎ`S<sub>А</sub> и qÎ`S_B.

Теорема 7. Для того чтобы `g была ценой игры, а p<sup>0</sup> и q<sup>0</sup> – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства M (A<sub>i</sub>, q<sup>0</sup>) £`g = M (p⁰, q⁰) £ M (p⁰, B_j), i = 1, 2, …, m,  j = 1, 2, …, n.

Т.е. если их применение обеспечивает игроку А средний выигрыш, не меньший, чем при применении им любой другой стратегии Р, игроку В – средний проигрыш, не больший, чем при применении им любой другой стратегии q.

Теорема 8. Для того чтобы `g была ценой игры, а p<sup>0</sup> и q<sup>0</sup> – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно, чтобы (p<sup>0</sup>,q<sup>0</sup>) была седловой точкой функции выигрыша M (p, q) и  M (p<sup>0</sup>, q<sup>0</sup>) = `g.

11.7.Свойства оптимальных стратегий

Пусть и – оптимальные стратегии соответственно игроков А и В. В общем случае некоторые из вероятностей  могут быть равными нулю.

Если , где i – одно из чисел 1, 2, …, m, то в оптимальной смешанной стратегии  чистая стратегия A_i не участвует и поэтому называется пассивной.

Чистые стратегии A_i, входящие в оптимальную стратегию