Переговоры в динамических играх

В данном диссертационном исследовании рассматриваются некоторые теоретико-игровые модели переговоров и арбитража.

Задачу переговоров (bargaining problem) впервые сформулировал Эджворт (Edge-worth F.Y. [41]), рассматривая её как фундаментальную проблему экономики. В качестве решения задачи торга между двумя лицами он предложил так называемую контрактную кривую и показал, что для модели с двумя товарами и двумя типами потребителей контрактная кривая превращается во множество конкурентных равновесных ситуаций, если число потребителей каждого типа стремится к бесконечности.

Содержательно переговорные модели можно разделить на несколько групп. К первой группе относятся задачи дележа, в которых игроки должны путём переговоров разделить между собой некоторый ресурс. Ко второй группе относятся игры, в которых делёж ресурса регулируется арбитром — лицом, не являющимся игроком, независимым от игроков и пользующимся собственными соображениями о справедливости. Такие задачи иначе называются арбитражными схемами. К третьей группе относятся игры, не являющимися моделями дележа, в которых игроки ведут переговоры, реализуя переговорные стратегии, определённые правилами. Как пример таких игр, можно привести задачу переговоров между органами правопорядка и террористами (Kraus S., Wilkenfeld J. [48]) или задачу инспектирования, допускающую переговоры о даче взятки налоговому инспектору (Vasin A.A., Agapova О.В. [72]).

К настоящему времени сформировалось два основных подхода к решению задачи переговоров. Первый из них, так называемый аксиоматический подход, был разработан Нэшем (Nash J.F. [55], [56]). Предположим, что в бескоалиционной игре I игроков вектор гарантированных выигрышей обозначен через (и°)=1. Рассматривается переговорное множество U — множество всех возможных векторов выигрышей (щ)[=1 таких, что щ ^ и° для всех i = 1./. Определяется система аксиом, являющаяся принципом оптимальности игры переговоров и в переговорном множестве разыскиваются все векторы выигрышей, удовлетворяющие этому принципу оптимальности. В случае аксиоматики Нэша оптимальное решение (и*)1Ы1 имеет вид i.

1 = argmax — и°).

0≠1еи г=1.

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

В дальнейшем система асиом Нэша подвергалась критическому рассмотрению со стороны ряда авторов. Калаи и Смородинский (Kalai Е., Smorodinsky М. [46]) заменили аксиому независимости от посторонних альтернатив аксиомой монотонности, принимая во внимание работу Райфы (Raiffa Н. [60]). Перле и Машлер (Perles М., Maschler М. [59]) разработали так называемое супераддитивное решение, введя в переговорное множество всё множество векторов выигрышей, оптимальных по Парето. Шепли (Shapley L.S. [69]) предложил собственную систему аксиом, позволяющую находить решение игры переговоров, рассматривая коалиции игроков и определённую на этих коалициях характеристическую функцию, отражающую гарантированный суммарный выигрыш игроков каждой коалиции. Рассматривая меры частей пространства выигрышей игроков, задаваемых неравенствами щ ^ и*, где (и*)=1 суть возможное оптимальное решение, и определяя оптимальное решение как элемент множества оптимальных по Парето векторов выигрышей, для которого все меры указанных множеств равны, было получено так называемое равноплощадное (Equal Area) решение (Anbarci N., Bigelow J. [19]). Аксиоматический подход обсуждался в работах таких авторов, как Рот (Roth А. [61]), Бинмор (Binmore K.G. [23], [24], [25]), Харсаньи (Harsanyi J.C. [43], [44]), Новак (Nowak A.S. [57]), Лере (Lehrer Е. [49]).

Второй, стратегический подход к решению задачи переговоров заключается в том, что игроки в процессе обмена предложениями (реализуя свои стратегии) без участия арбитра пытаются достигнуть ситуации равновесия. Обычно в рамках такого подхода процесс переговоров моделируется динамическими играми. Чтобы игра не продолжалась бесконечно, либо вводится дисконтирование выигрышей, либо назначается плата за разыгрывание каждой партии. В русле стратегического подхода Рубинштейн (Rubinstein А. [62]) разработал понятие совершенного равновесия. Лейтманн и Лиу (Leitmann G., Liu Р.Т. [50], Leitmann G. [51]) исследовали дифференциальную модель переговоров между рабочими и администрацией о величине заработной платы. Мулен (Moulin Н. [12]) описал задачу дележа доллара при дисконтировании, рассмотренную Дуттой и Дживерсом (Dutta В., Gevers L.).

Стратегические переговорные игры могут являться играми арбитража, однако в этом случае арбитр представляет собой активное лицо, которое предлагает свои решения, пользуясь, например, некоторым вероятностным распределением или рассматривая предложения, сделанные ранее игроками. Задачи подобного рода описаны Брамсом (Brams S.J. [27]). Модели согласительного арбитража и арбитража по последнему предложению, которые практикуются при разрешении производственных споров в США, исследованы Чаттерджи (Chatterjee К. [30]), Брамсом и Мериллом (Brams S.J., Merill S. [28], [29], Brams S.J. [27]), Самуэльсоном (Samuelson W.F. [68]). Модель арбитража между рабочим и администрацией, согласно которой предложения о величине заработной платы делают два арбитра (или адвоката), а не игроки, предложил Сакагучи (Sakagichi М. [64]).

В первой главе представляемой диссертационной работы исследованы некоторые модели согласительного арбитража и арбитража по последнему предложению. Согласно их правилам, два игрока, рабочий и администратор, ведут переговоры об увеличении заработной платы, которая выплачивается администратором рабочему. Не умаляя общности, можно положить, что величина заработной платы принимает значения из промежутка [0−1]. Договор между спорящими сторонами может быть заключён в том случае, когда требования рабочего не превосходят предложения администратора. В противном случае спор разрешает арбитр. В условиях согласительного арбитража он выбирает некоторую величину, которая и полагается в качестве заработной платы рабочего. В условиях арбитража по последнему предложению он выбирает некоторую величину из сегмента [0−1], но не она полагается в качестве решения спора, а то предложение из сделанных рабочим и администратором, которое ближе всего к решению арбитра.

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

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

Sakagichi M. [64]) и Чаттерджи (Chatterjee К. [30]).

В первом параграфе второй главы исследован антагонистический случай многошагового арбитража. Особенностью модели является то, что предложения о величине заработной платы в каждом периоде игры делают не игроки, а арбитр. Его выбор представляет собой случайную величину с равномерным распределением на [0−1]. Игроки должны либо согласиться, либо не согласиться с этим решением. Игра переходит в новый период если только оба игрока не приняли предложения арбитра. В противном случае игра завершается. Если только рабочий согласен с решением" *ар-битра а, то его выигрыш равен min (a, 1 — а), если же только администратор согласен с решением арбитра, то рабочий получает max (a, 1 — а) (спор разрешается в пользу несогласной стороны). В том случае, когда оба игрока согласны, рабочий получает в качестве выигрыша величину а. В исследуемой модели количество периодов конечно. Кроме того, учтена возможность дисконтирования выигрышей.

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

В третьей главе исследована игра инспектирования. Первоначально она была предложена Дрешером (Dresher М. [38]) в контексте контроля за соблюдением оборонных договоров. Машлер (Mashler М. [52]) решил антагонистическую игру инспектирования в достаточно простой постановке, учитывающей всего три параметра: количество периодов игры п ^ 1, максимальное количество инспекций 1 ^ к ^ п (положено, что у проверяемого, в отличие от инспектора, всего одна возможность совершить преступление) и фиксированный выигрыш инспектора q е (0- 1) в случае, если за всё время игры инспектируемый ни разу не совершил запрещённого действия. Сакагучи (Sakaguchi М. [65], [66]) предложил модели, согласно правилам которых проверяемый может несколько раз совершать противоправные действия, однако решения были найдены только для нескольких специальных случаев. В первом параграфе третьей главы рассмотрен неантагонистический вариант подобной игры двух лиц (между налогоплательщиком и инспектором налоговой службы). Инспектор имеет две стратегии — проверить налогоплательщика или не проверять его. Налогоплательщик имеет тоже две стратегии — укрывать налоги или не укрывать налогов. Игра многошаговая, поэтому совершать проверку или укрывать налоги игроки могут несколько раз. Решено несколько вариантов игры в зависимости от максимального количества возможностей совершать преступление и проводить проверку.

Все указанные модели не предусматривают возможности переговоров между игроками о заключении сговора с целью избежания преступником наказания. Васин и Агапова (Vasin A.A., Agapova О.В. [72]) исследовали игру инспектирования в контексте системы налогообложения, предлагая учитывать то, что инспектор может вступить в переговоры, требуя взятку за сокрытие преступления. Была предложена модель с переговорами в форме конечной позиционной игры с полной информацией.

Во втором параграфе третьей главы диссертации исследован вариант данной задачи. Введён третий игрок — руководитель налоговой службы (или государство), который контролирует остальных игроков, проводя повторные проверки. Игра многошаговая, максимальное количество периодов предполагается конечным. Каждая партия представляет собой розыгрыш позиционной неантагонистической игры с неполной информацией и полной памятью. Решение игры найдено в стратегиях поведения.

1. Берж К. Общая теория игр нескольких лиц: Пер. с франц. И. В. Соловьёва, под ред. В. Ф. Колчина. — М.: Государственное издательство физико-математической литературы, 1961. — 128 с.

2. Васин А. А., Панова Е. И. Собираемость налогов и коррупция в налоговых органах. — М.: РПЭИ, Фонд «Евразия», 1999 — 31 с.

3. Гермейер Ю. Б.

Введение

в теорию исследования операций. — М.: Наука, Главная редакция физико-математической литературы, 1971. — 384 с.

4. Гермейер Ю. Б. Игры с непротивоположными интересами. — М.: Наука, Главная редакция физико-математической литературы, 1976. — 328 с.

5. Дюбин Г. Н., Суздаль В. Г.

Введение

в прикладную теорию игр. — М.: Наука, Главная редакция физико-математической литературы, 1981. — 336 с.

6. Жуковский В. И. Кооперативные игры при неопределённости и их приложения: Под ред. B.C. Молостнова. — М.: Эдиториал УРСС, 1999. — 336 с.

7. Забелин А. А. Игры типа «преступник полиция»: Математический анализ и его приложения. — Чита, 1998. — Вып. 3. — с. 43 — 52.

8. Забелин А. А. Решение игр типа «преступник полиция»: Математический анализ и его приложения. — Чита, 2000. — Вып. 4. — с. 48 — 57.

9. Карлин С. Математические методы в теории игр, программировании и экономике: Пер. с англ. Н. А. Бодина, Л. И. Горькова, А. А. Корбута, А. Н. Ляпунова, Н. М. Митрофановой, А. Н. Смирнова, Е. Б. Яновской, под ред. Н. Н. Воробьёва. — М.: Мир, 1964. — 840 с.

10. Льюис Р. Д., Райфа X. Игры и решения.

Введение

и критический обзор: Пер. с англ. И. В. Соловьёва, под ред. Д. Б. Юдина, с предисл. А. А. Ляпунова — М.: Издательство иностранной литературы, 1961. — 664 с.

11. Мак-Кинси Дж.

Введение

в теорию игр. — М.: Государственное издательство физико-математической литературы, 1960. — 420 с.

12. Мулен Э. Теория игр с примерами из математической экономики: Пер. с франц. — М.: Мир, 1985. — 200 с.

13. Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение: Пер. с англ., под ред. и с доб. Н. Н. Воробьёва. — М.: Наука, Главная редакция физико-математической литературы, 1970. — 708 с.

14. Петросян Л. А. Принципы оптимальности в многошаговых играх. — Соросов-ский образовательный журнал, № 10, 1996. — с. 120 125.

15. Петросян Л. А., Зенкевич Н. А., Сёмина Е. А. Теория игр: Учебное пособие для университетов. — М.: Высшая школа, Книжный дом «Университет», 1998. — 304 с.

16. Петросян Л. А., Кузютин Д. В. Игры в развёрнутой форме: оптимальность и устойчивость. — Санкт-Петербург: Издательство Санкт-Петербургского университета, 2000. — 292 с.

17. Петросян Л. А., Томский Г. В. Динамические игры и их приложения: Учебное пособие. — Л.: Издательство ЛГУ, 1982. — 252 с.

18. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. — М.: Наука, Главная редакция физико-математической литературы, 1969. — 384 с.

19. Anbarci N., Bigelow J. The Area Monotonic Solution to the Cooperative Bargaining Problem. — Mathematical Social Sciences, No. 28, 1994. — pp. 133 142.

20. Aumann R.J., Maschler M. The Bargaining Set for Cooperative Games. — Advances in Game Theory, Annals of Mathematics Studies, 52, Dresher M., Shapley L.S., Tucker A.W., eds. — Princeton: Princeton University Press, 1964. — pp. 443 -476.

21. Aumann R.J., Maschler M. Game Theoretic Analysis of a Bankruptcy Problem from the Talmud. — Journal of Economic Theory, No. 36, 1985. — pp. 195 213.

22. Banzhaf J.F. Weighted Voting Doesn’t Work: A Mathematical Analysis. — Rutgers Law Review, No. 19. — pp. 317 343.

23. Binmore K. Nash Bargaining Theory I. — ICERD: London School of Economics, D.P. 80−09, 1980.

24. Binmore K. Nash Bargaining Theory II. — ICERD: London School of Economics, D.P. 80−14, 1980.

25. Binmore K. Bargaining and Coalitions: in Game-Theorelic Models of Bargairning, A. Roth ed. — Cambridge University Press: Cambridge, 1985.

26. Binmore K., Rubinstein A., Wolinsky A. The Nash Bargaining Solution in Economic Modelling. — RAND Journal of Economics, Vol. 17, No. 2, Summer, 1986.

27. Brams S.J. Negotiation Games: Applying Game Theory to Bargaining and Arbitration. — New York: Routledge, 1990. — 280 pp.

28. Brams S.J., Merill S. Equilibrium Strategies for Finall-Offer Arbitration: There Is No Median Convergence. — Management Science, Vol. 29, No. 8, 1983.

29. Brams S.J., Merill S. Binding Versus Final-Offer Arbitration: A Combination Is Best. — Management Science, Vol. 32, No. 10, 1986.

30. Chatterjee K. Comparison of Arbitration Procedures: Models with Complete and Incomplete Information. — IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-11, No. 2, February, 1981. — pp. 101 109.

31. Chatterjee K., Samuelson L. Bargaining with Two-Sided Incomplete Information: An Infinite Horizon Model with Alternating Offers. — Review of Economic Studies, No. 54, 1987. — pp. 175 192.

32. Chatterjee K., Samuelson L. Bargaining under Incomplete Information: The Unrestricted Offers Case. — Operations Research, No. 36, 1988. — pp. 605 618.

33. Cramton P.C. Bargaining with Incomplete Information: An Infinite-Horizon Model with Two-Sided Uncertainty. — Review of Economic Studies, LI, 1984. — pp. 579 -593.

34. Chun Y. Equivalence of Axioms for Bankruptcy Problems. — International Journal of Game Theory, No. 28, 1999. — pp. 511 520.

35. Dagan N., Volij O. The Bancruptcy Problem: A Cooperative Bargaining Approach. — Math. Social Sciences, No. 26, 1993. — pp. 287 297.

36. Dagan N. New Characterizations of Old Bankruptcy Rules. — Social Choice and Welfare, No. 13, 1996. — pp. 51 59.

37. Davis M., Maschler M. The Kernel of a Cooperative Game. — Naval Resarch Logistics Quarterly, No. 12, 1965. — pp. 223 259.

38. Dresher M. A Sampling Inspection Problem in Arms Control Agreements: A Game-Theoretic Analysis: Memorandum RM-2972-ARPA. — The RAND Corporation: Santa Monica, California, 1962.

39. Driessen T.S.H. Relations Between Bancruptcy Games and Minimum Cost Spanning Tree Games, Essays in Game Theory in Honor of M. Mashler, N. Megiddo, ed. — Springer-Verlag, New York, 1994. — pp. 51 64.

40. Dutta В., Gevers L. On Voting Rules and Perfect Equilibrium Allocation of a Srinking Cake. — Мулен Э. Теория игр с примерами из математической экономики: Пер. с франц. — М.: Мир, 1985. — с. 58 59.

41. Edgeworth F. Y. Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences. — Kegan Paul: London, 1881. (Reprinted Augustus M. Kelley: New York, 1967).

42. Fudenberg D., Tirole I. Sequential Bargaining with Incomplete Information. — Review of Economic Studies, No. 50. — pp. 221 247.

43. Harsanyi J.C. Approaches to the Bargaining Problem Before and After the Theory of Games: A Critical Discussion of Zeuthen’s, Hick’s, and Nash’s Theories. — Eco-nometrica, Vol. 24, 1956. — pp. 144 157.

44. Harsanyi J.C. A Simplified Bargaining Model for the n-Person Cooperative Game. — International Economic Review, No. 4, 1963. — pp. 194 220.

45. Kalai E., Samet D. On Weighted Shapley Values. — International Journal of Game Theory, No. 16, 1987. — pp. 205 222.

46. Kalai E., Smorodinsky M. Other Solutions to Nash’s Bargaining Problem. — Econometrica, Vol. 43, 1975. — pp. 513 518.

47. Kilgour D.M. Optimal Cheating and Inspection Strategies under a Chemical Weapons Treaty. — INFOR, Vol. 28, No. 1, February, 1990. — pp. 27 39.

48. Kraus S., Wilkenfeld J. A Strategic Negotiations Model with Applications to an International Crisis. — IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 1, 1993. — pp. 313 323.

49. Lehrer E. An Axiomatization of the Banzhaf Value. — International Journal of Game Theory, No. 17, 1988. — pp. 89 99.

50. Leitmann G., Liu P.T. A Differential Game Model of Labor-Management Negotiation During a Strike. — Paper Presented at the 5th IFIP Conference on Optimization Techniques, Rome, Italy, 1973.

51. Leitmann G. Collective Bargaining: a Differential Game. — JOTA, Vol. 11, No. 4, 1973. — pp. 405 412.

52. Mashler M. A Price Leadership Method for Solving the Inspector’s Non-Constant Sum Game. — Naval Research Logistic Quaterly, No 13. — pp. 11 33.

53. Mazalov V.V., Zabelin A.A. Large Non-Symmetric Solution of an Arbitration Game. — Logic, Game Theory and Social Choice: Extended Abstracts of International Conference. — SPb, DOP, Institute of Chemistry, SPbSU, 2001. — pp. 180 183.

54. Nash J. F. The Bargaining Problem. — Econometrica, Vol. 18, 1950 — pp. 155 -162.

55. Nash J. F. Two Person Cooperative Games. — Econometrica, Vol. 21, 1953 — pp. 128 140.

56. Nowak A.S. On the Axiomatization of the Banzhaf Value without the Additivity Axiom. — International Journal of Game Theory, No. 26, 1997. — pp. 137 141.

57. Owen G. Game Theory. — New York: Academic Press, 1982.

58. Perles M., Maschler M. A Superadditive Solution to Nash Bargaining Games. — International Journal of Game Theory, No. 10, 1981. — pp. 163 193.

59. Raiffa H. Arbitration Schemes for Generalized Two-Person Games. — Annals of Mathematics Studies, No. 28, 1953. — pp. 361 387.

60. Roth A.E. Axiomatic Models of Bargaining. — Berlin: Springer-Verlag, 1979.

61. Rubinstein A. Perfect Equilibrium in a Bargaining Model. — Econometrica, Vol. 50, No. 1, January, 1982. — pp. 97 109.

62. Rubinstein A. A Bargaining Model with Incomplete Information about Preferences. — Econometrica, Vol. 50, 1985. — pp. 1151 1172.

63. Sakaguchi M. A Time-Sequential Game Related to an Arbitration Procedure. — Math. Japonica, Vol. 29, No. 3, 1984. — pp. 491 502.

64. Sakaguchi M. A sequential Game of Multi-Opportunity Infiltration. — Math. Japonica, Vol. 37, 1994. — pp. 157 166.

65. Sakaguchi M. A Non-Zero-Sum Repeated Game — Criminal vs. Police. — Math. Japonica, Vol. 48, 1998. — pp. 427 436.

66. Sakaguchi M. Repeated Game of Criminal vs Police. Incomplete-Information Case. — preprint.

67. Samuelson W.F. Final-Offer Arbitration under Incomplete Information. — School of Management, Boston University, preprint.

68. Shapley L.S. A Value for n-Person Games. — Contributions to the Theory of Games, Vol. II, Annals of Mathematics Studies, Vol. 28, H.W. Kuhn, A.W. Tucker, eds. — Princeton: Princeton University Press, 1953. — pp. 307 317.

69. Sobel I., Takahashi L. A Multi-Stage Model of Bargaining. — Review of Economic Studies, No. 50, 1983. — pp. 411 426.

70. Thomson W. Cooperative Models of Bargaining: in Handbook of Game Theory, Vol. 2, Aumann R., Hart S, eds. — North Holland: Amsterdam, 1995.