12.5. ВАЖНОСТЬ АППРОКСИМАЦИИ

Почти все исследования в теории игр до настоящего времени касались точных утверждений, но ведь имеется существенная

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

1. Принцип горизонтальной неточности

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

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

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

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

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

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

рис. 12.5.1.

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

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

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

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

2. Принцип вероятностной неопределенности

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

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

Если азартный игрок постоянно ставит на одно и то же событие и если вероятность выигрыша в действительности равна 0,45, хотя он думает, что она равна 0,5, то ему надо сделать очень много попыток, для того чтобы почувствовать свою ошибку. Большая часть науки статистики посвящена выводам, которые можно сделать из таких повторных попыток, и предмет этот далеко не прост. Не нужно переоценивать важность закона больших чисел, который в данном случае утверждает только то, что для очень длинного ряда испытаний игрок почти наверное выиграет в числе случаев, очень близком к 45%.

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

какова же ценность улучшенной стратегии, если рассматривается малое число партий?

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

Рассмотрим в качестве примера движущуюся цель, например самолет или корабль, обстреливаемый противником. С точки зрения теории игр плата должна выражать следующий факт: поражен этот объект или нет. Цель может делать определенные маневры, так что ее положение трудно обнаружить или предсказать. Выбор маневра составляет стратегию, причем в этой игре, сущность которой состоит в информации, стратегия определенно должна быть смешанной. За плату следует принять вероятность поражения.

Предположим, что с помощью различных улучшений стратегии цель может свести вероятность поражения, например, к 5, 10, 25 или 50%. Для отдельных или немногочисленных реализаций ситуация становится похожей на случай с азартным игроком. Играет ли большую роль сведение шансов к 5 или Если с 50%, то да, а если с

Но возможны повторения этой ситуации. На протяжении войны может произойти много столкновений подобного рода. Процент разбитых объектов приблизится к вероятности поражения. Стоит ли сводить процент сбитых самолетов к

Таковы наши основания для заключения, что практическая задача теории игр, особенно игр с недостатком информации, должна состоять в отыскании приближенных решений. Доказательств в пользу этого, видимо, немного. В самом деле, игра поиска с большим числом неподвижных объектов из § 12.3 — это единственный известный нам пример. В § 12.4 мы высказали догадку, что в случае подвижных объектов не очень существен выбор конкретных траекторий. Доказательство этого и подобных ему утверждений, если они верны, означало бы решительный и полезный прогресс в теории игр. Итак, существенная задача состоит в том, как оценить степень приближенности, приемлемую для различных классов игр.

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

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

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

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

Хотя мы агитируем за исследования в области приближенных решений, мы вовсе не против других подходов. Если точная оптимальная смешанная стратегия будет найдена, скажем, для игр поиска из § 12.3 и 12.4, то, несмотря на то что ее использование, по-видимому, мало что принесет соперникам, само ее открытие, возможно, бросит яркий свет на совершенно темную область.