Понятие стратегии, оптимальной во множестве смешанных стратегий. Основная теорема матричных игр дж. Фон неймана

Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V= = v называется ценой игры в смешанных стратегиях, а стратегии и , для которых выполняется равенство называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии и обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии. Обозначим через множества оптимальных стратегий игроков А и В. Очевидно, что множество оптимальных стратегий каждого из игроков является подмножеством множества смешанных стратегий:

, то есть цена игры в смешанных стратегиях не меньше нижней цены игры в чистых стратегиях α и не больше верхней цены игры в чистых стратегиях β.

Полным решением игры в смешанных стратегиях называется совокупность множеств оптимальных стратегий игроков и цены игры. Любая пара оптимальных стратегий и и цена игры образуют частное решение в смешанных стратегиях.

Основная теорема матричных игр фон Неймана. Любая матричная игра имеет решение в смешанных стратегиях, то есть существует цена игры в смешанных стратегиях и оптимальные смешанные стратегии и игроков А и В соответственно.

v =

 

 

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

Теорема (Критерий оптимальных стратегий.)

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S_B– множества смешанных стратегий игрока В.

Для того чтобы стратегия Р⁰ игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось нер-во Н(Р⁰,Q) V для любого Q S_B, (1)

т.е. выбор игроком А оптимальной стратегии Р⁰ гарантирует ему выигрыш Н(Р⁰,Q), не меньший цены игры V, при любой стратегии Q игрока В.

Док-во:

Необходимость. Пусть Р⁰- опт стратегия игрока А. тогда по т. Фон Неймана показатель эфф-ти α(Р) стратегии Р⁰ равен цене игры V: (2)

Рассматривая как пок-ль эф-ти стратегии Р⁰ относит множ-ва S_B смеш стр-гий игрока В, будем иметь по опр-нию: (3)

Из равенств (2)-(3)получаем (1)

Достаточность. Пусть для некоторой стр-гии Р⁰ игрока А выполнется нер-во (1)

Для док-ва оптимальности стратегии Р⁰ достаточно показать справедливость равенства: (4)

Т.к. нер-во(1) выполняется для любой стратегии Q S_B игрока В, то (5)

Но цена игры V равна нижней цене игры , по опр кот. (6)

Совокуп (5) и (6) эквивалентна рав-ву (4).

Достаточность доказана. Теорема доказана.

 

 

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

Теорема (Критерий оптимальных стратегий.)

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, S_A – множества смешанных стратегий игрока А.

Для того чтобы стратегияQ⁰ игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство

Н(Р⁰,Q) V для любого Р S_A, (1)

т.е. выбор игроком В оптимальной стратегии Q⁰ гарантирует ему проигрыш Н(Р, Q⁰), не больший цены игры V, при любой стратегии Р игрока А.

Док-во:

Необходимость. Пусть Q⁰- опт стратегия игрока B. тогда по т. Фон Неймана показатель эфф-ти β(Q)стратегии Q⁰ равен цене игры V: (2)

Рассматривая как пок-ль эф-ти стратегии Q⁰ относит множ-ва S_A смеш стр-гий игрока A, будем иметь по опр-нию: (3)

Из равенств (2)-(3)получаем (1)

Достаточность. Пусть для некоторой стр-гии Q⁰ игрока B выполнется нер-во (1)

Для док-ва оптимальности стратегии Q⁰ достаточно показать справедливость равенства: (4)

Т.к. нер-во(1) выполняется для любой стр-гии Q S_B иг-ка В, то (5)

Но цена игры V равна верхней цене игры , по опр кот. (6)

Совокуп (5) и (6) эквивалентна рав-ву (4).

Достаточность доказана. Теорема доказана.

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

Теорема

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, = – множества чистых стратегий игрока В.

Для того чтобы стратегия Р⁰ игрока А была оптимальной, необходимо и достаточно, чтобы Н(Р⁰, ) V, j=1,…,n (1)

Док-во:

Достаточно установить эквивалентность нер-в
(1) и Н(Р⁰,Q) V для любого Q S_B (2)

Пусть справедливо нер-во (2). Т.к. это нер-во имеет место для любой стр-гии Q S_B игрока В, то оно, в частности, будет справедливым и для его чистых стратегий В_j , j=1,…,n, т.е. нер-во (1) имеет место =>
импиликация (2)=>(1) доказана.

Теперь пусть имеет место быть нер-во (1). Тогда по ф-ле с учетом того, что получим

Q S_B, т.е. доказано нер-во (2). Т.о., справедлива импликация(1)=>(2) => эквивалентны