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

На правах рукописи

Кондратьев Алексей Юрьевич

Равновесие в теоретико-игровых моделях переговоров и коллективных решений

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ ~ 7 0КТ 20}5

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

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

005563071

005563071

Работа выполнена в Федеральном гоеударственном бюджетном учреждении науки Институте прикладных математических исследований Карельского научного центра Российской академии наук

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

профессор,

Мазалов Владимир Викторович

Официальные оппоненты: Яновская Елена Борисовна

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

заведующая международной лаборатории теории игр и принятия решений

Парилина Елена Михайловна

кандидат физико-математических наук, Санкт-Петербургский государственный университет,

доцент кафедры математической теории игр и статистических решений

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

имени М.В.Ломоносова

Защита состоится «. НйМ БР9 2015 г. в 16100 на заседании диссертационного совета Д 212.232.29 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 10 линия В. О., д. 33/35,

ауд.24.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199304, Санкт-Петербург, Университетская наб., 7/9 и на сайте http://spbu.ru/science/disser/dissertatsii-dopushchennyc-k-zashchite-i-svedcniya-o-zashchitc.html.

Автореферат разослан «

С£НТЗ£Р9 2015 г.

Ученый секретарь диссертационного совета, . /е, тт „ „ ,,

доктор физ.-мат. наук, профессор МГ..^ Нежинский В. М.

Общая характеристика работы

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

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

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

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

Для принятия коллективных решений используются различные процедуры. Одной из них является голосование, на основе которого делается ранжирование альтернатив с последующим принятием заключительного решения. Задачам ранжирования альтернатив были посвящены работы Эрроу, Брамса, Килгура, Тейлора, Фишбурна, Янга, Смита, Алсскерова и других. Важной

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

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

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

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

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

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

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

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

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

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

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

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

4. Предложены процедуры коллективного ранжирования альтернатив на основе методов кооперативной и некооперативной теории игр. Для этого строится характеристическая функция на множестве альтернатив, доказывается ее монотонность и неотрицательность. В качестве критерия ранжирования используется вектор Шепли. Доказано, что построенные процедуры удовлетворяют свойствам гомогенности, единогласия, монотонности, Кондорсе.

Апробация работы. Результаты диссертационной работы были представлены и обсуждались на научных конференциях: Шестая международная конференция Теория игр и менеджмент, Санкт-Петербург, Россия, 2729 июня, 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] диссертантом доказаны теоремы о равновесии среди двухпороговых и ?г-пороговых профилей стратегий, получены все численные результаты. В статье [5] диссертантом в приложении доказан результат о стимулирующем равновесии.

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации. Работа состоит из введения, трех глав, разбитых на разделы и подразделы, заключения и списка литературы. Общий объем рукописи составляет 110 страниц. Текст содержит 13 рисункоЕ и 21 таблиц. Библиографический список включает 66 наименований.

Содержание работы

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

В первой главе рассматривается теоретико-игровая модель переговоров при заключении сделок па примере двухстороннего двойного закрытогс аукциона. В разделе 1.1 рассматривается постановка задачи. В торгах участвуют две группы игроков: продавцы и покупатели. Для переговоров случайным образом формируются пары продавец-покупатель. Главным параметром каждого участника является его резервная цена, которую не знают другие участники. Для продавца это цена з. ниже которой он не согласен продавать свой товар, а для покупателя это максимальная цена Ь, которую он готов заплатить. При случайном формировании пары резервная цена продавца в и покупателя Ь являются независимыми случайными величинами с функциями распределения F(х) и (3(х). Игроки одновременно объявляют цену на товар. Продавец запрашивает цену 5, а покупатель предлагает цену В. Если В > то результатом переговоров является заключение сделки по цене (5 + В)/2. Если предложенная покупателем цена В меньше, чем запрашиваемая продавцом цена Б. то сделка считается несостоявшейся для данной пары участников. Участники переговоров стремятся максимизировать свой доход от сделки. Доходом участников является разница между резервными ценами и ценой сделки, т. е. для продавца это (5 + В)/2 — в, для покупателя Ь — (Б + В)/2. Профиль чистых стратегий участников это функции от резервных цен ¿'(в), В(Ь). т. е. игроки с одинаковой резервной ценой предлагают одинаковые цены. Игроки используют чистые стратегии, но поскольку пара продавец-покупатель формируется случайным образом, то в качестве

выигрышей рассматривается ожидаемый доход продавца с резервной ценой s и запрашиваемой S

H1(s,S,S(s),B(b)) = J dG(y),

y-B{y)>S

и покупателя с резервной ценой Ъ и запрашиваемой В

Н2(Ъ, В, S(s), В(Ь)) = J (ъ- 5(х)2+Д) dF{x).

x:S(x)<B

Равновесие по Нэшу в данной игре с профилем чистых стратегий ¿"(s), B(b) и выигрышами, определяемыми как ожидаемый доход, называется байесовским равновесием. Равновесие называется стимулирующим доход, если среди всех равновесий максимизирует суммарный ожидаемый доход игроков

ЕЯ! + ЕЯ2 = Е (Ъ - s) /{в(6)>5(,)}.

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

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

Теорема 1. Пусть функции распределения F(x) и G(x) имеют плотности f(x) и д(х), непрерывные и положительные па (0,1); h\,li2, п, 7 6 (0, +оо), F(x)~hixa, f(x) ~ ahixa~l, при х —О,

1 — G(x) ~ /г2(1 — х)7, д(х) ~ /¿2С1 — при х —>■ 1.

Маргинальные цены 0 < а < с < 1 удовлетворяют тождествам

1 — G(a) = ag{a),

F(c)= (2 + ^) (1 -c)f(c).

'Chatterjee K., Sainuelson W. Bargaining under incomplète information // Opérations Research. 19S3. Vol. 31. N 5. P. 835-851.

2Myerson R., Satterthwait М.Л. Efficient incclianisms for Bilatéral Trading // Journal of Economie Theory. 19S3. Vol. 29. P. 2G5-281.

Выполняются условия оптимальности в крайних точках

х

arg max {х(1 - G(x)) - J ydG(y)} = a,

о

i

arg max {(2 - x)F(x) + / ydF(y) \ = c. ie[c.i] J

X

Функции U(t),V(t) - дифференцируемые на [а, с], принимающие значения t<U(t)< 1, О<V(t)<t на (а, с), являются решением краевой задачи

1 - G(U(t))

uM = 2(t-vww(t)y a<t<c'

= 2(C/(í) — t)f(V(t))' a<t<C> U(a) = a, V(c) = c,

причем V(a) = 0,U(c) = 1.

Тогда строго возрастающие и дифференцируемые на [О, с] и [о, 1] профили чистых стратегий продавцов и noKynamejieü

I y~4s), 0<S<C, ib, 0 < b < a,

S{s)-\s, c<s< 1, B{b) = { U~\b), a <b < 1,

образуют байесовское равновесие в модели одношагового двухстороннего двойного закрытого аукциона с распределениями F(x) и G{x) резервных цен.

Определение 1. Назовем п-пороговым профилем стратегий с маргинальными ценами 0 < ai < ... < ап < 1, порогами 0 = сто < а\ < ... < ап < 1 = &п+1, 0 = Д) < ßi < ■ ■ ■ < ßn < 1 = ßn+i профиль стратегий продавцов вида

„, . I üí если сгг-_1 < S < &Í, i = 1,...,п b(s) — <

I s если ап = crn < s < 1,

где (Ti < a¡,¿ = 1, ...,п, и профиль стратегий покупателей вида

Ъ еыи 0 < Ъ < ß\ = ai,

^ 1 a¿ если ¡3¡ < b < Д+ь i = l,...,n

где Д > a¿,г = 1,...,п.

В работе3 получено необходимое условие для нахождения равновесия среди n-пороговых профилей стратегий в виде системы алгебраических уравнений. В разделе 1.3 найдены необходимые и достаточные условия для на-

3Leininger W., Linhart Р.В., Radnor R. Equilibria of the seaJed-bid mechanism for bargaining и-ith incompleto information // Journal of Economic Theory. 1089. Vol. 48. P. G3-100.

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

Во второй главе рассматриваются модели многошаговых переговоров. В разделе 2.1 предложена модель многошагового двухстороннего закрытого аукциона, обобщающая классическую модель из первой главы. Вводится коэффициент дисконтирования 6, и рассматривается игра с бесконечным временным горизонтом. Предполагается, что на каждом шаге количество продавцов равно количеству покупателей, с распределениями резервных цен Р(х),С(х). На каждом шаге г = 1,2,... для переговоров формируются случайным образом пары продавец-покупатель. После этого игроки одновременно объявляют цену на товар. Продавец запрашивает цену,?, покупатель предлагает цепу В. Если В > 5. то результатом переговоров является заключение сделки по цене (Б + В)/2. Покупатель и продавец, заключившие сделку, покидают игру. Если предложенная покупателем цена В меньше, чем запрашиваемая продавцом цена 5, то сделка не заключается, игроки переходят на следующий шаг г + 1, на котором покупатель (продавец) вступает в переговоры для заключения сделки с другим продавцом (покупателем).

Участники переговоров стремятся максимизировать свой доход от сделки. Доходом участников является разница между резервными ценами и ценой сделки, т. е. для продавца это д!^х((5 + В)/2 - в), для покупателя д'~1(Ь— (Б+В)/2). Профиль чистых стратегий участников это функции от резервных цен £>(в), ¿?(6). Игроки используют чистые стратегии, но поскольку пары продавец-покупатель формируются случайным образом, то в качестве выигрышей рассматривается суммарный ожидаемый доход при заключении сделки на текущем шаге и при продолжении игры.

Выигрыш продавца с резервной ценой в и запрашиваемой 5 равен

Выигрыш покупателя с резервной ценой Ь и предлагаемой В равен

Получены необходимые и достаточные условия равновесия в классе дифференцируемых профилей стратегий. Случай 5 = 0 соответствует одношаго-вой задаче из первой главы. В теореме 2 найдены необходимые и достаточные условия равновесия среди строго возрастающих (т.ч. производная конечна и больше нуля во всех точках) и дифференцируемых профилей стратегий.

Теорема 2. Пусть функции распределения Г(х), в(х) имеют непрерывные на [0,1] плотности /(ж), д(х). Пусть /(ж) положительная на [0,1), д(х) положительная на (0,1].

Функции дифференцируемые и возрастающие на [а,с], удовле-

творяющие г<и(*)<1, 0<У(4)<£ на (а,с), есть решение краевой задачи

_(1—<?(г/))(1-гс(г/))

дь

2 д(Ю

дУ дЬ ~~

(1

и

а < £ < с,

щу)

а < £ < с,

причем У(а) = 0, II(с) = 1, и\а) =-

и (а) = а, У{с) = с, (1 - С(а))(1 - дС(а))

2 д(а)

Г(с)=-

(1-6)а-Ц(и^(у)-а)сЮ(у)

а

Е(с)(1-6+6Г(с))

2/(с)

(1 _ Л-)(1 _ с)~Ц(с - У-^{х))йР{х)

Маргинальные цены 0 < а < с < 1 удовлетворяют условиям оптимальности в крайних точках

а 1

аг8Ж " С(х)) + / уйс{у) + / и'^У^Ш = а.

х а

С X

+ " х)Пх) ~ / ~ / УарШ = с-

О с

Тогда строго возрастающие и дифференцируемые на [0, с] и [а, 1] профили чистых стратегий продавцов и покупателей

3(Я) =

У'Ч«), 0 < 5 < с,

С < 5 < 1,

В(Ь) =

Ь,

0 < Ь < а,

и-х(Ь), а < Ь < 1,

образуют байесовское равновесие в модели многошагового двухстороннего закрытого аукциона с распределениями F(x) и G{х) резервных цен.

Теорема 3. Пороговые профили стратегий S(s), B(b) с маргинальной ценой a G (0,1) образуют байесовское равновесие в модели многошагового двухстороннего закрытого аукциона с распределениями F{х) и G(x) резервных цен. если выполняются уыовия оптимальности в крайних точках

а

arg max {^-J^-^l - С?(аг» + J уdG(у) + о(1 - G(a))]} = о,

X

X

arg max {——L—-[(2 - x)F(x) - aF(a) - f уdF(y)]} = a. ze[a,i] 1 —d + ör(a:j J

а

Условия теоремы 3 являются необходимыми и достаточными для нахождения равновесия среди пороговых профилей стратегий для любых (необязательно непрерывных) распределений резервных цен.

Теорема 4. Пусть F(x),G(x) имеют кусочно-непрерывные и ограниченные плотности /(х) < L на. [а, 1] и g(x) < М на [0, а]. Коэффициент дисконтирования достаточно близок к единице, такой что

6>i_(l-Ggf Р*(а)

2а M ' ~ 2(1 — a)L

Тогда пороговые профили стратегий S(s),B(b) с маргинальной ценой о€(0,1) образуют байесовское равновесие в модели многошагового двухстороннего закрытого аукциона с распределениями F(x) и G(x) резервных цен.

По теореме 4 для любой маргинальной цены a 6 (0,1) при ограниченных плотностях распределения игроков f(x),g(х) и достаточно близком к единице дисконтировании £ будет иметь место равновесие с одним порогом. Показано. что для случая равномерного распределения резервных цен участников на [0,1] равновесие с одним порогом существует, если коэффициент дисконтирования <5 > 2/3, а равновесие с возрастающими и дифференцируемыми профилями стратегий не существует при 5 > 4/5.

В разделе 2.2 исследуется модель последовательных переговоров о моменте встречи. В работе4 предложен метод обратной индукции для нахождения равновесия в классической задаче переговоров 2-х лиц о разделе пирога. В работе5 исследовано существование и единственность равновесия в переговорах п лиц при непрерывных без локальных максимумов функциях предпочтений.

'Rubinstein A. Perfect equilibrium in a bargaining model // Economctrica. 19S2. Vol. 50. P. 97—109. 3Cardona D., Ponsati C. Bargaining one-dimensional social choices // Journal of Economic Theory. 2007. Vol. 137. P. 627-051.

Участники /!,...,/„ договариваются о времени встречи х из интервала [0,1]. Предполагается, что их предпочтения описываются неотрицательными непрерывными функциями и^(х) с одним максимумом с; на интервале [0,1], так что Иу(х) возрастает на [0, с,] и убывает на [с,, 1]. По крайней мере для двух игроков предпочтения имеют вид «1(2:) = х. и2(х) = 1 — х. Функции предпочтений остальных участников удовлетворяют свойствам и^{5х) > 6и^(х). — 6 + > 5и^{х), для всех х, 5 е [0,1].

Игроки по очереди Д—>12-+ ...—>/„—>Д—К.. предлагают одну альтернативу, для принятия которой нужно согласие всех участников. На шаге г = 1 игрок 1\ предлагает альтернативу х\ € [0,1], и остальные игроки либо принимают. либо отвергают ее. Если все игроки согласны, то время встречи а; = жх выбрано и переговоры завершаются. Иначе, игра переходит на шаг г = 2, игрок 12 предлагает х2. а остальные голосуют. И так далее, пока участники не придут к согласию. На шаге г выигрыш игрока Д равен 51~1и^(х), если принята альтернатива х, где 6 6 (0,1) есть коэффициент дисконтирования.

Решение ищется в виде стационарного совершенного по подыграм равновесия по Нэшу. Найдены точные решения для случаев п = 2,3,4 игроков.

Теорема 5. Обозначим в убывающем порядке 0 — сп < сп~х < ... < с2 < с1 = 1 максимальные предпочтения участников последовательных переговоров о моменте встречи. Независимо от последовательности внесения предложений участниками существует предел оптимальных стратегий при стремящемся к единице коэффициенте дисконтирования.

' Ь если с2 < Ь

если — < ск <

П --- 71

если < £ < ск,

П=1, если П=! < сп-15

и переговоры завершаются на первом шаге принятием альтернативых\.

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

Птгг* = <

■5-+1 1

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

В разделе 3.1 рассматривается постановка задачи. Обозначим множество m > 2 альтернатив как А = {а, b.c....}, множество тг > 2 участников переговоров как Р = {/i. /2,..., In}, их веса li'i, И'2,..., lVn > 0 и суммарный вес IV. По профилю личных предпочтений вычисляются значения h(:г, у) как сумма весов участников, для которых альтернативах предпочтительнее, чем альтернатива у, и половины весов участников, для которых альтернативы х и у равноценны. Матрица со значениями h(x,y) называется турнирной матрицей. Говорим, что х побеждает у при попарном сравнении, если h(x, у) > 17/2. Альтернатива называется победителем Кондорсе, если она побеждает любую другую альтернативу при попарном сравнении. Обозначим w(x) - множество альтернатив, у которых х выигрывает при попарном сравнении, а 1(х) - тех, кому проигрывает.

Для процедуры ранжирования желательно выполнение свойств: Гомогенность. Коллективное ранжирование не меняется при пропорциональном изменении весов в профиле личных предпочтений. Единогласие. Если каждый участник ставит альтернативу х не ниже альтернативы у, тогда в коллективном предпочтении х не ниже, чем у. Монотонность. Если один из участников в личном предпочтении поднимет альтернативу х па одну позицию, не изменяя ранжирования других альтернатив, тогда в коллективном предпочтении х не понизит свой ранг. Если же один из участников, наоборот, в личном предпочтении опустит а; на одну позицию, не изменяя ранжирования других альтернатив, тогда в коллективном предпочтении х не повысит свой ранг.

Правило большинства. Для любого начального профиля предпочтений и любого порядка альтернатив ai > «2 > ... > п,„ существует число V, такое что при добавлении участника с данным порядком альтернатив и с весом не меньше, чем V, то для нового профиля получится коллективное ранжирование, где ai > о-2 > ... > аш.

Свойство Кондорсе. Если альтернатива является победителем Кондорсе, тогда эта альтернатива в коллективном предпочтении занимает первое место. Сильное свойство Кондорсе. Если w(x) 2 w(y), 1(х) С. 1{у) и h{x.y) > W/2, то в коллективном предпочтении х будет не ниже, чем у.

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

К и ее дополнение А \ К. Стратегиями коалиций является выбор единой альтернативы г € К и ■} 6 Л \ К. Альтернатива, набирающая больше половины голосов участников, объявляется победителем, в противном случае объявляется ничья. Выигрыш в этой игре равен

( IV

Щг,Л = I [к&з) - у

где индикаторная функция 1(г)=1 если 2>0, 1{г)=1/2 если л=0, и 0 иначе.

Смешанная стратегия коалиции К обозначается как вектор р = т. ч. р-1 > 0 для всех г е К, кр, = 1, а стратегия коалиции А \ К как вектор q = т. ч. щ > 0 для всех з £ А\ К, Ъ = Рав"

новссие в смешанных стратегиях гарантируется теоремой Нэша. В качестве выигрыша г'(А') коалиции К рассматривается значение биматричной игры с выигрышами Н(1,з) коалиции К против контркоалиции А \ К

у(К) = тахтт^

!6Л" }€А\К

Характеристическая функция и определяется следующим образом

и(К) = тахтт^ ^ /г(г,

р ч

¿еА' ]€А\К

как значение биматричной игры с выигрышами/1(1,7) коалиций К и А\К. Характеристические функции г>ь г;2. г;3 определяются по формулам:

Ы'О = XI ЫЛ') = ^ ттЛ(г,ДЯ(и'),

'"¡{К) = ^ тш¡1(1,3).

Для построенных характеристических функций вычисляется сила альтернативы, используя вектор Шепли

*х(у)= Е "1)!№'и.г)-в(А')), хеА.

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

Теорема 6. Характеристические функции V, и, г^ — г'з являются неотрицательными и монотонными. Процедуры коллективного ранжирования согласно вектору Шепли для этих функций обладают свойствами, представленными в таблице ниже.

Свойство V и Vi v2 г'з Бо Ко Ма

Гомогенность да да да да да да да да

Единогласие да да да да да да да да

Монотонность да да да да да да да да

Правило большинства да нет да да да да да пет

Кондорсе да да да да ист нет да да

Сильное Кондорсе да нет да нет нет пет да нет

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

Публикации автора по теме диссертации

1. Мазалов В. В., Кондратьев А. Ю. Задача о сделках с неполной информацией // Вестн. С.-Петерб. ун-та. Сер. 10. - 2012. - Вып. 1. - С. 33—40.

2. Мазалов В. В., Кондратьев А. Ю. Равновесие в сделках с пороговыми стратегиями // Математическая теория игр и ее приложения. - 2013. - Т. 5, № 2. - С. 046-063.

3. Кондратьев А. Ю. Равновесие по Нэшу в стационарном состоянии в многошаговой модели двойного закрытого аукциона // Современные проблемы науки и образования. — 2013. -№6,-URL: http://www.science-education.ru/113-11533 (12.01.2014)

4. Kondratev A. Y. Stationary State in a Multistage Auction Model // Contributions to game theory and management. - 2014. - Vol. 7, SPbSU. - P. 151-158.

5. Mazalov V. V., Kondratev A. Y. The bargaining solution among threshold strategies // Automation and Remote Control. - March 2015. - Vol. 76, Issue 3. - P. 507-520.

G. Kondratev A. Y. The relationship between discreto and continuous equilibria in bargaining model // Collected abstracts of papers presented on the Seventh International Conference Game Theory and Management. St. Petersburg, Russia June 26-28, 2013. - P. 115-116.

7. Kondratev A. Y. N-thrcshold approximation of continuous equilibrium in internet auction// Extended abstracts presented on international workshop "Networking Games and Management". Petrozavodsk, Russia, june 23-25. 2013. - P. 51-52.

8. Кондратьев А. Ю. Модели еделок с честными стратегиями // Труды VII Московской международной конференции по исследованию операций (Москва, Россия, Октябрь 15-19, 2013). - T. И. - С. 183-185.

9. Кондратьев А. Ю. Многошаговая задача о сделках с неполной информацией // XII Всероссийское совещание по проблемам управления ВСПУ-2014, Москва, 16-19 июня 2014 г.: Труды. - С. 8314-8320.

10. Kondratev A. Y., Mazalov V. V. Bargaining about meeting time // Game theory and management. Abstracts. St. Petersburg. - 2012. - P. 122-123.

11. Kondratev A. Y. Bargaining about meeting time with pieeewisc-linear utilities // Game theory and management. Abstracts. - 2014. - P. 118-119.

Подписано в печать 21.09.2015.Формат 60x84 '/|г„ Уч.-изд. л. 1,1. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 312.

Карельский научный центр РАН Редакционно-издательский отдел 185003, Петрозаводск, пр. А. Невского, 50