Выработка решений в условиях неопределенности

ГЛАВА 6. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ КОНФЛИКТА

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

6.1.1. Предмет, задачи и основные понятия теории игр

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

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

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

В ряде случаев задача о принятии решения в условиях неопределенности ставится в таком виде: какую цену можно заплатить за недостаточную информацию, чтобы экономический эффект всей операции был бы максимальным?

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

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

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

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

Игра - упрощенная, схематизированная модель конфликтной ситуации.

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

Правила игры - система условий, регламентирующая:

- возможные варианты действий игроков,

- объем информации каждой стороны о поведении другой,

- результат (исход) игры, к которому приводит каждая данная совокупность ходов.

Человечество издавна пользуется такими формализованными моделями конфликтов – «играми» в буквальном смысле слова (шашки, шахматы, карточные игры и т.п.). Отсюда и название теории игр и её терминология: конфликтующие стороны условно называются «игроками», одно осуществление игры – «партией», исход игры – «выигрышем» или «проигрышем». Мы будем считать, что выигрыши (проигрыши) участников имеют количественное выражение (если это не так, то всегда можно им его приписать, например, в шахматах считать «выигрыш» за единицу, «проигрыш» - за минус единицу, «ничью» - за нуль).

Игра называется игрой с нулевой суммой, если один игрок выигрывает ровно столько, сколько проигрывает другой, т.е. сумма выигрышей сторон равна нулю. В игре с нулевой суммой интересы противников прямо противоположны. Мы будем рассматривать именно такие игры.

Развитие игры во времени можно представить как ряд последовательных «ходов» участников. Ходом называется выбор игроком одного из предусмотренных правилами игры действий и его осуществление. Ходы бывают личные и случайные. При личном ходе игрок сознательно выбирает и осуществляет тот или другой вариант действий (пример - любой ход в шахматах). При случайном ходе выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора (бросание монеты, игральной кости, вынимание карты из колоды и т.п.). Некоторые игры (так называемые «чисто азартные») состоят только из случайных ходов - ими теория игр не занимается. Её цель - оптимизация поведения игрока в игре, где (может быть наряду со случайными) есть и личные ходы. Такие игры называются стратегическими.

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

Обычно, участвуя в игре, игрок не следует каким-либо жестким, «железным» правилам: выбор (решение) принимается им в ходе игры, когда он непосредственно наблюдает ситуацию. Однако теоретически дело не изменится, если предположить, что все эти решения приняты игроком заранее («если сложится такая-то ситуация, то я поступлю так-то»). Это будет означать, что игрок выбрал определенную стратегию. Теперь он может и не участвовать в игре лично, а передать список правил незаинтересованному лицу - судье. Стратегия может быть также задана машине-автомату в виде программы действий (именно так играют в шахматы ЭВМ).

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

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

Теория игр, как и всякая математическая модель, имеет свои ограничения. Одним из них является:

1) предположение о полной («идеальной») разумности противника (противников). В реальном конфликте зачастую оптимальная стратегия состоит в том, чтобы угадать, в чем противник «глуп», и воспользоваться этой глупостью в свою пользу.

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

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

Классификация игр

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

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

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

Большое место в теории игр занимают так называемые неантагонистические игры или игры против природы. Характерной особенностью этого класса игр является наличие частично противоположных и частично совпадающих интересов «играющих» сторон. Дело в том, что природа как бы скрывая свои закономерности от человека, по остроумному выражению А.Эйнштейна, ведет себя коварно, но не злонамеренно. Следует заметить, что методы принятия решений в конфликтных или частично конфликтных ситуациях разрабатывались также в математической статистике, теории оптимизации и т.д.

 

Рис.6.1. Классификация игр

 

В общем случае игра n сторон может быть задана в виде множества

{ x ¹, x ², …, xⁿ, H (x ¹, x ², …, xⁿ)}

где Н - платеж игры, который, в частности, может быть задан в виде матрицы; xⁱ - множество стратегий i -й стороны; n - число играющих сторон.

Если множества стратегий конечны, то игра считается конечной, если множества стратегий бесконечны, то имеет место бесконечная игра.

Рассмотрим игру двух сторон или лиц. Пусть «синие» имеют n стратегий, каждая из которых обозначается буквой j = 1, 2,..., n, а «красные» - m стратегий, каждая из которых обозначается буквой i = 1, 2,..., m. На первом ходу «красные» выбирают какую-то стратегию i. На следующем ходу «синие», зная какой выбор сделали «красные», выбирают стратегию j.

Эти два выбора определяют партию игры и платеж обоим игрокам. В общем случае игроки не обязательно ходят поочередно и могут делать свои ходы (выбирать стратегии) не зная, как сходил противник. Пусть a_ij - платеж «красных». Если рассматривается игра с нулевой суммой, когда обе стороны ведут расчеты только между собой, то платеж «синих» равен - a_ij.

Поэтому в общем случае такая игра определяется платежной матрицей вида

 

«Красные» стремятся к тому, чтобы значение a_ij (платеж) было максимальным, но они распоряжаются только своей стратегией i, «синие», наоборот, стремятся к тому, чтобы платеж a_ij был как можно меньше, но они распоряжаются только своей стратегией j. В этой ситуации необходимо выработать оптимальные стратегии поведения. Такие игры называют матричными или прямоугольными. Игра с рассмотренной матрицей называется игрой m х n.

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

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

Однако имеются чисто случайные (второй тип неопределенности) по своей природе игры. Ставить вопрос об оптимальности или правильности выбора стратегий в такой игре неразумно, так как исход игры не зависит от поведения игрока. К этой категории игр относятся игры в кости, орлянку, рулетку и т.д.

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

Существуют реальные игры, в которых имеют место все три вида неопределенности. Так, в карточной игре «преферанс» случайный аспект неопределенности определяется случайным раскладом карт, стратегический - в правилах «сноса» карт и «заказа» игры и комбинаторный - в сложности определения поведения при открытых картах. Антагонистические и неантагонистические игры встречаются только в играх двух лиц. В случае n лиц имеют место некоалиционные (некооперативные) и коалиционные (кооперативные) игры. В зависимости от формы задания игры делятся на игры в нормальной (или матричные), когда игра задается в виде матрицы платежей, и динамические игры (или позиционные), геометрически изображающиеся в виде графа (рис.6.2). В случае динамической игры она представляется в виде некоторого поэтапного многошагового процесса, который как правило задается в виде разностных (рекуррентных) уравнений.

Рис.6.2. Граф динамической (позиционной) игры.

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

Непрерывные игры можно рассматривать как предельный случай дискретных игр при увеличении числа стратегий до бесконечности.

Действительно, при матричном задании дискретной игры в пределе при увеличении числа строк и столбцов матрицу платежей можно заменить функцией платежей f (x,y), которая будет определять непрерывную игру в нормальной форме.

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

Один класс антагонистических непрерывных игр называется играми с выбором времени действия (игры типа дуэли). Чем позже выстрелит каждый из участников дуэли, тем больше вероятность успешного выстрела (противники сходятся к барьеру). Но при этом противник может выстрелить раньше. Если противник слышит выстрелы, дуэль называется «шумной», в противном случае дуэль называется «бесшумной».

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

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

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

 

Матричные игры