Производящие функции в играх голосования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Калугина, Анастасия Михайловна

• Калугина, Анастасия Михайловна
• кандидат физико-математических наук
• 2009

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

Введение.

1. Производящие функции для индексов влияния.

1.1. Вычисление индексов влияния с помощью производящих функций.

1.1.1. Индекс Банцафа и индекс Шепли-Шубика.

1.1.2. Индекс Холлера и индекс Дигана-Пакела.

1.2. Индекс Хеде-Баккера в терминах производящих функций.

1.2.1. Индекс Хеде-Баккера.

1.2.2. Модификация индекса Хеде-Баккера.

1.2.3. Индекс Хеде-Баккера в терминах производящих функций.

2. Производящие функции для нахождения n-ядра и составления комитетов.

2.1. n-ядро для игр голосования.

2.2. Производящие функции для процедуры выбора комитета.

2.2.1. Процедуры минисуммы и минимакса.

2.2.2. Производящие функции для процедур минисуммы и минимакса.

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

3.1. Определение силы влияния партий Государственной думы Российской Федерации I-V созывов.

3.1.1. Первый созыв.

3.1.2. Второй созыв.

3.1.3. Третий созыв.

3.1.4. Четвертый созыв.

3.1.5. Пятый созыв.

3.2. Определение силы влияния партий в Законодательном собрании Забайкальского края первого созыва.

3.3. Моделирование игр голосования с влиянием одних игроков на других.

Введение диссертации (часть автореферата) на тему «Производящие функции в играх голосования»

Актуальность темы.

Игры голосования являются частью кооперативной теории игр. Первые работы по анализу роли игроков в коалиции принадлежат JI. Шепли [56,57]. Вектор Шепли широко используется в различных прикладных задачах, связанных с принятием решений в управлении сложными социальными и экономическими системами. Развитие современной теории кооперативных игр характеризуется разработкой методов, позволяющих более глубоко описывать процессы принятия коллективных решений. Одним из таких методов является анализ распределения влияния участников в органах, осуществляющих коллективное принятие решений, таких, как выборные органы и органы коллегиального управления. Проблема распределения влияния привлекает внимание именно потому, что без учета этого феномена принятие решений не может корректно моделироваться.

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

После работы Шепли появились различные исследования в области теории кооперативных игр. Важные результаты в этой области представлены Шмайдлером, Банцафом, Холлером, Шубиком, Диганом, Пакелом в [27,34,36,37,41,44,51,54,55].

Коалиция называется выигрывающей, если она может принять решение без голосов остальных партий. В противном случае коалиция называется проигрывающей. Чем больше коалиций, которые данная партия делает выигрывающими, тем больше у нее возможностей влиять на исход голосования. На первый взгляд, влияние партии напрямую зависит от числа её голосов. Чтобы проиллюстрировать, что это не совсем так, рассмотрим пример. Пусть парламент, состоящий из 99 мест, представлен 3 партиями А, В, С с числом голосов каждой партии равным 33. Правило принятия решений - простое большинство, т.е. 50 голосов. В этом случае выигрывающие коалиции: А+В, А+С, В+С, А+В+С, т.е. любая партия делает выигрывающими две парные коалиции. В силу симметрии, очевидно, что все партии имеют одинаковое влияние. Теперь представим себе, что распределение мест в этом парламенте изменилось и у партий А и В стало по 48 голосов, а у партии С только 3 голоса. Однако, выигрывающие коалиции остались те же, и партия С, несмотря на резкое уменьшение числа голосов, делает выигрывающими то же число коалиций, что и остальные партии, т.е. возможности всех партий влиять на исход голосования по-прежнему одинаковы. Приведенный пример показывает, что число голосов не является точным показателем влияния партии. Поэтому вводятся индексы влияния, измеряющие степень влияния партии в парламенте на основании числа коалиций, которые партия делает выигрыва.-ющими.

Наиболее известны следующие индексы:

• Индекс Шепли-Шубика для игры голосования G — (N, W),

Sh(G) = {Sh1(G),.iShn{G)), где

Shk{G) = (fc = l,.,n), (1)

Рк - число коалиций, в которых игрок к является ключевым.

• Индекс Банцафа для игры голосования G — (N, W), Bz{G) = (Bz1(G)1.1Bzn(G)),rpie

Bzk(G) = -^-, (к = 1, .,п), (2)

2^1 Vj jeN щ - число коалиций, в которых игрок к является ключевым.

• Индекс Пенроуза-Банцафа, также называемый ненормализованным или абсолютным индексом Банцафа, для игры голосования G = (N, W),

PBz(G) = (PBZl(G),.,PBzn(G)), где

PBZk(G) = fk = ^-v (к = 1,., n), (3)

Зк - обозначает общее число коалиций, содержащих игрока к.

Индекс Дигана-Пакела. для игры голосования G = (N, W), DP(G) = (DPtiG^.^DPniG)), где i Е ? = (4)

SeM-.keS

М - набор всех минимальных выигрывающих коалиций, т - общее число выигрывающих коалиций, и s - число игроков в S.

Индекс Холлера для игры голосования G — (N, W), H(G) = (H!((?),.,tfn(G0), где

Hk(G) = (к = 1,., п), (5)

171 j jeN т,к - число минимальных выигрывающих коалиций, содержащих игрока к.

Индекс Шепли для игры голосования G = (N, W), ip(G) = (v?i(G),.,</?n(G)), где w = Е - w(e/0), (6)

SCN Пs - число игроков, входящих в рассматриваемую коалицию, п - общее число игроков, v(s) - функция выигрыша рассматриваемой коалиции, v(s/i) - функция выигрыша этой коалиции без зафиксированного игрока.

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

Кроме теоретического исследования, важную роль играет практическое применение индексов влияния для определения влияния партий в выборных органах. Значительное число работ посвящено исследованию разнообразных институтов власти: Государственных Дум Российской империи, Совета Министров Евросоюза, парламентов Японии, Германии, России. Кроме того, индексы находят широкое применение не только в политике, но и в экономике, экологии, менеджменте, юриспруденции и других науках [1,24,25,26,51,54,59].

Перечисленные индексы не учитывают возможного влияния одних игроков на других. Такое влияние учитывает индекс Хеде-Баккера:

HBk(gd(B)) = ^- £ gd(Bp), (7) р:рк=1} где gd(Bp) - коллективное решение.

Этот индекс был предложен в 1982 году. Некоторые его свойства были рассмотрены в [40,52,53]. Кроме того, А.Русиновской и Де Свартом был предложен обобщенный индекс Хеде-Баккера:

GHB(gd(B)) = ^ ( Е 9d(Bp) - ]Г gd(Bp) j , (8) p:pfc=1 ■ р:рк=0 / который охватывает большее число игр голосования, нежели индекс Хеде-Баккера.

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

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

Производящей функцией некоторой последовательности {ап} называется сумма:

G(x) = а0 -f aix + а2х2 + . + апхп + . (8)

Для индексов Шеили-Шубика и Банцафа производящая функция была определена и описана в работах [28,30,46].

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

В работе проведено исследование следующих теоретико-игровых моделей:

1. игра голосования без влияния игроков друг на друга;

2. игра голосования с влиянием игроков друг на друга;

3. игра голосования для выбора комитета.

Научная новизна работы.

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

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения:

1. Получено представление индексов Холлера, Дигана-Пакела., Хеде-Баккера и обобщенного индекса Хеде-Баккера в терминах производящих функций.

2. Найден вид n-ядра во взвешеной игре голосования с 3-мя и 4-мя игроками и условия для связи n-ядра в играх для п-1 и п игроков.

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

4. Разработан комплекс программ для вычисления индексов Холлера, Дигана-Пакела и определения выигрывающего комитета в пакете символьных вычислений Mathematica.

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

1. Межвузовская конференция "Проблемы прикладной математики", г.Чита, ЗабГПУ, 5-7 мая 2005г.

2. Городская научная конференция к 100-летию Государственной Думы России "Российский парламентаризм: история и современность", г.Чита, 2526 апреля 2006 г.

3. Всероссийская научно-практическая конференция "Выборы депутатов Государственной Думы Федерального собрания Российской Федерации в условиях демократизации Российского государства", г.Чита, 26-27 октября 2006 г.

4. V Московская международная конференция по исследованию операций (ORM-2007), посвященная 90-летию со дня рождения академика Н.Н. Моисеева, г.Москва, 10-14 апреля 2007 г.

5. II Международная конференция по Теории игр и Менеджменту GTM2008, г.Санкт-Петербург, 26-27 июня, 2008 г.

По материалам диссертации опубликовано 11 работ, из них - 9 статей [6,7,8,9,11,12,13,14,15] и тезисы двух докладов [10,47].

Структура работы. Диссертационная работа состоит из введения, трех

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Калугина, Анастасия Михайловна

Заключение

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

Получены следующие результаты:

1. Рассмотрена игра голосования без влияния игроков друг на друга. Получено представление индексов Холлера и Дигана-Пакела в терминах производящих функций. Рассмотрена игра голосования, в которой игроки могут влиять друг на друга. Оператор перехода от векторов предпочтений к векторам решений представлен в линейном виде.

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

2. Найдены точные значения n-ядра для игр голосования 3-х и 4-х лиц. Сформулирована теорема об условиях для связи п-ядра в играх с п — 1 и п игроками. Рассмотрена игра выбора комитета. Предложен алгоритм, использующий производящие функции, для процедур минисуммы и минимакса.

3. С помощью производящих функций найдены индексы влияния для Государственной Думы Российской Федерации I-V созывов и Законодательного собрания Забайкальского края первого созыва. Рассмотрены ситуации консолидированного и неконсолидированного голосования депутатов, не примкнувших ни к какой из партий.

Рассмотрены сценарии поведения партий в ЗС Забайкальского края с указанием влияния партий друг на друга. Для каждой модели найден индекс Хеде-Баккера.

4. Разработан комплекс программ для вычисления индексов Холлера, Дигана-Пакела и определения выигрывающего комитета в пакете символьных вычислений Mathematica.

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

1. Алескеров Ф.Т. Оценка влияния групп и фракций в российском парламенте( 1994-2003 гг.)/ Ф.Т. Алескеров, Н.Ю. Благовещенский, Г.А. Сатаров, А.В. Соколова, В.И. Якуба , Экономический журнал ВШЭ, том 7, №4,2003, С. 496-512.

2. Благовещенский Н.Ю. Индекс согласованности позиций групп в выборных органах. /Н.Ю. Благовещенский, Препринт WP7/2004/02 — М.: ГУ ВШЭ,2004. 16 с.

3. Воробьев Н.Н. Теория игр: лекции для экономистов-кибернетиков /Н.Н. Воробьев. Л.: Изд-во Ленинградского ун-та, 1974. - 160 с.

4. Дюбин Г.Н. Введение в прикладную теорию игр / Г.Н. Дюбин,В.Г. Суздаль. М.: Наука, Главная редакция физико-математической литературы, 1981. -336 с.

5. Жуковский В.И. Кооперативные игры при неопределенности и их приложения: Под ред. B.C. Молостнова / Жуковский В.И. М.: Эдиториал УРСС, 1999. - 336 с.

6. Калугина A.M. Индекс власти как показатель политической силы партии // Молодая наука Забайкалья: Аспирантский сборник. Чита: Изд-во ЗабГПУ,2005. Часть II. С. 128-132.

7. Калугина A.M. Индекс Хеде-Баккера // Математический анализ и его приложения: сборник научных трудов / Заб. гос. гум.-иед. ун-т. Вып. 8. - Чита: Изд-во ЗабГГПУ, 2008. С. 29-33.

8. Калугина A.M. Индексы власти для ГДРФ I-V созывов // Проблемы гражданского общества и правового государства: сб. статей. Вып. 11. - Чита, 2008. С. 93-101.

9. Калугина A.M. Индексы власти и парадоксы власти в Читинской Областной Думе // Известия Российского государственного педагогического университета им.А.И. Герцена. № 13(36): Аспирантские тетради: Научный журнал. -СПб., 2007. С. 53-57.

10. Калугина A.M. Применение теории игр в политике: анализ состава парламентов России и Украины // Математический анализ и его приложения: сборник научных трудов / Забайкал. гос. гум.-пед. ун-т. Вып. 6. - Чита, 2006. С. 1926.

11. Калугина A.M. Современный российский парламентаризм в цифрах // Российский парламентаризм: история и современность: сб. статей / Заб. гос. гум.-пед. ун-т. Чита, 2006. С. 113-116.

12. Калугина А. М. Анализ распределения влияния в Законодательном Собраггаи Забайкальского края первого созыва // Моделирование. Системный анализ. Технологии: межвузовский сборник научных трудов. Чита: ЗабИЖТ, 2009. - С. 150-154.

13. Калугина A.M. Производящая функция для индексов Холлера и Дигана-Пакела // Информационные технологии моделирования и управления. № 2(54). Воронеж: Изд-во "Научная книга", 2009. С. 193-199.

14. Калугина A.M. Индекс Хеде-Баккера в терминах производящей функции // Системы управления и информационные технологии. № 1.2(35). Воронеж: Изд-во "Научная книга", 2009. - С. 255-259.

15. Карлин С. Математические методы в теории игр, программировании и экономике / С. Карлин. М.: Мир, 1964. - 838 с.

16. Мазалов В.В. Математическая теория игр и приложения. Учебное пособие, (в печати)

17. Муллен Э. Теория игр с примерами из математической экономики /Э. Мул-лен. М.: Мир, 1985. - 200 с.

18. Нейман Дж. Теория игр и экономическое поведение / Дж. Нейман,О. Морген-штерн. М.: Наука, Главная редакция физико-математической литературы, 1970. - 708 с.

19. Оуэн Г. Теория игр / Г. Оуэн. М.: Мир, 1971. - 230 с.

20. Официальный сайт Государственной Думы: http://www.duma.gov.ru.

21. Официальный сайт Областной Думы Читинской области:http://www.obladm.chita.ru.

22. Петросян JI.А. Теория игр: учебное пособие для студентов университетов, обучающихся по специальности „Математика" / Л.А. Петросян,Н.А. Зенкевич, Б.А. Семина. М.: Высшая школа, 1998. - 304 с.

23. Якуба В.И. Институционный баланс власти в Совете Министров расширенного Евросоюза. Экономический журнал ВШЭ, том 7, №4, 2003, С. 513-523.

24. Aleskerov F., Avci G., Yakuba V., Umit Turem Z. European Union Enlargement: Power distribution implications of the new institutional arrangements. European Journal of Political Research, v. 41, № 3, May 2002. P. 379-394.

25. Aleskerov F., Ersel H., Sabuncu Y. Power and Caolitional Stability in the Turkish Parliament (1991-1999) // Turkish Studies. 2000. Vol. 1. № 2. P. 21-38:

26. Banzhaf J., Weighted voting doesn't work: a mathematical analysis, Rutgers Law Review 19, 1965, P. 317-343.

27. Bilbao J.M., Fernandez J.R., Jimenes A., Lopez J.J., Generating functions for computing power indices efficiently. Top, 2000, 8(2): P. 191-213.

28. Brams S.F. Game theory and politics. New York, Free Press, 1975.

29. Brams S.F., Affuso P.J., Power and size: A new paradox-Theory and Decisions,7, 1976, P. 29-56.

30. Carter M. Cooperative games. In H. R. Varian, Ed., Economic and Financial Modeling with Mathematica, Springer-Verlag, Berlin, 1993, P. 167-191.

31. Deegan J., Packel E.W., A new index of power for simple n-person games, International Journal of Game Theory 7 (1978), 113-123.

32. Deegan J., Packel E.W., To the (minimal winning) victors go the (equally divided) spoils: a new index of power for simple n-person games, In Brams, S.J., Lucas, W.F. and Straffin, P.D., o.c., 1982. P. 239-255.

33. Davis M., Maschler M., The kernel of a cooperative game. Naval Res. Logist.Quart. 12, 1965, P. 223-359.

34. Dubey P., Shapley L.S., Mathematical properties of the Banzhaf power index, Mathematics of Operations Research 4, 1979, P. 99-131.

35. Felsenthal D.S., Machover M., The measurement of voting power: theory and practice, problems and paradoxes, London: Edward Elgar Publishers, 1998.

36. Felsenthal D.S., Machover M., Zwicker W., The bicameral postulates and indices of a priori voting power, Theory and Decision 44, 1998, P. 83-116.

37. Fishburn C., Brams S., Minimal winning coalitions in weighted-majority voting games. Social Choice and Welfare 13, 1996, P. 397-417.

38. Hoede C., Bakker R.(1982), A theory of decisional power, Journal of Mathematical Sociology8: P. 309-322.

39. Holler M.J., Forming coalitions and measuring voting power, Political Studies 30 (1982), P. 262-271.

40. Holler M.J., Myths and Meanings of Voting Power: A Reply Holler, Journal of

41. Theoretical Politics, 13, 2001, P. 107-110.

42. Holler M.J., Two stories, one power index. Journal of Theoretical Politics 10, 1998 P. 179-190.

43. Holler M.J., Packel E.W., Power, luck and the right Index, Journal of Economics 43, 1983, P. 21-29.

44. Kilgour D.M., A Shapley value for cooperative games with quarreling, in: A. Rapoport (ed.) Game theory as a theory of conflict resolution, Boston: Reidel, 1974, P. 193-206.

45. Lucas W.F. Measuring Power in Weighted Voting Systems.- In the book Political and Related Models, Edited by Brams S.J., Lucas W.F., Straffin, Springer, 1975, P. 183-238.

46. Straffin P.D., Power indices in politics, In Brams S.J., Lucas W.F. and Straffin P.D., o.c., 1982.

47. Tannenbaum P., Power in Weighted Voting Systems. The Mathematica Journal 7, 1997, P. 58-63.

48. Penrose L.S., The elementary statistics of majority voting, Journal of the Royal Statistical Society 109, 1946, P. 53-57.

49. Rusinowska A., Paradox of redistribution in Polish politics, Annals of the Marie Curie Fellowships, European Commission, Brussels, Vol. 2, 2001, P. 46-54.

50. Rusinowska A., De Swart H., On some properties of the Hoede-Bakker index, forthcoming in Journal of Mathematical Sociology, 2006.

51. Rusinowska A., Adrian van Deemen, The redistribution paradox and the Paradox of new members in the German parliament. Nova Science Publishers, 2004.

52. Schmeidler D., The nucleolus of a characteristic function game. SIAM. Journal on Applied Mathematics, 17, 1969, P. 1163-70.

53. Shapley L.S., A value for n-person games, Annals of Mathematics Studies 28, 1953, P. 307-317.

54. Shapley L.S., Shubik M., A method for evaluating the distribution of power in a committee system, American Political Science Review 48, 1954, P. 787-792.

55. Taylor A.D. Mathematics and Politics. Springer Verlag, New York, USA, 1995.

56. Van Roozendaal P., Cabinets in the Netherlands (1918-1990): The importance of 'dominant' and 'central' parties, European Journal of Political Research 23, 1993, P. 35-54.