Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 229
Текст из файла (страница 229)
° сь Действия, которые могут быть выбраны игроками. В этой главе имена действий записываются строчными буквами, например опе или ееягйГу. В распоряжении игроков могут находиться одинаковые или неодинаковые множества действий. ° гв Матрица вознаграждений, которая определяет полезность для каждого игрока каждой комбинации действий всех игроков. Матрица вознаграждений для игры чет или нечет на двух пальцах приведена в табл. 17.! (опе — выбор действия, в котором игрок показывает один палец, саго — два пальца). Таблица 17.1. Матрица вознаграждений для игры чет или мечет иа двух пальцах Ою оае В=2,0=-2 в=-з,о=з е=-з,о=з в=а, о=-4 в: опе в; сис Например, в нижнем правом углу показано, что если игрок О выбирает действие саго, а игрок е также выбирает пью, то вознаграждение для е равно 4, а для О равно -4.
Каждый игрок, участвующий в игре, должен выработать, а затем осуществить стратегию (напомним, что такой же термин используется для обозначения способа выбора действий не только в теории игр, но и в теории принятия решений). оь Чистая стратегия — это детерминированная стратегия, определяющая конкретное з Игра в чет и нечет — это развлекательная версия реальной игры в ииспекцпю. В таких играх инспектор выбирает день лля инспектирования предприятия (такого как ресторан или завод биологического оружия), а оператор предприятия выбирает пень, в который нужно спрятать все запрещенные предметы. Если эти дни ие совпадают, выигрывает инспектор, а если совпадают— выигрывает оператор предприятия. 841 Глава 17.
Принятие сложных решений Таблица 17.2. Матрица вознаграждений для дилеммы заключенного Лззсег Оееоззтг Лддсегсееиее ВсЬ:ГеесзГу ВСЬгдЕГиЗЕ л = -зо,в = о л = -з,в = -т Л = — 5,В = — 5 л= ов=-зо Алиса анализирует эту матрицу вознаграждений следующим образом: предположим, что Боб будет свидетельствовать против меня. В таком случае я получу 5 лет, действие, которое должно быть выполнено в каждой ситуации; в игре, состоящей из одного хода, чистая стратегия состоит из одного действия.
Анализ игр приводит к формулировке идеи 'гзг смешанной стратегии, которая представляет собой рандомизированную стратегию, предусматривающую выбор конкретных действий среди доступных действий в соответствии с определенным распределением вероятностей. Смешанная стратегия, в которой обычно выбирается действие а с вероятностью р, а в противном случае выбирается действие Ь, условно обозначается как [р:аг (1-р):Ь]. Например, смешанной стратегией для игры в чет и нечет на двух пальцах может быть ( О .
5: опеп О . 5: сгго] . Ъ. Профилем стратегии называется вариант присваивания стратегии каждому игроку; после того как задан профиль стратегии, 'в. результат игры для каждого игрока принимает определенное числовое значение. ск Решением игры называется профиль стратегии, в котором каждый игрок принимает рациональную стратегию. Как будет показано ниже, наиболее важной проблемой в теории игр является определение того, что подразумевается под словом "рациональный", когда каждый агент выбирает только часть профиля стратегии, определяющую этот результат. Важно понять, что результаты представляют собой фактические итоги ведения игры, а решения являются теоретическими конструкциями, которые используются для анализа игры.
Ниже будет показано, что некоторые игры имеют решение только в смешанных стратегиях. Но это не означает, что игрок должен в буквальном смысле слова принимать смешанную стратегию, чтобы действовать рационально. Рассмотрим описанную ниже историю. Два отпетых грабителя, Алиса и Боб, были пойманы с поличным недалеко от места совершенного ими ограбления, и теперь их отдельно допрашивают следователи. Оба они знают, что, признавшись в совместном совершении этого преступления, получат по 5 лет тюремного заключения за грабеж, а если оба откажутся признаваться, то получат только по 1 году каждый за менее грубое правонарушение — владение краденым имуществом. Но следователи предлагают отдельно каждому из них такую сделку: если вы дадите свидетельство против вашего партнера как главаря шайки грабителей, то вас освободят, а партнера осудят на 10 лет.
Теперь Алиса и Боб сталкиваются с так называемой 'а. дилеммой заключенного: должны ли они свидетельствовать(селедку) или отказаться (теннисе)? Будучи рациональными агентами, и Алиса, и Боб желают максимизировать свою собственную ожидаемую полезность. Предположим, что Алиса полностью безразлична к судьбе своего партнера, а ее оценка полезности уменьшается пропорционально количеству лет, которые она проведет в тюрьме, независимо от того, что случится с Бобом. Боб думает точно так же. Чтобы упростить для себя выработку рационального решения, оба грабителя составляют матрицу вознаграждений, приведенную в табл. 17.2.
842 Часть У. Неопределенные знания и рассуждения в условиях неопределенности если буду свидетельствовать против него, и 10 лет — если откажусь, поэтому в данном случае лучше свидетельствовать против него. С другой стороны, если Боб откажется, то я получу 0 лет, если буду свидетельствовать, и ! год, если откажусь, поэтому и в данном случае лучше свидетельствовать. Итак, и в том и в другом случае для меня лучше свидетельствовать против Боба, поэтому так я и должна поступить. Алиса обнаружила, что сеэ сйЕу — это 2аь доминантная стратегия для рассматриваемой игры. Принято считать, что стратегия э для игрока р аь строго доминирует над стратегией э', если результат стратегии э лучше для игрока р, чем результат стратегии э ', при любом выборе стратегий другими игроками.
Стратегия э аь слабо доминирует над э', если э лучше чем э' по меньшей мере в одном профиле стратегий и не хуже в любом друпзм. Доминантной стратегией является стратегия, которая доминирует над всеми остачьными. Нерационально вести игру на основе стратегии, над которой строго доминируют другие стратегии, и нерационально не вести и!ру на основе доминантной стратегии, если она существует. Будучи рациональным агентом, Алиса выбирает доминантную стратегию. Прежде чем перейти к дальнейшему изложению, необходимо рассмотреть еще несколько терминов: принято считать, что некоторый результат является Ъ. оптимальным согласно принципу Парето', если нет другого результата, который предпочли бы все игроки.
Над результатом 2в. доминирует по принципу Парето другой результат, если все игроки предпочитают этот другой результат. А если Алиса — не только рациональный, но и умный агент, она должна продолжить рассуждение следующим образом: доминантной стратегией Боба также является свидетельствование против меня. Поэтому он будет свидетельствовать, и мы оба получим по пять лет. Если оба игрока имеют доминантную стратегию, то комбинация этих стратегий называется 'в.
равновесием доминантных стратегий. Вообще говоря, профиль стратегий образует 'ак равновесие, если ни один игрок не может извлечь выгоду от переключения с одной стратегии на другую, при условии, что все остальные игроки продолжают придерживаться одной и той же стратегии. Равновесие по сути представляет собой локальный оптимум в пространстве стратегий; оно является вершиной пика, вокруг которого находятся спады вдоль всех измерений, где измерения соответствуют вариантам выбора стратегии игроком.
Парадоксальность дилеммы заключенного состоит в том, что результат в точке равновесия для обоих игроков хуже по сравнению с результатом, которого они достигли бы, если бы оба отказались свидетельствовать друг против друга. Иными словами, результат для равновесного решения доминируется по принципу Парето результатом )-1,-1), который соответствует обоюдному отказу от свидетельства, ! кейцэе, кеЕиэе) .
Существует ли какой-либо способ, с помощью которого Алиса и Боб могли бы формально прийти к результату (-1, -1)? Безусловно, что для них обоих вариант, в котором они отказываются свидетельствовать, является допустимым, но этот вариант маловероятен. Любой игрок, анализирующий вариант хода кеГцэе, поймет, что для него было бы лучше выбрать ход сеэ сб Гу. В этом состоит притягательная мощь точки равновесия. Математик Джон Нэш (род. в 1928 году) доказал теорему, согласно которой каждая игра имеет ривновесие такого типа, которое определено в данном примере. " Опти мал ьносп по принципу Парето названа в честь э кон омисга Вильфрело Парето ! ! 848 — 1 923). Глава 17. Принятие сложных решений о43 Таблица 17.3. Матрица вознаграждений для компаний Асме и Веа1 Лсиезса А=9,В=9 А=-З,В= -1 А=-Е,В=-З А=5,В=5 Веаг: с) е) Вевг:сс) Для этой игры отсутствует равновесие доминантных стратегий, но имеются два равновесия Нэша: 1с)т с), е)те)) и 1сс), сс)).
Известно, что это — равновесия Нэша, поскольку, если один из игроков примет одностороннее решение перейти на другую стратегию, ситуация для него ухудшится. Теперь эти агенты сталкиваются с такой проблемой: «еп имеется несколько приемлемых решений, но если калсдый агент выберет другое решение, то результирующий профиль стратегий вообще не будет предстивлять собой решение, и оба агента понесут убытки. Каким образом эти игроки могут согласованно прийти к какому-то решению? Один из возможных ответов состоит в Теперь указанное условие называют в его честь равновесием Нэша.
Очевидно, что равновесием доминантных стратегий является равновесие Нэша (упр. 17.9), но не все игры имеют доминантные стратегии. Теорема Нэша означает, что равновесные стратегии могут существовать даже при отсутствии доминантных стратегий. В дилемме заключенного равновесием Нэша является только профиль стратегий 1сеэсйбу, сеасзбу). Трудно понять, как рациональные игроки могут избежать такого результата, поскольку в любом предложенном неравновесном решении по меньшей мере один из игроков будет подвергаться соблазну изменить свою стратегию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
