2. Критерии сравнивания альтернатив при неопределенности исходов

Вряд ли возможно (да и целесообразно) в кратком обзоре рассмотреть все важнейшие результаты теории игр (опубликовано много монографий; интересующимся можно рекомендовать начать изучение с книг [7; 21; 29]). Однако об основных идеях и подходах к решению задач теории игр желательно иметь представление всем, кому придется проводить исследования систем.

Центральным моментом является введение критерия для оценки выбираемого варианта. В силу неопределенности исхода нужно дать оценку сразу целой строке платежной матрицы; имея такие оценки для всех строк и сравнивая их, мы и можем делать выбор.

Самым распространенным является критерий выбора "наименьшего из зол", называемый максиминным критерием. В каждой из строк матрицы платежей находится наименьший выигрыш min(q_ij), который характеризует гарантированный выигрыш в самом худшем случае и считается оценкой альтернативы х_i. Теперь остается найти альтернативу x^*, обеспечивающую наибольшее значение этой оценки: x^*=arg(max|_i(min|_jq_ij)). Эта альтернатива и называется оптимальной по максиминному критерию. Поскольку часто платежную матрицу определяют не через выигрыш, а через проигрыш, тот же принцип приводит к минимаксному критерию.

Минимаксный критерий является крайне осторожным, очень пессимистическим, поэтому были предложены другие критерии. Таков, например, критерий минимаксного сожаления, предложенный Сэвиджем. При этом по платежной матрице Q вычисляется "матрица сожалений" S, элементы которой определяются как s_ij=q_ij-min|_iq_ij и минимаксный критерий применяется к матрице S: x^*=arg(max|_i(min|_js_ij)).

Дальнейшее ослабление пессимистичности оценки альтернатив дает критерий пессимизма-оптимизма (критерий Гурвица), который сводится к взвешенной комбинации наилучшего и наихудшего исходов. А именно: за оценку альтернативы x_i в критерии Гурвица принимается величина

g(x_i)= min|_j q_ij+(1-)max|_j q_ij, 0 1.

Показатель  называется показателем пессимизма-оптимизма (при  имеем снова максиминный критерий); оптимальная альтернатива есть x^*=arg(max|_ig(x_i)).

3. Общее представление о теории игр

Некоторые особенности игровых ситуаций хорошо видны на простейшем примере. Пусть имеется игра с континуальными множествами Х и Y, строгим соперничеством сторон и нулевой суммой. Это делает достаточным рассмотрение лишь одной функции платежей q(x, у), которую один игрок старается максимизировать по х, а другой - минимизировать по y.

В тех случаях, когда max|_xmin|_yq(x, у)=min|_ymax|_xq(x, у), точка (х^*, у^*), в которой достигается это равенство, одновременно удовлетворяет амбиции обоих игроков. Эта точка равновесия интересов сторон называется седловой. Отход от этой точки невыгоден обеим сторонам, так что ее выбор решает игру.

Однако существуют игры без седловой точки. В такой ситуации становится выгодным скрывать от противника свой выбор и даже свой способ выбора. Это достигается введением смешанной стратегии. В отличие от чистой стратегии, при которой альтернатива выбирается однозначно по детерминированному правилу, смешанная стратегия состоит в том, что задаются лишь вероятности выбора альтернатив, а сам выбор осуществляется случайным механизмом, подчиняющимся заданному распределению. В результате получаемый выигрыш становится случайной величиной и сравнение стратегий можно вести через средние значения выигрыша. Оказывается (теорема фон Неймана), что любые матричные игры со строгим соперничеством имеют решение в смешанных стратегиях. Кроме того, матричную игру можно свести к задаче линейного программирования, что дает не только практические методы численного решения игр, но и позволяет перенести ряд теоретических результатов из теории программирования в теорию игр.

Подведем итог: Неопределенность в момент выбора характеризуется распределением потерь и выигрышей по исходам, связанным с каждой альтернативой. Вводя подходящую числовую характеристику этого распределения, мы получаем возможность упорядочения (сравнения) альтернатив. Разнообразие задач теории игр связано с разными числовыми характеристиками распределения потерь, различными степенями конфликтности между сторонами, с другими особенностями конкретных задач.