Теоретико-игровые модели переговоров тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

- 3 МР 1997

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

на правах рукописи СУРВИЛЛО Татьяна Геннадиевна

УДК 519.6

ТЕОРЕТИКО-ИГРОВЫЕ МОДЕЛИ ПЕРЕГОВОРОВ (01.01.09 - математическая кибернетика)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петрбург - 1997

Работа выполнена на кафедре Математической статистики, теории надежности и массового обслуживания Санкт-Петербургского Государственного Университета.

Научный руководитель: кандидат физико-математических

наук, доцент Н.А. Зенкевич

Официальные оппоненты:: доктор физико-математических наук,

профессор В.В. Захаров

кандидат физико-математических наук, доцент Г.Г. Ткаченко

Ведущая организация: Саратовский Государственный Университет.

Защита состоится "_"_1997 г. в

часов на заседании специализированного совета К-063.57.16 по защите диссертации на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском Государственном Университете по адресу: 190004, Санкт-Петербург, 10-я линия В.О., д. 33, ауд. 41.

С диссертацией можно ознакомиться в библиотеке СПбГУ им. А.М. Горького по адресу: С. Петербург, Университетская наб., 7/9.

Автореферат разослан "_" февраля 1997 года.

Ученый секретарь Диссертационного

совета, д. ф.-м. н. В.Ф. Горьковой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Исследования в области теоретико-игрового моделирования переговорных процессов активно ведутся в течение последних двух десятилетий в ряде стран. Свой вклад в области пр ил ожигай теории игр к анализу реальных процессов внесли H.H. Воробьев, Ю.Б. Гермейер, JI.A. Петросян, H.H. Моисеев, Е.Б. Яновская, И.С. Меньшиков, В.В. Захаров, H.A. Зенкевич и другие. За рубежом разработкой теоретико-игровых подходов к моделированию переговоров занимались С. Брамс, К. Бинмор, Р. Зелтен, Э. Калаи, Дж. Нэш, А. Рот, А. Рубинштейн, Д. Фуденберг, Дж. Харсани и другие.

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

Целью настоящей работы является построение и исследование теоретико-игровых моделей динамических переговоров.

ч

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

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

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

Апробация работы и публикации. Материалы диссертации опубликованы в работах [1 - 6]. Результаты исследований, представленные в работе, прошли апробацию на международных конференциях: Internaitonal Congress on Computer Systems and Applied Mathematics (С.Петербург, 1993), International Conference of Interval and Computer-Algebraic Methods (С.Петербург, 1994), Международной конференции по математическому моделированию (Якутск, 1994), Decision-Making in Future (Amsterdam, 1995), N.N.Vorob'ev Memorial Conference (С.Петербург, 1996); международном научном конгрессе "Народы содружества независимых государств накануне третьего тысячелетия" (С.Петербург, 1996). Кроме того, основные

результаты работы докладывались на городском семинаре по теории игр под руководством проф. Л.А. Пстросяна (Санкт-Петербург) и на семинарах кафедры математической статистики, теории надежности и массового обслуживания Санкт-Петербургского государственного университета.

Структура. Диссертация состоит из введения, двух глав, списка литературы из 63 наименований и имеет общий объем 110 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В § 1.1. приведено теоретико-игровое описание процесса переговоров. Предполагается, что в основе переговоров лежит конфликт п лиц, описываемый конечной игрой в нормальной форме Г=<1, {Х*}^, {11.} ¡<=1 ), где X] ......... Хпи}- конечный набор возможных предложений или действий ьго трока; К,\Х->[1, 2, ..., П,=1..пш,] - отношения ранга допустимых ситуаций игрока ¡, причем

&

наихудшая для игрока ситуация имеет ранг 1 и названа в работе конфликтной точкой, множество которых обозначается К.

В § 1.2. дано определение схемы переговоров и приведены правила соответствующих процедур.

Схемой переговоров названа система правил, которая игре Г, заданной ситуации х° и фиксированному порядку игроков ставит в соответствие некоторую ситуацию х*. В работе исследованы схемы переговоров, которые определяются следующей системой правил.

Р. Начальная ситуация. Игра начинается с некоторой начальной ситуации х°, которая задана до начала игры и определяется историей конфликта.

2°. Очередность. Любой из игроков может изменить свою стратегию и перевести игру в новую ситуацию, после чего право выбора стратегии переходит к следующему по порядку в множестве I игроку.

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

3°. Рациональность (доброжелательная). Игрок i, i=l..n, при выполнении хода выбирает новую стратегию х!е Xi так, чтобы выполнялось:

Ri(x*/xi\xM(xi")) = max Я(х*/хпхм(х,))>^х*) (1)

Ri+1(x*/xi,xi+1(xi))>Ri(x*), (2)

где Rw(х*/Xi,xi+1 (Xj))= naxR,(x */х;,xl4,), (3)

т

х* - текущая неконфликтная ситуация, х+1(») - наилучший ответ (¡+1)- го игрока на ситуацию (х1..х*м, х, х*+1..х*п).

Игрок п, пользуясь концепцией наилучшего ответа, предполагает реакцию игрока I.

4°. Рациональность (конфликтная). Игрок 1=1..п, при вьтолнении хода из своей конфликтной ситуации выбирает

стратегию Х°б)ч так, чтобы:

Щх */х;,хм (*,")) = тахД,.(х »- (4>

1 в -Т

где х* - текущая конфликтная ситуация, и хм(х;) - наилучший ответ игрока (х+1) на стратегию ж

(х * /х,, хы (х,))= тах II, (х* /х,, хм). (5)

5°. О с т а н о в к а. Процесс переговоров продолжается до тех пор, пока очередной игрок не остановится (т.е. согласится с текущей ситуацией) и ни один из игроков не захочет продолжать игру:

тахЯ|(х*,...х *[_1,х1,хы(х1)...хп*)<Км(х*)Л=1..п, (6)

и/или 11ы(х*1)...х^хы(х1)...х*п) <Иы(х*), (7)

для всех х^х*1, х^еХь где х* - текущая ситуация, хм(х1) - наилучший ответ игрока (¿+1) на стратегию х,. Это означает, что для установления окончательного решения необходимо согласие всех игроков.

а

5к°. Остановка (конфликтная). Процесс переговоров продолжается до тех пор, пока очередной игрок не остановится (т.е. выберет повторно свою текущую стратегию):

тахК;(х*,...х , х;, (х*), (8)

где х* - текущая ситуация, х^х;) - наилучший ответ игрока з на стратегию х^5).

6°. Ц и к л. Возвращение в процессе игры дважды в одну и ту же ситуацию (точку цикла) на ходе одного игрока означает цикл. В этом случае игра прекращается и результатом становится точка цикла.

Ситуация, в которой останавливается движение, названа результатом переговоров и результат переговоров, установленный согласно (7), точкой компромисса.

Приведенные правила позволили сформировать две схемы переговоров: а) из правил 1°, 2°, 3°, 4°, 5°, 6° - доброжелательная схема; б) из правил 1°, 2°, 4°, 5К°, 6° - конфликтная схема.

Теорема 1. Процесс переговоров, происходящий по "доброжелательной" и "конфликтной" схемам, всегда заканчивается за конечное число ходов.

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

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

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

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

В § 1.4 рассмотрена схема переговоров в общем виде как игра на графе, стратегией в которой является способ поведения игрока в ходе переговоров, а результат устанавливается при согласии всех игроков. Тогда правила 3°, 4° являются одними из возможных стратегий в игре на графе.

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

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

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

Схема определяется следующими правилами.

1°. Начальная точка. Переговоры начинаются с одновременного объявления всеми игроками своего наилучшего выбора: R, (х?) = maxRj (х), х° е X

хеХ

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

При этом игрок i в раунде к предлагает некоторый исход Xi так, чтобы

R:(xh = max R(>$ ä: min R.(x),где (9)

хег* 1 jeY'1"1 1

P* ={xeX: xeV4xi,...,xik1,x>xf;1l)...,x;;-1)} , (10)

иначе xf s xf"1,

где И"7 (XIе'1)- множество результатов предыдущего раунда и задается следующим образом:

Xj eV(x,,...,xn) o\7kj £<7к(х^> 2>k(Xj). О1)

к=1..п к=1..п

где

il, Хк = X:

*к0ч>= Г * '

р, Хк Ф Xj

н

3°. Правило остановки. Переговоры считаются законченными, если ни один из игроков не изменяет своей страте-

k k-1 k ✓ k k ч

гии: x s x , x = (x,.....xn), и окончательным соглашением

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

4°. Правило второго тура. В последнем случае проводятся дополнительные переговоры, началом для которых служит набор стратегий последнего раунда с результатом d. При этом результатом 2 F раунда второго тура может быть либо предложенное наибольшим числом игроков соглашение, если Vk(xk) одноэлементное множество, либо d.

Теорема 2. Переговоры, проведенные в соответствии со схемой "простого большинства", всегда заканчиваются принятием соглашения х* не более, чем за два тура. В каждом туре количество раундов не превосходит (min{ т, п}+1) раундов, где т - количество допустимых ситуа ций в игре Г, если R-(d) =1, i=l..n.

Следствие 1. Переговоры, проведенные в соответствии со схемой "простого большинства " по правилам 1° - 3° всегда заканчиваются не более, чем за (min{n, т}+]) раундов.

Построенная схема исключает возможность возникновения парадокса голосования Кондорсе.

В § 1.6. построено обобщение доброжелательной и конфликтной схем для произвольных игр в нормальной форме Г-(1, {Xi}ieI, {Ri}ie! \ где Xi, iel, - подмножества конечномерного пространства, u-v iel, - функции полезное™ игроков на множестве ситуаций X.

Схемы переговоров задаются теми же правилами, что и в §1.2 за исключением правил рациональности. Здесь под наилучшим ответом штоков на стратегию Xi понимается ситуация вида:

Ь I\{1 .i) (Х*/Х; ) = (Х, *.. Х;_, *, х,, х1+1 (xs).. хп (х;)), (12)

где Xj(Xi), j>i строятся последовательно следующим образом:

иы(х*/х;>хы(х;)) е Q ( sup ц+1(х*/^,

х еК

и; + 2(Х*/Х;,Х; + 1(Х;),Х;+2(Х^) б0£ ( SUp U;+j (X * /Ц , ХЫ (Х; ), Xj+2 )) ,

хек

Х...ЕХ,.,

и так далее.

3°. Рациональность (доброжелательная). Игрок i при выполнении хода выбирает новую стратегию Xi е Xi так, чтобы выполнялось условие:

Ui(bl\}..i}(X*/Xi ))>Ui(X*) :

>с GK

(13)

GW; (x*) ,

(14)

где х* - текущая неконфликтная ситуация, хм^) - наилучший ответ (¡+1)- го игрока в ситуации (х*1..х*м, ха, х*1+1..х*п). Игрок п, пользуясь концепцией наилучшего ответа, предполагает реакцию игрока 1.

в

4°. Рациональность (конфликтная). Игрок 1 при выполнении хода из своей конфликтной ситуации выбирает стратегию ХР е X так, чтобы:

1^(Ь1чи)(х*/х?) еОг ( 5ирц (Ь,чи)(х )), (15)

хд

I I

где х* - текущая конфликтная ситуация, и - наилучший ответ игрока] на ситуацию (х*/хО.

Теорема 3. Пусть последовательности (ц; (ЬЦ) (х1 / х,))} ь > сходятся в естественной топологии и

существуют по крайней мере два таких игрока Щ, что е' ФеК Тогда решение В* (Г, х°), установленное вследствие нарушения условия (15), при любой начальной ситуации 1 достигается за конечное число раундов.

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

Специальное исследование проведено для игр двух лиц с множествами стратегий из Яи непрерывными функциями полезности. Удалось показать, что в условиях выпуклости и компактности множества X точка компромисса, установленная вследствие нарушения условия (14) может быть рассмотрена как арбитражное решение, соответствующее арбитражной схеме В, поскольку удовлетворяет свойствам симметричности, независимости от масштаба и эффективности.

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

В § 2.1 сформулирована конечная бескоалиционная игра Г ) п лиц на интервалах, где Н;(х)=['ах~, 1ах], Ь1(х)еН1(х:). Предполагается, что границы интервалов известны всем игрокам.

Равновесной ситуацией в игре Г названа ситуация х*, для которой найдутся значения выигрышей к,(х)е['ах~, 1ах], удовлетворяющие неравенствам:

Ь^х^ЦСх*/^), X; х; еХ; (16)

Теорема 5 .Для того, чтобы ситуация х*е X была равновесной в смысле определения (16) необходимо и достаточно, чтобы для нее выполнялись условия:

' > тах('сГЛ ), 1 =1.. п, (17)

причем выигрьпп в равновесной ситуации находится в следующем интервале:

Ь, (х*) е[ гт^; а ^ Х!,' , 1= 1 ..п. (18)

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

В § 2.2 игра на интервалах рассмотрена как задача принятия решения в условиях неопределенности, когда неопределенным фактором является величина выигрыша при заданном исходе. Неопределенность оценивается с помощью критериев Вальда, Лапласа, Сэвиджа и Гурвица. В качестве решения игры рассматривается равновесие по Нэшув смешанных стратегиях для бескоалиционной игры, построенной согласно выбранным критериям. Показано, что критерий Гурвица является обобщающим для всех остальных критериев, и, в то же время, он является частным случаем подхода, изложенного в § 2.1.

В § 2.3 проведен анализ почти антагонистических игр на интервалах. Получен частный случай теоремы 5.

В § 2.4 исследованы матричные игры на интервалах как частный случай игры § 2.3. Решена задача построения по заданной матричной игре ГА такой игры на матричном интервале, которая имеет по крайней мере одну равновесную ситуацию.

Теорема 6. Для любой матричной игры ГЛ размерности тхп можно построить соответствующую игру на матричном интервале Г(А-ЗЕ, А+5Е),8>0, где Е={^}, Сц -1, г-1..т, }-1..п, имеющую по крайней мере одну равновесную по Нэшу ситуацию.

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

Предполагается, что выигрыши игроков зависят от номера хода 1;, на котором принято соглашение: И; (^ О 6*-' ].

{Ь

Переговоры описываются многошаговой позиционной игрой ГФ.

Теорема 7. Рассмотрим игру Га и две ситуации х*:

'а* =тах'а!, у*: 2а*„ =тах2а!,

х х ' хеСУ, х

где 0\У,- =1х: ^йтах' ¿Х, 1

3 ^ х 1 хеСТ/, ^1 ^

Пусть 8{ е(0, 1), 1=1,2 таковы, что выполнены соотношения:

'«^•е«;.), 09)

Тогда игра Га имеет равновесную ситуацию и*=(и1*, и2*),

где

СУ, Л, У- шах1«;

*(уЛ) =

(20)

(х*,Д х: 1а*х <5;Пшх'<

причем 1*=0.

Другими словами, согласно стратегии №* игрок 1 предлагает соглашение х* и принимает соглашение игрока при этом момент остановки игры 1*=0.

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

На защиту выносятся следующие результаты диссертационной работы:

п

- формализация процесса переговоров как игры переговоров на основе игры на упорядочениях в форме схемы переговоров, концепция решения и исследование свойств;

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

- модель достижения соглашения путем голосования;

- модель переговоров в форме игры на интервалах;

- критерии существования решения в чистых стратегиях в играх на интервалах для конечных, почти антагонистических и матричных игр;

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

Основные результаты диссертации опубликованы в следующих работах:

1. Зенкевич Н.А., Кузнецов В.Е., Сурвилло Т.Г., Теоретические проблемы интеграции и теоретико-игровой анализ переговоров по международным вопросам., в сб.: Народы содружества: история и современность. С. Петербург, 1996, стр. 23 - 34.

2. Зенкевич Н.А, Сурвилло Т.Г., К вопросу об играх с неопределенными платежными матрицами. Вестник ХГУ им.Н.Катанова, серия Математика - Информатика, вып. 1, Абакан, 1996, стр. 14- 17.

3. Сурвилло Т.Г., Моделирование международных конфликтов. Вестник ХГУ им. Н.Катанова, серия Математика - Информатика, вып. 1, Абакан, 1996, стр. 48 - 52.

а

4. Сурвилло Т.Г., Матричная игра с неопределенными платежными матрицами. Международная конференция по математическому моделированию (Тезисы докладов), Якутск, 1994, стр. 116.

5. Survillo Т., Game-theoretic approach to Negotiation problem., in: Abstracts of N.N. Vorob'ev memorial conference Game Theory and Economics, St.Petersburg, 1996, p. 67.

6. Survillo Т., A Strategy of optimal portfolio composing. International Conference on Interval and Computer-Algebraic Methods in Science and Engineering, St.Petersburg, 1994.