ТЕОРИЯ ИГР
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
Чем занимается теория игр
Что такое теория игр?
Это — математическая теория конфликтов.
А что такое конфликт?
Это — такая ситуация (положение, стечение обстоятельств), в которой сталкиваются интересы сторон, происходит борьба интересов. Каждый из участников хочет чего-то своего, не того, чего хотят другие.
Самые простые примеры конфликтов — это игры (шашки, шахматы, различные спортивные игры). Они отличаются тем, что ведутся по определенным правилам. Правила игры — это система условий, указывающих, какие возможности предоставляются игрокам (перечень возможных ходов); к какому результату (выигрышу, проигрышу) приводит каждая данная совокупность ходов.
Далеко не каждый встречающийся на практике конфликт протекает по правилам. Чтобы сделать возможным математический анализ конфликта, нужно представить конфликт в игровой форме, т. е. указать стратегии (образы действий), возможные для участников, и уточнить, к какому результату приведет игра, если каждый из игроков выберет определенную стратегию. Таким образом, игра есть конфликт с четко сформулированными условиями.
Часто бывает так, что результат конфликта — даже при вполне определенных стратегиях участников — предсказать в точности нельзя, так как он зависит от случая. Такими случайными обстоятельствами, вмешивающимися в ход игры, могут быть, например, тасовка и сдача карт, попадание или непопадание в цель при стрельбе и т. п. Тогда вместо
«результата игры» нужно говорить о среднем результате, т. е. о результате, приходящемся в среднем на одну партию игры, если будет сыграно достаточно большое количество партий. Действительно, в одной партии может случайно «повезти» и игроку, применяющему явно неразумную стратегию. Если же партий будет много, то в среднем выигрывает тот, кто ведет себя разумно.
Мы будем предполагать, что в любом конфликте выигрыш (проигрыш) каждого из игроков выражается числом. Тогда основную задачу теории игр можно сформулировать так: как должен вести себя (какую, стратегию применять) разумный игрок в конфликте с разумным противником (или противниками), чтобы обеспечить себе в среднем наибольший возможный выигрыш?
Парная игра с нулевой суммой. Цена игры
Если в конфликте участвуют две стороны, игра называется парной, если несколько— множественной. Парные игры проще множественных и имеют большее практическое значение. Мы ограничимся только парными играми.
Каждую игру будем рассматривать как конфликт между двумя игроками: К («красные») и С («синие»). Для удобства рассуждений, чтобы иметь какую-то определенную точку зрения, будем обычно становиться на сторону одного из игроков (пусть это будет К) и говорить о нем «мы», а о другом — «противник». Это не означает, что сторона К будет иметь какое-нибудь реальное преимущество. Просто нам так будет удобнее.
Игра называется игрой с нулевой суммой, если одна сторона выигрывает то, что проигрывает другая, т. е. сумма выигрышей К и С равна нулю. В жизни часто встречаются конфликты, в которых это условие не соблюдается. Например, в военном столкновении вполне возможно, что проигрывают обе стороны. Однако во многих случаях можно, не слишком искажая сущность явления, рассматривать парные конфликты как игры с нулевой суммой.
Итак, допустим, что интересы К и С строго противоположны и что сумма выигрышей их равна нулю. Это будет для нас очень удобно в вычислительном смысле. Еще бы! Ведь если выигрыш К равен по величине и противоположен по знаку выигрышу С, то можно рассматривать выигрыш только одного из игроков: выигрыш другого определится автоматически.
Давайте выберем в качестве выигрывающего игрока К. Игрок К заинтересован в том, чтобы обратить свой выигрыш (обозначим его k) в максимум (сделать его наибольшим). Игрок С, наоборот, заинтересован в том, чтобы обратить его в минимум (сделать наименьшим). Каждый из игроков К и C, преследуя свою цель, принимает все меры к тому, чтобы ему было лучше, а сопернику — хуже.
В результате борьбы интересов, если оба противника одинаково разумны, по-видимому, должно быть найдено некоторое равновесное положение, при котором каждый игрок получит то, что ему причитается,— не больше и не меньше. Этот равновесный средний выигрыш, на который вправе рассчитывать игрок К, если обе стороны будут вести себя разумно, т. е. придерживаться своих оптимальных (наилучших) стратегий, называется ценой игры.
Если цена игры равна нулю, значит, это справедливая игра, т. е. она в одинаковой мере выгодна или невыгодна той и другой стороне. Если цена игры положительна, значит, игра выгодна для К. Если отрицательна, придется признать, что она выгодна для С...
Решить игру — это значит найти пару оптимальных стратегий (для К и С) и
цену игры, т. е. средний выигрыш игрока К, если оба — и К и С — будут вести себя разумно.
А если разумно будет вести себя только К, а не С? Ну что же — тем хуже для С! Выигрыш К от этого уменьшиться не может. В худшем случае он останется таким же, а в лучшем — увеличится.
Игра в нормальной форме. Матрица игры
Мы будем рассматривать только конечные игры, т. е. такие, в которых каждый участник располагает конечным числом стратегий.
Если у игрока К имеется в распоряжении т стратегий, а у игрока С имеется n стратегий, игра называется игрой т X п.
Правила игры можно записать в виде таблицы
(или матрицы), в которой m строк и n столбцов. Строки соответствуют стратегиям «красных», которые мы обозначим: K1, К2, ..., Кm, а столбцы — стратегиям «синих»: C1,C2 ...Cn.
В клетках таблицы помещены выигрыши (или средние выигрыши) «красных» при соответствующей паре стратегий. Например, k12 — выигрыш, который получат «красные», если выберут стратегию К1, а «синие» — C2; вообще, kij — выигрыш «красных» при комбинации стратегий Кi и Cj.
Такая таблица называется платежной матрицей или просто матрицей игры.
Если конечная игра записана в виде такой матрицы, то говорят, что она приведена к нормальной форме. Но попробуйте, например, записать в нормальной форме обыкновенные шахматы! Вы сразу столкнетесь с тем, что количество возможных стратегий необозримо велико — настолько велико, что их перечисление выходит за пределы возможностей не только человека, но и современной вычислительной машины. А жаль! Потому что, если бы построение матрицы шахматной игры было возможно, это имело бы очень любопытные последствия... Но не будем забегать вперед.
Примеры конечных игр. Принцип минимакса
Приведем несколько примеров конечных игр. Каждую из них мы запишем в нормальной форме.
Пример 1. Рассматривается игра, которую назовем «Поиск». В ней участвуют две стороны: К и С. К хочет найти С; С, наоборот, хочет спрятаться от К.
У С есть два места — убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок К по правилам игры тоже может искать С, где ему вздумается. Если он нашел С, С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался Г, то, наоборот, К проиграл одно очко. Требуется записать игру в нормальной форме.
Решение. У К — две стратегии:
К1— искать в убежище I,
К2— искать в убежище II.
У С — тоже две стратегии:
С1 — прятаться в убежище I,
С2 — прятаться в убежище II. Игра конечная — 2x2, матрица игры будет:
К этой игре мы еще вернемся в дальнейшем и найдем ее решение. А пока что просто порассуждаем за игрока К. Представим себе, что мы игрок К и что нам предлагается выбрать себе стратегию. Что ж, попробуем! Выберем, например, K1, т. е. будем искать всегда в убежище I. Но тогда разумный противник через несколько партий догадается о нашей стратегии и будет прятаться там, где мы его не ищем,
т. е. в убежище II. Плохо! Выберем стратегию К2. Ничуть не лучше: противник снова догадается и будет прятаться в убежище I. Что же нам делать? Попробуем применять стратегии К1 и K2 попеременно, через одну партию игры. Но ведь противник и об этом может догадаться и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь — все клин! Что же, значит, наше положение безвыходно? При любом выборе стратегии нам придется проигрывать? Выходит, что так.
Давайте теперь встанем на точку зрения противника. С удивлением мы обнаружим, что его положение — ничуть не лучше нашего! Какую бы стратегию он ни выбрал — все ему невыгодно.
Позже мы с вами решим эту игру, т. е. найдем пару оптимальных стратегий К и С. Впрочем, о них можно по секрету сообщить заранее: каждому игроку надо будет чередовать свои стратегии, но не регулярно (через одну), а случайным образом (например, подбросить монету и, если она упадет гербом, искать в убежище I, а если цифрой — в убежище II). Аналогично должен будет действовать и С. При этом в среднем на одну партию будет приходиться нулевой выигрыш (цена этой игры будет равна нулю): К не будет ни выигрывать, ни проигрывать. Не очень приятно, но все-таки много лучше, чем всегда быть в проигрыше!
Здесь мы впервые столкнулись с одним из важных понятий теории игр — с понятием смешанной стратегии, т. е. чередования нескольких «чистых» стратегий по случайному закону в определенных пропорциях, или, как говорят, с определенными частотам и. В данном примере каждая из стратегий применяется с частотой 1/2.
Рассмотрим теперь другую игру, решение которой уже не будет столь очевидным.
Пример 2. Игра «Три пальца».
Два игрока К и С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если всего показанных пальцев (первым и вторым вместе) будет четное число, то выигрывает К: он получает столько очков, сколько всего было пальцев, если нечетное — выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.
Решение. Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:
Поразмыслим немного над стратегиями каждой стороны. Станем сначала на сторону К. Предположим, что мы выбрали стратегию К1. Что будет делать противник? Он разумен и хочет отдать поменьше. Ясно, он выберет стратегию C2; наш выигрыш при этом будет равен -3, т. е. мы потеряем 3 очка. Плоховато! Запишем число -3 против первой строки в добавочном столбце (см. матрицу (3).
Попробуем другую стратегию — К2. На нее разумный противник ответит С3. Мы тогда потеряем 5 очков. Еще хуже! Третья стратегия — К3 — дает точно тот же результат: выигрыш (-5).
Что же делать? Пожалуй, лучше других будет все-таки стратегия К1 — при ней мы по крайней мере не проиграем больше 3 очков! Ведь против этой стратегии стоит максимальное число дополнительного столбца — мы его отметили звездочкой.
Выбрав стратегию К1, мы гарантируем себе, что, как бы ни вел себя противник, мы никак не проиграем больше 3 очков (т. е. не выиграем меньше (-3) очков). Величина (-3) есть максимальный гарантированный выигрыш, который мы («красные») можем себе обеспечить, применяя только одну-единственную стратегию. Такой стратегией должна быть К1.
Как мы получили (-3)? Нашли минимум каждой строки и из этих минимумов взяли максимальный. Эта величина называется максимином или нижней ценой игры. Будем обозначать ее a.
Подумаем теперь за противника. Он тоже хочет отдать поменьше, а получить побольше. Но, какую бы он стратегию ни выбрал, мы («красные») поведем себя таким образом, чтобы получить с него побольше. Значит, противник («синие») должен в каждом столбце выписать не минимальное, а максимальное число (см. нижнюю добавочную строку в матрице (3).
Из этих максимумов он должен найти минимальный, так называемый минимакс или верхняя цена игры, которую мы обозначим b. Эта величина в нашем случае равна 4 и отмечена звездочкой. Чтобы не проиграть больше 4, «синие» должны придерживаться любой из своих двух стратегий С1, С2.
Значит, если каждому участнику предлагается выбрать одну-единственную стратегию, то эти стратегии должны быть: К1 для «красных» и С1 или C2 для «синих».
Как мы выбрали эти стратегии? Руководствуясь принципом осторожности, который говорит: в игре веди себя так, чтобы получить наибольшую выгоду при наихудших для тебя действиях противника. Этот принцип называется принципом минимакса и является в теории игр основным.
Применяя этот принцип, мы пока что рекомендовали игроку К показывать один палец, игроку С — показывать один или два пальца.
Но нашли ли мы решение игры, т. е. такую пару стратегий, которая является равновесным положением? Легко убедиться, что нет. Найденные нами стратегии обладают досадным свойством: они неустойчивы. Действительно, пусть оба игрока держатся рекомендованных чистых стратегий: К1 и, скажем, С1. Пока оба держатся этих стратегий, выигрыш будет равен 2, т. е. на каждую партию игры С проигрывает К два очка. К, может быть, и доволен, но С досадно. Он не хочет проигрывать. Допустим, он откуда-то узнал, что мы придерживаемся стратегии К1. Что он будет делать? Разумеется, немедленно перейдет к стратегии С2 и будет получать по 3 очка, т. е. сведет наш выигрыш к -3. А если мы теперь узнаем о поведении С? Перейдем на стратегию К2. В ответ на это С переидет на С3 и т. д.
Мы убедились, что пара стратегий, вытекающих из принципа минимакса, неустойчива: стоит одному игроку узнать, что делает другой, как равновесие нарушается...
Всегда ли это будет так? Оказывается, не всегда.
Седловая точка. Чистая цена игры
Рассмотрим пример. Пусть дана матрица игры (4):
Требуется найти нижнюю цену игры a, верхнюю цену игры b и минимаксные стратегии и проверить, являются ли они устойчивыми.
Решение. Из анализа дополнительных столбца и строки получаем: a = 5, b=5. Максимин равен минимаксу! Случай особый. Что же из этого следует?
Возьмем пару минимаксных стратегий: К2 и С3. Если оба держатся этих стратегий, то выигрыш будет равен 5. Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем держаться стратегии К2, потому что любое отступление от нее нам невыгодно. Знаем мы или не знаем о поведении противника — все равно будем держаться стратегии К2! То же относится и к «синим» — им нет смысла менять свою стратегию С3.
В данном примере пара стратегий К2 и С3 устойчива, т. е. представляет собой положение равновесия и дает решение игры.
Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой. Если матрица имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это — пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры — в нашем примере она равна 5.
Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности,
доказано, что если по правилам игры каждый из игроков знает результат всех предыдущих ходов, как своих, так и противника (так называемая игра с полной информацией), то игра имеет седловую точку и, значит, имеет решение в чистых стратегиях.
Примерами игр с полной информацией могут служить: шахматы, шашки, «крестики и нолики» и т. п.
Приведем пример игры с полной информацией, решение которой легко найти.
Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается).
Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, гарантирующая выигрыш тому из игроков, который кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относительно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет...
Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра имеет смысл только до тех пор, пока не найдено ее решение.
Теоретически доказано, что решение существует и исход шахматной игры в сущности предрешен: если каждая сторона будет пользоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стратегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку...
Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.
Заметим в заключение, что седловых точек в матрице может быть не одна, а несколько; тогда решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.
Решение игры в смешанных стратегиях. Основная теорема теории игр
Мы знаем, что если нижняя цена игры a равна верхней b (максимин равен минимаксу), то игра имеет седловую точку и по крайней мере одно решение в чистых стратегиях.
А если a¹b? Можно доказать, что и в этом случае решение всегда есть, только оно лежит не в области чистых, а в области смешанных стратегий. Решением игры называется такая пара стратегий — в общем случае смешанных, систематическое применение которых обеспечивает каждой стороне максимально возможный для нее по условиям игры выигрыш, определяемый ценой игры. Если же одна из сторон отступает от своей оптимальной стратегии (в то время как другая продолжает придерживаться своей), то это ни в коем случае не может быть выгодно для отступающего: это либо оставит его выигрыш неизменным, либо уменьшит. Таким образом, каждая конечная игра имеет решение (возможно, в области смешанных стратегий). Это положение называется основной теоремой теории игр.
Введем специальное обозначение для смешанных стратегий. Пусть К применяет свои стратегии К1, К2, К3 с частотами соответственно р1, р2, р3 (p1+p2+p3=1). Эту смешанную стратегию будем обозначать:
Аналогично смешанную стратегию игрока Г будем обозначать:
Очевидно, любая чистая стратегия — частный случай смешанной, в которой все частоты, кроме одной, равны нулю, а одна — единице.
Решение игры — пару оптимальных стратегий — будем обозначать S*k и S*c , а соответствующий ему выигрыш (цену игры) v.
Очевидно, что цена игры v не может быть меньше нижней и больше верхней цены:
a£v£b.
В первом примере мы путем нестрогих соображений догадались, что решение игры должно быть:
а цена игры v = 0. Проверим это. Пусть мы («красные») держимся своей стратегии S*k, т. е. ищем С в убежище I и II одинаково часто, чередуя эти стратегии случайным образом. Может ли С улучшить свое положение (повысить свой выигрыш), отступая любым образом от своей стратегии S*с? Очевидно, нет. А если одностороннее отступление от стратегии S*k придет в голову нам (в то время как разумный С будет держаться стратегии S*c), то это нам тоже не может быть выгодно. Значит, мы и в самом деле нашли решение игры и ее цену v = 0. Правда, эта игра была довольно простой! Уже второй пример дает игру, решение которой не так очевидно. Из того, что в нем a¹b, следует только, что решение нужно искать в смешанных стратегиях.
Но каково это решение? Какова цена игры? Выгодна ли игра «красным», или «синим», или никому из них?
Ответы на эти вопросы вы можете найти в книге, указанной на стр. 509.
Решения и ответы
Решение к стр. 386. Введем обозначения: а — Саша, b — Костя, с — не Саша, d —18 лет, е — 21 год и f — 25 лет.
Мама сказала: «a•е», папа сказал: «b•d», а дочь сказала: «с•f». Так как часть каждой информации неверна (имеет значение 0), то a•e=b•d=c•f=0 и а+е=1, b+d=l, c+f=l. Сын Николая Ивановича не может иметь сразу два имени и два возраста; следовательно, а•b=a•с=d•e=d•e=e•f=0.
Перемножим суммы a+е=1 и b+d=l, тогда a•b+a•d+b•e+e•d=1; после выбрасывания нулевых членов останется равенство: a•d+b•e=1. Перемножим эту сумму и сумму с+f=1,что после выбрасывания нулевых членов даст равенство b•с•е=1, откуда следует, что b=1, с=1 и е=1 (верная информация). Значит, сына Николая Ивановича зовут не Саша (с=1), а Костя (b=1) и возраст его 21 год (е=1).
Решение к стр. 461. Пусть число рыб в озере, годных для улова данной сетью, равно х. Тогда отношение числа меченых рыб к числу всех рыб равно
38/x.
Во второй раз рыбовод выловил 53 рыбы, из них две меченые. Следовательно, отношение числа меченых рыб к числу выловленных равно 2/53.
Будем предполагать, что меченые рыбы равномерно распределились среди всех рыб в водоеме, тогда оба отношения одинаковы: 38/x=2/53, откуда
x=1007.
Значит, в озере имеется примерно тысяча рыб, годных для улова данной сетью.