Содержание к диссертации
Введение
1 Модели переговоров при заключении двухсторонних сделок 16
1.1 Модель одношагового двухстороннего двойного закрытого аукциона Чаттержи и Самюэльсона 16
1.2 Равновесие в классе дифференцируемых профилей стратегий 19
1.3 Равновесие в классе пороговых профилей стратегий
1.3.1 Равновесие в классе профилей стратегий с одним порогом 30
1.3.2 Равновесие в классе 2-пороговых профилей стратегий 34
1.3.3 Равновесие в классе n-пороговых профилей стратегий
1.4 Равновесие при равномерном распределении резервных цен 44
1.5 Сравнение найденных решений. Примеры 53
2 Модели многошаговых переговоров с дисконтированием 57
2.1 Модель многошаговых двухсторонних торгов 57
2.1.1 Равновесие в классе дифференцируемых профилей стратегий 59
2.1.2 Равновесие в классе пороговых профилей стратегий 66
2.2 Модель последовательных переговоров о моменте встречи 71
2.2.1 Постановка задачи и общая схема решения 71
2.2.2 Равновесие для случая трех участников 74
2.2.3 Равновесие для случая четырех участников 75
2.2.4 Равновесие для случая п участников и близком к единице коэффициенте дисконтирования 79
3 Переговоры с конечным множеством альтернатив 82
3.1 Задача коллективного ранжирования альтернатив з
3.2 Характеристическая функция как значение игры с постоянной суммой 85
3.3 Ранжирование на основе турнирной матрицы 92
3.4 Сравнение с классическими процедурами ранжирования 97
Заключение 104
Литература
- Равновесие в классе пороговых профилей стратегий
- Равновесие при равномерном распределении резервных цен
- Модель последовательных переговоров о моменте встречи
- Ранжирование на основе турнирной матрицы
Введение к работе
Актуальность темы. Потребность в принятии коллективных решений возникает во многих сферах человеческой деятельности, например, в политике, экономике, управлении. Стороны могут принять решение в результате переговоров, обмениваясь информацией между собой. Решение также может быть принято независимой стороной, арбитром, учитывающим интересы сторон. Переговоры с участием арбитра совмещают оба подхода, при этом независимая сторона привлекается в спорных ситуациях.
Математическая теория игр является хорошим инструментом для моделирования существующих механизмов принятия коллективных решений и для разработки новых подходов. Математическая модель позволяет исследовать количественные и качественные характеристики механизма принятия решений. Для ее построения необходимо определить множества участников, независимых сторон и доступных альтернатив. Должны быть сформулированы критерии и способы реализации принятия решения, вид информации и правила обмена информацией между участниками.
К задачам переговоров относятся распределение ресурсов, проведение конкурсов и торгов, разрешение политических конфликтов, принятие законов в законодательных органах власти и другие. Удобной моделью решения данной задачи является принцип совершенного подыгрового равновесия в игре с полной информацией, предложенный Рубинштейном, развитый в работах Кардона, Понсати, Бэнкса, Дуггана, Мерло, Предтеченского и других.
Важный подход в моделировании проведения торгов был развит в работах Чаттержи, Самуэльсона, Майерсона, Маскина, Саттервейта, Уильямса и других как теоретико-игровая модель взаимодействия с неполной информацией между продавцами и покупателями. Существует много недостаточно изученных аспектов торгов. Среди них - различаемость товаров, дополняемость и комплект продуктов, многошаговость торгов, вопросы динамики, процессы обмена информацией, существование второй и последующих возможностей для сделки, если на первом этапе сделку совершить не удалось, согласованный выбор процедур и правил между продавцами и покупателями, прямое взаимное влияние участников торгов для создания или корректировки правил заключения сделки, вопросы построения наилучшей процедуры.
Для принятия коллективных решений используются различные процедуры. Одной из них является голосование, на основе которого делается ранжирование альтернатив с последующим принятием заключительного решения. Задачам ранжирования альтернатив были посвящены работы Эрроу, Брамса, Килгура, Тейлора, Фишбурна, Янга, Смита, Алескерова и других. Важной
задачей здесь остается исследование различных свойств ранжирования и построение процедур, удовлетворяющих оптимальным свойствам.
Целью диссертационной работы является построение оптимальных решений в моделях переговоров, исследование свойств полученных решений, нахождение необходимых и достаточных условий существования равновесия и их применение в задачах принятия коллективных решений.
В работе проведено исследование следующих теоретико-игровых моделей: двухсторонний двойной закрытый аукцион Чаттержи-Самуэльсона; последовательные многосторонние переговоры о моменте встречи; коллективное ранжирование альтернатив по личным предпочтениям.
Научная новизна работы. Все основные результаты, представленные в диссертации являются новыми. В классической модели двухсторонних торгов с одновременными предложениями найдено равновесие по Нэшу среди строго возрастающих дифференцируемых профилей стратегий без особых точек.
Построена теоретико-игровая модель многошаговых торгов. В ней найдены необходимые и достаточные условия для дифференцируемых и пороговых профилей стратегий быть равновесием по Нэшу. Найдены условия существования равновесия с пороговыми профилями стратегий участников.
В модели переговоров о моменте встречи найден точный вид совершенного подыгрового равновесия для случая бесконечно терпеливых участников с непрерывными без локальных максимумов функциями предпочтений.
В задаче коллективного выбора предложены новые процедуры ранжирования альтернатив, проверено выполнение свойств процедур, и проведено сравнение с классическими способами ранжирования.
Теоретическая и практическая значимость работы. Полученные результаты исследования применимы при разработке процедур проведения переговоров, в том числе и многошаговых, связанных с торгами, аукционами, задачами коллективного выбора. Предложенные схемы ранжирования альтернатив могут быть использованы при выборе одного или группы кандидатов на вакантную позицию.
Методы исследования. Применяются методы кооперативной и некооперативной теории игр, математического анализа и теории вероятностей.
Основные результаты, выносимые на защиту: 1. Найдены необходимые и достаточные условия для строго возрастающих дифференцируемых профилей стратегий без особых точек являться равновесием по Нэшу в классической модели двухсторонних торгов с одновременными предожениями, в предположении непрерывности плотности распределения резервных цен.
-
Построена теоретико-игровая модель многошаговых двухсторонних торгов с дисконтированием. Найдены необходимые и достаточные условия для дифференцируемых профилей стратегий в предположении непрерывности плотности распределения резервных цен и для профилей стратегий с одним порогом в случае произвольных распределений резервных цен быть равновесием по Нэшу. Показано, что в случае распределений резервных цен с ограниченной плотностью равновесие в классе профилей стратегий с одним порогом существует при близком к единице коэффициенте дисконтирования.
-
В модели последовательных переговоров о моменте встречи с близким к единице коэффициентом дисконтирования найден точный вид совершенного подыгрового равновесия для случая непрерывных без локальных максимумов функций предпочтений участников.
-
Предложены процедуры коллективного ранжирования альтернатив на основе методов кооперативной и некооперативной теории игр. Для этого строится характеристическая функция на множестве альтернатив, доказывается ее монотонность и неотрицательность. В качестве критерия ранжирования используется вектор Шепли. Доказано, что построенные процедуры удовлетворяют свойствам гомогенности, единогласия, монотонности, Кондорсе.
Апробация работы. Результаты диссертационной работы были представлены и обсуждались на научных конференциях: Шестая международная конференция Теория игр и менеджмент, Санкт-Петербург, Россия, 27-29 июня, 2012; Международный семинар Сетевые игры и менеджмент, Петрозаводск, Россия, 23-25 июня, 2013; Седьмая международная конференция Теория игр и менеджмент, Санкт-Петербург, Россия, 26-28 июня, 2013; VII Московская международная конференция по исследованию операций, Москва, Россия, 15-19 октября, 2013; XII Всероссийское совещание по проблемам управления (ВСПУ-2014), Россия, Москва, ИПУ РАН, 16-19 июня, 2014; Восьмая международная конференция Теория игр и менеджмент, Санкт-Петербург, Россия, 25-27 июня, 2014.
Основные результаты диссертации были получены в рамках выполнения исследований при финансовой поддержке РФФИ (проекты 13-01-91158-ГФЕН_а, 13-01-00033-а), РГНФ (проект 15-02-00352), Отделения математических наук РАН (программа 'Алгебраические и комбинаторные методы математической кибернетики и новых информационных систем") и Программы стратегического развития ПетрГУ в рамках реализации комплекса мероприятий по развитию научно-исследовательской деятельности.
Публикации. По теме диссертации опубликовано 11 работ, из них 5 статей в рецензируемых научных журналах из списка ВАК РФ [1-5] и тезисы 6 докладов [6-11]. В статье [1] диссертанту принадлежит построение гра-
ниц сделки в теореме 1 и численные расчеты для различных распределений резервных цен. В [2,5] диссертантом доказаны теоремы о равновесии среди двухпороговых и n-пороговых профилей стратегий, получены все численные результаты. В статье [5] диссертантом в приложении доказан результат о стимулирующем равновесии.
Личный вклад автора. Все представленные в диссертации результаты получены лично автором.
Структура и объем диссертации. Работа состоит из введения, трех глав, разбитых на разделы и подразделы, заключения и списка литературы. Общий объем рукописи составляет 110 страниц. Текст содержит 13 рисунков и 21 таблиц. Библиографический список включает 66 наименований.
Равновесие в классе пороговых профилей стратегий
Рассмотрим игру двух групп игроков с неполной информацией, которая относится к модели двухстороннего двойного закрытого аукциона. Участники переговоров здесь продавец и покупатель. Каждый из них обладает личной информацией о своей резервной цене, которую не знают другие игроки. Резервная цена - это цена, ниже которой продавец не согласен продавать свой товар, либо максимальная цена, которую готов заплатить покупатель. Для продавца это могут быть затраты на производство товара s, а для покупателя - его оценка данного товара Ь.
В настоящей работе построим равновесие по Нэшу для случая произвольных распределений для резервных цен. Продавцов и покупателей континуум, и их резервные цены распределены на интервале [0,1]. Каждый покупатель (продавец) знает свою резервную цену, для него это неслучайная величина. Предположим, что при случайном выборе одного продавца и одного покупателя их резервные цены продавцов s и покупателей Ь есть независимые случайные величины на интервале [0,1] с функциями распределения F(x) и G(x) соответственно (плотностями f(x) и д(х), если они существуют).
Игроки появляются на рынке, случайным образом формируются пары продавец-покупатель для переговоров. Затем участники одновременно объявляют цену на товар (не обязательно совпадающую с резервными ценами). Продавец запрашивает цену S, а покупатель предлагает цену В. Если В S, то результатом переговоров является заключение сделки по цене kS + (1 — к)В: где параметр к отражает рыночную силу участников. Будем далее полагать, что рыночная сила покупателей и продавцов одинаковая, то есть к = 1/2. Если предложенная покупателем цена В меньше, чем запрашиваемая продавцом цена S, то сделка не состоится.
Участники переговоров стремятся максимизировать свой доход от сделки. Доходом участников является разница между резервными ценами и ценой сделки, т. е. для продавца это (S + В)/2 — s, для покупателя Ь — {S + В)/2. Будем считать, что профиль чистых стратегий игроков есть функции от резервных цен S(s),B(b), т. е. участники с одинаковой резервной ценой предлагают одинаковые цены. Игроки используют чистые стратегии, но поскольку пара продавец-покупатель формируется случайно, то в качестве выигрышей рассмотрим ожидаемый доход продавца с резервной ценой s и запрашиваемой ценой S
Каждый игрок знает свою личную резервную цену, распределения F(x),G(x) резервных цен среди групп продавцов и покупателей, но не знает точное значение резервной цены второго участника переговоров. Равновесие по Нэшу в данной игре с профилем чистых стратегий игроков S(s),B(b) и выигрышами (1.1), (1-2) называется байесовским равновесием. При оптимальном поведении игроков очевидно, что S(s) s и В{Ь) 6, т. е. продавец завышает, а покупатель занижает истинную цену на продукт, чтобы получить дополнительный доход от сделки. В работе [1] показано, что в равновесии стратегии всегда будут неубывающие. Далее мы увидим, что существуют байесовские равновесия, где функции S(s) и В{Ь) имеют пороговый или нелинейный вид. Вначале мы будем рассматривать равновесия, в которых функции S{s) и В(Ь) диффе 18 ренцируемые. Если таких равновесий несколько, то можно предложить то из них, которое максимизирует суммарный ожидаемый доход продавцов
У этой задачи существует множество тривиальных решений. Например, стратегии S(s) = 1 для всех s Є [0,1], B(b) = 0 для всех Ь Є [0,1] являются байесовким равновесием для любых распределений F(x) и G(x) продавцов и покупателей. Такое равновесие никого не устраивает, так как сделка никогда не происходит и выигрыши всех продавцов и всех покупателей в этом случае равны нулю.
Предположим, что резервные цены продавцов и покупателей s и Ь распределены на интервале [0,1] с непрерывными плотностями распределения соответственно f(x),x є (0,1), и д(х),х Є (0,1).
Для нахождения оптимальных стратегий игроков воспользуемся следующими соображениями. Будем считать их функциями от резервных цен, соответственно S = S(s) и В = В{Ь). Допустим, что это дифференцируемые и строго возрастающие функции соответственно на ( т, с) и (а, (3) вида где 0 сг а с /3 1. Обратные к ним функции U = В 1 и V = S l являются дифференцируемыми и строго возрастающими на (а, с), т. е. соответственно s = V(S) и b = U(В). Сделка происходит по цене (S(s) + B(b))/2: если В S. Функции выигрыша игроков имеют вид (1.5) и (1.6), где математическое ожидание берется по соответствующим распределениям. Зафиксируем стратегию покупателя В{Ъ) и установим наилучший ответ продавца для различных значений параметра s.
Равновесие при равномерном распределении резервных цен
Аналогичные рассуждения проведем для покупателей. Пусть продавцы следуют двухпороговой стратегии. Тогда выигрыш покупателей при у с откуда, учитывая монотонное возрастание F{y) и условие (6), следует, что выигрыш покупателя принимает на [с, Ь] наибольшее значение при у = с. Значит оптимальным предложением любого покупателя будет цена а или с. Легко находим, что H2(b,a) = (b-a)F(a), Я2(Ь, с) = (Ъ - c)(F(c) - F(a)) + (6- )F(a), Я2(6, с) - Я2(6, а) = (Ь- c)(F(c) - F(a)) - F(a) = (b - fl)(F(c) - F(o)), откуда следует, что покупатели Ь Є [а, (3) должны назвать цену В = а, а покупатели Ь Є (/3,1] должны объявить цену В = с.
Необходимость выполнения условий (а) и (Ь) следует из определения байесовского равновесия. В силу непрерывности и монотонности Hi(s,c) — Hi(s,a) и H2(b}c) — H2(b}a) по s и 6, и того факта, что продавцы с резервной ценой т и покупатели с резервной ценой (3 получают одинаковые выигрыши при предлагаемых ценах а и с, следуют уравнения для порогов а и (3. Лемма доказана.
Условия (а) и ( ) леммы 1.5 можно заменить на равносильные им, учитывая (1.37) и (1.38), что приводит нас к необходимому и достаточному условию равновесия среди двухпороговых стратегий.
Теорема 1.4. Двухпороговые профили стратегий S(s), B(b) с маргинальными ценами а}с Є (0,1) и порогами т,/З Є (0,1) образуют байесовское равновесие в модели одношагового двухстороннего закрытого аукциона с непрерывными и возрастающими распределениями F{x) и G{x) резервных цеп, если выполняются условия оптимальности в крайних точках
По теореме 1.4 можно найти все равновесия среди двухпороговых стратегий для любых непрерывных и возрастающих распределений для резервных цен. Заметим, что при произвольных (необязательно непрерывных) распределениях резервных цен условия теоремы 1.4 остаются достаточными для равновесия. 1.3.3 Равновесие в классе n-пороговых профилей стратегий Распространим описанную ранее схему на случай n-пороговых стратегий. Определение 1.4. Назовем п-пороговой стратегией с маргинальными ценами 0 а\ ... ап 1, порогами 0 = то (Т\ ... о п 1 = ап+\ и О = /Зо /Зі ... [Зп 1 = /3n+i профиль чистых стратегий продавцов вида
Предположим, что продавец использует n-пороговую стратегию (1.39). Таким образом, все продавцы разбиты на п + 1 группу в зависимости от значений резервных цен, и если резервная цена s принадлежит г-ой группе, т.е. s Є [ 7j_i, 7j), то продавец называет цену a , і = 1,..., п. Если же резервная цена достаточно высока (s ап), продавец называет истинную цену s.
Найдем наилучший ответ покупателя для различных значений параметра Ь. Заметим, что сделка происходит только если резервная цена покупателя Ь не меньше а\. Если же Ь а\, то сделка может произойти при условии, что В S(s). откуда, учитывая монотонное возрастание F(у) и условие (6), следует, что выигрыш покупателя принимает на [ап, Ь] наибольшее значение при у = ап. Значит оптимальным предложением любого покупателя будет одна из цен а\,..., ап. Учитывая (1.41), условие (Ь) равносильно следовательно, для покупателей с резервной ценой b (ЗІ запрашиваемая цена di-i выгоднее, чем а , а для покупателей с резервной ценой b (ЗІ запрашиваемая цена di лучше, чем а _ь
Таким образом, показано, что наилучшим ответом покупателя на стратегию S(s) является стратегия n-порогового вида (1.40), где /ЗІ,і = 1,...,п определяются выражениями (1.42), (Зп+\ = 1,/ = 0.
Аналогичные рассуждения проводятся для нахождения оптимального ответа продавца на пороговую стратегию покупателя. Предполагая, что покупатель использует стратегию (1.40), можно показать, что оптимальный ответ продавца
Напомним, что функции G(x): F(x) определяются no (1.25),(1.26). В теоремах 1.1-1.5 для выполнения условий оптимальности в крайних точках достаточно неубывания G(x)} х Є (0, 2і), и невозрастания F(x)} х Є (ап,1). Если F(x),G(x) имеют кусочно-непрерывные плотности f(x) на (ап, 1) и д(х) на (О, 2i), то в теореме 1.5 для выполнения условий оптимальности в крайних точ 42 ках достаточно в точках непрерывности тогда второе условие оптимальности в крайних точках выполнено для всех ап Є [С, 1). В уравнениях выше можно заменить f(y) на Е7 д(у) на D, для нахождения А, С. По теореме 1.5 можно найти все равновесия среди n-пороговых стратегий для любых непрерывных и возрастающих распределений для резервных цен. Заметим, что при произвольных (необязательно непрерывных) распределениях резервных цен условия теоремы 1.5 остаются достаточными для равновесия. При этом, стратегии и область сделки имеет вид, изображенный на рис. 1.9 и рис. 1.10.
Связь равновесий с непрерывными и n-пороговыми профилями стратегий. Пусть распределение резервных цен имеют непрерывные на [0,1] плотности f(x),g(x)7 а маргинальные цены а, с удовлетворяют условиям оптимальности в крайних точках (теоремы 1.1-1.5). Допустим последовательность n-пороговых равновесий с уровнями цены сделки 0 а = а\ ... ап = с 1: таковы что последовательности
Правая и левая части обоих выражений выше совпадают с дифференциальными уравнениями теоремы 1.1 для непрерывного равновесия. Можно ожидать, что такая последовательность равновесий с п порогами будет сходиться к непрерывному равновесию.
Модель последовательных переговоров о моменте встречи
Пороговые стратегии и область сделки изображены на рис. 1.5 и рис. 1.6 в первой главе. При выполнении условий теоремы 2.3 сделка всегда происходит по фиксированной цене а. По теореме 2.3 можно найти все равновесия среди пороговых стратегий для любых (необязательно непрерывных) распределений для резервных цен. Далее будет показано, например, для случая равномерного распределения резервных цен участников на [0,1] равновесие с одним порогом существует, если коэффициент дисконтирования 5 2/3.
Теорема 2.4. Пусть F(x),G(x) имеют кусочно-непрерывные и ограниченные плотности f(x) L па [а, 1] и д(х) М на [0, а]. Коэффициент дисконтиро 68 вания достаточно близок к единице, т.ч. Тогда пороговые профили стратегий S(s),B(b) с ценой сделки а Є (0,1) образуют байесовское равновесие в модели многошагового двухстороннего двойного закрытого аукциона с распределениями F(x) и G(x) резервных цен.
Т.е. мы доказали, что производная выигрыша .(1,2/) неположительна на [а, 1], значит, выполнено второе условие теоремы 2.3. Доказательство завершено.
Теорема 2.4 показывает, что для любой цены сделки а Є (0,1) при ограниченных плотностях распределения игроков f(x),g(x) и при дисконтировании 6 достаточно близком к единице будет иметь место равновесие с одним порогом.
В модели мы предположили, что распределение резервных цен продавцов и покупателей остается постоянным на каждом шаге. Это будет происходить, если вместо заключивших сделку участников на каждом шаге в игру будут вступать новые участники с тем же распределением резервных цен. Пусть на каждом шаге ri\F(x) это количество новых продавцов, которые готовы вступить в игру, если рыночная будет не меньше чем х. Аналогично, пусть 712(1 — G(x)) это количество новых покупателей, готовых купить товар, если его цена не превосходит х. В начале главы мы предполагали для простоты, что щ = щ. Таким образом, мы получаем следующее уравнение баланса для нахождения рыночной цены а: mF(a) = п2(1 - ЭД), а Є (0, Г
Если участники достаточно терпеливы (коэффициент дисконтирования достаточно близок к единице), то их поведение предсказуемо: оптимальной стратегией каждого участника является назвать рыночную равновесную цену, если его резервная цена позволяет это (теоремы 2.3 и 2.4). Если же участники нетерпеливы, то они будут предлагать различные цены на товар в зависимости от своей резервной цены (теоремы 2.1 и 2.2).
Игроки /i,..., Іп договариваются о времени встречи х из интервала [0,1]. Предположим, что их предпочтения описываются неотрицательными непрерывными функциями полезности Uj(x) с одним максимумом Cj на интервале [0,1], так что Uj(x) возрастает на [0,Cj] и убывает на [с ,1]. Не ограничивая общности, можно считать с\ = 1, с = 0. Будем предполагать, что по крайней мере для двух игроков предпочтения имеют видмі(ж) = х7 щ(х) = 1 — ж, а функции предпочтений остальных участников Ij удовлетворяют свойствам Uj(5x) 5uj(x) и Uj(l — 5 + 5х) 5uj(x), для всех х,6 Є [0,1]. Геометрически это означает, что функция лежит не ниже любого отрезка, соединяющего лежащую на графике точку и точки (0,0) и (1,0). Это свойство очевидным образом выполнено для вогнутых функций. предлагают различные варианты решения, для принятия которого нужно согласие всех участников. На шаге і = 1 игрок 1\ предлагает альтернативу Х\ Є [0,1], и остальные игроки либо принимают, либо отвергают ее. Если все игроки согласны, то время встречи х = Х\ выбрано и переговоры завершаются. Иначе, игра переходит на шаг і = 2, на котором 1 предлагает решение Х2, а остальные голосуют. И так далее, пока игроки не придут к согласию. На шаге і будем считать, что если принята альтернатива ж, то полезность игрока Ij равна 5% lUj{x)1 где 5 Є (0,1) есть коэфициент дисконтирования.
Для нахождения равновесия в задаче будем использовать метод обратной индукции. Допустим, игрок Ij знает, что на следующем шаге будет предложена альтернатива Xj+\ = х. Найдем множество предложений у на текущем шаге, устраивающее всех игроков. Игрок 1\ согласится, если щ(у) 6щ(х), т. е. у 6х. Игрока Li устроит у 1 — 5 + 5х. Таким образом, допустимое предложение принадлежит интервалу [5х, 1 — 5 + 5х]. Остальные игроки с пиками с& Є [0,1] согласятся на любое такое предложение, так какщ(бх) 5uk(x)}Uk(l—6+6x) 5uk(x)} для всех х,6 Є [0,1].
Будем искать стационарные совершенные по подыграм равновесия по Нэшу. Следовательно, игрок Ij на каждом шаге использует одинаковую стратегию Xj: которая является его наилучшим ответом (2.18) на стратегию Xj+\ следующего в очереди игрока Ij+і- Решение уравнения w(x) = Х\(... хп-\(хп(х))) = х является равновесием в переговорах о времени встречи. Если задача уже решалась для п — 1 игроков, то мы можем использовать полученные расчеты наилучших ответов для решения в случае п игроков, при этом количество областей параметров решения утраивается. В общем случае пространство параметров (6, Сі,..., сп) разбивается на Зп 2 частей.
В [24] был предложен метод обратной индукции для нахождения равновесия в классической задаче переговоров двух лиц о разделе пирога. В [31] исследовано существование и единственность равновесия в переговорах п лиц для случая непрерывных без локальных максимумов функций предпочтений. Один из полученных ими результатов можно сформулировать следующим образом.
Предложение 2.1(Кардона, Понсати). Если функции предпочтений участников последовательных переговоров о моменте встречи Uj(x) непрерывные без локальных максимумов, то стационарное совершенное подыгровое равновесие по Нэшу существует, причем на первом шаге принимается предложение первого игрока х\.
Игроки по очереди предлагают различные варианты решения и для его принятия нужно согласие всех участников. Покажем, что в зависимости от соотношения между с и 5 равновесие будет иметь различный вид.
Ранжирование на основе турнирной матрицы
Аналогично можно показать, что приращение значения для у в векторе Ше-пли не превосходит приращения для z. Таким образом, доказано, что кандидат х не уменьшит свой ранг, а кандидат у не увеличит свой ранг в коллективном предпочтении при изменении характеристической функции cv nav.
Теорема 3.1. Характеристическая функция v является неотрицательной и монотонной. Ранжирование согласно вектору Шепли для функции v обладает свойствами гомогенности, единогласия, монотонности, правила большинства, Кондорсе и сильного свойства Кондорсе.
Доказательство. Неотрицательность и монотонность функции v очевидно следует из их определения. Заметим, что при нечетном числе избирателей v будет также и супераддитивной.
Докажем, что выполняется свойство единогласия. Пусть кандидата предпочтительнее, чем кандидат у7 для всех голосующих. Достаточно проверить выполнение неравенства v(y U S) v(x U S) для любой коалиции S С А \ {ж, у}. Обозначим К = А \ {х, у} \ S. Заметим, что h(i,x) h(i,y), h(y,j) h(x,j) для любых i,j. Следовательно, H(i,x) H(i,y): H(y,j) H(x,j) для любых г, j. Сравним матрицу выигрышей коалиции у U S против х U К
Элементы нижней матрицы не меньше соответствующих элементов верхней матрицы. Согласно лемме 3.2, выполняется v(yUS) v(xUS). Следовательно, для кандидата х значение в векторе Шепли не меньше, чем для кандидата у.
Докажем выполнение свойства монотонности ранжирования. Пусть в одном из бюллетеней кандидат х поднимется на одну позицию вверх, а кандидат у опустится на одну позицию вниз. Обозначим v характеристическую функцию после этого изменения. Нетрудно видеть, что для любой коалиции S С А\{х, у} выполняются условия леммы 3.3. По лемме 3.3 кандидат х не уменьшит свой ранг, а кандидат у не увеличит свой ранг в коллективном предпочтении.
Проверим выполнение свойства Кондорсе. Пусть кандидат х есть победитель Кондорсе. Сравним его с любым другим кандидатом у. Для любого множества S С А \ {ж, у} коалиция х U S выставляет единого кандидата х и выигрывает. Поэтому выполняется 1 = v{xUS) v(yUS) = О, откуда вытекает, что для кандидата х значение в векторе Шепли больше, чем для кандидата у. Докажем выполнение сильного свойства Кондорсе. Пусть w(x) w(y): 1(х) С 1(у) и h(x, у) п/2. Тогда I(h(i, х) - f) I(h(i, у) - f), /(/1(2/, j) - f) I(h(x,j) — ) для любых г, j. Проверим выполнение неравенства г (г/ U5) г»(ж U 5") для любого множества S Q А\ {ж,у}. Обозначим множество К = А \ {ж, у} \ S. Матрицы выигрышей коалиции у U S против х U К в точности такие же, как и матрицы (3) и (4) при проверке свойства единогласия. Тогда согласно лемме 3.2 выполняется условие v(y U S) v(x U S). Следовательно, для кандидата х значение в векторе Шепли не меньше, чем для кандидата у.
Для функции v выполняется сильное свойство Кондорсе, а по лемме 3.1, следовательно, и правило большинства. Теорема доказана.
Характеристическая функция v учитывают только факт победы одного кандидата над другим при попарном сравнении. Преимущество в один голос и единогласное здесь равнозначны. Такой способ ранжирования показывает способность кандидата создавать коалиции, выдвигающие победителя Кондорсе. Если среди всех кандидатов уже есть победитель Кондорсе, то вектор Шепли будет равен (1, 0,... , 0).
Замечание. Выше значение характеристической функции было определено как значение игры с постоянной суммой в смешанных стратегиях. Можно также определить характеристическую функцию ограничиваясь рассмотрением лишь чистых стратегий. Тогда ее значением в игре коалиции К против контркоалиции А \ К будет
Для вычисления функции v использовалась матрица выигрышей, состоящая из нулей и единиц. Далее будем более точно оценивать преимущество одного кандидата над другим. Рассмотрим как и раньше игру с постоянной суммой ко 93 алиции К против контркоалиции А\К. Каждая коалиция выставляет единого кандидата. Выигрышем коалиции будем считать количество голосов h(i,j), набранных единым кандидатом і Є К против единого кандидата j Є А
Для коалиции ас единый кандидат а гарантирует 20 голосов против 6, а кандидат с гарантирует 17 голосов против d. Для коалиции bde единый кандидат b гарантирует 45-29=16 голосов против с, d- 45-30=15 против а, е - 45-24=21 против с. Гарантированные выигрыши при использовании чистых стратегий здесь равны и(ас) = 20, u(bde) = 45 — 24 = 21. В равновесии в смешанных стратегиях коалиция ас использует вероятности для стратегий (7/15,8/15), а коалиция bde - (0, 2/15,13/15). При этом получаются выигрыши и(ас) = 346/15 « 23.07, u(bde) = 329/15 « 21.93.