ПРИНЯТИЕ РЕШЕНИЙ ПРИ НАЛИЧИИ НЕСКОЛЬКИХ АГЕНТОВ: ТЕОРИЯ ИГР
Данная глава в основном посвящена теме принятия решений в неопределенных вариантах среды. А как обстоят дела в том случае, если неопределенность связана с наличием других агентов и осуществлением ими решений, которые они принимают? И что будет, если на решения этих агентов, в свою очередь, влияют решения нашего агента? Эти вопросы уже рассматривались в настоящей книге при описании игр в главе 6. Но в этой главе речь в основном шла об играх с полной информацией, в которых игроки делают ходы по очереди: в подобных играх для определения оптимальных ходов может использоваться минимаксный поиск. А в данном разделе рассматриваются некоторые идеи теории игр, которые могут применяться при анализе игр с одновременно выполняемыми ходами. Для упрощения изложения вначале рассмотрим игры, которые продолжаются только в течение одного хода. На первый взгляд может показаться, что слово "игра" не совсем подходит для обозначения такого упрощения, которое сводится к одному ходу, но в действительности теория игр используется в очень серьезных ситуациях принятия решений, включая ведение дел о банкротстве, организацию аукционов по распределению спектра радиочастот, принятие решений по разработке промышленной продукции и назначению на нее цен, а также национальную оборону. В таких ситуациях речь часто идет о миллиардах долларов и сотнях тысяч человеческих жизней. Теория игр может использоваться по меньшей мере в двух описанных ниже направлениях.
1. Проектирование агента. Теория игр позволяет анализировать решения агента и вычислять ожидаемую полезность для каждого решения (с учетом предположения, что другие агенты действуют оптимальным образом согласно теории игр). Например, в игре в чет и нечет на двух пальцах (эту игру на пальцах называют также тогга, от итальянского слова сатогга — группа) два игрока, О (Odd — нечетный) и Е (Even — четный), одновременно показывают один или два пальца. Допустим, что общее количество показанных пальцев равно f. Если число f является нечетным, игрок О получает f долларов от игрока Е, а если число f — четное, игрок Е получает f долларов от игрока О. Теория игр позволяет определить наилучшую стратегию в игре против рационально действующего игрока и ожидаемый выигрыш для каждого игрока5.
2. Проектирование механизма. Если в среде присутствует много агентов, то может существовать возможность так определить правила действий в этой среде (т.е. правила игры, в которую должны играть агенты), чтобы общее благосостояние всех агентов максимизировалось, если каждый агент принимает обоснованное теорией игр решение, максимизирующее его собственную полезность. Например, теория игр позволяет проектировать такие протоколы для коллекции маршрутизаторов трафика Internet, чтобы каждый маршрутизатор стремился действовать в направлении максимизации глобальной пропускной способности. Проектирование механизма может также использоваться для создания интеллектуальных мультиагентных систем, которые решают сложные задачи в распределенной форме без необходимости для каждого агента знать о том, какая задача решается в целом.
Любая игра в теории игр определяется с помощью описанных ниже компонентов.
• Игроки, или агенты, которые должны принимать решения. Наибольшее внимание в исследованиях уделялось играм с двумя игроками, хотя достаточно часто рассматриваются также игры с п игроками, где п>2. В этой главе имена игроков записываются с прописной буквы, например Alice и Bob или О и Е.
• Действия, которые могут быть выбраны игроками. В этой главе имена действий записываются строчными буквами, например one или testify. В распоряжении игроков могут находиться одинаковые или неодинаковые множества действий.
• Матрица вознаграждений, которая определяет полезность для каждого игрока каждой комбинации действий всех игроков. Матрица вознаграждений для игры чет или нечет на двух пальцах приведена в табл. 17.1 (one — выбор действия, в котором игрок показывает один палец, two — два пальца).
Например, в нижнем правом углу показано, что если игрок О выбирает действие two, а игрок Етакже выбирает two, то вознаграждение для ? равно 4, а для О равно -4.
Каждый игрок, участвующий в игре, должен выработать, а затем осуществить стратегию (напомним, что такой же термин используется для обозначения способа выбора действий не только в теории игр, но и в теории принятия решений). Чистая стратегия — это детерминированная стратегия, определяющая конкретное действие, которое должно быть выполнено в каждой ситуации; в игре, состоящей из одного хода, чистая стратегия состоит из одного действия. Анализ игр приводит к формулировке идеи смешанной стратегии, которая представляет собой рандомизированную стратегию, предусматривающую выбор конкретных действий среди доступных действий в соответствии с определенным распределением вероятностей. Смешанная стратегия, в которой обычно выбирается действие а с вероятностью р, а в противном случае выбирается действие Ь, условно обозначается как [р:а; (1-р) :Ь]. Например, смешанной стратегией для игры в чет и нечет на двух пальцах может быть [0.5: one; 0.5: two]. Профилем стратегии называется вариант присваивания стратегии каждому игроку; после того как задан профиль стратегии, результат игры для каждого игрока принимает определенное числовое значение.
Решением игры называется профиль стратегии, в котором каждый игрок принимает рациональную стратегию. Как будет показано ниже, наиболее важной проблемой в теории игр является определение того, что подразумевается под словом "рациональный", когда каждый агент выбирает только часть профиля стратегии, определяющую этот результат. Важно понять, что результаты представляют собой фактические итоги ведения игры, а решения являются теоретическими конструкциями, которые используются для анализа игры. Ниже будет показано, что некоторые игры имеют решение только в смешанных стратегиях. Но это не означает, что игрок должен в буквальном смысле слова принимать смешанную стратегию, чтобы действовать рационально.
Рассмотрим описанную ниже историю. Два отпетых грабителя, Алиса и Боб, были пойманы с поличным недалеко от места совершенного ими ограбления, и теперь их отдельно допрашивают следователи. Оба они знают, что, признавшись в совместном совершении этого преступления, получат по 5 лет тюремного заключения за грабеж, а если оба откажутся признаваться, то получат только по 1 году каждый за менее грубое правонарушение — владение краденым имуществом. Но следователи предлагают отдельно каждому из них такую сделку: если вы дадите свидетельство против вашего партнера как главаря шайки грабителей, то вас освободят, а партнера осудят на 10 лет. Теперь Алиса и Боб сталкиваются с так называемой дилеммой заключенного: должны ли они свидетельствовать (testify) или отказаться (refuse)? Будучи рациональными агентами, и Алиса, и Боб желают максимизировать свою собственную ожидаемую полезность. Предположим, что Алиса полностью безразлична к судьбе своего партнера, а ее оценка полезности уменьшается пропорционально количеству лет, которые она проведет в тюрьме, независимо от того, что случится с Бобом. Боб думает точно так же. Чтобы упростить для себя выработку рационального решения, оба грабителя составляют матрицу вознаграждений, приведенную в табл. 17.2.
Алиса анализирует эту матрицу вознаграждений следующим образом: предположим, что Боб будет свидетельствовать против меня. В таком случае я получу 5 лет, если буду свидетельствовать против него, и 10 лет — если откажусь, поэтому в данном случае лучше свидетельствовать против него. С другой стороны, если Боб откажется, то я получу 0 лет, если буду свидетельствовать, и 1 год, если откажусь, поэтому и в данном случае лучше свидетельствовать. Итак, и в том и в другом случае для меня лучше свидетельствовать против Боба, поэтому так я и должна поступить.
Алиса обнаружила, что testify — это доминантная стратегия для рассматриваемой игры. Принято считать, что стратегия s для игрока р строго доминирует над стратегией s •, если результат стратегии s лучше для игрока р, чем результат стратегии s', при любом выборе стратегий другими игроками. Стратегия s слабо доминирует над s •, если s лучше чем s • по меньшей мере в одном профиле стратегий и не хуже в любом другом. Доминантной стратегией является стратегия, которая доминирует над всеми остальными. Нерационально вести игру на основе стратегии, над которой строго доминируют другие стратегии, и нерационально не вести игру на основе доминантной стратегии, если она существует. Будучи рациональным агентом, Алиса выбирает доминантную стратегию. Прежде чем перейти к дальнейшему изложению, необходимо рассмотреть еще несколько терминов: принято считать, что некоторый результат является оптимальным согласно принципу Парето6, если нет другого результата, который предпочли бы все игроки. Над результатом доминирует по принципу Парето другой результат, если все игроки предпочитают этот другой результат.
А если Алиса — не только рациональный, но и умный агент, она должна продолжить рассуждение следующим образом: доминантной стратегией Боба также является свидетельствование против меня. Поэтому он будет свидетельствовать, и мы оба получим по пять лет. Если оба игрока имеют доминантную стратегию, то комбинация этих стратегий называется равновесием доминантных стратегий. Вообще говоря, профиль стратегий образует равновесие, если ни один игрок не может извлечь выгоду от переключения с одной стратегии на другую, при условии, что все остальные игроки продолжают придерживаться одной и той же стратегии. Равновесие по сути представляет собой локальный оптимум в пространстве стратегий; оно является вершиной пика, вокруг которого находятся спады вдоль всех измерений, где измерения соответствуют вариантам выбора стратегии игроком.
Парадоксальность дилеммы заключенного состоит в том, что результат в точке равновесия для обоих игроков хуже по сравнению с результатом, которого они достигли бы, если бы оба отказались свидетельствовать друг против друга. Иными словами, результат для равновесного решения доминируется по принципу Парето результатом (-1,-1), который соответствует обоюдному отказу от свидетельства, (refuse,refuse).
Существует ли какой-либо способ, с помощью которого Алиса и Боб могли бы формально прийти к результату (-1,-1)? Безусловно, что для них обоих вариант, в котором они отказываются свидетельствовать, является допустимым, но этот вариант маловероятен. Любой игрок, анализирующий вариант хода refuse, поймет, что для него было бы лучше выбрать ход testify. В этом состоит притягательная мощь точки равновесия.
Математик Джон Нэш (род. в 1928 году) доказал теорему, согласно которой каждая игра имеет равновесие такого типа, которое определено в данном примере.
Теперь указанное условие называют в его честь равновесием Нэша. Очевидно, что равновесием доминантных стратегий является равновесие Нэша (упр. 17.9), но не все игры имеют доминантные стратегии. Теорема Нэша означает, что равновесные стратегии могут существовать даже при отсутствии доминантных стратегий.
В дилемме заключенного равновесием Нэша является только профиль стратегий (testify, testify). Трудно понять, как рациональные игроки могут избежать такого результата, поскольку в любом предложенном неравновесном решении по меньшей мере один из игроков будет подвергаться соблазну изменить свою стратегию. Специалисты в области теории игр соглашаются с тем, что обязательным условием того, чтобы некоторый ход представлял собой решение, является принадлежность его к равновесию Нэша, но еще не достигнуто полное согласие в отношении того, является ли это условие достаточным.
Решения (testify, testify) можно довольно легко избежать, немного изменив правила игры (или взгляды игроков). Например, можно перейти к итерационной игре, в которой игроки знают, что когда-то обязательно снова встретятся и вспомнят, как действовали при прошлой встрече (но крайне важно то, что они не должны иметь определенной информации о том, через какое время встретятся). Кроме того, если агенты имеют моральные убеждения, которые способствуют сотрудничеству и справедливому отношению друг к другу, то можно изменить матрицу вознаграждения так, чтобы она отражала для каждого агента полезность взаимодействия с другим агентом. Как будет показано ниже, на результатах может также отразиться такая модификация агентов, чтобы они обладали ограниченной вычислительной мощью, а не способностью рассуждать абсолютно рационально, а также предоставление одному агенту информации о том, что способности другого рассуждать рационально ограничены.
Теперь рассмотрим игру, в которой отсутствует доминантная стратегия. Предположим, что компания Acme, изготовитель аппаратных средств для видеоигр, должна решить, будут ли в ее следующей игровой машине использоваться DVD или CD. Между тем компания Best, производитель программного обеспечения для видеоигр, должна принять решение о том, следует ли выпускать свою очередную игру на DVD или CD. Для обеих компаний прибыль будет положительной, если они примут согласованные решения, и отрицательной, если решения не будут согласованными, как показывает матрица вознаграждений, приведенная в табл. 17.3.
Для этой игры отсутствует равновесие доминантных стратегий, но имеются два равновесия Нэша: (dvd, dvd) и (cd, cd). Известно, что это — равновесия Нэша, поскольку, если один из игроков примет одностороннее решение перейти на другую стратегию, ситуация для него ухудшится. Теперь эти агенты сталкиваются с такой проблемой: имеется несколько приемлемых решений, но если каждый агент выберет другое решение, то результирующий профиль стратегий вообще не будет представлять собой решение, и оба агента понесут убытки. Каким образом эти игроки могут согласованно прийти к какому-то решению? Один из возможных ответов состоит в том, что оба игрока должны выбрать решение, оптимальное по принципу Парето, — (dvd, dvd); это означает, что можно ограничить определение понятия "решения" уникальным, оптимальным по принципу Парето равновесием Нэша, при условии, что оно существует. Каждая игра имеет по меньшей мере одно оптимальное по принципу Парето решение, но в любой игре может быть несколько таких решений, или эти решения могут не оказаться точками равновесия. Например, можно было бы установить вознаграждения за решение (dvd, dvd), равные 5, а не 9. В этом случае имеются две одинаковые точки равновесия, оптимальные по принципу Парето. Чтобы выбрать между ними, агенты должны либо пользоваться догадками, либо прибегать к общению, что можно сделать, приняв соглашение об упорядочении решений до начала игры, или проводить переговоры, чтобы достичь обоюдно выгодного решения во время игры (это может означать, что в состав многоходовой игры должны быть включены коммуникативные действия). Таким образом, необходимость в общении возникает в рамках теории игр точно по тем же причинам, что и в мультиагентном планировании, описанном в главе 12. Игры, подобные этой, в которых игроки должны вступать во взаимодействие, называются координационными играми.
Выше было показано, что игра может иметь больше одного равновесия Нэша; но на основании чего мы можем утверждать, что каждая игра должна иметь по меньшей мере одно такое равновесие? Может оказаться, что в игре отсутствует равновесие Нэша для чистой (не смешанной) стратегии. Рассмотрим, например, любой профиль чистых стратегий для игры в чет и нечет на двух пальцах (с. 839). Если общее количество показанных пальцев является четным, то игрок О может захотеть переключиться на другую стратегию, а если это количество нечетно, то будет стремиться переключиться игрок Е. Поэтому ни один профиль чистых стратегий не может представлять собой равновесие и приходится рассматривать смешанные стратегии.
Но какой должна быть смешанная стратегия? В 1928 году фон Нейман разработал метод поиска оптимальной смешанной стратегии для игр с двумя игроками, называемых играми с нулевой суммой. Игрой с нулевой суммой называется игра, в которой вознаграждения в каждой ячейке матрицы вознаграждения в сумме равны нулю7. Очевидно, что игра в чет и нечет является именно таковой. Известно, что для игр с двумя игроками и нулевой суммой вознаграждения являются равными и противоположными, поэтому достаточно рассмотреть вознаграждения только для одного игрока, который будет считаться максимизирующим игроком (точно так же, как и в главе 6). Применительно к игре в чет и нечет выберем в качестве максимизирующего игрока Е, который выбрал для себя в качестве выигрышного результата четное количество пальцев, поэтому можно определить матрицу вознаграждений на основе значений иЕ(е, о) — вознаграждение, получаемое игроком Е, если игрок Е выбирает действие е, а О — действие о.
Метод фон Неймана называется методом максимина и действует, как описано ниже.
• Предположим, что правила игры изменились таким образом, что игрок Е вынужден раскрывать свою стратегию первым, а за ним следует игрок О. В таком случае мы имеем дело с игрой, где ходы выполняются поочередно, к которой можно применить стандартный минимаксный алгоритм из главы 6. Допустим, что такая игра приводит к получению результата иЕ>0. Очевидно, что эта игра окончится в пользу игрока О, поэтому истинная полезность и данной игры (сточки зрения игрока Е) равна по меньшей мере иЕ)0. Например, если рассматриваются только чистые стратегии, то минимаксное дерево игры имеет корневое значение, равное -3 (рис. 17.9, а), поэтому известно, что U>-3.
• Теперь предположим, что правила изменились таким образом, что свою стратегию вынужден раскрывать игрок О, а за ним следует игрок Е. В таком случае минимаксное значение этой игры становится равным и0)Е, а поскольку игра складывается в пользу игрока Е, ТО известно, что полезность и самое большее равна u0iE. При использовании чистых стратегий это значение равно +2 (см. рис. 17.9, б), поэтому известно, что и<+2.
Рассматривая эти два предположения совместно, можно прийти к заключению, что истинная полезность и рассматриваемого решения должна удовлетворять следующему неравенству:
UE,o U < U0,E или в данном случае -3 < U < 2
Чтобы точно определить значение и, необходимо перейти к анализу смешанных стратегий. Вначале отметим следующее: как только первый игрок раскрыл свою стратегию, второй игрок не может проиграть, ведя игру согласно чистой стратегии. Причина этого проста — если второй игрок ведет игру на основе смешанной стратегии, [р: one; (1-р) : two], то ожидаемая полезность этой игры представляет собой линейную комбинацию (p-uone+ (1-р) -utwo) полезностей чистых стратегий uone и utwo. Эта линейная комбинация ни при каких условиях не будет лучше по сравнению с лучшим из значений uone и utwo, поэтому второй игрок вполне может просто выбрать для ведения игры чистую стратегию.
С учетом этого замечания минимаксные деревья можно рассматривать как имеющие бесконечное количество ветвей, исходящих от корня, которые соответствуют бесконечному количеству смешанных стратегий, доступных для выбора первым игроком. Каждая из этих ветвей ведет к узлу с двумя ветвями, соответствующими чистым стратегиям для второго игрока. Эти бесконечные деревья можно изобразить как конечные, предусмотрев один "параметризованный" выбор у корня, как описано ниже.
• Ситуация, возникающая, если игрок Е ходит первым, показана на рис. 17.9, в. Игрок Е делает из корневой позиции ход [р: one; (1-р) : two], а затем игрок О выбирает ход с учетом значения р. Если игрок о выбирает ход one, то ожидаемое вознаграждение (для Е) становится равным 2р-3(1-р)=5р-3; если игрок О выбирает ход two, то ожидаемое вознаграждение равно -Зр+4 (1-р) =4-7р. Зависимости, выражающие величину этих двух вознаграждений, можно изобразить в виде прямых линий на графике, где р изменяется от 0 до 1 вдоль оси х, как показано на рис. 17.9, д. Игрок О, минимизирующий стоимость игры, должен всегда выбирать наименьшее значение на двух прямых линиях, как показано на этом рисунке жирными отрезками прямых. Поэтому наилучшее решение, которое может
принять игрок Е, выбирая ход, подлежащий выполнению из корневой позиции, состоит в том, чтобы выбрать значение р, соответствующее точке пересечения и определяемое следующим образом:
5р-3 = 4-7р => р=7/12
Полезность для игрока Е в этот момент времени равна иЕ, 0= -1 /12.
• А если первым ходит игрок О, то складывается ситуация, показанная на рис. 17.9, г. Игрок О из корневой позиции делает ход [g: one; (1-д) : two], после чего игрок Е выбирает ход с учетом значения д. При этом вознаграждения определяются соотношениями8 2g-3 (1-g) =5д-3 и -Зд+4(1-д)=4-7д. Опять-таки на рис. 17.9, е показано, что наилучший ход, который может быть сделан игроком О из корневой позиции, состоит в выборе точки пересечения, следующим образом: 5д-3 = 4-7д => д=7/12
Полезность для игрока Ев этот момент равна u0iE=-l/12.
Теперь известно, что истинная полезность этой игры находится в пределах от -1/12 до -1 /12, т.е. она точно равна -1/12! (Общий вывод состоит в том, что в эту игру лучше играть от имени игрока О, а не Е.) Кроме того, истинная полезность достигается при использовании смешанной стратегии [7/12 : one; 5/12 : two], которой должны придерживаться оба игрока. Такая стратегия называется максиминным равновесием игры и соответствует равновесию Нэша. Обратите внимание на то, что каждая составляющая стратегия в равновесной смешанной стратегии имеет одну и ту же ожидаемую полезность. В данном случае и ход one, и ход two имеют ту же ожидаемую полезность, -1/12, что и сама смешанная стратегия.
Приведенный выше результат для игры в чет и нечет на двух пальцах представляет собой пример общего результата, полученного фон Нейманом: с5 каждая игра с нулевой суммой с двумя игроками имеет максиминное равновесие, если разрешены смешанные стратегии. Кроме того, каждое равновесие Нэша в игре с нулевой суммой представляет собой максиминное равновесие для обоих игроков. Но общий алгоритм поиска максиминных равновесий в играх с нулевой суммой немного сложнее по сравнению с тем, что показано в виде схем на рис. 17.9, д и е. Если количество возможных действий равно п, то смешанная стратегия представляет собой точку в n-мерном пространстве и прямые линии становятся гиперплоскостями. Возможно также, что над некоторыми чистыми стратегиями для второго игрока будут доминировать другие стратегии, так что они перестанут быть оптимальными по отношению к любой стратегии для первого игрока. После удаления всех подобных стратегий (а эту операцию может потребоваться выполнить неоднократно) оптимальным вариантом хода из корневой позиции становится самая высокая (или самая низкая) точка пересечения оставшихся гиперплоскостей. Поиск этого варианта представляет собой пример задачи линейного программирования — максимизации целевой функции с учетом линейных ограничений. Такие задачи могут быть решены с помощью стандартных методов за время, полиномиально зависящее от количества действий (а также формально и от количества битов, используемых для определения функции вознаграждения).
Остается нерешенным следующий вопрос: как фактически должен действовать рациональный агент при ведении такой одноходовой игры, как игра в чет и нечет? Рациональный агент пришел логическим путем к выводу, что [7/12 юле; 5/12 : two] представляет собой максиминную равновесную стратегию, и исходит из предположения, что знаниями об этом обладает и его рациональный противник. Агент может использовать игральную кость с 12 сторонами или генератор случайных чисел для выбора случайным образом хода, соответствующего этой смешанной стратегии, и в этом случае ожидаемое вознаграждение для игрока Е будет равно -1/12. В ином случае агент может просто решить сделать ход one или two. В любом случае для игрока Е ожидаемое вознаграждение остается равным -1/12. Удивительно то, что односторонний выбор конкретного действия не уменьшает ожидаемое вознаграждение для данного игрока, но если другой агент будет иметь возможность узнать, что данный игрок принял такое одностороннее решение, то ожидаемое вознаграждение изменится, поскольку противник сможет откорректировать свою стратегию соответствующим образом.
Поиск решений для конечных игр с ненулевой суммой (т.е. равновесий Нэша) немного сложнее. Общий подход заключается в использовании двух этапов. Во-первых, необходимо составить список из всех возможных последовательностей действий, которые могут образовывать смешанные стратегии. Например, вначале следует проверить все профили стратегий, в которых каждый игрок выполняет одно действие, затем те, в которых каждый игрок выполняет либо одно, либо два действия, и т.д. Количество таких проверок экспоненциально зависит от количества действий, поэтому может применяться только в относительно простых играх. Во-вторых, для каждого профиля стратегий, включенного в список на первом этапе, необходимо провести проверку для определения того, представляет ли он некоторое равновесие. Такая задача выполняется путем решения ряда уравнений и неравенств, аналогичных используемым в случае с нулевой суммой. В игре с двумя игроками эти уравнения являются линейными и могут быть решены с помощью основных методов линейного программирования, но в случае трех или большего количества игроков они являются нелинейными и задача поиска их решения может оказаться очень сложной.
До сих пор мы рассматривали только такие игры, которые состоят из одного хода. Простейшей разновидностью игры, состоящей из нескольких ходов, является повторяющаяся игра, в которой игроки снова и снова сталкиваются с одним и тем же выбором, но каждый раз пользуются знаниями истории всех предыдущих выборов всех игроков. Профиль стратегий для повторяющейся игры определяет выбор действия для каждого игрока на каждом временном интервале для всех возможных историй предыдущих выборов. Как и в случае задач MDP, вознаграждения определяются аддитивной функцией от времени.
Рассмотрим повторяющуюся версию поиска решения дилеммы заключенного. Будут ли Алиса и Боб действовать совместно и откажутся свидетельствовать друг против друга, зная о том, что им придется снова встретиться? Ответ зависит от деталей их соглашения. Например, предположим, Алиса и Боб знают, что им придется провести ровно 100 раундов игры в дилемму заключенного. В таком случае оба они знают, что 100-й раунд не будет повторяющейся игрой, т.е. что ее результат не сможет оказать влияния на будущие раунды, и поэтому оба они выберут в этом раунде доминантную стратегию testify. Но как только будет определен результат 100-го раунда, 99-й раунд перестанет оказывать влияние на последующие раунды, поэтому в нем также будет достигаться равновесие доминантной стратегии в случае выбора действий (testify, testify). По индукции оба игрока должны выбирать действие testify в каждом раунде, заработав общий срок по 500 лет тюремного заключения на каждого.
Изменяя правила взаимодействия, можно получить другие решения. Например, предположим, что после каждого раунда существует 99% шансов, что игроки снова встретятся. В таком случае ожидаемое число раундов все еще остается равным 100, но ни один из игроков не знает точно, какой раунд будет последним. При таких условиях возможно поведение, характеризующееся большей степенью сотрудничества. Например, одной из стратегий равновесия для каждого игрока является выбор действия refuse, если другой игрок никогда не выбирал действие testify. Такую стратегию можно назвать вечным наказанием. Предположим, что оба игрока приняли данную стратегию и это известно им обоим. В таком случае, при условии, что ни один из игрок не выберет действие testify, в любой момент времени ожидаемое суммарное вознаграждение в будущем для каждого игрока составляет следующее:
Игрок, который выберет testify, получит 0 очков вместо -1 в каждом следующем ходе, но его суммарное ожидаемое будущее вознаграждение становится равным:
Поэтому на каждом этапе игроки не имеют стимула, который заставил бы их отказаться от стратегии (refuse, refuse). Вечное наказание— это стратегия "взаимно гарантированного уничтожения" в рамках дилеммы заключенного: как только один из игроков решит выполнить действие testify, он обеспечит получение обоими игроками больших неприятностей. Но такая перспектива развития событий может стать предостережением, только если другой игрок знает, что вы приняли эту стратегию или по меньшей мере что вы могли ее принять.
Существуют и другие стратегии в этой игре, которые являются не такими бескомпромиссными. Наиболее известная из них, называемая отплатой "зуб за зуб", предусматривает, что игрок начинает с действия refuse, а затем повторяет предыдущий ход другого игрока во всех последующих ходах. Поэтому Алиса должна отказываться свидетельствовать против Боба до тех пор, пока Боб отказывается свидетельствовать против нее, затем должна выбирать в своем ходе дачу показаний против Боба, как только Боб даст показания против нее, но должна возвращаться к отказу от дачи показаний, после того как это сделает Боб. Хотя эта стратегия очень проста, оказалось, что она является в высшей степени надежной и эффективной в противодействии самым разнообразным стратегиям.
Кроме того, другие решения могут быть получены в результате модификации самих агентов, а не изменения правил их взаимодействия. Предположим, что агенты представляют собой конечные автоматы с п состояниями и играют в игру с общим количество ходов т>п. Поэтому агенты в какой-то момент становятся неспособными представить целый ряд оставшихся ходов и должны рассматривать их как неизвестные. Это означает, что они не могут выполнять логический вывод по индукции и вправе переходить к наиболее благоприятному равновесию (refuse,refuse). В таком случае глупость идет на пользу или, скорее, идет на пользу мнение противника о том, что вы глупы. Ваш успех в таких повторяющихся играх зависит от мнения о вас другого игрока как о тупице или простаке, а не от ваших фактических характеристик.
Полное описание повторяющихся игр, которые представляют собой большую и важную научную область, выходит за рамки данной книги, но они возникают во многих ситуациях. Например, последовательную игру можно организовать, поместив двух агентов в мир 4x3, показанный на рис. 17.1. Если будет определено, что не должно происходить никакого движения, если два агента пытаются одновременно перейти в один и тот же квадрат (эта проблема часто возникает на многих пересечениях разных направлений дорожного движения), то некоторые чистые стратегии могут привести к бесконечному тупику. Одно из решений состоит в том, чтобы для каждого агента был рандомизирован выбор между движением вперед и остановкой на месте; патовая ситуация будет быстро разрешена и оба агента смогут продолжить свое движение. Именно такой подход применяется при разрешении коллизий между пакетами в сетях Ethernet.
Известные в настоящее время методы выработки решений для повторяющихся игр напоминают методы, применяемые в играх с поочередными ходами, описанных в главе 6, в том, что дерево игры может быть сформировано от корня вниз и решено от листьев вверх. Основное различие между ними состоит в том, что вместо простого определения максимума или минимума дочерних значений алгоритм должен найти решение игры в терминах смешанных стратегий на каждом уровне, при условии, что для дочерних узлов найдены решения и имеются точно определенные значения, с которыми можно дальше работать.
Повторяющиеся игры в частично наблюдаемых вариантах среды называются играми с частичной информацией. К примерам таких игр относятся карточные игры наподобие покера и бриджа, в которых каждый игрок видит только некоторое подмножество карт, а также более серьезные "игры", такие как моделирование атомной войны, когда ни одна из сторон не знает местонахождение всех пусковых установок противника. Решения игр с частичной информацией можно найти, рассматривая дерево доверительных состояний, как и в случае задач POMDP (см. раздел 17.4). Одно важное различие между ними состоит в том, что собственное доверительное состояние является наблюдаемым, а доверительное состояние противника — нет. Для таких игр практически применимые алгоритмы были разработаны только недавно. Например, найдено решение для некоторой упрощенной версии покера и доказано, что вариант, в котором игроки блефуют, действительно является рациональным, по крайней мере в составе тщательно сбалансированной смешанной стратегии. В результате этих исследований было сделано одно важное открытие, которое заключается в том, что смешанные стратегии полезны не только для того, чтобы сделать действия игрока непредсказуемыми, но и для минимизации объема информации, которую противник может извлечь из наблюдений за действиями этого игрока. Интересно отметить, что разработчики программ для игры в бридж хорошо понимают важность сбора и сокрытия информации, но ни один из них не предложил использовать рандомизированные стратегии.
До сих пор обнаруживались определенные барьеры, которые препятствовали широкому использованию теории игр в проектах агентов. Во-первых, следует отметить, что при поиске решения на основе равновесия Нэша игрок предполагает, что его противник со всей определенностью будет вести игру на основе равновесной стратегии. Это означает, что игрок не способен учесть какие-либо убеждения, которые у него могут быть в отношении того, как скорее всего будут действовать другие игроки, и поэтому не сможет воспользоваться своими важными преимуществами, защищаясь от угроз, которые так никогда и не материализуются. Эта проблема частично решается благодаря использованию понятия равновесия Байеса—Нэша, т.е. равновесия применительно к распределению априорных вероятностей игрока по отношению к стратегиям других игроков; иными словами, равновесие Байеса—Нэша выражает уверенность игрока в том, какие вероятные стратегии будут применять другие игроки. Во-вторых, в настоящее время отсутствует удобный способ совместного применения стратегий управления, основанных на теории игры и модели POMDP. Из-за наличия этих и других проблем теория игр в основном использовалась для анализа вариантов среды, находящихся в равновесном состоянии, а не для управления агентами, действующими в некоторой среде. Но ниже будет показано, что теория игр может помочь и при проектировании вариантов среды.