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

• Культина, Мария Владимировна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Культина, Мария Владимировна

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Приложение 1

Приложение 2

Введение диссертации (часть автореферата) на тему «Равновесия по Нэшу в игре голосования»

Введение

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

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

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 приведены исходные тексты программ, позволяющих получить экспериментальные данные для вычисления

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Культина, Мария Владимировна

Заключение

Подведем основные итоги диссертационной работы.

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

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

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

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

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

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

Литература

[1] Ашманов С. А. Линейное программирование. М.: Наука, 1981.

[2] Вольский В. И., Лезина 3. М. Голосование в малых группах: Процедуры и методы сравнительного анализа. М.: Наука, 1991. 191 С.

[3] Воробьев Н. Н. Теория игр для экономистов кибернетиков. М.: Наука, 1985.

[4] Воробьев Н. Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984. С. 495.

[5] Дюбин Г. Н., Суздаль В. Г. Введение в прикладную теорию игр. М.: Наука, 1981.

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

[7] Kultina М. 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.

[8] Культина M. В. Принцип решающего большинства в демократическом парламенте.// Международный научный конгресс "На-

роды содружества независимых государств накануне третьего тысячелетия: реалии и перспективы": Тезисы докладов. Санкт-Петербург, 15-17 мая 1996, том III. Санкт-Петербург, ТОО ТК "Петрополис", 1996. С. 86-88.

[9] Kultina М. 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. Moscow, 1996. P. 51.

[10] 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.

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

[12] Kultina M. V., Kwon O-Hun. Winning Coalitional Partition in Voting Games.// XII Convegno di Teoria dei Giochi ed Applicazioni: Books of Abstracts. Genova, 26-27 June 1998. Italy, Genova: DIMA, Universita di Genova. P. 49.

[13] Льюис P., Райфа X. Игры и решения. Введение и критический обзор. М.: ИЛ, 1961.

[14] Мак-Кинси Дж. Введение в теорию игр. М.: Физматгиз, 1960.

[15] Миркин Б. Г. Проблема группового выбора. М.: Наука, 1974. С. 256

[16] Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985.

[17] Мулен Э. Кооперативное принятие решений: Аксиомы и модели. М., 1991.

[18] Фон Нейман Дж., Моргенштейн О. Теория игр и экономическое поведение. М.: Наука, 1970.

[19] Оуэн Г. Теория игр. М.: Мир, 1971.

[20] Петросян J1. А. О непрерывной зависимости множества управляемости от параметра. Всесоюзная конференция "Динамическое управление": Тезисы докладов. Свердловск, 30 мая - 1 июня 1979 г. С. 208-210.

[21] Петросян JI. А. Устойчивость решений в дифференциальных играх со многими участниками.// Вестн. Ленингр. ун-та, 1977, N19, вып. 4. С. 46-52.

[22] Petrosjan L. A. Voting the directorial council. VIII Workshop on Dynamics and Control: Abstracts. Hungary, Sopron, 1995.

[23] Петросян JI. А., Данилов H. H. Устойчивые решения в дифференциальных играх с трансферабельными выигрышами.// Вестн. Ленингр. ун-та, 1979, N1. С. 52-59.

[24] Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. М.: Высш. шк., 1998. - с.

[25] Петросян Л. А., Культина М. В. Обобщенная процедура Кондор-се для множественного выбора. Теоретико - игровой подход. //

"Понтрягинские чтения - VIII" на Воронежской весенней математической школе "Современные методы в теории краевых задач": Тезисы докладов. Воронеж, 4-9 мая 1997. С. 116.

[26] Petrosjan L. A., Kultina М. V. Dynamic Model of Board Election.// 11th Coference on Game Theory and Applications: Abstracts. Milano, 9-10 June 1997. Italy, Milano. P. 160-161

[27] Петросян JI. А., Савищенко H. И. Теоретико - игровая модель загрязнения воздушного бассейна: Учебное пособие. СПб.: Изд-во С. Петербургского уриверситета, 1997. - 92 с.

[28] Petrosjan L. A., Zenkevich N. A. Game Theory. Singapore: Uto-Print, 1996. - p. 352.

[29] Петросян JI. А., Ширяев В. Д. Иерархические игры: Учебное пособие. Саранск: Изд. Мордов. Ун-та, 1986. - 92 с.

[30] Arrow К. J. Social choice and individual values. New Javen: Yale University Press, 1963. (2nd edn.)

[31] Aumann R. A survey of cooperative games without side payments.// M. Shubik (ed.) Essays in Mathematical Economics. Princeton University Press, 1967. P. 3-27.

[32] Bernheim B. D., Peleg В., Whinston M. Coalition proof Nash Equilibria, I: Concepts.// Journal of Economic Theory, no. 42, 1987. P. 1-12.

[33] Bernheim B. D., Whinston M. Coalition proof Nash Equilibria, II: Applications.// Journal of Economic Theory, no. 42, 1989. P. 13-29.

[34] Brams S. J. Game theory and politics. New York: Free Press. 1975.

[35] Brams S. J. Theory of moves. Cambridge: Cambridge University Press, 1994.

[36] Brams S. J. Voting Procedures.// Aumann R., Hart S. (eds.) Handbook of Game Theory with Economic Applications, vol. II. Amsterdam, 1994. P. 1055-1089.

[37] Farquharson R. Theory of voting. New Haven: Uale university Press. 1969.

[38] Greenberg J. Coalition Structers. // Aumann R., Hart S. (eds.) Handbook of Game Theory with Economic Applications, vol. II. Amsterdam, 1994. P. 1305-1337.

[39] Gul F. Bargaining Foundations of Shapley Value.// Econometrica, no. 57, 1989. P. 81-95.

[40] Hart S., Mac-Coell A. N-person non-cooperative bargaining, MIMEO, Center for Rationality and Interactive Decision Theory, 1992.

[41] Kuhn H. W. Extensive games and the problem of information. // Annals of Mathematics Studies, no. 28, 1953. P. 193-216.

[42] Nash J. Equilibrium points in n-person games. // Proc. Nat. Acad. Sci., vol. 36, 1950. P. 48-49.

[43] Selten R. A demand commitment model of coalition bargaining. The disscussion paper NB-191, Univ. of Bonn, 1991.

[44] Straffin P. D. Power and Stability and Politics. // Aumann R., Hart S. (eds.) Handbook of Game Theory with Economic Applications, vol. II. Amsterdam, 1994. P. 1127-1151.