Равновесия по Нэшу в игре голосования

Культина, Мария Владимировна

Равновесия по Нэшу в игре голосования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Культина, Мария Владимировна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

1998 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Равновесия по Нэшу в игре голосования»

Автореферат диссертации на тему "Равновесия по Нэшу в игре голосования"

C-'i С})

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

а? УНИВЕРСИТЕТ

ar 3 c=

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

КУЛЬТИНА Мария Владимировна

РАВНОВЕСИЯ ПО НЭШУ В ИГРЕ ГОЛОСОВАНИЯ

(01.01.09- "Математическая кибернетика")

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

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

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

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

наук, профессор Л. А. Петросян

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

кандидат физико-математических наук, С. Н. Возшок

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

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

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

Защита состоится '

1998 г. в__ часов на заседании

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

Ученый секретарь Диссертационного совета, д.ф.-м.н.

В. Ф. Горьковой

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

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

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

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

Исследования в области теоретико-игрового моделирования процедур голосования и процессов формирования коалиций на множестве выборщиков активно ведутся в течение последних десятилетий во многих странах. Здесь следует отметить работы Э. Мулена, С. Брамса, Р. Ауманна, Р. Зелиена, Ф. Страффина, Р. Мейерсопа, Е. Винтера, Дж. Гринберга.

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

Равновесие по Нэшу является основным принципом оптимальности в некооперативных (стратегических) неантагонистических играх п лиц. По циклу работ, связанных с данным принципом оптимальности, в 1994 г. группе ученых: Дж. Нэшу, Дж. Харсани и Р. Зельтеиу была присуждена Нобелевская премия.

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

блематикой. Здесь следуех отметить работы Н. Н. Воробьева, JI. А. Петросяна, А. Ф. Клейменова, А. В. Кряжимского, О. А. Малафеева, С. В. Чистякова, В. В. Захарова, В. И. Жуковского, Н. А. Зенкевича, С. Н. Вознюка, Н. И. Савищенко, С. И. Тарашниной, А. Е. Вардана, К. С. Вайсмана.

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

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

Подход к вопросу формирования коалиций, состоящий в построении циклической многошаговой игры п лиц с полной информацией, был предложен Л. А. Петросяном [1994, 1996J. В диссертационной работе рассмотрено обобщение этого подхода для процесса формирования коалиционных разбиений.

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

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

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

Апробация работы. Результаты исследований, представленные в работе, прошли апробацию на международных конференциях: N.N.Vorob'ev Memorial Conference (С.Петербург, 1996), IV International Workshop "Multiple criteria and game

problems under uncertainty" (Moscow, 1996), XI Conference on Game Theory and Applications (Milano, 1997), XII Conference on Game Theory and Applications (Genova, 1998); международном научном конгрессе "Народы содружества независимых государств накануне третьего тысячелетия: реалии и перспективы" (Санкт-Петербург, 1990). Кроме того, основные результаты работы докладывались на городском семинаре по теории игр под руководством проф. Л. А. Петрос.яна (Санкт-Петербург) и на семинарах кафедры математической статистики, теории надежности и массового обслуживания Санкт-Петербургского государственного унииерситста.

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

Структура. Диссертация состоит из введения, трех глав, разбитых на 11 параграфов и заключения, изложенных на 112 страницах текста и содержащих 6 рисунков и 8 таблиц, а также включает приложение с исходными текстами программ на 6 страницах.

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

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

Глава 1 посвящена исследованию теоретико - игровой модели выборов правления концерна, состоящего из п независимых компаний А\,...,Ап. Обозначим а; — количество избирателей в компании Ai, I € N — {1,.. ., л}; а, представляет вес А{ о концерне.

Каждая компания, входящая в концерн, выдвигает одного кандидата в правление. Избиратели голосуют да или нет относительно каждого из представленных кандидатов. Победители определяются по правилу относительного большинства: кандидат 6; от компании А^, ! € ЛГ = {1,... ,п}, считается избранным в правление, если за него отдано более половины голосов от общего числа избирателей (более, чем ^ ■ ^ а, да).

выигрыш К > 0, если ]Г ai > г ' S ач и = если ^ а,- < | • а>-igs ¡глг ¡es ¿ел

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

правление, пропорционально их весу в концерне:

a(S)

где a(S) = а,; выигрыш компаний, чьи кандидаты не вошли в избранное правление, составляет 0, т. е. для i £ S:

А = о. (2)

Рассмотрим одновременную игру п лиц, в которой игроками являются избиратели. Число мест в правлении не фиксировано и определяется в результате голосования.

Будем называть коалицией любое подмножество 5 С N. Определение 1. Коалиция S называется выигрывающей, если для нее выполнено условие:

(3)

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

a{S) — mm a(S), (4)

seiv

Множество всех минимальных выигрывающих коалиций обозначим W.

Коалиция 5 включает в себя более половины избирателей, и, в то же время, является минимальной из всех коалиций, удовлетворяющих этому условию. Вообще говоря, коалиция S, определяемая из условия (4), не единственная. Однако, члены некоторой фиксированной минимальной выигрывающей коалиции не заинтересованы в том, чтобы к ним присоединялись другие участники, т. к. в этом случае выигрыш первых уменьшится (см. (1)).

Объединившись в минимальную выигрывающую коалицию, игроки смогут сформировать правление из наиболее благоприятных для них кандидатов, обеспечив себе, при этом, наибольший выигрыш. Для этого участники некоторой фиксированной минимальной выигрывающей коалиции S должны проголосовать да относительно кандидатов от компаний AJt j Е S, и нет относительно всех остальных. Стратегии избирателей из U А, не могут повлиять на результат выборов,

I $s

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

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

Предлагается рассмотреть следующую модель процесса формирования коалиций: пусть игроками являются компании N — {1,. .., г,.. ., п}. Случайным образом выбирается первый игрок, который может предложить кому-либо из игроков - компаний сформировать коалицию. Если выбранный игрок желает присоединиться к такой коалиции, он соглашается и выбирает следующего участника, и т. д. Если принимающий решение игрок не хочет вступать в коалицию, в которую его пригласили, он может отклонить предложение и начать формирование другой коалиции, выбрав в качестве следующего принимающего решение одного из ее предполагаемых участников и т. д. Процесс заканчивается, когда будет сформирована выигрывающая коалиция или все игроки примут решение по одному разу. Если в ходе игры не сформировалась ни одна выигрывающая коалиция, выигрыши всех игроков полагаются равными нулю. В случае, когда сформировалась некоторая выигрывающая коалиция 5, ее участники получают выигрыш, пропорциональный весу:

^ = як ■ К> э6 ,5)

Л, = О, Н 5.

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

Зафиксируем й € Ш - произвольную минимальную выигрывающую коалицию. Определим набор стратегий (оь..., а;,..., а„) следующим образом: если г ^ 5, то ¡1; - произвольная. Предположим, что г € 5. В позиции и = (М, 5, г) (г ё 5

- принимающий решение игрок) игрок i решает сформировать новую коалицию (если SnS = 0), включив в нее себя, и, приглашая войти туда остальных игроков из 5, выбрав одного из них в качестве принимающего решение. (То есть, отказывается формировать коалицию S). Таким образом, a¿ = RYk, к е S \ {¿}. Если SnS ф 0, то игрок г соглашается войти в коалицию S и, если (М\{г})П5 ф 0, то он приглашает любого из игроков к 6 (Aí\{¿})n5 войти в S, выбрав его в качестве следующего принимающего решение (a¿ = YYk, к £ (M\{j})nS). Если (M\{i})nS = 0, игрок входит в эту коалицию S и отказывается выбирать следующего принимающего решение, то есть завершает формирование коалиции (а, = YR).

Теорема 1.4. Ситуация (ai, ..., а,,..., а„) является равновесием по Нэшу в игре Gj.

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

Определение 5. Коалицию Scr е N назовем критической, если для нее выполнены следующие условия : 6 W, и существует такой игрок i0 6 5„, что (S* \ {¿o}) i W.

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

¡6 N\S

У ti < К - x^S1^ для каждой scr С N, (6)

l6Scr\S v '

í, > 0, г е N \ S,

где 5 € W - любая фиксированная минимальная выигрывающая коалиция.

Пусть {£,; i € JV \ S} - какое-либо решение (6). Пределы для допустимых требований > = 1,..., я определим следующим образом:

0<(¡<l, i€N\S,

— (') О < ti < -'t, • К, i е s.

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

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

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

Даппая процедура порождает многошаговую игру (3} п лиц с полной информацией.

Теорема 1.6. Ситуация а = (Зь.. ., а,,.. .,»„), где

если в позиции и = (Л/, 0 не существует ни одной критической коалиции С 5* и {¿}, и

а,(и) ^

и $ 1/Т,

Яст с 5" и {'/}, если в позиции и = иь'1,') суу^ествуепг коа-

лиция типа 5„ С 5" и {г}, {Л}, если в позиции и = (А/,,») € 1!т не суще-

ствует коалиция типа 5СГ С 5* и {г}, где в' и в — множества игроков, которые выдвинули максимально допустимые требования и тех, кто выдвинул меньшие требования, соответственно, в ситуации и — а 11'г — множество терминальных позиций в С?з(Г), является равновесием пв Ношу в игре <?з.

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

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

Обобщим определение множества выигрывающих коалиций.

Определение 7. Коалиция § называется выигрывающей (5 е И7), если:

а(§) > - • а(Ю, Р

где а(5) = X) аи а(М) = ^ а*. ¡е4 ¿ел

W — множество минимальных выигрывающих коалиций, то есть таких коалиций S, что:

a(S) = mm a(S). sew

Определение 8. Коалиционным разбиением множества компаний назовем:

r = {Sll...,S',}, = (8)

¡=1

В рассматриваемой модели может существовать одновременно несколько выигрывающих коалиций.

Определение 9. Выигрывающим коалиционным разбиением назовем такое разбиение т:

f = {Sx.....Я; Sr+1}, (9)

для которого выполнены следующие условия:

Sr+i £ W.

Очевидно, что разбиение указанного типа не единственно.

Для сформировавпшгося коалиционного разбиения выигрыши игроков определим следующим образом: каждая выигрывающая коалиция получает К > 0 и эта величина делится между компаниями (игроками), вошедшими в данную коалицию в соответствие с некоторым правилом таким образом, чтобы выполнялось:

= к> SjET, Sj е W

ies,

где gi — выигрыш игрока г € S1,. Для любой компании I 6 Sp е г, где Sp £ И-', величина gi полагается равной нулю.

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

В главе 2 рассматривается приложение моделей, построенных в главе 1 к теории кооперативных игр. В частности показано, что для кооперативной игры (N,v) с непустым ядром, где N — множество игроков, под которым мы понимаем

множество компаний, а V — характеристическая функция, определенная следующим образом:

'К, если С е IV

VI Г"

' если С ¿IV

г к,

"(СНо.

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

Обозначим Со — С-ядро данной игры. Зафиксируем некоторый дележ -у = (7b.--.7i.---,7») € Со.

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

0< (, <1„ г= 1,...,п (11)

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

Теорема 2.1. Ситуация а = («1,... ,аг,.. ., а„), где

7,, если позиция и = (М, ^ия',*) ^ ^г,'

О; = >

. 5* и {г}, если позиция и = (Л/, 6>иЯ">г) £ Vт

где 5* — множество игроков, выдвинувших максимальные требования ("¡0, о, 51 — немаксимаяъпяс, является ситуацией равновесия по Н&шу в рассматриваемой игре.

На основании многошаговой игры с требованиями предложен новый подход к определению оптимального дележа. Проведена серия численных экспериментов, что позволило сравнить новый оптимальный дележ с известпыми решениями кооперативных игр (вектор Шепли, индекс Банзафа, индекс Дегана - Пакеля). Так, например, в случае, когда концерн состоит из 6 компаний: N = {1,... ,6}, с весами: 10, 15, 20, 45, 30, и 10, соответственно, и выигрыш, который делят между собой члени правления К = 140, имеем дележи, приведенные в таблице.

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

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

Игроки 1 2 3 4 5 6

Веса 10 15 20 45 30 10

Средние выигрыши 14.75 16.64 30.58 42.84 21.32 14.99

Вектор Шепли 9.33 14.0 21.0 58.30 28.0 9.33

Индекс Банзафа 10.37 15.56 20.74 57.04 25.93 10.37

Индекс Дегана-Пакеля 27.22 31.11 11.67 31.11 11.67 27.22

Таблица 4

В этом смысле можно говорить о большей справедливости рассматриваемой схемы. Кроме того, отличительной чертой этой процедуры является то, что оиа поддерживается равновесием по Нэшу (теорема 2.1).

Глава 3 посвящена исследованию динамического процесса выборов в правление концерна. Процесс рассматривается па временном интервале [О, Т]. Этот промежуток разбит точками 0 = <о < ¡1 < ... < = Т, определяющими моменты времени, в которые компании, объединенные в концерн, переизбирают свое правление. Голосование так же происходит по правилу относительного большинства, но каждая компания имеет возможность выдвинуть несколько кандидатов.

Обозначим Л,(£) — мгновенный выигрыш г-ой компании в момент времени Тогда суммарная прибыль А, от начала функционирования концерна до момента времени I составляет:

сц(Ь) = У Л,(г)о!г, I 6 [0,Т], ! 6 N (12)

Обозначим выигрыш компании Ai на отрезке времени [¡¿-ь^]:

г»

»;[<*-!,г*] = I (13)

и-1

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

Члены коалиции 5* получают дополнительную прибыль от непосредственного участия в руководстве деятельностью концерна. Пусть К — суммарный выигрыш, получаемый члепами 5* за период

Данную величину К члены коалиции распределяют между собой, определяя таким образом свой выигрыш, обозначаемый: тД^-ь^Ь который они получат за период деятельности концерна до следующих выборов, ^ Т^-ь^] = Л*-

В течении суммарный выигрыш I € выплачивается компании

А,, г 6 Зк в соответствии с законом который будет определен ниже. Тогда

функцию выигрыша компании А, можно определить следующим образом:

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

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

гея'

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

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

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

Введем обозначение для множества выигрывающих коалиций, содержащих некоторое фиксированное подмножество игроков IVм-. WM — {S : S Ç W, M С S}. В частности, множество выигрывающих коалиций, содержащих игрока г0, будет выг лядеть следующим образом: Wl*0' = {S : S £ W,iо € S}.

Определим так же множество выигрывающих коалиций но некотором фиксированном подмножестве M: W (M) = {S : S e W, S С M}.

Стратегией "ведущего" игрока является пара:

а10(а) = {S* £ ÎTibes*. X] = К' > aifa-uh]} (16)

tes*

Стратегией "активного" игрока j является одно из значений фупкции ipj, заданной на множестве всевозможных предложений 7j игроку j "ведущим" игроком ¿о. Функция ipi(fj) может принимать одно из двух значений: {о, па}, что означает, соответственно, "согласиться с предложением "ведущего" игрока" (то есть присоединиться к формирующейся коалиции Sk) и "отказаться от предложения".

Рассмотрим "активного" игрока j 6 S* \ {г0}, который должен ответить на предложение "ведущего". Пусть каждый игрок j определяет для себя минималъ-

ное значение у*, на которое он готов согласиться. Это означает, что стратегия ] определяется следующим образом:

{а, если 7* < 7; < К па, если 7, < 7*

Эта модель может быть проиллюстрирована с помощью блок-схемы.

Введем обозначение для множества выигрывающих коалиций, содержащих некоторое фиксированное подмножество игроков XVм-. = {5 : 5 € И' М С 5}. В частности, множество выигрывающих коалиций, содержащих игрока ги, будет выглядеть следующим образом: И'*'0' = {5: 5 6 ¿о 6 й).

Определим так же множество выигрывающих коалиций на некотором фиксированном подмножестве М: 1 У(М) = {5 : 5 € С Л/}.

Можно рассмотреть многоступенчатую суперигру б(С?5(Г)) продолжительностью Т, определенную на промежутке [О,Т], на каждой ступени которой разыгрывается многошаговая игра С5(Г) и построить в ней равновесие по Кэшу.

Пусть на множестве Цг(">) решена задача максимизации выигрыша "ведущего" игрока:

тах 1,4*] = тах

£ ъ

уез\{;„}

(18)

при условии:

К- £ ъ1Ь-ъЬ]> аг00*-</ь-1) (19)

и пусть, в С IV — ее решение.

Теорема 3.1. Следующий набор стратегии образует ситуацию равновесия по Нэшу в игре Сг5(Г):

а;0(и) = (5; {7,}у€г)

аЛи) = ¥>/Ы = а, з е {¿о}

(20)

Определение 11. Функции /?*(т), определяющие правило, согласно которому на интервале распределяются выигрыши, называются процедурой распределения платежей: и

I ${Т)*Т = - ^-1] - 11 iesk\ Ы; 'к-1

распределения платежей:

J 0^{r)dr = 7*[í* - ít_J =7?, i esk\ {¿o}; it-i

í ^(r)dr = Jf- -y?;

«,"_, ¡€S»\(¿ol

0Í{r) > o, i e s*

где S* — выигрывающая коалиция, сформировавшая правление в момент времени ti¡-i, а г'о — "ведущий" игрок на fc-ой ступени.

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

таким образом, чтобы ни для одного из игроков не нашлось бы такого момента времени, в который выбранная стратегия перестала бы являться оптимальной. То есть, любой из "активных" игроков в каждый промежуточный момент времени t € , ífc] должен быть уверен в том, что, продолжая работать в правлении и далее, он получит прибыль не меньше, чем, выйдя из его состава.

Показано, что процедура распределения платежей fli(t), t £ [ít_i,íi] динамически устойчива на шаге к, если для любого t 6 [ít_i,ít] верно неравенство:

P-(t)<hj(t), jeS (21)

В заключении обобщены основные результаты диссертационной работы.

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

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

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

— предложен новый способ построения дележа, поддержанного равновесием по Нэшу в соответствующей многошаговой игре;

— исследованы два принципиальных подхода к вопросу создания выигрывающей коалиции:

- подход, основанный на учете требований игроков - потенциальных участников выигрывающей коалиции;

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

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

1. Культипа М. В. Теоретико - игровая модель выборов правления концерна. //Сложные управляемые системы. Межпузовский сборлик научных трудов. М.: РосЗИТЛП, 1996. Стр. 129-132.

2. Культина М. В. Принцип решающего большинства в демократическом парламенте./ / Международный научный конгресс "Народы содружества независимых государств накануне третьего тысячелетия: реалии и перспективы": Тезисы докладов. Санкт-Петербург, 15-17 мая 1996, том III. Стр. 86-88.

3- Kultina M. The multistage game modeling the board election.// Game theory and economics. N. N. Vorob'ev memorial conference: Abstracts. St. Petersburg, June 27-30, 1996. P. 36.

4. Kultina M. Construction of the minimal admissible coalition for the voting game.// Fourth International Workshop "Multiple criteria and game problems under uncertainty": Abstracts. Moscow, 8-14 September, 1996. P. 51.

5. Kultina M. Game theoretic model of the board election.// International Journal of Mathematics Game Theory and Algebra. N.Y.: Nova Science Publishers, Inc., 1997. P. 127-138.

6. Петросян JI. А., Культина М. В. Обобщенная процедура Кондорсе для множественного выбора. Теоретико - игровой подход. // "Понтрягинские чтения - VIII" на Воронежской весенней математической школе "Современные методы в теории краевых задач": Тезисы докладов. Воронеж, 4-9 мая 1997. Стр. 116.

7. Leon A. Petrosjan, Maria V. Kultina Dynamic Model of Board Election.// 11th Coference on Game Theory and Applications: Abstracts. Milano (Italy), 9-10 June, 1997. P. 160-161

8. Kultina M., Kwon O-Hun Board election in a concern.// The Korean Mathematical Society Meeting: Abstracts. Seoul (Republic of Korea), October 1997, vol. 34, no. 2. P. 53.

9. Maria V. Kultina, O-Hun Kwon Winning Coalitional Partition in Voting Games.// XII Ccmvegno di Teoria dei Gioclii ed Applicaziom: Books of Abstracts. Genova (Italy), DIMA, Universita di Genova, 26-27 June 1998. P. 49.

ЛР №040815 от 22.05.97

Подписано к печати 20.09.98 г. Формат 60x90 1/16. Усл. п.л. 1,0. Тираж 100 экз. Заказ 510.

Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ. 198904, Санкт-Петербург, Ст. Петергоф, Университетский пр., 2.

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

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

УНИВЕРСИТЕТ

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

КУЛЬТИНА МАРИЯ ВЛАДИМИРОВНА

РАВНОВЕСИЯ ПО НЭШУ В ИГРЕ ГОЛОСОВАНИЯ

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09. - "Математическая кибернетика"

Научный руководитель,

д.ф.-м.н., профессор Л. А. Петросян

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

Содержание

Введение 3

1 Теоретико — игровая модель выборов правления 13

1.1 Равновесие по Нэшу в одновременной игре голосования. Число мест в правлении не фиксировано..............13

1.2 Равновесие по Нэшу в одновременной игре голосования. Число мест в правлении фиксировано..................19

1.3 Многошаговая игра формирования коалиции..............23

1.4 Ситуация равновесия в многошаговой игре с требованиями..............................................................34

1.5 Многошаговый процесс построения выигрывающего коалиционного разбиения множества игроков................53

2 Приложения к теории кооперативных игр 66

2.1 Новый подход к определению оптимального дележа. . . 66

2.2 Теоретико - игровая модель полной кооперации..........78

2.3 Теоретико - множественный подход к формированию выигрывающей коалиции......................................81

3 Динамический процесс построения выигрывающей коалиции 84

3.1 Суперигра, моделирующая выборы правления...... 84

3.2 Ситуация равновесия в суперигре............. 98

3.3 Динамическая устойчивость оптимального поведения . 102

Заключение 106

Литература 108

Приложение 1 113

Приложение 2 116

Введение

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

Основные положения диссертации, выносимые на защиту, состоят в следующем:

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

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

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

Банзафа и др.).

4. Исследованы два подхода к вопросу создания выигрывающей коалиции:

- подход, основанный на учете требований игроков — потенциальных участников выигрывающей коалиции;

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

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

В настоящее время в основном моделируются вопросы, связанные не с тем, как происходит или должен происходить групповой выбор, а с тем, какой выбор "справедлив" или "разумен" с каких-либо точек зрения. Основные концепции социального выбора возникли в экономической науке еще до начала нашего столетия и связаны с именами Курно, Эджворта, Парето. Одним из основоположников теории голосования как науки по праву считается Ж. Ш. Борда, первым предпринявший попытку сравнительного и критического анализа процедур голосования в своем докладе "О способе проведения выборов", сделанному в Академии наук во Франции 16 июня 1770 г.

Дальнейшим исследованиям социального выбора посвящено немало работ К. Эрроу [30], Э. Мулена [16,17], С. Брамса [34, 35, 36], Р.

Фаркуарсона [37], Ф. Страффина [44] и других ученых. Среди отечественных работ, связанных с проблемами группового выбора, в том числе - посвященных процедурам голосования и их сравнительному анализу, следует отметить Б. Г. Миркина [15], В. И. Вольского и 3. М. Лезину [2].

Исход выборов во многом зависит от того, какие коалиции сформировались среди избирателей в ходе предвыборной борьбы. Поэтому вопрос формирования выигрывающих коалиций, обладающих всей полнотой права принятия решения в предположении, что члены коалиции могут координировать свои действия, заслуживает особого внимания. Его значительную роль отмечали еще основоположники теории игр — фон Нейман и Моргенштейн [18]. Они же и предложили первую некооперативную модель формирования коалиций, основанную на одновременной игре п лиц. Стратегия игрока в этой модели состояла в выборе коалиции, к которой он хотел бы присоединиться. Коалиция 5 считалась сформированной тогда и только тогда, когда все игроки из 5 выбирали стратегию: "Я хочу присоединиться к 5 ". В диссертационной работе проведен анализ данной модели и построено равновесие по Нэшу (см. [б]).

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

Тем не менее, был предпринят ряд попыток построения модели формирования коалиций в рамках некооперативных игр.

Ауманн [31], исследуя этот вопрос, вводил в рассмотрение стра-

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

Для дальнейшего изучения вопроса было введено специальное понятие "сильного равновесия по Нэшу" (см. JI. А. Петросян [29]), которое учитывало так называемые "самопринудительные" соглашения среди членов коалиции (Бернхейм [32], Бернхейм и Вин-стон [33] ).

Процесс формирования коалиций исследуется также с точки зрения игр в развернутой форме, что позволяет рассмотреть эту процедуру как последовательность принятия решений: Гул [39], Харт и Мак-Коел [40]. Упомянутые работы посвящены, в основном,

Boo о

модели, предлагаемой в данной диссертационнои работе, рассмотрен случай п игроков, п > 2.

Подход к вопросу формирования коалиций в рамках теории стратегических игр, состоящий в построении циклической многошаговой игры п лиц с полной информацией, впервые был предложен JI. А. Петросяном [22]. Дальнейшее развитие этот вопрос получил в работе JI. А. Петросяна, где рассматривается модель для случая, когда число мест в правлении не фиксировано. Результаты опубликованы в монографии JI. А. Петросяна и Н. А. Зенкевича (см. [24, 28]) В данной диссертационной работе предложено обобщение этого подхода для процесса формирования коалиционных разбиений.

В качестве основного принципа оптимальности для исследования построенных моделей выбрано равновесие по Нэшу (см. [42]),

которое является основным принципом оптимальности в некооперативных неантагонистических играх. По циклу работ, связанных с ним, в 1994 г. группе ученых: Дж. Нэшу, Дж. Харсани и Р. Зельте-ну была присуждена Нобелевская премия.

В отечественной литературе по многошаговым и дифференциальным играм также уделяется большое внимание равновесию по Нэшу и связанной с ним проблематикой. Здесь следует отметить работы Н. Н. Воробьева, Л. А. Петросяна, А. Ф. Клейменова, А. Б. Кряжимского, О. А. Малафеева, С. В. Чистякова, В. В. Захарова, А. Ф. Каноненко, Г. И. Дюбина, В. И. Жуковского, Н. А. Зенкевича, С. Н. Вознюка, Н. И. Савищенко, С. И. Тарашниной, А. Е. Бардина, К. С. Вайсмана.

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

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

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

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

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

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

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

Четвертый параграф первой главы посвящен исследованию процесса формирования коалиций в случае, когда игроки - компании

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

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

Вторая глава состоит из трех параграфов и посвящена некоторым приложениям рассматриваемых моделей и методов их исследований к кооперативным играм.

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

Второй параграф посвящен построению процедуры формиро-

вания выигрывающей коалиции, поддерживающей полную кооперацию. В данном параграфе проводится анализ классической кооперативной игры (ТУ, г»), где n — множество игроков, которыми являются компании, а« — характеристическая функция. Предполагается, что С-ядро данной игры не пусто. За основу выбрана модель формирования коалиции, предложенная во второй части параграфа 1.4. В качестве максимально допустимых требований рассматриваются элементы ядра. Для данной игры построено равновесие по Нэшу, сформулирована и доказана соответствующая теорема.

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

Третья глава состоит из трех параграфов.

Процесс рассматривается на временном интервале [0,Т]. Этот промежуток разбит точками 0 = ^ < tl < ... < tk = Т, определяющими моменты времени, в которые компании, объединенные в концерн переизбирают свое правление. Пусть голосование происходит по правилу относительного большинства, причем каждая компания выдвигает несколько кандидатов.

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

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

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

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

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

В заключении обобщены основные результаты диссертационной работы.

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

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

Глава 1

Теоретико — игровая модель выборов правления

1.1 Равновесие по Нэшу в одновременной игре голосования. Число мест в правлении не фиксировано.

Пусть п независимых компаний, объединенных в концерн, собираются выбрать правление. Обозначим аг- — число избирателей в компании А{, г Е N = {1, 2,..., гг}; аг- будем называть весом компании Аг- в концерне.

Каждая компания предлагает одного кандидата для принятия участия в выборах. Обозначим его 6г; Ьг- £ Аг-,г = 1 ,...,гг. Таким образом, имеем п кандидатов:

Каждый избиратель решает да или нет относительно каждого из кандидатов. Такая процедура голосования носит название "approval voting" (см. [36, 38]). Итогом голосования избирателя бу-

дет n-мерный вектор, г-ая компонента которого принимает одно из значений: да или нет. Например, бюллетень избирателя после голосования может выглядеть так: (да,нет,,... ,да, ...,нет). Кандидат b¡ считается избранным в правление по правилу относительного большинства (см. [16] ), если за него отдано более половины голосов

(более, чем | • да).

i= 1

Предположим, что правление выбрано. Обозначим его В = {Ьг- : i Е S С N}. Правление В получает выигрыш К, который не зависит

от его членов и их числа. Причем, К > О, если ^ > \ • Yh ai-> и

ies i€N

К = 0, если Yhai ^ Yh ai- То есть, ненулевой выигрыш получает ies i€N

только то правление, которое представляет интересы большинства избирателей.

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

члена Ь{ (или, что тоже самое, компании Ai), составляет: