34. Grossman G., Shapiro C. Research Joint Ventures: An Antitrust Analysis // Journ. Law, Econ., a. Organization. 1986. Vol. 2. P. 315-337.
35. Grossman G., Shapiro C. Dynamic R&D Competition // Econ. Journ. 1987. Vol. 97. P. 372-387.
36. Guesnerie R., Tirole J. L'Economie de la Recherche-Developpement: Introduction a Certains Travaux Theoriques // Rev. Econ. 1985. Vol. 36. P. 843-870.
37. McDowell J. The Determinants of Technology Adoption: The Case of Banking Firm // Rand Journ. Econ. 1984. Vol. 15. P. 328-335.
38. Harris C., Vickers J. Perfect Equilibrium in a Model of a Race // Rev. Econ. Stud. 1985. Vol. 52. P. 193-209.
39. Harris C., Vickers J. Racing with Uncertainty // Ibid. 1987. Vol. 54. P. 1-22.
40. Holmstrom B. Moral Hazard in Teams // Bell Journ. Econ. 1982. Vol. 13. P. 324-340.
41. Holmstrom B. Managerial Incentive Problems – A Dynamic Perspective // Essays in Economics and Management in Honor of Lars Wahlbeck. Helsinki : Swedish School of Economics, 1983.
42. Holmstrom В., Ricart i Costa J. Managerial Incentives and Capital Management // Quart. Journ. Econ. 1986. Vol. 101. P. 835-860.
43. Judd K. Closed-Loop Equilibrium in a Multi-Stage Innovation Race // Discussion Paper 647. Kellogg Graduate School of Management. North-western Univ., 1985.
44. Kamien M., Schwartz N. Market Structure and Innovation. Cambridge Univ. Press, 1982.
45. Kamien M., Tauman Y. The Private Value of a Patent: A Game Theoretic Analysis // Discussion Paper 576. Northwestern Univ., 1983.
46. Katz M., Shapiro C. Perfect Equilibrium in a Development Game with Licensing or Imitation // Discussion Paper 85. Woodrow Wilson School. Princeton Univ., 1984.
47. Katz M., Shapiro work Externalities, Competition, and Compatibility // Amer. Econ. Rev. 1985. Vol. 75. P. 424-440.
48. Katz M., Shapiro C. On the Licensing of Innovations // Rand Journ. Econ. 1985. Vol. 16. P. 504-520.
49. Katz M., Shapiro C. How to License Intangible Property // Quart. Journ. Econ. 1986. Vol. 101. P. 567-590.
50. Katz M., Shapiro C. Product Compatibility Choice in a Market with Technological Progress // Oxford Econ. Papers. 1986. Vol. 38. P. 146-165.
51. Katz M., Shapiro C. Technology Adoption in the Presence of Network Externalities // Journ. Polit. Econ. 1986. Vol. 94. P. 822-841.
52. Klette Т., Meza D. de. Is the Market Biased against R&D? // Rand Journ. Econ. 1986. Vol. 17. P. 133-139.
53. Lambert R. Executive Effort and the Selection of Risky Projects // Ibid. P. 77-88.
54. Lee Т., Wilde L. Market Structure and Innovation: A Reformulation // Quart. Journ. Econ. 1980. Vol. 194. P. 429-436.
55. Lippman S., McCardle K. Dropout Behavior in R&D Races with Learning // Rand Journ. Econ. 1987. Vol. 18. P. 287-295.
56. Loury G. C. Market Structure and Innovation // Quart. Journ. Econ. 1979. Vol. 93. P. 395-410.
57. Mansfield E. Industrial Research and Technological Innovation – An Econometric Analysis. New York : Norton, 1968.
58. Mansfield E., Schwartz M., Wanger S. Imitation Costs and Patents: An Empirical Study // Econ. Journ. 1981. Vol. 91. P. 907-918.
59. Nelson R. The Simple Economics of Basic Research // Journ. Polit. Econ. 1959. Vol. 67. P. 297-306.
60. Nelson R., Winter S. An Evolutionary Theory of Economic Change. Cambridge, Mass. : Harvard Univ. Press, 1982.
61. Nordhaus W. Invention. Growth. and Welfare. Cambridge, Mass. : MIT Press, 1969.
62. Ordover J., Willig R. An Economic Definition of Predation: Pricing and Product Innovation // Yale Law Journ. 1981. Vol. 91. P. 8-53.
63. Ordover J., Willig R. Antitrust for High-Technology Industries: Assessing Research Joint Ventures and Mergers // Journ. Law a. Economics. 1985. Vol. 28. P. 311-333.
64. Oster S. The Diffusion of Innovation among Steel Firms: The Basic Oxygen Furnace // Bell Journ. Econ. 1982. Vol. 13. P. 45-56.
65. Pakes A. Patents as Options: Some Estimates of the Value of Holding European Patent Stocks // Econometrica. 1986. Vol. 54. P. 755-784.
66. Ponssard J.-P. Marches Publics et Innovation: Concurrence ou Regulation? // Rev. Econ. 1981. Vol. 32. P. 163-179.
67. Postrel S. Bandwagons and the Coordination of Standardized Behavior. Mass. Inst. of Tecnology, 1986. (Mimeo).
68. Quirmbach H. The Diffusion of New Technology and the Market for an Innovation // Rand Journ. Econ. 1986. Vol. 17. P. 33-47.
69. Reinganum J. Dynamic Games with R&D Rivalry: Ph. D. dissertation. Northwestern Univ., 1979.
70. Reinganum J. Market Structure and the Diffusion of New Technology // Bell Journ. Econ. 1981. Vol. 12. P. 618-624.
71. Reinganum J. On the Diffusion of a New Technology: A Game-Theoretic Approach // Rev. Econ. Stud. 1981. Vol. 48. P. 395-405.
72. Reinganum J. A Dynamic Game of R&D: Patent Protection and Competitive Behavior // Econometrica. 1982. Vol. 50. P. 671-688.
73. Reinganum J. Technology Adoption under Imperfect Information // Bell Journ. Econ. 1983. Vol. 14. P. 57-69.
74. Reinganum J. Uncertain Innovation and the Persistence of Monopoly // Amer. Econ. Rev. 1983. Vol. 73. P. 741-748.
75. Reinganum J. Practical Implications of Game Theoretic Models of R&D // Amer. Econ. Rev. Papers a. Proc. 1984. Vol. 74. P. 61-66.
76. Reinganum J. Innovation and Industry Evolution // Quart. Journ. Econ. 1985. Vol. 100. P. 81-100.
77. Roberts K., Weitzman M. Funding Criteria for Research, Development, and Exploration Projects // Econometrica. 1981. Vol. 49. P. .
78. Rohlfs J. A Theory of Interdependent Demand for a Communication Service // Bell Journ. Econ. 1974. Vol. 5. P. 16-37.
79. Rothschild M., Stiglitz J. Increasing Risk I: A Definition // Journ. Econ. Theory. 1970. Vol. 2. P. 225-243.
80. Salant S. Preemptive Patenting and the Persistence of Monopoly: Comment // Amer. Econ. Rev. 1984. Vol. 74. P. 247-250.
81. Scherer F. Research and Development Resource Allocation under Rivalry // Quart. Journ. Econ. 1967. Vol. 131. P. 359-394.
82. Scherer F. Industrial Market Structure and Economic Performance. 2nd ed. Chicago : Rand–McNally, 1980 (русский перевод: , Структура отраслевых рынков. М. : Инфра-М, 1997. – Прим. ред.).
83. Schumpeter J. Capitalism, Socialism and Democracy. London : Unwin Univ. Books, 1943 (русский перевод: Капитализм, социализм и демократия. М., 1995. – Прим. ред.).
84. Shepard A. Licensing to Enhance Demand for New Technologies. Yale Univ., 1986. (Mimeo).
85. Solow R. Technical Change and the Aggregate Production Function // Rev. Econ. a. Statist. 1957. Vol. 39. P. 312-320.
86. Spence M. Cost Reduction, Competition and Industry Performance // Econometrica. 1984. Vol. 52. P. 101-122.
87. Tauman Y., Weiss Y. Shelving and Licensing of Innovations. Tel-Aviv Univ., 1986. (Mimeo).
88. Taylor C., Silberston Z. Economic Impact of Patents. Cambridge Univ. Press, 1973.
89. Vaughan F. The United States Patent System. Norman : Univ. of Oklahoma Press, 1956.
90. Weitzman M. Optimal Search for the Best Alternative // Econometrica. 1979. Vol. 47. P. 641-654.
91. White L. The Automobile Industry Since 1945. Cambridge, Mass. : Harvard Univ. Press, 1971.
Глава 11. ТЕОРИЯ БЕСКОАЛИЦИОННЫХ ИГР: РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
Теория бескоалиционных игр стала важным инструментом анализа стратегического взаимодействия между игроками и имеет много приложений в области организации промышленности. Эта глава предназначена для рассмотрения тех аспектов теории, которые оказались наиболее полезными в организации промышленности, и ознакомления читателя с их применениями. Она поможет читателю освоить некий набор понятий теории игр, к которому он сможет прибегнуть при изучении организации промышленности. Этот набор будет состоять из четырех основных концепций, начиная с понятия равнове-сил по Нэшу для статических игр с полной информацией и его естественных распространений на динамические игры с полной информацией, статические и динамические игры с неполной информацией.
Анализ преднамеренно неформален и не претендует на полный обзор. В нем широко используются материалы [26] (а в части, посвященной динамическим играм с несовершенной информацией, также [66]). Серьезно изучающим теорию игр студентам настоятельно рекомендуем изучать более специальную литературу.* **
* Из отечественной учебной литературы последних лет можно рекомендовать: , , Семина игр. М. : Высшая школа, 1998. – Прим. ред.
** Более формальные рассуждения см. в [19, 37, 39, 41, 52]. В [49] содержится богатый выбор упражнений.
11.1. Игры и стратегии
Существуют два способа формализации игры. Один заключается в описании развернутой формы, которая определяет порядок игры, информацию и выборы, доступные игроку при наступлении его очереди делать ход, выигрыши игроков (зависящие от выборов всех игроков) и (возможно) распределение вероятностей ходов «природы».* «Дерево» игры (некоторое упорядочение «узлов») изображает эту развернутую форму. Дерево, представленное на рис. 11.1, отображает следующую игру двух лиц. В момент t = 1 только игрок 1 принимает решение. У него две альтернативы, названные «левая» (L) и «правая» (R). В «момент t = 2» игрок 2, наблюдающий первоначальный выбор игрока 1, делает свой выбор. Он выбирает между «левой» (l) и «правой» (r). Так как каждый игрок выыбирает только на одном шаге, нет необходимости нумеровать альтернативы и стратегии по шагам. Для удобства полезности (или выигрыши) обоих игроков показаны в нижней части дерева (они могут равняться сумме выигрышей, полученных вдоль ветви дерева). Например, если (a1, a2) = (L, l), где ai – альтернатива, выбранная игроком i, игрок 1 получает выигрыш, равный 2, а игрок 2 – нулевой выигрыш.
* Более формальные определения см. в [39] или в [41].
Рис. 11.1. Игра 1.
В этой игре игрок 2 наблюдает выбор игрока 1, прежде чем сделать свой выбор. Случай, когда он не наблюдает этот выбор (когда оба выбора осуществляются «одновременно»), изображен на рис. 11.2. На этом рисунке овал, который объединяет узлы, где делает выбор игрок 2, и тем самым показывает, что этот игрок обладает одинаковой информацией о том, какой из двух ходов – левый или правый – сделал (делает или будет делать) игрок 1,* изображает информационное множество игрока 2.** (В игре 1 каждый узел составляет отдельное информационное множество.) В игре с последовательными ходами (игра 1) игрок 2 может иметь различные выборы альтернатив в разных узлах; в игре с одновременными ходами (игра 2) он неизбежно выбирает одинаковые альтернативы, ибо в противном случае он был бы способен различать эти узлы. В терминологии этой главы игра 2 – статическая, а игра 1 – динамическая; это объясняется тем, что в последней игре, но не в первой, игрок (игрок 2) имеет возможность наблюдать и реагировать на выбор альтернативы другим игроком. На формальном уровне нет необходимости разделять эти два типа игр, однако такое различие делает более удобным постепенное развитие концепции Нэша.
* Мы также могли бы представить эту игру с помощью развернутой формы, где игрок 2 первым делает ход, но информационное множество игрока 1 включает два узла.
** Информационное множество игрока 2 в данном случае – это множество узлов, выделенное овалом; ход – выбор альтернативы. – Прим. ред.
Рис. 11.2. Игра 2.
Мы предполагаем, что общий вид дерева игры «общеизвестен»: все игроки знают его, знают, что их противники знают его, и т. д.* Любые экзогенные неопределенности (т. е. ходы природы) должны быть включены в это дерево.**
* О понятии «общеизвестное» см. в [3, 4, 45].
** См. разделы 11.4 и 11.5.
При нашем обсуждении игр 1 и 2 мы говорили о том, что игроки выбирают левую или правую альтернативу. Эти выборы альтернатив и называются чистыми стратегиями. Чистая стратегия – это детерминированный выбор игроком некоторой заданной альтернативы.* Напротив, игрок (скажем, игрок 1) мог бы рандомизировать выбор между левой и правой альтернативой, т. е. выбрать левую альтернативу с вероятностью х и правую с вероятностью 1 – х, где х лежит в интервале [0,1]. Такая стратегия называется смешанной стратегией.** Чистая стратегия представляет частный случай смешанной стратегии (при х = 0 или х = 1 в предыдущем примере).
* Этот выбор должен быть сделан для каждого информационного множества игрока, и сам выбор зависит от этого множества. Заметим также, что здесь понятия «выбор альтернативы» и «совершение хода» эквивалентны. – Прим. ред.
** Точнее, в игре в развернутой форме стратегия поведения для г-го игрока определяет для каждого из его информационных множеств распределение вероятностей на множестве альтернатив, возможных для данного информационного множества. Термин «смешанная стратегия» часто сохраняется для нормальной формы (см. ниже). В [40] показано, что эти две концепции эквивалентны, если каждый игрок помнит в любом узле дерева то, что он знал раньше (т. е. в предыдущих узлах). Поэтому мы будем отождествлять обе концепции.
Представление развернутой формы игры в нормальной форме является некоторым итоговым описанием развернутой формы. Нормальная форма может быть описана совокупностью чистых стратегий, доступных каждому игроку в каждом из его информационных множеств в развернутой форме. В играх 1 и 2 игрок 1 имеет две чистые стратегии: = L и = R. В игре 1 игрок 2 имеет четыре чистые стратегии: = {l, l}, = {r, r}, = {l, r} и = {r, l}, где, например, = {l, r} означает, что игрок 2 реагирует на ходом l, а на – ходом r. В игре 2 игрок 2 имеет только две чистые стратегии, которые соответствуют стратегиям и игры 1. Нормальная форма также отображает наборы чистых стратегий игроков в выигрыши каждого игрока.** Например, в игре 1 выигрыш игрока 1 для чистых стратегий {,} составляет П1(,) = 2, так как игрок 1 делает ход L и игрок 2 реагирует ходом I. Нормальные формы часто изображаются в виде матриц, как в таблице 11.1.
* Набор чистых стратегий всех игроков в игре в отечественной литературе обычно называется ситуацией в игре. – Прим. ред.
Таблица 11.1
Нормальная форма
Игра 1
Игрок 2
Игрок l
= (l, l)
= (r, r)
= (l, r)
= (r, l)
= L
= R
2,
1,
0
0
2,
3,
-1
1
2,
3,
0
1
2,
1,
-1
0
Игра 2
Игрок 2
Игрок l
= l
= r
= L
= R
2,
1,
0
0
2,
3,
-1
1
В общем случае игру в нормальной форме можно определить как набор возможных чистых стратегий Ai и функций выигрыша
для каждого игрока i.
Как и при развернутой форме, мы можем расширить пространство стратегий и ввести смешанные стратегии. Смешанная стратегия для игрока i – это распределение вероятностей на Ai. (Таким образом, пространством стратегий является, множество распределений вероятностей на Ai.) Выигрышами в смешанных стратегиях являются просто ожидаемые значения соответствующих выигрышей в чистых стратегиях.
Упражнение 11.1(*). Рассмотрите игру в развернутой форме, изображенную на рис. 11.3.
Рис. 11.3. Игра 3.
1. Каковы информационные множества игрока 2? Игрока 1?
2. Запишите эту игру в нормальной форме.
11.2. Равновесие по Нэшу
В этом разделе мы будем пользоваться только представлением игры в нормальной форме. Для того чтобы принять оптимальное решение, игрок должен, как правило, предвидеть, как будут вести себя противники. Первым и бесспорным основанием для такого предположения является то, что противники не должны применять доминируемые стратегии. Если некоторое поведение всегда приносит игроку выигрыш меньший, чем другое поведение, независимо от поведения остальных игроков, мы можем предположить, что игрок не выберет это поведение. Рассмотрим, к примеру, нормальную форму игры 1. Выбор стратегий, или (слабо) доминируется выбором стратегии для игрока 2. Таким образом, игрок 2 выбирает, если он «рационален», а игрок 1 должен рассчитывать на выигрыш 2 или 3, если он выбирает L () или, соответственно, R (). Поэтому он выберет стратегию R, и мы получаем вполне определенный исход этой игры: {, }. Отметим, что выбор стратегии L не является a priori доминируемым для игрока 1. Однако он становится таким после исключения доминируемых стратегий игрока 2. В общем случае можно действовать с помощью последовательного исключения доминируемых стратегий в нормальной форме игры. На каждом шаге исключение доминируемых стратегий для некоторых игроков на предыдущем шаге открывает доминируемые стратегии для других игроков. Процесс прекращается, когда больше невозможно найти доминируемые стратегии.
Исключение доминируемых стратегий также дает единственный ответ в известной игре «Дилемма заключенного», представленной в таблице 11.2. История, лежащая в основе этой игры, заключается в том, что два человека арестованы за преступление. Полиция не располагает достаточными доказательствами, чтобы обвинить подозреваемых, и поэтому необходимо, чтобы они дали свидетельские показания друг против друга. Полиция помещает каждого подозреваемого в отдельную камеру и тем самым не дает им возможности общаться друг с другом. Полиция сообщает каждому подозреваемому, что если он даст показания против другого (предаст), то он будет освобожден (при условии, что второй подозреваемый не предаст его) или получит снисхождение за дачу показаний. Если ни один из подозреваемых не предаст, то оба будут освобождены по причине недостаточных доказательств. Если предаст один, то он будет освобожден, а другой будет отправлен в тюрьму; если предадут оба – оба будут посажены, но при этом получат снисхождение за дачу показаний. В этой игре оба игрока одновременно выбирают одну из двух стратегий. Если оба игрока кооперируют (С) (не дают показаний), каждый получает 2. Если они оба не кооперируют (F) (от fink – предавать), каждый получает –2. Если один не дает показаний, а другой предает, второй выходит на свободу (получает 3), а первый – строгое наказание (–3).*
* В примере игры для организации промышленности С обозначало бы «назначение высокой цены», a F – «назначение низкой цены».
Таблица 11.2
Игра «Дилемма заключенного»
Игрок 2
Игрок 1
F
С
F
С
-2,
-3,
-2
3
3,
2,
-3
2
Очевидно, что F – доминирующая стратегия для обоих игроков. Поэтому {F, F} – единственный правдоподобный исход. Этот исход очень плох для обоих игроков: кооперируя, каждый смог бы получить 2 вместо –2. Однако корысть приводит к Парето-доминируемому исходу. (Читатель, который считает этот исход неправдоподобным, в частности, что игроки должны уметь поддерживать кооперацию, должен поставить под сомнение описание игры, т. е. способ изображения ситуации реальной жизни, а не способ выбора исхода.)
Упражнение 11.2(**). Продавец имеет одну неделимую единицу товара, п участников торгов имеют оценки на этот товар 0 ≤ υ1 ≤ υ2 ≤ ... ≤ υn соответственно, и эти оценки общеизвестны. Участники одновременно делают свои предложения цены bi за товар. Участник, предложивший самую высокую цену, выигрывает торги и выплачивает вторую предложенную цену, т. е. если i выигрывает, он имеет выигрыш
Проигравшие ничего не выплачивают.
1. Покажите, что предложение цены, равной своей оценке (bi = υi), является доминирующей стратегией для i-го участника торгов.
2. Сделайте вывод, что n-й участник торгов выигрывает и имеет излишек υn – υn-1.
3. Изменятся ли эти результаты, если каждый участник торгов будет знать только свою оценку, но не оценки других участников?
Упражнение 11.3(**). Имеется n потребителей с функциями полезности
где ti – доход i-го потребителя; а – общественное решение (например, количество общественного блага); gi(а, θi) – оценка i-м покупателем решения а; – параметр полезности. Функции gi общеизвестны. Денежные затраты решения а равны С (а).
1. Покажите, что для плановика, которому известны все параметры, общественно оптимальное решение a*( θ1 , . . . θn), максимизирует
(правило Самуэльсона).
2. Предположим, что θi известна только i-му потребителю. Плановик старается сконструировать механизм, побуждающий потребителей честно сообщить свои оценки и реализовать общественно оптимальное решение. Рассмотрим следующую игру. Потребителей просят одновременно сообщать свои оценки. – сообщение i-го потребителя (оно может расходиться с истиной). Плановик осуществляет решение a*(, ,) (т. е. решение, являющееся оптимальным, если все потребители говорят правду) и выдает трансферты:
где Кi – константа. Покажите, что объявление правды ( = θi) является доминирующей стратегией i-го потребителя. Сделайте вывод, что плановик может осуществить первое наилучшее (при полной информации) распределение.
К сожалению, во многих играх исключение доминируемых стратегий не имеет большого значения для выбора единственного «правдоподобного» исхода игры (или ограниченного множества исходов). Примером служит игра с одновременными ходами 2. Ни одна из четырех стратегий не является доминируемой, и этот метод оставляет нам неопределенный исход. Точно так же в играх Бертрана и Курно с одновременным выбором цен и количеств (глава 5) оптимальное поведение одной фирмы зависит от оптимального поведения другой фирмы, а это означает, что уже имеется большое количество недоминируемых стратегий.
Два других известных примера одновременного выбора двух игроков представлены в таблицах 11.3 и 11.4. В игре «Орлянка» игроки выбирают «орла» (Н) или «решку» (Т). Если выборы совпадают, игрок 1 получает 1 от игрока 2, и наоборот, если выборы не совпадают. В игре «Семейный спор» каждый игрок выбирает между походом в кино и походом в театр. Эти два игрока всегда стремятся пойти куда-либо вместе, а не поодиночке, однако игрок 1 предпочитает кино, а игрок 2 – театр.
Таблица 11.3
Игра «Сравнение монет»
Игрок 2
Игрок 1
Н
T
Я
Т
1,
-1
-1
1
-1
1
1
-1
Таблица 11.4
Игра «Семейный спор»
Игрок 2
Игрок 1
М
Р
М
Р
3,
1,
2
1
1,
2,
1
3
В таких случаях понятие равновесия по Нэшу дает более слабую концепцию «правдоподобного исхода».
Определение. Набор стратегий составляет равновесие по Нэшу в чистых стратегиях тогда и только тогда, когда для всех i и всех аi из Ai
где. Другими словами, равновесие по Нэшу есть такой набор стратегий, что ни один игрок не захочет изменить свое поведение, предполагая, что его противники придерживаются выбранных стратегий. Это определение, конечно, непосредственно распространяется на случай смешанных стратегий в предположении, что – множество стратегий г-го игрока (множество распределений вероятностей на Ai), а – математическое ожидание его выигрыша в смешанных стратегиях.
«Орлянка» иллюстрирует возможность отсутствия равновесия по Нэшу в чистых стратегиях. Если игрок 1 выбирает H (от head), то игрок 2 выберет Т (от tail), что вызывает у игрока 1 желание выбрать Т, и т. д. Но здесь существует равновесие в смешанных стратегиях: каждый игрок выбирает H и Т равновероятно. Для того чтобы это было равновесием, ситуация должна быть такой, чтобы обе чистые стратегии давали одинаковые выигрыши каждому игроку. Выбор H дает игроку 1
;
в то время как выбор Т дает ему
.
Равновесия в чистых стратегиях не всегда должны существовать в играх общего вида, однако равновесия в смешанных стратегиях всегда существуют (см. Дополнительный раздел).
«Семейный спор» иллюстрирует возможность множественности равновесий. {М, М} и {Р, Р} – два равновесия в чистых стратегиях. Существует также и равновесие в смешанных стратегиях, при котором игрок 1 выбирает М с вероятностью 2/3 (и Р с вероятностью 1/3), а игрок 2 выбирает Р с вероятностью 2/3 (и М с вероятностью 1/3). В таких случаях неясно, какой прогноз следует сделать. Для обоих игроков ни одно из равновесий не является предпочтительным. С другой стороны, некоторые элементы истории (не включенные в описание игры) могут указывать на «фокальное» равновесие (например, то, что оба игрока прежде чередовались и на прошлой неделе они сходили в кино, поэтому на этой неделе будет «естественным» пойти в театр).* Такой вид выбора из равновесий по Нэшу в значительной мере связан с личной оценкой (по сравнению с использованием систематического метода).
* Примеры фокального равновесия из [60] могут быть более убедительными.
Часто Ai является непрерывным пространством (скажем, R), а функция П1 обладает хорошими свойствами дифференцируемости. Тогда можно получить равновесие в чистых стратегиях, если оно существует, дифференцируя функцию выигрыша каждого игрока по стратегии этого игрока. Таким образом, условие первого порядка:
где обозначает частную производную по стратегии этого игрока. (Локальное условие второго порядка имеет вид ≤ 0.) Условия первого порядка дают систему n уравнений с n неизвестными, которая, если решение существует и для каждого игрока выполняется условие второго порядка, дает равновесие (или равновесия) по Нэшу в чистых стратегиях. Например, предположим, что две фирмы (производящие дифференцированные товары) конкурируют по ценам, ai = pi. Спрос на товар, произведенный фирмой i, составит
qi = Di(pi, pj) = 1 – bрi+ dpj
при 0 ≤ d ≤ b. Если фирма i имеет удельные затраты с, то
Пi = (pi – c)(1 – bpi + dpj).
Отметим, что Пi вогнута по pi. Условиями первого порядка для i = 1,2 являются
1 + dpj +bc – 2bpi = 0.
Равновесие по Нэшу в чистых стратегиях единственно и симметрично:
Теперь вернемся к играм 1 и 2. Игра с одновременными ходами (игра 2) имеет два равновесия в чистых стратегиях: {} и {}. Игра с последовательными ходами (игра 1) допускает кроме этих двух равновесий по Нэшу еще и третье: {}, которое дает те же альтернативы (и, следовательно, те же выигрыши), что и второе. Для одновременной игры оба равновесия по Нэшу кажутся правдоподобными.* Это не так в случае игры с последовательными ходами, для которой, как утверждалось, существует единственное правдоподобное решение (после исключения доминируемых стратегий). Вопрос, как мы увидим, состоит в том, что понятие равновесия по Нэшу правдоподобно только тогда, когда все решения принимаются одновременно (раз и навсегда); оно обычно оказывается слишком слабым при последовательных решениях.
* За исключением того, что выигрыши (3, 1) при втором равновесии превышают выигрыши (2, 0) при первом. Можно было бы утверждать, что двум игрокам следует выбрать второе равновесие, но данный пример можно немного изменить, чтобы этого не происходило.
Упражнение 11.4*. Найдите равновесия по Нэшу в чистых стратегиях для игры, определенной в упражнении 11.1.
Упражнение 11.5**. Потребители расположены равномерно в линейном городе протяженностью 1. Каждый потребитель хочет купить у одной из существующих фирм единицу товара. Транспортные расходы для потребителя пропорциональны расстоянию до фирмы, у которой он покупает. Закон запрещает любой вид ценовой и сервисной конкуренции (кроме конкуренции местоположения), поэтому покупатели ходят покупать в близлежащую фирму. Полезность фирмы равна количеству ее покупателей. Фирмы, расположенные в одном месте, имеют одинаковое количество покупателей.
1. Имеются две фирмы, и они выбирают местоположение одновременно. Покажите, что существовует единственное равновесие по Нэшу в чистых стратегиях и что при этом обе фирмы расположены в середине отрезка.
2. Покажите, что при наличии трех фирм равновесия по Нэшу в чистых стратегиях не существует.
Упражнение 11.6(**). Имеется п потребителей. Каждый i-й потребитель тратит сумму денег рi на общественное благо. Выборы делаются одновременно. Полезность i-го потребителя
где g(0) = 0; g'(0) > 1; g' > 0; g" < 0, . Вычислите равновесие по Нэшу. Обсудите множественность. Покажите, что общественные расходы слишком малы.
11.3. Абсолютное равновесие
В равновесии по Нэшу игроки принимают стратегии своих противников как данные и поэтому не учитывают возможность влияния на них. В играх, в которых игрок выбирает альтернативы на основе наблюдения выбора альтернатив своих противников (так называемые динамические игры), это предположение наивно и приводит к некоторым абсурдным равновесиям по Нэшу, как мы видели в предыдущем разделе. В этом разделе вводится уточнение равновесия по Нэшу для динамических игр, которое смягчает его недостатки.
Рассмотрим вновь последовательную игру 1 (рис. 11.1) и равнрвесие по Нэшу {}. Игрок 1 не делает ход R, так как игрок 2 угрожает в этом случае сделать ход I. Но предположим, что игрок 1 сделает ход R. Тогда игрок 2, столкнувшись со свершившимся фактом, получает выгоду, сделав ход r, так как тогда он получает 1 вместо 0. Таким образом, угроза игрока 2 неправдоподобна. Игрок 1, который должен это предвидеть, делает ход R, приносящий ему выигрыш 3 – больший, чем он бы получил, сделав ход L. Таким образом, предложенное равновесие по Нэшу базируется на неправдоподобной угрозе, т. е. угрозе, которая не осуществилась бы, если бы игрок получил возможность сделать это.
Основная идея абсолютного равновесия состоит в том, чтобы выбирать равновесия по Нэшу, которые не вызывают неправдоподобных угроз, (грубо) требуя, чтобы поведение игроков было оптимальным даже в ситуациях, не достигаемых на равновесной траектории. Например, решение игрока 2 сделать ход I, после того как игрок 1 сделал ход R, не является оптимальным; причина, по которой {} составляет равновесие по Нэшу, состоит в том, что это субоптимальное решение не стоит игроку 2 ничего, потому что игрок 1 должен сделать ход L (на языке теории игр ход R игрока 1 имеет нулевую вероятность). Наоборот, абсолютное равновесие требует, чтобы игрок 2 сыграл оптимально независимо от того, какой сделает ход игрок 1 – R или L. Это равнозначно исключению доминируемых стратегий для игрока 2; вот почему абсолютность дает тот же ответ, что и последовательное исключение доминируемых стратегий для этой игры (см. ниже класс игр, в которых два метода дают одинаковый ответ).
Чтобы получить абсолютное равновесие, мы действуем «в обратном направлении». Зная оптимальную реакцию игрока 2 на каждое из потенциальных действий игрока 1, мы можем «свернуть дерево», как показано на рис. 11.4. Оценки игрока 1 (соответственно игрока 2) равны 2 и 3 (соответственно 0 и 1), когда игрок 1 сделал ход l или r. (Оценки представляют собой выигрыши, которые получают игроки по достижении определенной вершины на дереве игры.) Тогда игра сводится к задаче одного лица, принимающего решение, в котором игрок 1 выбирает R. Этот процесс обратной индукции на дереве называется алгоритмом Куна [40].
Рис. 11.4.
Для игр более общего вида определим (собственную) подыгру как подмножество дерева исходной игры, которое: 1) начинается с информационного множества, содержащего только один узел, 2) замкнуто по последовательности (если узел находится в подыгре, то в ней находятся и все последующие узлы) и 3) таково, что все информационные множества подыгры являются информационными множествами исходной игры.
В частности, сама игра составляет одну из своих подыгр. Например, игра 1 имеет три подыгры: саму себя и две другие подыгры, начинающиеся после того, как игрок 1 сделает ход. Наоборот, игра 2 составляет свою единственную подыгру в силу требования 1. Абсолютное равновесие [61]* – это такой набор стратегий для каждого игрока, что в любой подыгре стратегии (усеченные до этой подыгры) образуют равновесие по Нэшу. Таким образом, абсолютность требует, чтобы стратегии были в равновесии, независимо от вершины (понимаемой как подыгра) на дереве игры, а не только вдоль равновесной траектории. Абсолютное равновесие с необходимостью является равновесием по Нэшу (возьмем большую подыгру, представленную самой игрой). В игре 1 две подыгры второго шага являются играми с одним лицом, принимающим решение. Равновесие по Нэшу в этих подыграх означает, что лицо, принимающее решение (игрок 2), выбирает свою наилучшую альтернативу.
* См. также: , , Семина игр. М. : Высшая школа, 1998; Petrosjan L., Zenkevich N. Game Theory. World Scientific, 1996. – Прим. ред.
Имеется два типа обычно используемых игр, для которых абсолютность является сильным определением: игры с полной информацией и игры с «почти полной» информацией.
11.3.1. Игры с полной информацией
Попросту говоря, в этих играх игрок, чья очередь делать ход, знает (обладает полной информацией) все альтернативы, которые были выбраны до этого хода. Здесь отсутствует элемент одновременности. Формально все информационные множества состоят только из одного узла. Примером такой игры служит игра 1; другими примерами служат игра Штакельберга из главы 8 и ценовая игра с краткосрочным обязательством из главы 6. Интересным в этих играх является то, что повторное исключение слабо доминируемых стратегий из нормальной формы порождает абсолютные равновесия (по крайней мере, для конечных игр). Чтобы убедиться в этом, начнем с последнего шага или терминальных узлов (в игре 1 есть два таких узла). Исключение (на первой стадии) доминируемых стратегий игрока, делающего последний ход, определяет его оптимальное поведение в каждой конечной вершине. Когда поведение на последнем шаге свернуто в оценки, предпоследний шаг становится, последним, и вновь исключение (на второй стадии) доминируемых стратегий дает оптимальное поведение, и т. д. Таким образом, повторное исключение доминируемых стратегий удовлетворяет обратной индукции на дереве [40]. (Эти две концепции почти эквивалентны. Чтобы привести пример, где они различаются, заменим выигрыш 3 в игре 1 на выигрыш 2. {R, r} – абсолютное равновесие, но оно устраняется исключением слабо доминируемых стратегий. Читатель может убедиться, что последовательное исключение сильно доминируемых стратегий игры «в нормальной форме с агентами» порождает именно набор абсолютных равновесий. Определение игры в нормальной форме с агентами см. в подразделе 11.6.1; результаты исключения слабо доминируемых стратегий см. в [49].)
Пример 1.
Рассмотрим алгебраический пример с двухшаговой структурой игры 1. Для этого рассмотрим ценовую игру, отличающуюся от игры из раздела 11.2 лишь тем, что фирма 2 наблюдает цену фирмы 1 до выбора своей цены. Логика обратной индукции требует, чтобы фирма 1 предвидела, что фирма 2 будет оптимально реагировать на любой выбор р\. Это означает, что фирма 1 должна решить проблему оптимизации второго шага для фирмы 2 до решения своей проблемы первого шага. Зная р\ , фирма 2 максимизирует
(р2 – с)(1 – bp2 + dp1);
таким образом,
где R2 – (оптимальная) реакция фирмы 2. Поэтому фирма 1 максимизирует
(p1 – с)[1 – bpi + dR2(pi)].
Отметим, что она учитывает влияние р\ на р2. Решение тогда имеет вид:
и
(Равновесные цены выше в последовательной игре, чем в одновременной. Объяснение в терминах стратегических дополнителей см. в главе 8.)
Пример 2.
Рассмотрим игру «Дележ пирога» Рубинштейна [58], в которой два игрока, которые должны разделить пирог размера 1, делают последовательные чередующиеся предложения. В момент 1 игрок 1 делает предложение х1 в [0, 1]; игрок 2 принимает или отвергает x1. Если он принимает предложение, то получает 1 – х1, оставляя х1 игроку 1. Если он отвергает это предложение, то делает предложение х2 в [0, 1] в момент 2. Если это предложение принимается, он получает 1– х2 на втором шаге, а игрок 1 получает х2; если игрок 1 отвергает это предложение, ему приходится сделать предложение хз в момент 3, и т. д. Игроки делают предложения поочередно до тех пор, пока один из них не примет предложения своего противника. Выигрыши составляют δtхt для игрока 1 и δt(1 – xt) Для игрока 2, если они соглашаются в момент t выделить долю xt игроку 1. Коэффициент дисконтирования
δ принадлежит (0, 1). Нетерпение – та движущая сила, которая приводит к соглашению в этой модели. Это игра с полной информацией. Каждый игрок, делающий предложение или отвечающий на него, знает все действия, предпринятые до его хода. Предположим, что имеется Т шагов. Чтобы определить абсолютное равновесие, необходимо рассмотреть сначала последний шаг. Ясно, что игрок, делающий предложение на шаге Т, требует весь пирог, так как другой игрок не сможет сделать следующее предложение. Таким образом, xT = 0, если Т – четное, и xT = 1, если Т – нечетное. На шаге Т – 1 игрок, делающий предложение, дает другому игроку такую долю пирога, что тому безразлично, что получить: эту долю в Т – 1 или целый пирог в T и т. д.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
