Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2. Игры с полной информацией. Точки равновесияОбратимся теперь к играм особого рода — к так называемым играм с «прлной информацией». Эти игры характеризуются тем, что во всякой точке в любой партии игрок, чья очередь делать ход, точно знает, какие выборы были сделаны раньше. По отношению к диаграмме игры это значит, что любое информационное множество состоит из одного элемента. Так, например, игра, изображенная на рис. 24, есть игра с полной информацией. Поскольку в диаграмме игры с полной информацией каждая пунктирная линия заключает лишь одну точку разветвления, мы можем в случае таких игр опустить совсем пунктирные линии. Таким образом, рис. 24 мы заменим на рис. 25. Учащийся сам может распознать, какие из обычных салонных игр являются играми с полной информацией. Таковы, например, тик-так-ту, шашки, шахматы и трик-трак. Напротив, большинство карточных игр (например, бридж, покер, канаста) не является играми с полной информацией, так как игроки не знают, какие карты были выданы другим игрокам.
Рис. 24. Мы покажем теперь, что матрица любой игры в нормальной форме двух лиц с нулевой суммой и полной информацией имеет седловую точку, то есть в такой игре есть оптимальные чистые стратегии.
Рис. 25. Для такой простой игры, как тик-так-ту, это, конечно, известно каждому, кто когда-нибудь играл в эту игру хоть несколько раз. Каждый игрок в тик-так-ту может играть таким образом, что он выиграет (если другой игрок будет играть неправильно) или добьется ничьей. По этой причине взрослые редко играют в тик-так-ту: после того как они узнали оптимальные стратегии для этой игры, она уже не ставит перед ними умственных задач. Чтобы найти такие оптимальные стратегии игры, нужно лишь переписать все стратегии игры, написать матрицу (поставив «1», «0» и «-1» для «выигрыша», «ничьей» и «проигрыша») и выбрать седловую точку. Но число возможных стратегий для шахмат так велико, что вряд ли возможно провести такое перечисление. Поэтому, вероятно, люди будут еще долгое время увлекаться игрой в шахматы. Вследствие того, что наше доказательство будет проводиться путем математической индукции, оказывается удобнее доказать несколько более сильное утверждение, чем упомянутое выше, — теорему, относящуюся ко всем играм двух лиц с полной информацией, а не только к играм двух лиц с нулевой суммой и полной информацией. Для формулировки этой более сильной теоремы необходимо ввести понятие точки равновесия, являющееся обобщением понятия седловой точки. Пусть платежные функции стратегии игры
Интуитивный смысл точки равновесия таков: это такой способ игры, что если все игроки, кроме одного, принимают его, то и оставшемуся игроку лучше всего тоже принять этот способ. В случае игры двух лиц с нулевой суммой точка равновесия есть то же самое, что и седловая точка матрицы для игры в нормальной форме. Действительно, предположим, что
Но поскольку игра имеет нулевую сумму, мы имеем:
поэтому из второго неравенства, написанного выше, мы заключаем, что
или
Отсюда мы получаем:
Это значит, что точка
Рис 26. Итак, чтобы показать, что всякая игра двух лиц с нулевой суммой и полной информацией имеет седловую точку, достаточно показать, что всякая игра двух лиц с полной информацией имеет точку равновесия; это мы сейчас и сделаем. Чтобы провести наше доказательство, удобно ввести цоцятие усечения игры с полной информацией. Мы под разумеваем под этим игру, которая получается из данной исключением первого хода. Так, предположим, что игра имеет диаграмму, показанную на рис. 26, и платежная функция для
Рис. 27.
Рис. 28. Тогда имеются три усечения этой игры, соответствующие трем альтернативам при первом ходе. Их диаграммы приведены на рис. 27, 28, 29. Платежные функции для этих усеченных игр суть лервоначальные платежные функции, но их области определения соответственно ограничены. Так, платежная функция для (Нужно заметить, что такой способ образования усеченных игр возможен потому, что игра является игрой с полной информацией. Если бы мы попытались определить усечения для такой игры, как, например, игра, изображенная на рис. 23, то перед нами возникла бы задача разделить каким-нибудь образом информационные множества
Рис. 29. Поскольку стратегия игрока в игре с полной информацией есть функция, определяющая некоторую альтернативу при каждом ходе игрока, мы можем также рассматривать усечения данной стратегии, соответствующие усечениям данной игры, усечение стратегии определяется только в точках разветвления соответствующего усечения игры и выбирает те же альтернативы в точках разветвления, что и первоначальная стратегия. Теорема 6.1. Пусть Доказательство. Мы докажем теорему индукцией по длине игры, то есть по числу точек разветвления в самой длинной возможной партии игры. Для игр длиною 0 (то есть для игр, не имеющих ходов) теорема очевидна. Действительно, в этом случае каждый из игроков имеет только одну стратегию, которая состоит в том, чтобы ничего не делать, и, следовательно, декартово произведение А содержит лишь один элемент, который по определению является точкой равновесия. Мы предполагаем, что теорема справедлива для всех игр длины меньше к; пусть Г — игра длиной к. Предположим, что для первого хода имеются Пусть для каждой из игр Г. По условию индукции, имеется точка равновесия в каждом из множеств
для Мы будем различать три случая: 1) первый ход игры Г случайный, 2) первый ход игры Г делает Случай 1. Если q есть точка разветвления одной из усеченных игр
Аналогично, если q есть точка разветвления одной из усеченных игр
Поскольку первый ход выбирает случай (то есть ни Аналогично, g есть элемент множества Пусть альтернативам при первом ходе назначены вероятности Пусть
В частности, поскольку стратегии
и
Из неравенств (1), с учетом неотрицательности всех
Подставляя (2) и (3) в (4), получаем:
так что пара Случай 2. В этом случае первый ход
конечно и, следовательно, имеет максимум. Пусть целое число
Определим функцию
а если
Мы определяем функцию g точно так же, как в первом случае, то есть если q — точка одной из усеченных игр
Очевидно,
и
Из равенств (7) и (8), поскольку g? есть усечение стратегии g для игры
и
Итак, если g есть любая стратегия игрока
Пусть теперь f - любая стратегия игрока
Пусть
в частности,
Из равенства (5) мы имеем:
Из (9), (13), первого неравенства (1) и из (12) мы заключаем, что
Из (11) и (14) мы видим, что Случай 3 аналогичен случаю 2. Теорема доказана. Следствие 6.2. Матрица любой игры в нормальной форме двух лиц с нулевой суммой и полной информацией имеет седловую точку. Доказательство следует из теоремы 6.1, поскольку, как было указано выше, точка равновесия игры двух лиц с нулевой суммой является седловой точкой. Замечание 6.3. Теорему 6.1 можно столь же легко доказать для игр n лиц, но обозначения будут несколько сложнее. Это расширение теоремы мы оставляем в качестве упражнения. Мы определили точки равновесия только среди множеств чистых стратегий. Однако можно, очевидно, определить точки равновесия также среди смешанных стратегий. Действительно, можно доказать, что всякая игра n лиц имеет точку равновесия в множестве смешанных стратегий. Этому факту большое значение придают те, кто лелеет надежду построить всю теорию рационального способа игры в играх n лиц на понятии точки равновесия. Не принимая полностью эту точку зрения, мы можем, по крайней мере, сделать следующее замечание. Когда группа лиц часто и в течение долгого времени играет в некоторую игру, они иногда приобретают привычку выбирать точку равновесия. Если кто-нибудь играет в эту игру с членами данной группы, самое лучшее для него — самому выбрать точку равновесия. Таким образом, точка равновесия представляет, так сказать, принятую норму поведения для группы: нарушающий соглашение рискует проиграть, если ему не удастся убедить и других нарушить соглашение.
|
1 |
Оглавление
|