Предмет и задачи теории игр

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

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

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

Такого рода задачами занимается специальный раз­дел математики, носящий причудливое название «тео­рия игр и статистических решений». В некоторых (редких) случаях разработанные в нем методы дают возможность фактически найти оптимальное решение. Гораздо чаще эти методы позволяют попросту глубже разобраться в ситуации, оценить каждое решение с различных (иногда противоречивых) точек зрения, взвесить его преимущества и недостатки и, в конце? концов, принять решение, если не единственно правильное, то, по крайней мере, до конца продуманное. Нельзя забывать, что при выборе решения в условиях неопределенности неизбежен некоторый произвол и эле­мент риска. Недостаток информации — всегда беда, а не преимущество (хотя именно при отсутствии информа­ции исследователь может щегольнуть наиболее тонкими математическими методами). Тем не менее, в сложной ситуации, плохо обозримой в целом, когда, как гово­рится, «рябит в глазах» от подробностей, всегда полез­но представить варианты в такой форме, чтобы сделать произвол выбора менее грубым, а риск — по возмож­ности минимальным. Нередко задача ставится так: какой ценой можно заплатить за недостающую инфор­мацию, чтобы за ее счет повысить эффективность опе­рации? Заметим, что иногда для выбора решения и не требуется точной информации об условиях, а достаточ­но только указать «район», в котором они находятся (метод «районирования» И. Я. Динера, см. [23]).

В данной главе излагаются некоторые минимальные сведения из теории игр и статистических решений. Для более подробного ознакомления с нею можно рекомен­довать работы [24—28].

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

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

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

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

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

В игре могут сталкиваться интересы двух или более участников; в первом случае игра называется «пар­ной», во втором — «множественной». Участники мно­жественной игры могут образовывать коалиции (посто­янные или временные). Одна из задач теории игр — выявление разумных коалиций во множественной игре и правил обмена информацией между участниками. Множественная игра с двумя постоянными коалиция­ми, естественно, обращается в парную.

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

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

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

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

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

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

Игра называется игрой с нулевой суммой, если сумма выигрышей всех игроков равна нулю (т. е. каждый игрок выигрывает только за счет других). Са­мый простой случай — парная игра с нулевой сум­мой — называется антагонистической (или игрой со строгим соперничеством). Теория ан­тагонистических игр — наиболее развитый раздел тео­рии игр, с четкими рекомендациями. Ниже мы позна­комимся с некоторыми ее понятиями и приемами.

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