Критерий эффективности в матричной игре. Чистые и смешанные стратегии

Теорией игр называют теорию математических моделей принятия оптимальных решений в условиях соперников. Игровая ситуация, естественно, получается из модели исследования операции в предположении, что неконтролируемые факторы связаны с действиями других активных участников операции. Основной класс стратегических игр составляют бескоалиционные игры, в которых множество игроков I совпадает с множествами коалиций и коалиций интересов. В такой игре отношение предпочтения всегда описывается функцией выигрыша, которую обозначим W_i, i ÎI, т.е. бескоалиционную игру можно описать тройкой Г={I,{M_i},iÎI,{W_i}, iÎI}. Если все множества стратегий конечны, то игра Г является конечной. Конечные бескоалиционные игры называются биматричными, если всего два игрока. Если же в биматричной игре (I={ I, II }), W_I(x) =- W_I (y) для всех критериев х, то игра Г называется антагонистической, или игрой с нулевой суммой, т.е. Г={M₁,M₂, w}, где W - функция выигрыша первого игрока. Конечная антагонистическая игра называется матричной. Антагонистической игрой (или игрой двух лиц с нулевой суммой) в нормальной форме называется совокупность Г={X,Y,W(x,y)}, где Х- множество стратегий 1-го игрока, Y- множество стратегий 2-го игрока, а функция W(x,y) представляет собой выигрыш первого игрока в ситуации (х, у), т.е. когда первый игрок выбирает стратегию х j Х, а второй - стратегию у j Y. При этом выигрыш второго игрока равен - W(x, у). Стратегии х и у называются чистыми стратегиями игроков. В антагонистической игре первый игрок стремится по возможности максимизировать функцию W(x, у), а второй игрок - минимизировать. Границы возможностей игроков определяются значениями нижней и верхней ценой игры. Нижней ценой игры в чистых стратегиях называется величина , а верхней ценой игры будет . Смысл величина a и b заключается в следующем: первый игрок может гарантировать себе выигрыш не менее a независимо от действий игрока 2; второй игрок может гарантировать себе проигрыш не более b независимо от действий первого игрока в чистых стратегиях. Таким образом величины a и b являются наилучшей гарантированной оценкой соответст­венно для первого и второго игрока, а величины х и у, при которых достигаются значения a и b являются оптимальными чистыми стратегиями игроков по критерию максимума (минимума). Нижняя и верхняя цена игры всегда связаны соотношением a £ b. Действительно, если функция W(x, у) такова, что значения a и b дости­гаются, то из определения максимума и минимума следуют неравенства , отсюда следует, что . Рассмотрим использование смешанных стратегий. Поскольку множества стратегий игроков Х и Y дискретны и конечны, все вероятностные распределений на этих множествах являются просто конечным набором вероятностей. Если обозначить множество смешанных стратегий первого игрока S₁ а второго – S₂: , , и определение игры со смешанными стратегиями будет Г=S₁,S₂,W(P,Q)},PÎS_1, QÎS₂, где функция выигрыша первого игрока в смешанных стратегиях имеет смысл математического ожидания . Чистые стратегии являются подмножествами множеств смешанных стратегий, т.е. вершинами симплексов и . Выбору i-той чистой стратегии первого игрока соответствует вектор Р с компонентами р_i = 1,р_k = 0 при k¹0 вектору j-той чистой стратегии второго игрока соответствует вектор Q с компонентами q_j = 1,q_l = 0 при l¹0. Нижней ценой матричной игры в смешанных стратегиях называется величина . Верхней ценой матричной игры в смешанных стратегиях будет величина . Для модели игры в смешанных стратегиях справедлива основная теорема матричных игр фон Неймана. Любая матричная игра имеет цену в смешанных стратегиях, а игроки имеют оптимальные смешанные стратегии Р₀ и Q₀, т.е. . Доказательство теоремы следует из того, что выпуклая функция имеет седловую точку на компонентах S₁ и S₂. Очевидно, что функция W(P,Q) линейна по Р и Q и, следовательно, выпукло - вогнута. Решить матричную игру - это означает найти все оптимальные стратегии и цену игры.