Бусыгин

621

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

Игра 2.

В игре участвуют пешеход и автомобилист. Каждый из игроков имеет две стратегии: проявлять осторожность (A) и не проявлять осторожности (B). От выбранных стратегий зависит вероятность дорожно-транспортного происшествия (автомобилист собьет пешехода). Если оба ведут себя неосторожно, то вероятность происшествия равна 1/2, если только один ведет себя неосторожно, то вероятность равна 1/10, а если оба осторожны, то вероятность равна 1/100.

В случае, если произойдет столкновение, то ущерб пешехода составит 1000 у.е.,235 а ущерб автомобилиста — 200 у.е. Кроме того, осторожное поведение на дороге связано для обоих игроков с издержками в 100 у.е.

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

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

Пусть оба участника игры проявляют осторожность, то есть реализовался исход (A, A). Если произойдет столкновение, то выигрыш пешехода составит (–1100), а выигрыш водителя — (–300). В противном случае выигрыш пешехода составит (–100), а выигрыш водителя — (–100). Ожидаемые выигрыши равны в этом случае:

1001 (–1100) + 10099 (–100) = –110 — для пешехода,

1001 (–300) + 10099 (–100) = –102 — для автомобилиста.

235условных единиц

236Здесь, как это обычно делается в экономической теории, предполагается, что определенные на лотереях предпочтения каждого игрока удовлетворяют условиям, которые гарантируют существование представляющей их линейной функции полезности (имеется в виду линейность по вероятностям). См. Дж. фон Нейман, О. Моргенштерн, "Теория игр и экономическое поведение", М.: Наука, 1970, П. Фишберн, "Теория игр для принятия решений". М.: Наука, 1978.

621

622

Аналогичные вычисления нужно провести для трех других исходов. Рассчитанные выигрыши представлены в Таблице 6.

Заметьте, что полученная нормальная форма игры не содержит информацию о случайных ходах природы, их вероятностях и соответствующих случайных выигрышах.

Концепция доминирования

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

Пусть в Игре 1 (стр. 619) выгода от совместимости программного обеспечения сравнительно мала, например, a = 2, b = 3, c = 1 (Таблица 7).

Тогда вне зависимости от того, какой компьютер выберет 2-й игрок, 1-му игроку выгодно выбрать компьютер IBM PC, поскольку 3 > 0 и 2 > 1. Аналогично, 2-й игрок предпочтет Макинтош, поскольку 3 > 1 и 4 > 0. В обоих случаях имеет место так называемое строгое доминирование двух указанных стратегий: если стратегия A при любых действиях других игроков дает больший выигрыш, чем стратегия B, то принято говорить, что стратегия A

строго доминирует стратегию B.

Дадим формальное определение строгого доминирования. Здесь и в дальнейшем мы будем применять обозначение x–i, что означает «все элементы вектора x, кроме i-го», т.е.

x–i = (x1, ..., xi–1, xi+1, xn).

При этом будем считать, что (xi, x–i).— это то же самое, что x.

Определение 1.

Стратегия xi Xi игрока i строго доминирует стратегию yi Xi, если при любых стратегиях, выбранных остальными игроками, x–i X–i, выполнено

ui(xi, x–i) > ui(yi, x–i),

где X–i = ×Xj.

j ≠i

622

623

Стратегия xi Xi игрока i является его строго доминирующей стратегией, если при любых стратегиях, выбранных остальными игроками, x–i X–i, она дает игроку i больший выигрыш, чем любая другая его стратегия yi Xi, т.е.

ui(xi, x–i) > ui(yi, x–i) x–i X–i yi Xi: yi ≠ xi.

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

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

Определение 3.

Стратегия xi Xi игрока i (слабо) доминирует стратегию yi Xi (или, другими словами, стратегия yi доминируется стратегией xi), если при любых стратегиях, выбранных остальными игроками, x–i X–i, выполнено

ui(xi, x–i) > ui(yi, x–i),

и существует хотя бы один набор стратегий других игроков, x–′i X–i, такой что ui(xi, x–′i) > ui(yi, x–′i).

623

Определение 4.

Стратегия xi Xi игрока i является его (слабо) до-

минирующей стратегией, если при любых страте-

гиях, выбранных остальными игроками, x–i X–i, она доминирует любую другую его стратегию, yi Xi, либо эквивалентна ей, т.е.

ui(xi, x–i) > ui(yi, x–i) x–i X–i yi Xi.

Из определения следует, что если стратегия xi строго доминирует стратегию yi, то стратегия xi доминирует стратегию yi. Кроме того, если стратегия является строго домини-

рующей, то она является доминирующей.

Определение 5.

Исход игры x* X является равновесием в доминирующих стратегиях, если стратегия каждого игрока в этом исходе является его доминирующей стратегией.

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

Игра 3. «Парламентское голосование»

Парламент разделен на 3 фракции: «белые», «зеленые» и «красные». В каждой фракции одинаковое количество членов. Проходит голосование по некоторому законопроекту. Каждая из фракций может проголосовать «за» или «против». Решение принимается большинством голосов. Зеленым и красным нравится законопроект, белым — нет. Если законопроект пройдет, то зеленые и красные получат выигрыш 1, а белые — –1, в противном случае все получат 0.

624

Удобно представить исходы игры в виде двух таблиц А и Б (см. Таблицу 8). Белые выбирают между таблицей А и таблицей Б. Их выигрыши записаны в левом верхнем углу этих таблиц.

Если зеленые проголосуют за, то вектор их выигрышей будет (1 (за, за), 1 (за, против), 1 (против, за), 0 (против, против)).

В скобках указано, как голосуют другие фракции. Если же они проголосуют против, то вектор выигрышей будет

(1 (за, за), 0 (за, против), 0 (против, за), 0 (против, против)).

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

Белые имеют следующие выигрыши (при аналогичных предположениях о том как голосуют другие фракции):

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

Тем самым, в этой игре существует равновесие в доминирующих стратегиях. В нем зеленые и красные голосуют «за», а белые — «против».

Приведем теперь пример игры с непрерывными стратегиями, в который есть равновесие в доминирующих стратегиях.

Игра 4. «Аукцион Ви′кри».237

Некий предмет продается с аукциона по следующим правилам. Каждый из участников аукциона (i = 1, ..., n) подает в тайне от других свою заявку — предлагаемую им цену pi. Побеждает участник, предложивший самую высокую цену, но платит он следующую по порядку убывания цену. Если самую высокую цену предложат сразу несколько участников, то победитель определяется жребием. Если i-й участник окажется победителем, то

237 W. Vickrey (1961), "Counterspeculation, Auctions, and Competitive Sealed Tenders", Journal of Finance, 16, 8- 37. Уильям Викри стал Нобелевским лауреатом по экономике за 1996г.

625

626

его выигрыш составит vi – p, где vi — ценность для него данного предмета, p — цена, которую он должен заплатить; выигрыш всех остальных участников будет равен нулю.

Особенность аукциона Викри состоит в том, что «правдивая» стратегия является доминирующей стратегией для каждого участника. Под «правдивой» стратегией понимается стратегия, заключающаяся в том, что участник называет цену, совпадающую с ценностью для него данного предмета, (pi = vi). Проверим это. Проанализируем данную игру при n = 2. (При большем количестве участников рассуждения будут аналогичными). Поскольку участники входят в данную игру симметрично, то достаточно рассмотреть мотивацию только одного из них, например, 1-го.

Вычислим сначала выигрыши 1-го игрока при разных исходах. Если 1-й участник назовет более высокую цену, чем 2-й (p1 > p2), то он выиграет аукцион и заплатит p2. При этом его выигрыш составит v1 – p2. Если 1-й участник назовет более низкую цену, чем 2-й (p1 < p2), то он проиграет аукцион и получит выигрыш 0. Если цены совпадут (p1 = p2), то с вероятностью 1/2 1-й участник выиграет и получит выигрыш v1 – p2, а с вероятностью 1/2 он проиграет и получит выигрыш 0. Таким образом, его ожидаемый выигрыш составит (v1 – p2)/2. Окончательно запишем функцию выигрыша 1-го участника:

Чтобы показать, что «правдивая» стратегия, p1 = v1, является доминирующей, нужно показать, что она дает не меньший выигрыш, чем любая другая стратегия. Следует рассмотреть 3 случая: p2 > v1, p2 = v1 и p2 < v1.

[p2 > v1] Если 2-й участник назовет цену, превышающую vi, то 1-му участнику не выгодно выигрывать аукцион; его выигрыш (полезность) в этом случае был бы отрицательный, а в случае проигрыша он получит 0. Поскольку в рассматриваемом случае при выборе «правдивой» стратегии 1-й участник проиграет аукцион, то «правдивая» стратегия является одной из оптимальных.

[p2 = v1] Если 2-й участник назовет цену, совпадающую с vi, то 1-й участник при любом выборе получит 0. Значит, «правдивая» стратегия даст ему выигрыш не меньший, чем любая другая.

[p2 < v1] Если 2-й участник назовет цену, меньшую vi, то для 1-го участника выгодно выиграть аукцион, поскольку в этом случае его выигрыш будет положительным. «Правдивая» стратегия обеспечивает ему победу на аукционе, и приносит максимальный выигрыш, v1 – p2.

Мы видим, что «правдивая» стратегия в самом деле является доминирующей для 1-го участника. Более того, как несложно увидеть, это единственная доминирующая стратегия. Если он назовет цену ниже или выше своей оценки v1, то можно подобрать такую цену 2- го участника, что 1-й участник потеряет по сравнению с p1 = v1.

Проведя аналогичные рассуждения для 2-го участника, мы сделаем вывод, что в этой игре существует (единственное) равновесие в доминирующих стратегиях:

626

627

Последовательное отбрасывание строго доминируемых стратегий

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

Рассмотрим в Игре 1 случай, когда a < c < b. Пусть, к примеру, a = 1, c = 2, b = 3.

Если 2-й игрок выберет IBM, то 1-му игроку тоже выгодно выбрать IBM. Если же 2-й игрок выберет Макинтош, то 1-му игроку будет выгодно выбрать Макинтош. Эти оптимальные решения выделены в Таблице 9 подчеркиванием соответствующих выигрышей. Здесь оптимальное для 1-го игрока решение будет зависеть от того, какое решение примет 2-й игрок.

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

«Рациональный игрок не станет выбирать строго доминируемую стратегию».

Определение 6.

Стратегия yi Xi игрока i называется строго доминируемой, если существует стратегия xi Xi, которая ее строго доминирует, т.е.

ui(yi, x–i) < ui(xi, x–i) x–i X–i.

Проанализируем ситуацию, в которой структура игры (множества стратегий и функции выигрышей), а также то, что все игроки рациональны, известно каждому игроку. Более того, мы рассмотрим ситуацию, в которой все это общеизвестно,238 то есть не только каждый игрок знает это, но он знает, что все другие игроки знают это, и так далее до бесконечности.

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

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

238 англ. common knowledge

627

628

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

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

В Таблице 10 и таблицах на Рис. 151 показан пример процесса отбрасывания строго доминируемых стратегий. В исходной игре 3×3 (Таблица 10) стратегия II строго доминирует стратегию III, поэтому стратегию III следует вычеркнуть (игрок выбирающий строки, не станет выбирать эту стратегию). Отбрасываемая стратегия обведена двойной волнистой рамкой. Остается игра 2×3 (Рис. 151 а) ), в которой стратегия A строго доминирует стратегию C. Стратегию C вычеркиваем (поскольку игрок, выбирающий столбцы, прогнозируя действия игрока, выбирающего строки, не станет ее выбирать). В получившейся игре 2×2 (Рис. 151 б) ) стратегия I строго доминирует стратегию II. В получившейся после отбрасывания стратегии II игре (Рис. 151 в) ) у игрока, выбирающего строки, осталась только одна стратегия. Для игрока, выбирающего столбцы, стратегия A строго лучше стратегии B, поэтому стратегия B вычеркивается. Остается игра (Рис. 151 г) ), в которой каждый игрок имеет только по одной стратегии: (I, A). На основании этого можно сделать вывод, что в исходной игре 3×3 должен реализоваться исход (I, A).

Рисунок 151.

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

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

628

629

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

Ситуации, когда в игре существует равновесие в доминирующих стратегиях, достаточно редки. И далеко не во всех играх можно найти решение, отбрасывая строго доминируемые стратегии. Соответствующий пример игры представлен в Таблице 11.

Равновесие по Нэшу

Кроме ситуаций, рассмотренных в предыдущем разделе, бывают ситуации,240 которые естественно моделировать, исходя из следующих предположений:

-игроки при принятии решений ориентируются на предполагаемые действия партнеров;

-ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями).

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

Формально равновесие Нэша определяется следующим образом.

Определение 7.

Набор стратегий x* X является равновесием Нэша,241 если:

1) стратегия x*i каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков xe–i:

240Можно представить себе популяцию игроков типа А (скажем, кошки) и игроков типа Б (скажем, мышки). Игрок типа А при встрече с игроком типа Б имеет оправданные своим или чужим опытом ожидания относительно поведения партнера типа Б, и заранее на них ориентируется (и наоборот). Однако это не единственный тип ситуаций, в которых рассматриваемый подход является адекватным.

241Американский математик Джон Нэш получил Нобелевскую премию по экономике в 1994 г. вместе с Дж. Харшаньи и Р. Зельтеном «за новаторский анализ равновесий в теории некооперативных игр». Концепция равновесия была предложена в следующих статьях: Nash, J. F. (1950) "Equilibrium Points in N-Person Games,"

Proceedings of the National Academy of Sciences of the United States of America, 36, 48-49. Nash, J. F. (1951) "Non-Cooperative Games," Annals of Mathematics, 54, 286-295.

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

629

630

ui(x*i, xe–i) = max ui(xi, xe–i) i = 1, ..., n;

xi Xi

2) ожидания совпадают с фактически выбираемыми стратегиями: xe–i = x–*i i = 1, ..., n.

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

Но если при анализе равновесия Нэша не важно, знает ли игрок цели других игроков, то может возникнуть сомнение в правомерности рассмотрения концепции Нэша в контексте игр с полной информацией. Все дело в том, что термин «полная информация» в теории игр имеет довольно узкое значение. Он фактически подразумевает только полноту сведений о типах партнеров (термин «тип игрока», разъясняется в параграфе, посвященном байесовским играм).

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

Набор стратегий x* X является равновесием Нэша, если стратегия x*i каждого игрока является наилучшим для него откликом на стратегии других игроков x–*i:

ui(x*i, x–*i) = max ui(xi, x–*i) i = 1, ..., n.

xi Xi

Это свойство можно также записать в терминах так называемых функций (отображений) отклика.

Определение 8.

Отображение отклика i-го игрока,

Ri: X–i & Xi,

сопоставляет каждому набору стратегий других игроков, x–i X–i, множество стратегий i-го игрока, каждая из которых является наилучшим откликом на x–i. Другими словами,

ui(yi, x–i) = max ui(xi, x–i) x–i X–i , yi Ri(x–i).

xi Xi

Введение отображений отклика позволяет записать определение равновесия Нэша более компактно: набор стратегий x* X является равновесием Нэша, если

x*i Ri(x–*i) i = 1, ..., n.

Если отклик каждого игрока однозначен (является функцией), то множество равновесий Нэша совпадает с множеством решений системы уравнений:

x*i = Ri(x–*i) i = 1, ..., n.

630