Стохастические модели проведения переговоров с несколькими участниками тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Носальская, Татьяна Эдуардовна

• Носальская, Татьяна Эдуардовна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Носальская, Татьяна Эдуардовна

Оглавление

Введение

Глава 1. Процедура проведения переговоров в задаче о

распределении ресурсов со случайными предложениями

1.1 Переговоры трёх лиц

1.1.1 Полный консенсус

1.1.2 Правило большинства

1.1.3 Несимметричный случай в условиях полного консенсуса

1.1.4 Несимметричный случай в условиях правила большинства

1.2 Переговоры четырёх лиц

1.2.1 Правило большинства

1.2.2 Влияние игроков с правом вето

1.3 Переговоры п лиц

1.3.1 Общий случай

1.3.2 Полный консенсус

Глава 2. Модели организации конкурсов

2.1 Модель с оценкой вектора

2.1.1 Игра четырёх лиц

2.1.2 Игра нескольких лиц

2.2 Модель с экспертной оценкой отдельных параметров

2.2.1 Теоретико-игровая модель конкурсов с линейными

полезностями

Глава 3. Последовательная задача распределения ресурсов

3.1 Игра с приоритетом

3.1.1 Взаимодействие агрессоров и толерантных игроков

3.1.2 Взаимодействие игроков, использующих прямую

или обратную стратегию вида tit for tat

3.2 Игра без приоритета

3.3 Стратегии с памятью два в игре с приоритетом

Заключение

Литература

Приложение 1

Приложение 2

Введение диссертации (часть автореферата) на тему «Стохастические модели проведения переговоров с несколькими участниками»

Введение

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

• Должны быть определены все участники переговоров;

• В переговорах могут принимать участие два и более лиц;

• Должна быть определена очередность предложений игроков;

• Должны быть определены выигрыши игроков;

• Переговоры должны заканчиваться;

• Переговоры должны приводить к определённому результату;

• Выигрыши равных игроков должны быть равны.

Особенно актуальным теоретико-игровое моделирование переговоров является в политике, экономике, медицине, а также сфере информационных технологий для решения различного рода прикладных задач. Примерами могут служить международные соглашения, голосование в парламенте, распре-

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

Задача переговоров изначально возникла как экономическая проблема. Первая её формулировка принадлежит Эджворту [24]. В дальнейшем эта задача получила широкое распространение и развитие. Хорошо известны такие модели переговоров, как представленные Гиббонсом [28] и Лейтом [32] переговоры работника и работодателя, рассмотренная Брамсом, Килгором и Дэвисом [18] игра обмена, исследованный Сакагучи [44,48] многоэтапный покер и другие. Кроуфорд [22] и Чаттерджи [21] анализируют модели, в которых игроки представляют свои предложения, а третий независимый участник, в качестве которого выступает арбитражный комитет, выбирает одно из этих предложений. Сакагучи в работе [45] рассматривает модель переговоров работника и работодателя с арбитражным комитетом, состоящим из двух арбитров. При этом оба арбитра предлагают размер заработной платы в каждый период переговоров. В трудах Сакагучи [46-48], Гарнаева [27], Ма-залова, Сакагучи и Забелина [37] эта модель арбитража была расширена для двустороннего случая, где арбитр представляет некоторые предложения для игроков и, если их решения отличаются, приоритет решения определяется лотереей. Мазалов и Банин [34] описывают близкую арбитражную задачу, где приоритет решения определяется голосованием.

Важную роль в теории переговоров играет задача о распределении ресурсов, которую также называют задачей дележа. Существуют различные процедуры дележа. Важнейшие из них представлены в работах Бастона и Гарнаева [13], Брамса и Тейлора [19,20], Хамерса [29] и Стромквиста [50].

Следует отметить, что понятие «справедливости» дележа является нетривиальным. Этот вопрос подробно освещают труды Мазалова, Менчера и Токаревой [4], Дубинса и Спэниера [23], а также Штейнхауса [49]. Целью дележа могут быть части гарантированного размера, при этом ни один участник не должен завидовать другим. Кроме того, делёж должен быть оптимальным по Парето.

Условно все существующие модели могут быть разбиты на две группы. В первой группе сами участники предлагают варианты распределения. Такая постановка рассмотрена Мазаловым, Сакагучи и Забелиным [37] и Рубинштейном [43]. Во второй группе для решения задачи приглашается третья независимая сторона — арбитр, который и формирует предложения участникам. Такие модели анализируются Мазаловым и Ваниным [34] и Сакагучи [48]. В работах Де Берга, Ван Кревельда, Овермарса и Шварцкопфа [14], Фарбера [25], Гиббонса [28], Килгора [31] получены решения переговорных задач двух лиц с нулевой суммой при участии одного арбитра в контексте установления заработной платы, а в работе Мазалова и Токаревой [33] найдено равновесие в такой задаче при участии арбитражного комитета.

Особый интерес представляют прикладные задачи, связанные с моделированием сдерживания. Большая часть моделей игнорирует соглашения о разделе и анализ их устойчивости. Сдерживанию в международных отношениях посвящены работы Жагаре и Килгора [51], Пауэлла [42], Брамса и Килгора [17]. Хиршлейфер [30], Гарфинкель и Скарпедас [26] разработали модель, в которой присутствует хищник - одна из сторон, которая пытается присвоить то, что получают другие. Перечисленные модели основаны по большей части на экономических сравнениях затрат и прибыли. Брамс и

Килгор в работе [16] строят теоретико-игровые модели, которые абстрагированы от этих деталей и призваны ответить на вопрос, следует ли пытаться захватить то, что получает соперник.

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

1. Задача переговоров п лиц со случайными предложениями и голосованием;

2. Задача переговоров п лиц, связанная с проведением конкурса;

3. Задача переговоров о распределении ресурсов с возможностью установления приоритета.

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

Научная новизна работы заключается в применении теоретико-игровых методов к различным стохастическим моделям проведения переговоров.

В задаче о распределении ресурса предложена многошаговая модель со случайными предложениями арбитра. Определён вид оптимальных стратегий и найдены выигрыши для случаев, когда решение о дележе принимается по правилу большинства и по правилу полного консенсуса. Используются как симметричные, так и несимметричные параметры распределения арбитра. Расмотрен случай добавления игрока с правом вето. Получено обобщение

модели, где для принятия окончательного решения о дележе требуется согласие р игроков из п.

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения:

1. Найдены равновесия в классе пороговых стратегий в теоретико-игровой задаче о разделе ресурса для п лиц с арбитром, представленным многомерным распределением.

2. Найдено равновесие в задаче о проведении конкурса для п > 3 лиц с использованием арбитражной процедуры, основанной на многомерном распределении, и для п > 2 лиц с линейными функциями полезности

при участии арбитражного комитета.

3. Предложена и исследована теоретико-игровая модель распределения ресурса для двух лиц с приоритетом одного из игроков и с равноправными игроками.

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

1. VIII Международная конференция «Вероятностные методы в дискретной математике» и летняя сессия XIII Всероссийского симпозиума по прикладной и промышленной математике, 2-9 июня 2012, Петрозаводск.

2. Шестая Международная конференция «Game Theory and Management», 27 - 29 июня 2012, Санкт-Петербург.

3. Международный семинар «Networking Games and Management», 30 июня - 2 июля 2012, Петрозаводск.

4. Восьмая Международная конференция «Game Theory and Management», 25 - 27 июня 2014, Санкт-Петербург,

а также на семинарах кафедры фундаментальной и прикладной математики, теории и методики обучения математике факультета естественных наук, математики и технологий Забайкальского государственного университета, г. Чита, и семинарах лаборатории математической кибернетики Института прикладных математических исследований Карельского Научного Центра РАН, г. Петрозаводск.

По материалам диссертации опубликовано 11 работ, из них 7 статей [5,7-10,35,38], среди которых две в изданиях, рекомендованных ВАК [5,10],

и одна в журнале, включённом в базу данных Scopus [35], а также тезисы 4 докладов [11, 39-41]. Диссертация поддержана грантами РФФИ (проект 12-01-90702-моб_ст) и Минобрнауки РФ в рамках Государственного задания вузу № 8.3641.2011.

Структура и объем работы. Диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и двух приложений. Во введении отражена актуальность работы, приведен краткий обзор литературы по теме диссертации, поставлена цель исследования, обоснована новизна работы, сформулированы положения, выносимые на защиту, показана практическая ценность полученных результатов.

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

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

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

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

В заключении представлен свод результатов, полученных в ходе исследований в рамках диссертационной работы. Общий объем диссертации составляет 119 страниц. Список литературы включает 50 наименований.

Глава 1. Процедура проведения переговоров в задаче о распределении ресурсов со случайными предложениями

Рациональное распределение ограниченных ресурсов всегда являлось первостепенной задачей как для любой производственно-экономической системы, так и для общества в целом. Это могут быть природные, материальные, финансовые, трудовые или иные ресурсы. Например, в условиях рыночной экономики распределение ресурсов сводится к установлению, что, как и для кого производить. Решение о том, что нужно производить, принимается исходя из предпочтений потребителей. На рынке ежедневно происходит своего рода голосование: потребители «голосуют» денежными единицами, приобретая тот или иной товар либо услугу. Конкуренция за доступные факторы производства диктует фирмам, как производить. При этом предприятие должно подобрать наиболее эффективные методы производства таким образом, чтобы минимизировать затраты и максимизировать свою прибыль. Платёжеспособность является определяющим фактором в вопросе о том, для кого производить. Предприятия производят продукцию для тех, кто имеет доход и, соответственно, может её приобрести.

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

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

из них получает некую величину Ъ, где Ъ « —.

п

Мы предполагаем, что генератор случайных чисел представлен распределением Дирихле с плотностью

1 71

/(ж1, . • • , хп) — П Жг! '

п

где > 0, ^ Хг — 1 и кг > 1. Константа В (к) в этом распределении

г=1

п

П Г(Ъ)

г=1

Г(А?1 + •■■ + &„)

зависит от набора параметров ..., кп), которыми можно регулировать веса участников.

1.1 Переговоры трёх лиц

Расмотрим задачу дележа пирога единичного размера для трех лиц. Пусть для переговоров отведено К шагов. Будем использовать обратный отсчет во времени. Пусть до конца осталось к шагов. Игроки получают предло-

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

Нхл Хо X*) ~ + + **) kl-l fa-1 Jb-1

при ЭТОМ X\ + X2 + Жз = 1.

После поступления пакета предложений (xi,X2,xs) кажДь1й из игроков должен решить, принимает ли он данное предложение или нет, ожидая более удачное предложение в будущем. Мы рассматриваем два сценария окончания процесса переговоров: полный консенсус и правило большинства. В первом случае, если на каком-то этапе переговоров все игроки согласны, осуществляется дележ (xi,x2,xz). Во втором случае, дележ осуществляется, если большинство игроков согласны с этим предложением. В противном случае игроки переходят на следующий шаг к — 1. При этом происходит дисконтирование и на следующем шаге игроки делят пирог размера 5 < 1.

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

игра закончится, как только наступит шаг к — 0. В этом случае все игроки

1

получат куски малого размера о « -.

О

1.1.1 Полный консенсус

Рассмотрим переговоры, в которых окончательное решение принимается при полном согласии игроков. Обозначим Нк значение данной игры в

состоянии, когда до конца переговоров остается к шагов. Предположим, что каждый игрок информируется только о значении его собственного предложения. Пусть (xi, Х2, хз) предложения игрокам I, II, III соответственно. Так как х\ + Х2 + хз = 1, достаточно рассматривать лишь переменные Х\ и х2.

Исследуем симметричный случай с распределением Дирихле с параметрами к\ = к2 — к% = 2. Функция совместной плотности распределения имеет вид

f(xi,x2) = 120Ж1Ж2(1 - xi - х2), xi + x2<l, xi,x2>0.

Введём в рассмотрение стратегии ßi(xi) (fi2(x2), //з(гсз)) - вероятность того, что игрок I (II, III) примет текущее предложение xi (х2, жз). Обозначим Д(-) = 1 — В силу симметрии задачи, равновесие будем искать среди одинаковых стратегий игроков.

Теорема 1.1 Оптимальные стратегии игроков на k-м шаге имеют вид

где 1а - индикатор события А.

Значение игры удовлетворяет рекуррентным соотношениям

Доказательство. Уравнение оптимальности для выигрыша на к-м ша-

ßi(xi) = I{Xi>5Hk_!>, i = 2,3,

Нк = -(1 - 2>5Hk_if(l + 66Hk_i - З^Я^ - Ш3^) + ÖHk—i, H0 = b.

1

ге имеет вид

1

о

1-Ж1

J Х2{1-XI- Х^)АХ2 {(^1/^2^1 + (1 - Ц1/Л21Мз)&Нк-1}

к = 1,2,..., Н0 = Ь.

Преобразуя уравнение (1.1), получаем

Нк = зир120 / х\11\{х{)<1х1 ^

ал)

1 —

I {(^1 - 5Нк_х) /¿2Дз} Ж2(1 - XI - Х2)(1Х2

(1.2)

Игрок I стремится максимизировать свой выигрыш. Обозначим

1—XI

Ск(хг) = хг (х\ - 5Нк~\) J х2(1 -хг- £2)^2/^3^2 •

Оптимальная стратегия игрока I имеет вид

/21 (ал)

1. если Ск(х 1) > О, О, иначе.

(1.3)

В силу симметрии задачи заключаем, что оптимальное поведение игроков II и III должно быть одинаковым, т.е. ¡12 = //3. Заметим, что С^(0) < О и 6^(1) > 0, поскольку 0 < 5Нк < 1. Значит За, для которого = 0.

Будем искать равновесие в данной игре среди пороговых стратегий. Пусть ^2(Х2) = 1{х2>а}, -XI- Х2) = 1{ 1 -Х1-Х2 >а}- Достаточно рассмотреть два случая

1. При а < х\ < 1 — 2а имеем

1—XI

J /Л2АЛ3Ж2С1 -Xi- x2)dx2 =

l—Xi—a

J x2(l -xi- x2)dx2 = i (4a3 - 6a2( 1 - xi) + (1 - xi)3) .

a

2. При Xi > 1 — 2a рассматриваемый интеграл равен нулю.

Отсюда

Gk(x 1) = xi{xi - 5Нк-\)-• Q (4a3 - 6a2( 1 - Xl) + (1 - ^i)3) • I{x 1 < 1 - 2a} + 0 • /{1 - 2a < хг < 1}^ .

Поскольку Gk(a) = 0, то a = 5Нк-1- А значит, Gk(x 1) можно переписать в виде

Gk(x 1) = - 6Нк_i)-

• Q (4- 6<52Fti(l - si) + (1 - *i)3) • /{Ж1 < 1 - 2¿tffc_1}+

+0 • /{1 - 26Hk-i <хг< 1}^.

Таким образом, если игроки II и III используют пороговые стратегии №{х2) = мз(1 - - ж2) = /{l-n-sa^fc-!}, наилучшим ответом

игрока I будет fii{xi) = /{^¿я^}-

Тогда имеет место равенство

1 l-Xi

Нк = 120 Jxidxi J {(si - 5Нк~i) (Л2Ц3} х2{1 ~ xi - x2)dx2 + 6Hk-i =

I Х1{Х1 - 5Нк.х) (4¿3Я£-1 - 6д2Н1_г{1 - хх) + (1 - Х1)3) (Ьц =

20

Окончательно получаем рекуррентную формулу

Нк = тк_г +1(1 - з^_х)3(1 + - 352н1_х - Шън1_х).□

1.1.2 Правило большинства

Пусть теперь решение о дележе принимается с учётом мнения большинства, т.е. по меньшей мере двух игроков. Снова предполагаем, что для переговоров отведено К шагов и предложения на к-м шаге (х^х^х^) распределены по закону Дирихле с параметрами к\ = к2 = = 2.

Теорема 1.2 Оптимальные стратегии игроков на к-м шаге имеют вид

/Лг(Жг) = 1{х>>6Нк-г}, г = 1, 2, 3. Значение игры удовлетворяет рекуррентным соотношениям

Нк = \- Ю^Я^а - ЗОД^ХЗ - 4<Щь_1), Но = Ъ.

Доказательство. Уравнение оптимальности для выигрыша на к-м шаге имеет вид

1 1—XI

Нк = Бир 120 J х\йх\ J Х2(1 -XI- х2)(1х2 {(¿¿1//2Мз + Д1/Л2МЗ+

М1 о о

+Д1Д2МЗ + + (/¿1Д2Д3 + Д1Д2Д3+

+Д1Д2М3 + Д1Д2Дз)ОДь-1} , А; = 1,2,..., (1.4)

где #0 = 6, М1 = тЫ), М2 = /¿2(^2), Мз = Мз(1 - жх - ж2). Преобразуя выражение (1.4), получаем

1

Нь = вир 120 / х\ • 11\(х\)<1х1 ^

о

1-Ж1 "1 1

J {(Ж1 - £#¿-1) (/¿2 + из - 2^2/лз)} а:2(1 - хг - ж2)<йЕ2 + 120 £

о

1 — XI

О

J {(®1 - (Ш^-х) Д2МЗ + <Щс-1> Ж2(1 - XI - х2)йх2

+ бНк-1- (1.5)

I. о

Цель игрока I максимизировать свой выигрыш. В формуле (1.5) он может повлиять только на значение первого интеграла. Обозначим

1—Х\

Ск(х1) =Х1 ! {(ал - 6Нк-1) {ц2 + ¿¿3 - 2/л2£*з)} ж2(1 - ал - х2)(1х2. о

Оптимальная стратегия игрока I по-прежнему имеет вид (1.3). Равновесие находим в классе пороговых стратегий ¡л2(х2) = 1{Х2>а}> Дз(1 ~ зл — = 1{1-Х1-Х2>а}- Рассмотрим три случая

1. При 0 < х\ < 1 — 2а получаем

1—XI

J (/*2 + Мз - 2д2Дз) Ж2(1 -XI- х2)йх2 =

1—Х\

= J х2(1 - XI - х2)с1х2 + J Х2(1-Х1~ х2)<1х2 = ^а2 (3 - Зя^ - 2а).

0 1— хг~ а

2. При 1 — 2а < хх < 1 — а значение указанного интеграла будет описываться формулой

1—хх—а 1— XI

У х2{1 -XI - х2)йх2 + J х2{1 -Х\- х2)йх2 =

==^(1-Я1 + 2а)(1-Х1-а)2.

3. При 1 — а < х\ < 1 рассматриваемый интеграл равен нулю.

Найдём соответствующее выражение для второго интеграла формулы (1.5)

1—х\ 1—х\— а

У • Ег(1 ~х1- Х2)(1х2 - £ Х2(1 - XI — Х2)(1Х2 =

= ¿(1 - Ж1 - 2а)(1 + 2а - 2а2 - 2хг - 2ахх + х2). С учётом полученных выражений, можно записать

вк{х{) = х^хг - бНк-х) 0а2 (3 - За* - 2а) - 1{хг < 1 - 2а}+

I

+-(1 -Х! + 2а)(1 - хх - а)2 • /{1 - 2а < хг < 1 - а}+

о

+0 • /{1 — а < Х\ < 1}^.

Так как Gk(a) — 0, то а = öHk-Тогда

Gk(xг) = а* (а* - 6Нк_г) ßö2Я\_Х (3 - За* - 26Нк-{) ■ I{Xl < 1 -

+i(l - хх + 2<ША:_1)(1 - X! - ¿Я^)2. /{1 - 2ÖHk-! <X!<1- 5Hk-1}+

+0 ■ /{1 - ÖHk^ < xi < 1}).

Таким образом, если игроки II и III используют пороговые стратегии /-¿2 = I{x2>SHk_1}^ Из = 1{х3>5Нк_г}, то наилучший ответ игрока I также ßi = I{Xl>5Hk^}- Следовательно

1

Нк = 120 J xißi(xi) ■ Gk(xi)dxi+ о

1 1-Жх

+120 J x\dx\ J {(xi - ÖHk-i) + SHk-1} x2(l - xi- x2)dx2SHk-i =

о о

l-25Hk-i

= Ш2н1_г J Xi (xi - 5#fc_i) (3 - 3xi - 2öHk-i) dxi+

1 -tffc-i

+40 J xi (xi - ¿#fc_i) (1 - xi + 2£tfÄ_i)(l - xi - №fc_i)2ctei+

l-2Hk.

+20 J x\(xi — 5Hk_i){l — xi — 25Нк-\)'

0

c2 TT2

(1 + - 252Щ_1 - 2xi - 2öHk_iXi + xf)dxi +

Откуда получаем соотношение вида

Нк = ÖHk-! + з (1 - 35Яа_1) (1 - + 120(55Я|_1). □

1

1.1.3 Несимметричный случай в условиях полного консенсуса

Изменим теперь параметры распределения Дирихле и выясним, как это повлияет на оптимальное решение. Положим, например, к\ = 1, к2 = = 2. Тогда функция совместной плотности распределения примет вид

Заметим, что для игроков II и III задача симметрична. Как и ранее, ¡лi(rci), /¿2(£2), ~ вероятности того, что игрок I, II, III примет теку-

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

Теорема 1.3 Оптимальные стратегии игроков на k-м шаге имеют вид

f(Xi,X2)= 24ж2(1 - Ж1 - Ж2), Х\+Х2<1, Xi,X2>0.

Р1Ы) = ^^Л}

(i_)i}, ßiixi) = I{Xi>5Hmi} г = 2,3.

Значение игры удовлетворяет рекуррентным соотношениям

(1 - )2 + в (1 - «£>,) т® + 452 (я<2Л)2

2 (1 - ¿Я^ ] +7(1

Доказательство. Уравнение оптимальности для выигрыша игрока / на к-м шаге имеет вид

1

= яир24 [ Ах 1

J

1—Х\

У ж2(1 - - + (1 - М1М2М3) }

& = 1, 2,...,

гдеЯ^ = 6, /¿1 =/х^жх), /¿2 = ^2(^2), /¿3 = ^3(1-^1-^2)-Перепишем (1.6) в виде

(1.6)

= вир 24 / /¿1(2:1)^1

1—Ж1

У - /¿2/^3^2(1 - Ж1 - Ж2)<йС2

1_ о

(1.7)

Сгруппируем члены, содержащие множитель ¿¿1(3:1), и введём обозна-

чение

1—Х\

Оптимальная стратегия игрока I имеет вид (1.3). Будем искать равно-

весие в классе пороговых стратегий. Пусть

= 1{Х1>С}, /¿2(ж2) = 1{х2>а}, - XI - Ж2) = /{1-ая-®а>о}

При с < х\ < 1 — 2а имеет место равенство

1—XI

J -XI- Х2)(1Х2

1—XI—а

/

1

ж2(1 -XI- х2)Лх2 = ^ (4а3 - 6а2(1 - я*) + (1 - Х1)3)

В остальных случаях этот интеграл равен нулю. Учитывая а = 6Н^ и с = можно записать

я!1' = 4

/

1 -

(V (я<2_\)3 - 652 (Я<2_\)2 (1 - + (1 - хх)3) Лг, + ЗН^.

Таким образом, уравнение оптимальности для I игрока на к-м этапе

принимает вид

1 - ¿Я«)2 + 6 (1 - ¿Я«) + 452 (Я<2Л):

+ 5Я«

Теперь рассмотрим уравнение оптимальности для игрока II

1 1-®2

вир 24 j йх2 J (1 - XI - {(/¿1^2/^2 + (1 -

М2 О О

О

1

= эир 24 / Х2/Л2(Х2)^Х2

/¿2 7 о

1-Ж2

У (х2 - Д1//3(1 - XI - х2)б£х1

I о

Обозначим

+

1-Х2

х2 - J /ад(1 - XI - Х2)^1

При а<Х2<1 — с — а получаем

1-Ж2

J ц- XI - Х2)с?Х1 =

1—Ж2—а

! (1 - XI - Х2)С?Х1 = 1 ^(1 - С - х2)2 - а2) . с

Тогда выражение (1.8) можно записать следующим образом

х-^Л-гя^Л

/

¿"ГЛ

Окончательно, для игрока II имеем

• 2 (1 - 6Н£\)2 + 7 (1 - гя&) «Я« - 2^ (я®,)2] + «я«о

Л-1

1.1.4 Несимметричный случай в условиях правила большинства

Параметры распределения оставим неизменными к\ — 1, к2 = кз — 2. Найдём решение в данной задаче для случая, когда окончательное решение принимается по правилу большинства.

Теорема 1.4 Оптимальные стратегии игроков на к-м шаге имеют вид

НчЫ = 1{Х1>6Н£)1}

(1_)1}, Иг(хг) = 1{х.>днт1} г = 2,3.

Значение игры удовлетворяет рекуррентным соотношениям

2

2 - 2*3 (Я«)' (10 + 56НЦ - 1М» (Я«)2)

(б + (Я'?,)2 - 7М» )3 + 235* (Я<2Л)6)

-4Í» (я«)2 (4 - т?\ + 25Н^ (я<2Л)2)

+

Доказательство. Уравнение оптимальности для выигрыша игрока I на к-м шаге имеет вид

я<" =

1 1-Я1

sup 24 J dxi J x2(l-xi- x2)dx2 {(/íi¿¿2A¿3 + Д1М2/Л3+

+A¿l/¿2/¿3 + + (/¿l/¿2/¿3 + A¿lA¿2A¿3 +

+М1М2МЗ + м^Мз)^1-^}

к — 1,2,...,

(1.9)

где Я^ = 6, /¿1 = ^(хх), ц2 = ц2(х2), № = цъ(\- XI- х2). Перепишем (1.9) в виде

Я,

(i)

i

sup 24 / /¿i(xi)GÍa:i Mi J

l—Xi

J | (xi - (Ш^) (fj,2 2/¿2/i3)} 2:2(1 - Ж1 -

+

1 l-xi

+24 J dx\ J + (1.10)

o o

Сгруппируем члены, содержащие множитель ¡ii{xi), и введём обозна-

чение

G«^) = [х, - М^)

1 — XI

J (М2 + Мз - 2/л2Мз) Ж2(1 - - х2)йх2.

о

Оптимальная стратегия игрока I имеет вид (1.3). Будем искать равновесие в классе пороговых стратегий. Пусть

М1ОС1) = ^{х^ф &(х2) = 1{х2>а}, Дз(1 - XI ~ Х2) = 1{1-Х1-Х2>а].

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

= (хг - 6Н£\) ^а2 (3 - За* - 2 а) • /{О <Х\<\ — 2а}+

+1(1 - хг + 2а) (1 -XI- а)2 • /{1 - 2а < х\ < 1 - а}+ о

+0 • /{1 - а < хг < 1} ).

Учитывая а = 5н[2^

к-л ис =

получаем

1

о

1 —XI

+ ¿Щ-1 Г Х2(1 ~ XI - х2)с1х2

0

0

+8 I (хг - (1 - ал + 26Н^) (1-хг- 6Н^ йхг+

1-2 я<2Л

1-2 Я&

+4 I (Х1-5Н£}1)(1-Х1-26Н12\)-о

• + 25 Н^ - 252 (н£\У - 2X1 - 28Н{*\хх + х2^ йхх + дН^.

Таким образом, уравнение оптимальности для I игрока на к-м этапе принимает вид

= 7

к 5

1 1 - Ьбн£\ + Ш» (Я<2Л) • (шя«! - 9 - шя^я® + 1М> (я®)

Запишем теперь уравнение оптимальности для игрока II

+«е

1 1-®2

Я^2) = вир 24 / х2сЬ2 / (1 - - {(/^/^/¿з + Д1Д2М3+ Ц2 J J

О

+М1Д2МЗ + /¿1/4гДз)®2 + (М1Д2Д3 + Д1/^Дз+

+Д1Д2/ЛЗ + Д1Д2Дз)^2_)1}, А; = 1,2,..., (1.11)

гдеЯ,52) = 6, /¿1=М1(ж1), = /¿2(^2), /¿3 = ^3(1-^1-^2). Перепишем (1.11) в виде

1

Я^2) = вир 24 / Х2/Л2(х2)<£с2

М2 ./

1-Х2

J | (х2 - (т + ^з - (1 х\ х2)йх2

[_ 0

1 1-Х2

+

+24 J х2Ах2 J { (®2 - им + ¿Я^} (1 - ал - х2)Ах2. (1.12)

о о

Обозначим

С^\х2)=х2 (х2-6Н

1-х2

J (^1 + Дз - 2/Х1/х3) (1 - XI - х2)Ахг.

Имеем три возможных варианта

1. При 0 < Х2 < 1 — с — а получаем

1 — Х2

J (/¿2 + Из ~ 2/^2МЗ) (1-Х1- Х2)АХ1

с 1-х2

У{1 — х\ — х2)йх\ + J (1 — х\ — х2)(1х 1 = 1 (а2 — с2 + 2с — 2сж2)

1—Ж2—а

2. При 1 — с — а < ал < 1-е значение указанного интеграла будет описываться формулой

1—Х2~ а 1—х2

! (1 — Ж1 — Х2)бХ\ + J (1 - XI - х2)(1х 1

= \ (с2 - а2 - 2с(1 - х2) + 2(1 - х2)2) .

3. При 1 — с < х\ < 1 рассматриваемый интеграл равен нулю.

Значение второго интеграла формулы (1.12) равно

1—Х2 1—Х2—а

У • (1 - Х1 - х2)АХ1 = J (1 - XI — Х2)(1Х1 =

О с

= 1((1 -*2-с)2-а2).

Тогда уравнение оптимальности для игрока II на к-м шаге можно записать следующим образом

1

о

1 1-Х2

+24 J х2<1х 2 У { [х2 - ¿Я^) /л^з + ¿Я^} (1-Х!- х2)(1х2 = о о

1-511^-511^

12 У (х2 - 6Н

'2 (ЯЕ)2 " ¿2 (Я^)2 + - 25Н^х2) <1х2+

+12 У я2 (ж2 - ¿Я^)

¿2 КЛ)2 - ¿2 (Я12Л)2 ~ 2^(1 - Х2) + 2(1 - х2)^ <1х2+

+12 У х2(х2-5Н^) ((1 - - 6Н^)2 - б2 (я!2Л)2)

Окончательно, для игрока II имеем

я?» = А

2 - 2<53 (Я«,)3 (lO + 5<_\ - IM» (ЯЦ\)2) --ÖHf\ (б + 4СМ2 (я®)2 - 70(53 (я<2Л)3 + 23? (я^)5) -

-4,? (н<£\)2 U - SH?\ + ¡Ш&У (я<2_\)2) -

-^(^'(s-Ti*®)'

1.2 Переговоры четырёх лиц

1.2.1 Правило большинства

Исследуем теперь задачу о разделе пирога для четырёх лиц. Предположим, что параметры распределения Дирихле симметричны и равны = к2 = кз = к± = 1. Тогда функция совместной плотности распределения имеет

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Носальская, Татьяна Эдуардовна

Заключение

В настоящем диссертационном исследовании представлены стохастические теоретико-игровые модели переговоров.

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

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

Предложена многошаговая процедура распределения ресурса для двух

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

Результаты, полученные в ходе диссертационного исследования, имеют как теоретическое, так и прикладное значение.

Список литературы диссертационного исследования кандидат наук Носальская, Татьяна Эдуардовна, 2014 год

Литература

1 Воробьёв Н. Н. Теория игр для экономистов-кибернетиков /H.H. Воробьёв. — JL: Издательство Ленинградского университета, 1974. — 160 с.

2 Дюбин Г. Н. Введение в прикладную теорию игр / Г.Н. Дюбин, В.Г. Суздаль. — М.: Наука, 1981. — 336 с.

3 Мазалов В. В. Математическая теория игр и приложения: учебное пособие - СПб.: Лань, 2010. - 448 с.

4 Мазалов В. В. Менчер А. Э. , Токарева Ю. С. Переговоры. Математическая теория. — СПб — М. — Краснодар: Лань, 2012. — 304 с.

5 Мазалов В. В. , Носальская Т. Э. Стохастический дизайн в задаче о дележе пирога // Математическая теория игр и её приложения. Петрозаводск, 2012. Т 4. Вып. 3. — С. 33-50.

6 Мазалов В.В., Токарева Ю.С. Теоретико-игровые модели проведения конкурсов // Математическая теория игр и её приложения. 2010. Т2, вып.2. - С. 66-78.

7 Менчер А. Э. , Носальская Т. Э. Об одной задаче распределения активов // Учёные записки Забайкальского государственного гуманитарно-педагогического университета им. Н.Г. Чернышевского. Чита: ЗабГГПУ, 2009. Т2, вып.25. - С. 84-91.

8 Носальская Т. Э. Марковские стратегии с памятью 1 в игре с приори-

тетом // Промышленная и экологическая безопасность на транспорте: Межвузовский сборник научных трудов. Чита: ЗабИЖТ, 2010. Т2. N 25. - С. 160-166.

9 Носальская Т. Э. Последовательная модель без приоритета в задаче распределения ресурсов // Математический анализ и его приложения. Чита: ЗабГГПУ, 2010. Вып. 9. - С. 36-42.

10 Носальская Т. Э. Правило большинства в задаче наилучшего выбора для трёх лиц // Учёные записки Забайкальского государственного гуманитарно-педагогического университета им. Н.Г. Чернышевского. Чита: ЗабГГПУ, 2012. Т 3. N 44. С. 9397.

11 Носальская Т. Э. Модель последовательных переговоров с голосованием в задаче о разделе единичного ресурса // VIII Международная конференция «Вероятностные методы в дискретной математике» и летняя сессия XIII Всероссийского симпозиума по прикладной и промышленной математике, 2-9 июня 2012, Петрозаводск. — с. 731

12 Токарева Ю. С. Модель проведения конкурса с оценкой отдельных параметров проектов // Труды Карельского научного центра РАН. — Петрозаводск: КарНЦ РАН, 2014. N4 - С.116-120

13 Baston V. Garnaev A. A Non-Zero-Sum War of Attrition. // Mathematical Methods of Operations Research, 1997. V. 45. Pp. 197-211

14 De Berg M., Van Kreveld M., Overmars M., Schwarzkopf O. Computational Geometry. Springer, 2000.

15 Brams J. S. Negotiation Games: Applying Game Theory to Bargaining and Arbitration — New York and London: Routledge. — 1990. — 302 p.

16 Brams J. S. , Kilgour D.M. The Instability of Power Sharing / / New York: New York University, Ontario: Wilfrid Laurier University. — 2005. — 24 p.

17 Brams J. S. , Kilgour D. M. Game Theory and National Security. — New York: Basil Blackwell. - 1988.

18 Brams J. S. , Kilgour D. M. , Davis M. D. Unravelling in games of sharing and exchange // Frontiers in Game Theory, MIT Press, Cambridge, 1993. - Pp. 194-212.

19 Brams S. J. , Taylor A. D. Fair Division: from Cake-Cutting to Dispute Resolution. Cambridge Univ. Press, 1996. — 272 p.

20 Brams S. J. , Taylor A. D. An envy-free cake division protocol // American Mathematical Monthly. 1995. V. 102. N 1. - Pp. 9-18.

21 Chatterjee K. Models with complete and incomplete information // IEEE Trans, SMC-11, 1981. - Pp. 101-109.

22 Crawford V. P. On Complusory arbitration schemes // Journal of Political Economy, 1973. N 11 - Pp. 131-159.

23 Dubins L. E., Spanier E. H. How to cut a cake fairly // American Mathematical Monthly. 1961. V. 68. - Pp. 1-17.

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

25 Farber N. An Analysis of Final-Offer Arbitration // Journal of conflict resolution. 1980. N 4. V. 24. - Pp. 683-705.

26 Garfinkel M. R. , Skaperdas S. The Political Economy of Conflict and Appropriation. — New York: Cambridge University Press. — 1996.

27 Garnaev A. Y. Value of information in optimal stopping games // Nova Sci. Publ, Commack, NY. 2000. V. 5 - Pp.55-64.

28 Gibbons R. A Primer in Game Theory Prentice Hall, 1992. — 278 p.

29 Hamers H. A Silent Duel over a Cake // Mathematical Methods of Operations Research. 1993. V. 43. - Pp. 119-127.

30 Hirshleifer J. The Dark Side of the Force: Economic Foundations of Conflict — New York: Cambridge University Press. — 2001.

31 Kilgour M. Game-Theoretic Properties of Final-Offer Arbitration // Group Decision and Negotiation, 1994. №3 Pp. 285-301.

32 Leitman G. Collective bargaining a differential game // Journal of Optimization Theory and Applications, 1973. N 11 — Pp. 405-412.

33 Mazalov V. V. Tokareva J. S. Arbitration procedures with multiple arbitrators // European Journal of Operational Research, v. 217, Issue 1. 2012. — Pp. 198-203.

34 Mazalov V. V. , Banin M. V. N-person best-choice game with voting // Game Theory and Applications, 2003. V 9. — Pp. 45-53.

36 Mazalov V. V. , Nosalskaya T. E. , Tokareva J. S. Stochastic Cake Division Protocol // International Game Theory Review, 2014. Vol. 16, N 2. — P. 1440009.

37 Mazalov V. V. , Sakaguchi M. , Zabelin A. A. Multistage arbitration game with random offers // Game Theory and Applications, 2002. V 8. — Pp. 95-106.

38 Nosalskaya T. E. Competition Form of Bargaining // Contributions to Game Theory and Management, 2014. V. VII. - Pp. 254-261.

39 Nosalskaya T. E. On a Discrete Model of the Cake Division Problem // International Workshop: Networking Games and Management. June 30 -July 2, 2012. Petrozavodsk - Pp. 45-46

40 Nosalskaya T. E. Sequential Bargaining Scheme in the Assets Sharing Problem // Game Theory and Management VI. June 27 - 29, 2012. St. Petersburg — Pp. 203-204

41 Nosalskaya T. E. Game-Theoretic Model of Negotiations with Incomplete Information // Game Theory and Management VIII. June 25 - 27, 2014. St. Petersburg — P. 41

42 Powell R. In the Shadow of Power: States and Strategies in International Politics. — Princeton, NJ: Princeton University Press, 1999.

43 Rubinstein A. Perfect Equilibrium in a Bargaining Model // Econometrica. 1982. Vol. 50(1). - Pp. 97-109.

44 Sakaguchi M. A simplified two-person multistage poker with optional stopping // Mathematica Japonica 28, 1983. — Pp. 287-303.

45 Sakaguchi M. A time-sequential game related to an arbitration procedure // Mathematica Japonica 29, 1984. - Pp. 491-502.

46 Sakaguchi M. Optimal stopping games for bivariate uniform distribution // Mathematica Japonica 41, 1995. — Pp. 677-687.

47 Sakaguchi M. Optimal stopping games where players have weighted priviledge // Game Theory and Applications 6, 2000. — Pp. 116-131.

48 Sakaguchi M. Best-choice game where arbitration comes in // Game Theory and Applications, 2003. V 9. — Pp. 141-149.

49 Steinhaus H. The problem of fair division // Econometrica. 1948. N 16. — Pp. 101-104.

50 Stromquist W. How to cut a cake fairly // American Mathematical Monthly. 1980. V. 87, N 8. - Pp. 640-644.

51 Zagare F. C. , Kilgour D. M. Perfect Deterrence. — New York: Cambridge University Press, 2000.