Переговоры в динамических играх тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Забелин, Анатолий Анатольевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Санкт-Петербург МЕСТО ЗАЩИТЫ
2001 ГОД ЗАЩИТЫ
   
01.01.09 КОД ВАК РФ
Диссертация по математике на тему «Переговоры в динамических играх»
 
 
Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Забелин, Анатолий Анатольевич

Введение.

1. Теоретико-игровая модель арбитража.

§1.1. Постановка задачи об арбитраже.

§1.2. Согласительный арбитраж и арбитраж по последнему предложению. Выбор арбитра постоянен.

§1.3. Согласительный арбитраж и арбитраж по последнему предложению. Выбор арбитра — непрерывная случайная величина.

§1.4. Арбитраж по последнему предложению. Решение арбитра — дискретная случайная величина.

§1.5. Моделирование на ЭВМ.

2. Динамические модели арбитража со случайными предложениями.

§2.1. Арбитражная схема для двух лиц. Антагонистический случай.

§2.2. Арбитраж между двумя лицами. Неантагонистический случай.

§2.3. Арбитраж между тремя лицами.

3. Задача о налогообложении, допускающая переговоры.

§3.1. Игровая модель инспектирования без переговоров.

§3.2. Инспектирование, допускающее переговоры.

 
Введение диссертация по математике, на тему "Переговоры в динамических играх"

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

Задачу переговоров (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.