Моделирование переговоров с помощью арбитражной схемы нэша ю. А. Дорофеева1
 Скачать 474.97 Kb.
|
|
ЮЖНО-СИБИРСКИЙ НАУЧНЫЙ ВЕСТНИК № 6 (46) • декабрь 2022 168 1.2.2 МОДЕЛИРОВАНИЕ ПЕРЕГОВОРОВ С ПОМОЩЬЮ АРБИТРАЖНОЙ СХЕМЫ НЭША Ю.А. Дорофеева 1 ,П.Л. Осипова 2 1 Национальный исследовательский университет ИТМО, г. Санкт-Петербург 2 Петрозаводский государственный университет, г. Петрозаводск Переговоры это неотъемлемая и важнейшая часть теории игр. Процессы обмена мнениями, споры, конкурсы, конфликты это все части переговоров, где решением будет состояние равновесия. Для двух игроков оптимальное состояние можно найти с помощью арбитражной схема Нэша. В этом случае особая роль отводится арбитру. Когда конкуренты не приходят к обоюдному согласию, он вступает в игру, и основной задачей является формирование случайных предложений для каждой из сторон. Кроме того, данный метод относительно прост в реализации и позволяет анализировать изменения выигрышей в зависимости от других параметров моделирования (предложений арбитра, коэффициента дисконтирования). В работе рассматриваются два сценария: переговоры о заработной плате и переговоры о времени встречи. Обе задачи решаются с помощью арбитражной схемы Нэша по одному и тому же алгоритму. Сложностью формализации можно считать определение интервала для арбитра. Для обоих случаев это сделано, исходя из постановки задачи с учетом особенностей реализации алгоритма в виде программы для численных экспериментов. Для более детального анализа в работе представлены результаты численного моделирования и показана зависимость длительности переговоров от параметров моделирования. Программа была написана на языке программирования С#. Ключевые слова: теория игр, арбитражная схема, уравнение оптимальности, переговоры, равновесие Нэша, случайное предложение, арбитр. ВВЕДЕНИЕ Переговоры являются неотъемлемой частью теории игр. Это сложный и многогранный процесс. Моделирование переговоров можно реализовать с помощью различных алгоритмов, например, с использованием схемы случайных предложений или организаций конкурсов и т.д. Важным параметром для данного процесса является информативность при любой форме организации переговоров. Это осведомленность о поведении соперников, выигрышах, штрафах, которые могут быть известны всем участникам или отдельным лицам. Поэтому переговоры могут вестись как с полной, так и с неполной информацией. Переговоры делятся на два типа [1]: позиционные и рациональные. Правила ведения переговоров играют важную роль в моделировании. Для разрешения конфликта есть независимый участник – арбитр. Он может быть представлен одним игроком, или это может быть арбитражный комитет. Стороны конфликта также могут объединиться, чтобы получить максимальную выгоду от конфликта. В связи с этим сторонами конфликта могут быть два или более игрока. Основная миссия арбитра - принять окончательное решение путем жеребьевки. Математическим аппаратом для разрешения конфликтов является теория переговоров, а оптимальным решением является равновесие Нэша. Достаточное количество исследований было посвящено моделированию переговоров по различным сценариям. Основной работой по этой проблеме, является исследование [1]. Это базовая работа, в которой авторы представляют основные теоретико-игровые модели переговоров между двумя, тремя или более лицами с использованием арбитражной схемы Нэша, со случайным предложением, а также переговоров во время заключения сделок и т.д. В работе [2] представлен метод поиска стратегии, максимизирующей вероятность завершения коммерческих переговоров. В такой формулировке всем участникам выгодно завершить переговоры как можно скорее. Работа авторов [3] посвящена изучению подхода к поиску оптимальных стратегий поведения для каждого из участников переговоров. Цель здесь состоит не только в том, чтобы увеличить собственную выгоду, но и в поиске совместных стратегий, которые максимизируют общие выигрыши в процессе переговоров. Исследование [4] посвящено различным подходам к торговым переговорам. В статье рассматриваются два основных вопроса: — как согласовывается политика переговоров в отсутствие коалиции для одной из сторон переговоров. — в рамках того, что участники создадут коалицию, насколько интересы каждой из сторон переговоров согласуются с общим результатом. Переговоры в теоретико-игровой формулировке используются в международной экологической политике. Таким образом, в [5] улучшены относительно простые игровые модели для DOI 10.25699/SSSB.2022.46.6.018 ЮЖНО-СИБИРСКИЙ НАУЧНЫЙ ВЕСТНИК 169 № 6 (46) • декабрь 2022 разрешения конфликтов и разрешения «переговоров по климату». В исследованиях [6], [7] рассматривается влияние игроков друг на друга и характеристики участников, а также модель группового выбора в процессе переговоров. Целью данной работы является моделирование переговоров с использованием арбитражной схемы Нэша. Впервые этот подход был описан и предложен в работе [8]. ОСНОВНАЯ ЧАСТЬ Для успешного моделирования должны быть выполнены следующие условия: — определение количества участников переговоров; — определение порядка подачи предложений; — настройка выигрышей игрока; — система определения штрафов; — правила поведения арбитра. Игра представляет собой многоступенчатый процесс с нулевой суммой. Предложения участникам поступают от арбитра, которые они могут принять или отклонить. Для второго варианта установлена ставка дисконтирования – 𝛿 ∈ 0,1 это способ остановить процесс переговоров, так как каждый раз участники будут терять долю от выигрыша. Важно отметить, что в арбитражной схеме окончательный выбор остается за игроками, а не за арбитром. Итак, пусть задана 𝑋 , 𝑌 , 𝑖 1,2, . . . , 𝐾 последовательность пар независимых одинаково распределенных случайных величин, которая может быть интерпретирована на шаге как предложение арбитра каждому из игроков. Как было установлено выше, игроки 𝑋 , 𝑌 могут принять 𝐴 или отклонить 𝑅 предложение. Выбирая второй вариант, игроки предполагают получить более выгодное предложение от арбитра. Если оба игрока принимают предложения на 𝑖 -ом шаге, игра заканчивается победой первого участника с выигрышем, равным. Если оба игрока отклоняют 𝑖 -ое предложение, переговоры переходят к следующему шагу 𝑖 1. При этом выигрыши получается с учетом коэффициента дисконтирования (уменьшен в 𝛿 раз). Если один из игроков принимает предложение, а другой отклоняет его, арбитр принимает решение в пользу «обиженной» стороны. Выигрыш равен: 𝑚𝑖𝑛 𝑋 , 𝑌 ,если 𝐴 𝑅, 𝑚𝑎𝑥 𝑋 , 𝑌 ,если 𝑅 𝐴. Процесс продолжается до тех пор, пока один из игроков не примет предложение или пока не наступит последний этап К. Оба вынуждены принять это предложение на последнем этапе. Пусть 𝐻 , 𝑘 𝐾 . значение игры. Тогда уравнение оптимальности имеет вид: 𝐻 𝐸 𝑣𝑎𝑙 𝐻 𝑋, 𝑌 , (1) где 𝑣𝑎𝑙 𝐻 𝑥, 𝑦 значение матричной игры, выигрыш на шаге 𝑘 1: 𝐴 𝑅 𝐻 𝑥, 𝑦 𝐴 𝑅 𝑥 𝑦 /2 𝑚𝑖𝑛 𝑥, 𝑦 𝑚𝑎𝑥 𝑥, 𝑦 𝛿𝐻 , (2) 𝑘 1,2, . . . , 𝐾 и граничное условие 𝐻 0. Матрица 𝐻 𝑥, 𝑦 имеет единственную седловую точку, которая зависит от 𝑥, 𝑦 . Тогда значение матрицы выигрыша определяется выражением: 1 1 1 1 min( , ), if min( , ) ( , ) , if min( , ) max( , ) max( , ), if max( , ) k k k k k x y H x y val H x y H x y H x y x y H x y (3) Оптимальные стратегии игроков на k-м шаге имеют следующий вид: 𝐴 𝑅, if 𝛿𝐻 𝑚𝑖𝑛 𝑥, 𝑦 𝐴 𝑅, if 𝛿𝐻 𝑚𝑎𝑥 𝑥, 𝑦 𝐴 𝑅, иначе. Переговоры о заработной плате для двух игроков с использованием арбитражной схемы Нэша В этой постановке принимают участие два игрока: менеджер и профессиональный союз. Цель переговоров установить заработную плату для работника. Задача менеджера минимизировать затраты, но профсоюз старается сделать оплату максимальной. Профсоюз настаивает на 100 единицах, а менеджер, из соображений экономии бюджета компании, настаивает на 50 единицах. В случае отказа профсоюза заработная плата снижается на 10 единиц относительно предложений арбитра. Если менеджер откажется, то зарплата увеличивается на 10 единиц относительно той же суммы. Игра переходит к следующему шагу, если оба откажутся. Решение обесценивается в 𝛿 раз. Арбитр делает предложения игрокам на каждом этапе. Для этого с заданным интервалом генерируется случайное целое число 𝑎. Установка этого параметра зависит от содержания задачи (размер штрафов, сумма выигрышей и т.д.). Для описанного выше сценария интервал случайных предложений арбитра является [40;60]. Выбор этого множества обусловлен суммой штрафов и типом выигрышей. Функции выигрыша менеджера 𝑓 𝑎 и функции для профессионального союза 𝑓 𝑎 являются унимодальными и имеют следующую форму: 𝑓 𝑎 75 |𝑎 100|, 𝑓 𝑎 75 |𝑎 50|, где 𝑎– предложение арбитра. Функции изображены на рисунке 1. ЮЖНО-СИБИРСКИЙ НАУЧНЫЙ ВЕСТНИК № 6 (46) • декабрь 2022 170 Рис. 1. Графики выигрышей в задаче о заработной плате Как описано выше, у игроков есть только две стратегии: принять предложение арбитра и отклонить предложение. Предположим, есть шаги для переговоров. В случае, когда переговоры не окончены, уравнение оптимальности (2) принимает вид: 𝐻 , 𝐻 𝐸 𝑣𝑎𝑙 𝑓 𝑎 , 𝑓 𝑎 𝑓 𝑎 10 , 𝑓 𝑎 10 𝑓 𝑎 10 , 𝑓 𝑎 10 𝛿𝐻 , 𝛿𝐻 , где 𝑎 принимает значения от 40 до 60 с одинаковой вероятностью . Одним из важных вопросов в процессе формализации переговоров о заработной плате является анализ периода переговоров (определение количества шагов). Это зависит от параметров моделирования, определения пороговых значений ставки дисконтирования и поведения всех участников процесса. На C# была написана программа для проведения многочисленных экспериментов, установления закономерностей и анализа модели в целом. Одним из основных вопросов численного моделирования является влияние изменения параметров моделирования (коэффициента дисконтирования и предложений арбитра) на время окончания переговоров. Текст программы опубликован в интернет- репозитории [9]. В таблице 1 приведены результаты программы. Здесь 𝑛 𝐾 𝑘 – это окончание переговоров. Переговоры о расписании для двух игроков с использованием арбитражной схемы Нэша В данном случае целью переговоров является определение даты встречи. Первый игрок настаивает на встрече 20-го числа месяца, а второй игрок хочет встретиться 10-го. Для моделирования и определения уравнения оптимальности (2) и определения выигрышей участников (1) необходимо соблюдать следующие правила. Если первый игрок отклоняет предложения арбитра, дата встречи сдвигается на 1 день влево относительно предложений арбитра. Если второй игрок отказывается, дата встречи сдвигается на 1 день вправо соответственно. Если оба участника отказываются, игра переходит к следующему шагу, при этом решение отклоняется в 𝛿 раз. На каждом шаге арбитр делает предложения игрокам, используя случайное целое число 𝑎 из интервала [6;24]. Установка интервала, как и в предыдущем случае, также зависит от постановки задачи. Выигрышные функции для первого 𝑓 𝑎 и второго 𝑓 𝑎 игроков имеют следующий вид: 𝑓 𝑎 15 |𝑎 20|, 𝑓 𝑎 15 |𝑎 10|. Графики представлены на рисунке 2. Рис. 2. Графики выигрышей в задаче о расписании Уравнение оптимальности (2) имеет вид: 𝐻 , 𝐻 𝐸 𝑣𝑎𝑙 𝑓 𝑎 , 𝑓 𝑎 𝑓 𝑎 1 , 𝑓 𝑎 1 𝑓 𝑎 1 , 𝑓 𝑎 1 𝛿𝐻 , 𝛿𝐻 , Параметр принимает 𝑎 значения от 6 до 24 с одинаковой вероятностью . Программа [9] позволяет проводить численные эксперименты с целью выявления зависимости поведения модели от изменения параметров. Результаты работы представлены в таблице. 2. Аналогично, как в предыдущей задаче выше, наступает этап 𝑛 𝐾 𝑘, на котором заканчиваются переговоры и определяется выигрыш обоих участников. ЗАКЛЮЧЕНИЕ Анализируя результаты моделирования для переговоров о заработной плате в таблице 1, можно сделать вывод о том, что при определении ставки дисконтирования из диапазона, наиболее близкого к 1, переговоры заканчиваются на втором шаге. Процесс прекращения переговоров не зависит от предложений арбитра в данном случае. Это означает, что значения параметра 𝛿 будут наиболее ”выгодными” с точки зрения скорости завершения переговоров. Для задачи согласования расписания, приведенной в таблице 2, такой интервал составляет. Кроме того, можно определить значения параметров, при которых достижение оптимальных значений выигрышей происходит за относительно длительный период — 52 итерации в первом случае и 66 — во втором. В обоих сценариях выигрыши игроков практически не меняются. Основной моделью для переговоров о заработной плате и расписании является арбитражная схема ЮЖНО-СИБИРСКИЙ НАУЧНЫЙ ВЕСТНИК 171 № 6 (46) • декабрь 2022 Нэша. Этот теоретико-игровой метод основан на модифицированном подходе разделения на части задачи. В отличие от классической проблемы, в арбитражной схеме присутствует нейтральный арбитр. Особенностью переговорной модели арбитражной схемы является ее универсальность и простота для задач с двумя конкурентами и предметом спора в числовой форме. Однако напрямую определить продолжительность переговоров невозможно. Численное моделирование было осуществлено с использованием компьютерной программы, чтобы ответить на этот вопрос. Целью численных экспериментов было определить влияние изменений параметров модели на период переговоров. Таким образом, все наиболее ”выгодные” решения переговорной проблемы были определены с точки зрения обоих игроков. Это наборы параметров моделирования, которые непосредственно влияют на период переговоров и значения функции выигрыша. Программный код опубликован в Интернет- репозитории [9]. Табл. 1 Результаты численного моделирования в задаче о заработной плате 𝜹 𝒂 𝒏 𝑯 𝒏 𝟏 𝑯 𝒏 𝟐 (0;0.77] [40;60] 2 32.6191 63.5714 (0.77;0.8] 40 14 33.7113 62.7780 [41;60] 2 32.6191 63.5714 (0.8;0.83) [42;60] 2 32.6191 63.5714 [0.83;0.85) [40;42] 27 35.9848 59.3472 [0.86;0.87) [40;43] 31 36.1502 58.7121 [0.87;0.89) [41;43] 36 36.5274 57.7465 [0.89;0.9) [42;44] 44 36.5274 56.2791 [0.9;0.92) [43;44] 44 36.7442 56.2791 [0.92;0.93] [44;45] 52 37.5427 62.4869 (0.93;1] [40;60] 2 32.6192 63.5714 Табл. 2 Результаты численного моделирования в задаче о времени встречи 𝜹 𝒂 𝒏 𝑯 𝒏 𝟏 𝑯 𝒏 𝟐 (0;0.22) [6;24] 2 9.2105 8.1579 [0.22;0.33] [7;24] 2 9.2105 8.1579 (0.33;044] [6;7] 15 9.7851 7.3064 (0.44;0.55] [6;8] 18 10.0595 6.9572 (0.55;0.66] [6;9] 22 10.5096 6.4881 (0.66;0.76] [6;10] 58 10.8187 6.1783 (0.76;0.77] [6;11] 59 11.0121 5.2902 (0.77;0.87] [6;11] 47 11.5488 5.2902 (0.87;0.98] [6;12] 66 13.1387 4.3868 (0.98;1] [14;24] 2 9.2105 8.1579 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. . Corfman, K. Chapter 3 Mathematical models of group choice and negotiations / K. Corfman, S. Gupta // Handbooks in Operations Research and Management Science. — 1993. — vol. 5. — pp. 83-142 2. Harrison, G. W. Trade Wars, Trade Negotiations and Applied Game Theory [Electronic resource] / G. W. Harrison, E. E. Rutstrom // The Economic Journal. — 1991. — Vol. 101, iss. 406. — P. 420. — Available from: https://doi.org/10.2307/2233549 3. Jackson, M., Sonnenshein, Y., Xing, Y., Tombazos, C., Ubaydly, O. A. The efficiency of negotiations with uncertain and multidimensional deals. Johns Hopkins Carey Business School Research Paper. — 2021. — P. 36. 4. Madani, K. Modeling international climate change negotiations more responsibly: Can highly simplified game theory models provide reliable policy insights? [Electronic resource] / K. Madani // Ecological Economics. — 2013. — Vol. 90. — P. 68-76. — Available from: https://doi.org/10.1016/j.ecolecon.2013.02.011 5. Manuell, G. C. Maximum probability negotiations in cooperative games with commercial purposes [Electronic resource] / G. C. Manuell, L. M. V // Revista Mexicana de Economía y Finanzas. — 2019. — Vol. 14, iss. 2. — P. 245-259. — Available from: https://doi.org/10.21919/remef.v14i2.382 6. Мазалов В.В. Математическая теория игр и приложения. Спб.:Лань,2016. . —448 с. 7. Мазалов В.В., Менчер А. Э., Токарева Ю. С. Переговоры. Математическая теория. Спб.:Лань,2012. . —304 с. 8. Wall, J. A. Negotiations [Electronic resource] / J. A. Wall, M. W. Blum // Journal of Management. — 1996. — Vol. 17, iss. 2. — P. 273- 303. — Available from: https://doi.org/10.1177/014920639101700203 9. Google. Google Drive. [Online] — 2012. — Available from: https://drive.google.com/drive/folders/14q0n6GwTQBXnOl8EZvaF7m WUODxnq7to?usp=sharing Дорофеева Юлия Александровна – ординарный доцент НОЦ «математики», Национальный исследовательский университет ИТМО Санкт-Петербург, тел. 89921735722, e-mail: julana2008@yandex.ru. Осипова Полина Леонидовна –, магистр 1 курса кафедры Прикладной математики и кибернетики, Петрозаводский государственный университет ФГБОУ ВПО ПетрГУ, тел. (963)7467426, e-mail: polina.polina20@yandex.ru ЮЖНО-СИБИРСКИЙ НАУЧНЫЙ ВЕСТНИК № 6 (46) • декабрь 2022 172 SIMULATION OF NEGOTIATIONS USING THE NASH ARBITRATION SCHEME Y.A. Dorofeeva 1 , P.L. Osipova 2 1 ITMO National Research University 2 Petrozavodsk State University, Petrozavodsk Negotiations are an integral and essential part of game theory. Processes of exchange of opinions, disputes, contests, conflations these are the parts of the conflict where the solution will be a state of equilibrium. An important task is to determine exactly this state for all competitors. One of the solutions for two players is the Nash arbitration scheme. When the competitors do not come to a mutual agreement, an arbitrator enters the game, whose task is to form a service proposal for each of the parties. The paper considers two scenarios: salary negotiations and negotiations on the meeting time. Both problems are solved using the Nash arbitration scheme using the same algorithm. For a more detailed analysis, the results of numerical simulation are presented and the dependence of the duration of negotiations on the simulation parameters is shown. The program was written in the C# programming language. Index terms: game theory, arbitration scheme, optimality equation, negotiations, Nash equilibrium, random sentence, arbiter. REFERENCES 1. Corfman, K. Chapter 3 Mathematical models of group choice and negotiations / K. Corfman, S. Gupta // Handbooks in Operations Research and Management Science,1993, vol. 5,pp. 83-142 2. Harrison, G. W. Trade Wars, Trade Negotiations and Applied Game Theory [Electronic resource] / G. W. Harrison, E. E. Rutstrom // The Economic Journal,1991,Vol. 101, p. 420 3. Jackson, M., Sonnenshein, Y., Xing, Y., Tombazos, C., Ubaydly, O. A. The efficiency of negotiations with uncertain and multidimensional deals. Johns Hopkins Carey Business School Research Paper, 2021,p. 36. 4. Madani, K. Modeling international climate change negotiations more responsibly/ K. Madani // Ecological Economics, 2013,Vol. 90,p. 68-76. 5. Manuell, G. C. Maximum probability negotiations in cooperative games with commercial purposes [Electronic resource] / G. C. Manuell, L. M. V // Revista Mexicana de Economía y Finanzas, 2019,Vol. 14, p. 245-259 6. Mazalov V.V. Mathematical game theory and applications. SPb: Lan,2016 7. Mazalov V.V., Mencher A. E., Tokareva Yu. S. Negotiations. Mathematical theory SPb:Lan,2012. 8. Wall, J. A. Negotiations [Electronic resource] / J. A. Wall, M. W. Blum // Journal of Management. ,1996, Vol. 17, p. 273-303 9. Google. Google Drive. [Online] — 2012. — Available from: https://drive.google.com/drive/folders/14q0n6GwTQBXnOl8EZvaF7mWUODxnq7to?usp=sharing Dorofeeva Yulia Alexandrovna Ordinary Associate Professor of the scientific and educational center "Mathematics", ITMO National Research University St. Petersburg, tel. 89921735722, e-mail: julana2008@yandex.ru. Osipova Polina Leonidovna –1st year Master of the Department of Applied Mathematics and Cybernetics, Petrozavodsk State University, PetrSU, tel. (963)7467426, e-mail: polina.polina20@yandex.ru. |