Теория игр

Введение

Лекции 8, 9, 10 посвящены обоснованию решений в условиях неполной информации о фактической обстановке, когда складываются так называемые конфликтные ситуации, исход которых зависит от действий двух сторон с противоположными интересами. Излагается сущность теории игр и раскрывается область ее применения; формулируются правила построения теоретико-игровых моделей; дается классификация таких моделей, и описываются математические методы, с помощью которых находятся оптимальные способы действий.

Основные понятия теории игр

В ситуациях, называемых конфликтными, предугадать исход и тем более определить действия, при которых этот исход оказался бы наиболее благоприятным, оказывается чрезвычайно сложно. Предположим, что сторона $$A$$ обладает способами действий $$A_1,A_2,...,A_m$$, на каждой из которых сторона $$B$$ может ответить одним из способов $$B_1,B_2,...,B_n$$. Пусть результат взаимных действий $$(A_i,B_j)$$ характеризуется критерием эффективности $$a_{ij}$$, который представляет собой выигрыш стороны $$A$$. Тогда конфликтную ситуацию можно представить в виде матрицы эффективности (рис. 8.a.).

Из рисунка 8.a. видно, что если сторона выбирает способ $$A_2$$, то исход конфликта, характеризуемый критерием эффективности $$a_{2j}(j=1,2,...,n)$$, будет целиком зависеть от выбора способа действий стороной $$B$$. Аналогичный вывод можно сделать в отношении любого другого способа действий стороны $$A$$. В этих условиях естественным подходом к выбору оптимального способа является сравнение между собой всех способов действия стороны $$A$$ при условии выбора стороной $$B$$ каждого из способов.

Например, сравнивая способ $$A_1$$ со способом $$A_2$$, можно в частном случае установить, что способ $$A_2$$ обеспечивает достижение лучшего результата, если каждый элемент его строки больше соответствующего элемента (по столбцам) строки способа $$A_1$$. Если путем подобного сравнения найдется такой способ $$А_i$$, каждый элемент строки которого больше соответствующего элемента (по столбцам) любой другой строки, то целесообразно применить способ $$А_i$$. В остальных случаях выбор способа стороной $$A$$ может быть осуществлен только для определенной гипотезы о действиях стороны $$B$$.

Другой естественный подход состоит в определении математического ожидания величины критерия эффективности для $$i$$ -го способа действия стороны $$A$$ по формуле

$$\bar{a_i}=\sum\limits_{j=1}^{n}a_{ij}y_j$$,

где $$\bar{a_i}$$ — математическое ожидание величины критерия эффективности при выборе способа действия $$A_i$$ ;

$$y_j$$ — вероятность выбора стороной $$B$$ способа действия $$B_j$$.

Тогда способы действия стороны $$A$$ можно сравнить по величине $$\bar{a_i}$$ и выбрать тот, при котором $$\bar{a_i}$$ будет максимальным. При этом как в первом, так и во втором случае для обоснования решения достаточно использовать методы оптимизации.

Таким образом, для применения в условиях конфликтной ситуации обычных методов оптимизации необходимо задаться или гипотезой о действиях противника, или законом распределения их вероятностей. Однако для конфликтных ситуаций как раз характерным является то, что отдать предпочтение какой-либо гипотезе не представляется возможным, а методов определения законов распределения вероятности выбора противником своих способов действий просто не существует.

В связи с этим возникает необходимость в теории специфического класса математических моделей принятия оптимальных решений. Такой теорией является теория игр .

Теорию игр можно рассматривать, с одной стороны, как раздел исследований операций, а с другой — как его уровень. В качестве раздела исследования операций теория игр представляет теорию математических моделей принятия оптимальных решений в конфликтных ситуациях. Как уровень исследования операций теория игр является теорией математических моделей принятия решений в условиях неопределенности. Однако не следует полагать, будто теория игр занимается вопросами принятия решений при полном неведении об обстановке. Известные элементы обстановки определяют множество способов действий сторон и значения критерия эффективности как функции, заданной на этом множестве. Неизвестные элементы обуславливают отсутствие любой, даже вероятностной информации о возможных реализациях того или иного способа действий противника. Таким образом, любую неопределенность можно расчленить на известную и неизвестную части, построить теоретико-игровую модель, на основании которой определяется оптимальное решение.

Для применения теории игр нужна существенная схематизация конфликтной ситуации и представление ее в виде игры, в которой противники, именуемые игроками, имеют противоположные цели и располагают различными путями для их достижения. Причем обязательным является то, что достижение одним игрокам своей цели находится в непосредственной зависимости от выбора способа действий другим игроком. Более того, отличительная особенность игры по сравнению с реальной конфликтной ситуацией состоит в том, что первая ведется по заранее определенным правилам. В этом и заключается основное ограничение в применении теории игр. Ведь если теоретико-игровой подход, безусловно, правомерен в любой игре, то не всегда можно построить соответствующую математическую модель для конкретных условий обстановки.

Основное значение теории игр состоит в том, что она дает ориентацию тогда, когда применение другого математического аппарата невозможно из-за отсутствия необходимой информации о действиях противника, а времени и, самое главное, других эффективных способов нет.

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

Для построения модели конфликтной ситуации прежде всего должны быть сформулированы правила игры, то есть система условий, которая определяет возможные варианты действий игроков, последовательность ходов, объем информации каждого игрока о поведении другого и о функции выигрыша .

Возможные варианты способов действий вытекают непосредственно из анализа конфликтной ситуации.

Выбор одного из возможных вариантов в процессе игры называется ходом .

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

Совокупность сделанных игроками ходов в соответствии с выбранными ими стратегиями определяет ситуацию игры, которая является моделью складывающейся обстановки в результате конкретных действий, предпринятых противоположными сторонами. Ситуация, на основании которой определяется исход игры, называется заключительной .

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

Таким образом, выигрыш – это оценка ожидаемых результатов всех возможных сочетаний стратегий одного игрока со стратегиями другого. Для получения таких оценок могут применяться методы теории вероятностей, теории массового обслуживания, теории управления запасами, теории поиска и различные экономические показатели. Следовательно, теория игр исходит из заранее определенных значений того или иного критерия эффективности для конкретного сочетания стратегий обоих игроков, то есть принимается, что функция выигрыша задана.

Теоретико-игровые модели боевых действий классифицируются в зависимости от числа последовательных ходов и возможных способов действий игроков, характера и объема информации, доступной каждому игроку относительно действий другого, а также отношения каждого из игроков к значению функции выигрыша.

В зависимости от числа возможных способов действий игры подразделяются на конечные и бесконечные. Конечной называется игра, в которой у каждого игрока имеется конечное число возможных способов действий. В бесконечной игре по крайней мере один из игроков имеет бесконечное множество возможных способов действий.

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

Многоходовая, или позиционная, игра развивается во времени, представляя собой ряд последовательных этапов, каждый из которых наступает после хода одного из игроков и соответствующего изменения обстановки.

Многоходовые игры в зависимости от характера и объема информации каждого игрока о сделанных ходах противником подразделяются на два класса: игры с полной информацией и игры с неполной информацией. В играх с полной информацией каждый игрок на каждом этапе знает результаты всех предыдущих ходов. В зависимости от отношения каждого из игроков к значению функции выигрыша игры подразделяются на антагонистические и неантагонистические. В антагонистических играх интересы ее участников прямо противоположны. Это означает, что сколько один игрок выиграл, то столько же другой проиграл. В этих условиях каждый игрок стремится обеспечить себе максимальный выигрыш, а противнику максимальный проигрыш. Это приводит к тому, что выигрыш одного игрока соответствует проигрышу другого, Поэтому можно считать, что суммарный выигрыш обоих игроков антагонистической игры во всех ситуациях равен нулю. Отсюда эти игры иногда называют играми с нулевой суммой или нулевыми играми.

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

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

В этой матрице строки всегда для стратегий выигрывающего (максимизирующего) игрока, то есть игрока, который стремится к максимизации критерия эффективности (игрок I).

Столбцы отводятся для стратегий проигрывающего игрока, то есть игрока, который стремится к минимизации критерия эффективности (игрок II). Клетки матрицы, стоящие на пересечении строк и столбцов, представляют результаты заключительных ситуаций и заполняются числами $$a_{ij}$$ — значениями критерия эффективности, характеризующего выигрыш игрока I и соответственно проигрыш игрока II.

Обычно матрицу, имеющую $$m$$ строк и $$n$$ столбцов, называют $$(m\times n)$$ матрицей и обозначают $$||a_{ij}||$$. Соответственно игру называют ( $$m\times n)$$ игрой.

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

Процесс сведения позиционной игры к игре, описываемой матрицей, называется нормализацией , а получающаяся игра – игрой в нормальной форме . Действительно, в этой игре значения функции выигрыша можно всегда записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям игрока I, а столбцы – стратегиям игрока II.

Принцип оптимальности в теории игр

Каждый игрок должен стремиться не вообще к ситуации, в которой значение функции выигрыша максимально или минимально, а прежде всего к такой ситуации, которая может сложиться в процессе игры. Чтобы ситуация могла быть осуществимой, в ней одновременно должны достигаться приемлемые результаты как для игрока I, так и для игрока II. Ситуации, обладающие этим свойством, называются ситуациями равновесия . Именно они могут складываться в результате разумного выбора игроками своих стратегий. При выявлении ситуации равновесия необходимо прежде всего проанализировать последовательно каждую стратегию игрока I с точки зрения наиболее неблагоприятного для него исхода при выборе игроком II одной из своих стратегий. Для этого в $$i$$ - строке матрицы отыскивается минимальное значение выигрыша. Обозначим его $$\alpha_i=\mathop{min}\limits_j a_{ij}$$, где знаком $$\mathop{min}\limits_j$$ (минимум по $$j$$ ) обозначена операция отыскания минимального из значений функции выигрыша при всех возможных $$j$$.

Числа $$\alpha_i$$, которые записаны рядом с матрицей $$||a_{ij}||$$ в виде добавочного столбца, характеризуют минимальные выигрыши игрока I с учетом разумных действий игрока II. Поэтому игрок I должен выбрать свою стратегию так, чтобы максимизировать свой минимальный выигрыш, то есть он должен остановиться на той стратегии, для которой число $$\alpha_i$$ является максимальным. Обозначим максимальное значение $$\alpha_i$$ через $$\alpha^*$$, то есть

$$\alpha^* = \mathop{max}\limits_i \alpha_i = \mathop{max}\limits_i \mathop{min}\limits_j \alpha_{ij}$$.

Величина $$\alpha^*$$ называется нижним значением игры или максимином, а соответствующая ей стратегия игрока I – максиминной стратегией .

Очевидно, что при выборе наиболее осторожной максиминной стратегии игрок I обеспечивает себе (независимо от поведения противника) гарантированный выигрыш не менее $$\alpha^*$$.

Далее проанализируем каждую стратегию игрока II с точки зрения наиболее неблагоприятного для него исхода при выборе игроком I одной из своих стратегий. В результате этого найдем максимальные значения проигрыша, которые обозначим

$$\beta_j= \mathop{max}\limits_i a_{ij}$$,

где знаком $$\mathop{max}\limits_i$$ (максимум по $$i$$ ) обозначено максимальное значение функции выигрыша при всех возможных $$i$$.

Числа $$\beta_j$$, которые записаны под матрицей $$||a_{ij}||$$ в виде добавочной строки, характеризуют максимальные проигрыши игрока II с учетом разумных действий игрока I. Поэтому игрок II должен выбрать свою стратегию так, чтобы минимизировать свой максимальный проигрыш. Для этого он должен остановиться на той стратегии, при которой число $$\beta_j$$ будет минимальным. Обозначим минимальное значение $$\beta_j$$ через $$\beta^*$$, то есть

$$\beta^* = \mathop{min}\limits_j \beta_j = \mathop{min}\limits_j \mathop{max}\limits_i a_{ij}$$.

Величина $$\beta^*$$ называется верхним значением игры или минимаксом, а соответствующая ей стратегия игрока II – минимаксной стратегией .

Очевидно, что при выборе наиболее осторожной минимаксной стратегии игрок II не дает возможности ни при каких обстоятельствах игроку I выиграть больше, чем $$\beta^*$$.

Следовательно, если оба игрока ведут себя разумно, то выигрыш игрока I должен быть не меньше, чем максимин, и не больше, чем минимакс, то есть:

$$\mathop{max}\limits_i \mathop{min}\limits_j a_{ij} \le \mathop{min}\limits_j \mathop{max}\limits_i a_{ij}$$

В некоторых играх выражение 7.1. превращается в равенство, то есть при определенных условиях может достигаться равенство максимина и минимакса, а именно:

$$\mathop{max}\limits_i \mathop{min}\limits_j a_{ij} = \mathop{min}\limits_j \mathop{max}\limits_i a_{ij}$$

Необходимым и достаточным условием выполнения равенства 7.2. является существование седловой точки. $$(m\times n)$$ матрицы. Термин "седловая точка" заимствован из геометрии. Однако наличие седловой точки в геометрии рассматривается в локальном, а в теории игр – в глобальном плане. То есть, декларируется существование пары целых чисел $$i_0,j_0$$, для которых $$a_{i_0j_0}$$ оказывается одновременно минимумом своей строки и максимумом своего столбца. Поэтому игрок I, применяя максиминную стратегию $$i_0$$, гарантирует себе выигрыш $$a_{i_0j_0}$$, а игрок II, применяя минимаксную стратегию $$j_0$$, не дает ему выиграть больше, чем $$a_{i_0j_0}$$.

Следовательно, для игрока I лучше всего выбирать стратегию $$i_0$$, а для игрока II — $$j_0$$. Согласно этому стратегии $$i_0$$ и $$j_0$$ называются оптимальными, а гарантированный выигрыш $$a_{i_0j_0}$$ игрока I – значением игры, которое обозначают через $$\nu$$.

Совокупность оптимальных стратегий называется решением игры .

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

Рассмотрим матрицу игры.

Так, матрица имеет седловую точку $$(i_0=2,j_0=1)$$, так как цифра 7 является минимумом второй строки и максимумом первого столбца. Следовательно, оптимальной стратегией игрока I является максиминная $$i_0$$, а игрока II – минимаксная $$j_0=1$$. Значение игры $$\nu=7$$.

Выбрав свою оптимальную стратегию, игрок I может быть уверен, что он получит по меньшей мере 7, а игрок II, выбрав свою оптимальную стратегию, не допустит, чтобы игрок I получил больше 7. Эти стратегии и составляют решение игры с седловой точкой.

Решение игры с седловой точкой обладает таким свойством: если игроки придерживаются своих оптимальных стратегий, то выигрыш равен значению игры. Если один из игроков придерживается своей оптимальной стратегии, а другой отклоняется от нее, то он только теряет в игре и ни в коем случае не может увеличить свой выигрыш. При этом наличие у любого игрока сведений о том, что другой избрал свою оптимальную стратегию, не служит основанием для выбора какой-либо иной, кроме оптимальной (минимаксной или максиминной), стратегии. Пара оптимальных стратегий в игре с седловой точкой создает ситуацию равновесия, и любое отклонение от оптимальной стратегии приводит игрока, применяющего неоптимальную стратегию, к невыгодным последствиям. Так, для рассматриваемой игры наличие информации у игрока $$II$$ о том, что игрок I выбрал оптимальную стратегию $$i_0=2$$, не влияет на выбор им своей оптимальной стратегии $$j_0=1$$. В противном случае игрок II даст возможность игроку I выиграть 9 вместо 7.

Смешанные стратегии. Наличие седловой точки определяет довольно простой способ выбора оптимальных стратегий, который вытекает из равенства 7.2. Однако равенство 7.2. справедливо не для всякой матрицы.

Пусть дана следующая матрица игры.

Из анализа этой матрицы видно, что максиминная стратегия игрока I гарантирует ему выигрыш не менее 20, а минимаксная стратегия игрока II — проигрыш не более 30. Однако, если игрок II будет придерживаться стратегии 2, игроку I выгодно отклониться от своей максиминной стратегии 2, то есть выбрать стратегию 1 и повысить выигрыш до 30. Тогда игроку I целесообразно выбрать стратегию не 2, а 1 и уменьшить выигрыш игрока I до 10. Но в свою очередь игрок I, выбирая 2, может увеличить выигрыш до 40, и так далее.

Оказывается, игрок I может добиться выигрыша более 20, а игрок II – проигрыша менее 30. Это следовало ожидать, так как принцип минимакса в этом случае обусловил область неопределенности выигрыша и проигрыша в пределах от 20 до 30. Каждый игрок поэтому получил шансы улучшить свое положение путем чередования всех стратегий.

Выбор каждым игроком своей чистой стратегии с некоторой заранее заданной вероятностью является не чем иным, как одним из планов проведения игры, то есть определенной стратегией. Для отличия стратегий такого вида от первоначально заданных стратегий их называют смешанными стратегиями, а первоначально заданные (то есть строки или столбцы матрицы) – чистыми стратегиями .

Смешанные стратегии обозначаются следующим образом:

$$x=(x_1,x_2,...,x_m);\\ y=(y_1,y_2,...,y_n)$$,

где $$x_i$$ — вероятность выбора игроком I $$i$$ - чистой стратегии;

$$y_j$$ — вероятность выбора игроком II $$j$$ - чистой стратегии;

$$m$$ — число чистых стратегий игрока I;

$$n$$ — число чистых стратегий игрока II.

Очевидно, что $$\sum\limits_{i=1}^{m}x_i=1; \sum\limits_{j=1}^{n}y_j=1$$, и каждая чистая стратегия является смешанной стратегией, в которой все стратегии, кроме одной, имеют вероятности, равные нулю, а данная – вероятность, равная единице.