В матричной игре существует пара смешанных стратегий, таких что
1. , " p Î Pm, q Î Qn.
2. a = b = .
Доказательство. Сначала покажем, как представить задачу о выборе
наилучших стратегий в виде ЛП, а затем докажем теорему.
Первый игрок: a (p) ® max
Пусть ui = pi / a (p), i = 1,…, m, в предположении a (p) > 0.
Тогда ui ³ 0, i = 1,…, m, и Заметим, что и задача a (p) ® max может быть записана следующим образом:
,
.
Аналогичным образом получаем задачу второго игрока:
где vj = qj / b (q), j = 1,…, n. Полученные задачи являются взаимодвойственными. Пусть — оптимальные решения этих задач.
Положим , . Из второй теоремы двойственности следует, что
Просуммировав, получим
.
Поделим на
Теперь докажем первое утверждение теоремы:
Аналогично
т.е.
Докажем второе утверждение теоремы.
Из предыдущего неравенства имеем:
т.е.
Но по лемме a £ b Þ a = b =
Дилемма заключенных
Два преступника пойманы за совершение преступления.
У следствия не хватает доказательств их виновности и преступникам предлагают сделку:
|
|
Если сознаешься и подтвердишь участие товарища в преступлении, то выйдешь на свободу, а товарищ получит 7 лет лишения свободы.
Преступники сидят в разных камерах и не могут общаться, но они знают, что каждому сделано такое предложение.
Если оба преступника сознаются, то каждый получит 5 лет.
Если оба не сознаются, то каждый получит по 1 году.