Верхняя и нижняя цена игры в матричной игре в чистых стратегиях, их нахождение

Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, у второго – n.

При анализе игр противник считается сильным, т.е. разумным.

Рассмотрим описанную конфликтную ситуацию с точки зрения первого игрока. Если мы(первый игрок) выбираем свою i-ю стратегию (i-ю строку матрицы А), то второй игрок, будучи разумным, выберет такую стратегию j, которая обеспечит ему наибольший выигрыш (а нам наименьший), т.е. он выберет такой столбец j матрицы А, в котором платеж a_ij(второго игрока первому) минимален. Переберем все наши стратегии i= 1,2,,..,m и выберм ту из них, при которой второй игрок, действуя максимально разумно, заплатит нам наибольшую сумму. Величина α = max_i=1,2,…n min_j=1,2,…m a_ij называется нижней ценой игры, а соответствующая ей стратегия первого игрока- максиминной. Аналогичный рассуждения(но уже с точки зрения второго игрока) определяют верхнюю цену игры

β = min_j=1,2,…n max_i=1,2,…m a_ij и соответствующую ей минимаксную стратегию второго игрока.

По своему определению нижняя цена игры α представляет собой максимальный гарантированный выигрыш первого игрока(т.е. применяя свою максиминную стратегию, первый игрок обеспечивает себе выигрыш, не меньший α), а верхняя цена- величину, противоположную минимальному гарантированному проигрышу второго игрок(т.е. применяя свою минимаксную стратегию, второй игрок гарантивует, что он не проиграет больше, чем β,или, иначе, выиграет не меньше, чем (-β)).