Математические модели голосования

Байчорова Мария Маратовна

Математические модели голосования

В данной работе описаны различные процедуры проведения голосования, которые проиллюстрированы на решениях конкретных задач. В ходе работы был изучен ряд монографий и был составлен краткий обзор моделей социально-биологических процессов, описываемых дифференциальными уравнениями. Данные модели успешно используются при исследовании задач, возникающих в процессе голосования. Также построена математическая модель выборов между n кандидатами, представляющая собой систему, состоящую из n+1 дифференциального уравнения. Рассмотрен ее частный случай голосования между тремя кандидатами (n=3), выведены формулы для вычисления стационарных точек соответствующей системы дифференциальных уравнений, проведено исследование на устойчивость. Кроме того, рассмотрен численный пример и реализован алгоритм для его расчета в программной среде MATLAB.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36485f1be77c40d58b7e

UUID: 980f718d-5da3-4c80-b929-be9884d126c8

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 129

Байчорова Мария Маратовна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 334711 bytes

Поделиться работой

Санкт-Петербургский государственный университет Кафедра математической теории игр и статистических решений Байчорова Мария Маратовна Выпускная квалификационная работа бакалавра Математические модели голосования Направление 010400 Прикладная математика, фундаментальная информатика и основы программирования Научный руководитель, доктор физ.-мат. наук, профессор Петросян Л. А. Санкт-Петербург 2016

Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Обзор литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Глава 1. Процедуры голосования . . . . . . . . . . . . . . . . . . . . 8 1.1. Виды процедур голосования . . . . . . . . . . . . . . . . . . . 8 1.2. Математическое моделирование при помощи систем дифференциальных уравнений. . . . . . . . . . . . . . . . . . . . . . 16 Глава 2. Дифференциальная модель голосования. . . . . . . . . . . 19 2.1. Модель для двух политических партий. . . . . . . . . . . . . 19 2.2. Модель для выборов между n кандидатами. . . . . . . . . . 20 2.3. Модель для выборов между тремя кандидатами. . . . . . . . 24 2.4. Устойчивость системы . . . . . . . . . . . . . . . . . . . . . . 31 2.5. Численный пример. . . . . . . . . . . . . . . . . . . . . . . . 34 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2

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

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

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

Обзор литературы При написании данной работы были использованы научная, а также учебно-методическая литература, публикации в различных научных изданиях. Основы процедур и методов голосования были изучены при помощи монографии [1]. Особый интерес представляет ее четвертая глава под названием Voting procedures, авторами которой являются Стивен Брамс и Питер Фишборн, известные своими работами в области альтернативных методик голосования, таких как одобряющее голосование. В данной главе описаны различные методики проведения голосования, такие как голосование большинства, голосование по правилу Борда и по принципу Кондорсе, а также возникающие при них парадоксы. Также о некоторых из этих процедур, а также исторических сведениях о развитии избирательных систем, говорится в работе [2]. Примеры моделирования социально-биологических процессов подробно описаны в ряде работ, среди них хотелось бы выделить [3] и [4]. В первом труде описывается самая известная дифференциальная модель модель Лотки-Вольттеры, также называемая модель "хищник-жертва". Исследуются ее стационарные точки и строится численное решение рассматриваемой системы. В девятой главе книги [4] под названием "Теория эпидемий" Бейли занимается построением различных моделей, представляющих собой системы дифференциальных уравнений, иллюстрирующие скорость распространения эпидемий в закрытом социуме, постепенно развивая каждую из них в зависимости от изменения внешних факторов, таких как начальное количество заболевших, скорость распространения инфекции, возможность изоляции заразившихся и т д. 6

Пример дифференциального моделирования в политической сфере был получен в работе [5]. В данной работе индийский профессор Арвинд Мисра описывает модель, которая помогает прогнозировать развитие политической ситуации в стране, а именно предсказать динамику изменения количества людей в каждой из двух основных политических партий, функционирующих в ней. Данная модель представляет собой нелинейную систему, состоящую из двух дифференциальных уравнений. При построении модели население считается однородным и постоянным. При подсчете людей, находящихся в одной или другой партии, также учитываются такие факторы, как ограничения для вступления в партию законом или смертность среди тех, которые уже являются членами одной из них. Также рассматривается различная расстановка политических сил в стране, то есть ситуация когда одна из партий доминирует над другой, когда они равны в своих возможностях и имеют одинаковое количество людей, а также случаи, когда в рассматриваемом государстве отсутствуют политические партии в целом. 7

Глава 1. Процедуры голосования 1.1. Виды процедур голосования Процедуры голосования имеют множество форм, таких как голосование абсолютного большинства, мажоритарные избирательные системы, одобряющее голосование и многие другие. Они могут применяться не только на государственном, но также и на муниципальном, и на региональном уровнях. Так же данные схемы могут найти достойное применение и при выборе президента фирмы или кампании, выборе главы совета директоров, выборе директора школы и других подобных ситуациях. Широкий спектр применения данных процедур делает их исследование и совершенствование задачей необыкновенной важности. Каждая из них имеет свои преимущества, которые могут быть различным образом использованы в зависимости от системы, в которой они находят применение. Для того чтобы более наглядно показать процесс работы каждого из них, рассмотрим некоторую конкретную задачу, опишем каждую из процедур, а затем попробуем решить задачу с помощью каждой из них. Задача. Пусть у нас проводится голосование между тремя кандидатами. Назовем их a, b и c. В голосовании принимают участие N человек, и пусть по условию задачи N = 15. Каждый из участников голосования имеет свои предпочтения, в соответствии с которыми он принимает решение и отдает свой голос. Допустим, что предпочтения некоторых людей совпадают, и имеется следующая картина: n1 = 20 : a b c, n2 = 10 : b c a, n3 = 20 : c b a. 8

где ni — число людей, имеющих одинаковые предпочтения. Выражение a b означает, что данный избиратель предпочитает кандидата a, и в ситуации выбора между a и b он склонен проголосовать за кандидата a. Рассмотрим следующие процедуры голосования: Голосование относительного большинства. Самый простой вид голосования. В своей последовательности предпочтений избиратель имеет лидера, которому он и отдает свой голос. Каждый человек голосует только за одного кандидата. После проведения этой процедуры проводится подсчет голосов и человек, набравший наибольшее их количество, побеждает в выборах. Голосование будет безрезультатным лишь в том случае, если кандидаты наберут равное количество голосов избирателей. Применим данную процедуру к нашей задаче. В ходе голосования кандидат a получит 20 голосов, кандидату b достанется 10 голосов, а кандидат c получит 15 голосов. Очевидно, что победит первый кандидат. Однако после такого голосования количество людей, которые останутся недовольны результатами будет равно 25, что больше половины от всего количества голосующих. Данный факт говорит нам о том, что подобные выборы нельзя назвать в полной мере справедливыми, так как победивший кандидат при попарном сравнении с остальными проигрывает каждому из них. Поэтому данный метод нуждается в модификации. Голосование абсолютного большинства. Данная процедура отличается от первой тем, что для победы кандидату необходимо набрать строго больше половины голосов избирателей. 9

Если в результате голосования это условие не выполняется, то обычно организовывается второй тур. Чаще всего в него проходят двое кандидатов, набравшие самое большое число голосов в первом туре. Голосование абсолютного большинства применяется при выборах президента страны во множестве государств мира, таких как, например, Франция, Португалия, Колумбия, Хорватия и т. д. Россия также входит в их число. Применим эту методику к задаче, описанной выше. При проведении первого тура голоса распределятся аналогичным прошлому случаю образом. Однако количество поддерживающих победившего в первом туре кандидата a меньше 50% всех голосующих, поэтому возникает необходимость второго тура. Кандидат a набрал 20 голосов, кандидат c набрал 15 голосов, и именно они вдвоем проходят во второй тур. При голосовании во втором туре те же 20 человек вновь поддержат первого кандидата, 15 представителей третьей группы предпочтений проголосуют за кандидата c, поэтому решающими станут голоса людей, которые в первом туре поддерживали второго кандидата. Для них предпочтительнее победа кандидата c, поэтому они отдадут свои голоса за него. Таким образом, третий кандидат получит 15 + 10 = 25 голосов и одержит победу. С подобным исходом будут согласны 56% избирателей, условие абсолютного большинства выполняется, и результаты второго тура могут быть признаны результатом выборов в целом. Преимущества данного вида голосования, а именно более точное отражение воли большинства избирателей, особенно важны при большой раздробленности политических взглядов в обществе и большом количестве различных предпочтений среди избирателей. Факт отсеивания кандидатов в ходе процедуры выборов позволяет в итоге получить наиболее умеренный результат, обеспечивающий мак10

симально стабильное развитие общества. Голосование с последовательным исключением. Иначе данную методику называют "олимпийской системой". Процедура данного голосования также довольно незатейлива. Будем считать, что в выборах участвует n кандидатов. Каждый кандидат последовательно, начиная с первого, сравнивается со следующим и победивший в парном противостоянии выходит в следующий тур. Следовательно, всего проводится n − 1 туров. Победитель последнего тура становится победителем всего голосования. Применим этот метод к нашей задаче. В первом туре проводится голосование между первым и вторым кандидатами, т.е. a и b соответственно. Первый кандидат получает 20 голосов, второй — 25. Следовательно, дальнейшую борьбу продолжает кандидат b, кандидат a выбывает. Во втором туре его соперником становится кандидат c. Голоса распределяются следующим образом: b — 30, c — 15. В этом противостоянии также побеждает кандидат b. Таким образом, он одерживает победу и в выборах в целом. Подобная процедура отбора находит широкое применения не только в вопросах голосования, но и при отборе во многих спортивных мероприятиях. Голосование по принципу Кондорсе. Данный метод был предложен французским математиком Маркизом де Кондорсе в XVIII веке. Согласно нему при проведении выборов необходимо организовать попарные голосования между всеми кандидатами, вследствие которых победителем считается тот, кто одержал победу в 11

каждом из них. Результаты данной процедуры записываются в таблице. В каждой ячейке с индексом ij записывается число голосов, которые были отданы за i-го кандидата в противостоянии с j-ым в ситуации, когда i-ый кандидат победил в рассматриваемом противостоянии. Построим эту таблицу для рассматриваемой нами задачи: a b c Итог a − 20 20 40 b 25 − 30 55 c 25 15 − 40 Таким образом, из таблицы очевидно, что в выборах одерживает победу второй кандидат, так как он победил первого и третьего кандидатов в очных противостояниях. Основной проблемой при проведении голосования при помощи данного метода является возникновение так называемого парадокса Кондорсе. Он заключается в том, что при проведении голосования в парных противостояниях среди кандидатов не оказывается единственного, который выиграл каждое из них. Иными словами, среди предпочтений избирателей образуется цикличность. Проиллюстрируем примером. Пусть предпочтения голосующих имеют следующий вид: n1 = 10 : a b c, n2 = 10 : b c a, n3 = 10 : c a b. При проведении попарных голосований мы получим следующие результаты: при выборе между a и b победу одержит a, при выборе между a и c победу одержит c, при выборе между b и c победу одержит b. Таким 12

образом, цепь всеобщих предпочтений голосующих примет вид: a b, b c, c a. Ни один кандидат не одержал победу во всех противостояниях, поэтому победителя по принципу Кондорсе выявить невозможно. Голосование по правилу Борда. Эта методика аналогично предыдущей была предложена в XVIII веке во Франции членом Парижской Академии Наук Жан Шарлем де Борда. Будем считать, что в голосовании принимает участие n кандидатов. Каждый избиратель, ориентируясь на свои личные предпочтения, ранжирует кандидатов, выставляя каждому баллы от n − 1 (для лучшего по его мнению) до 0 (для худшего соответственно). Затем проставленные баллы для каждого кандидата суммируются, и в итоге побеждает кандидат с максимальной суммой. Проведем эту процедуру в условиях нашей задачи. Составим таблицу для подсчета баллов: n1 = 20 n2 = 10 n3 = 15 Итог a 2 0 0 20 b 1 2 1 55 c 0 1 2 40 Из таблицы очевидно, что победу в выборах одержит второй кандидат. Кроме самих процедур голосования по правилу Борда и принципу Кондорсе существуют также и их обобщения. Голосование при помощи подсчета очков. Данный способ является обобщением голосования по правилу Борда. Пусть в голосовании участвуют n кандидатов. Вводится последовательность чисел (или рангов) вида r0 ≤ r1 ≤ · · · ≤ rn−1 , в которой 13

обязательно должно выполняться условие r0 < rn−1 . Затем каждый избиратель упорядочивает кандидатов по возрастанию в соответствии со своими предпочтениями и присваивает каждому ранг из последовательности ri . В выборах побеждает кандидат, набравший наибольшую сумму очков. Очевидно, что исход голосования зависит в первую очередь от выбора значений рангов в последовательности ri . Покажем это на примере рассматриваемой задачи. Если мы примем за значения рангов числа от 0 до n−1, то мы получим исходное голосование по правилу Борда, а его результат нам известен — победит кандидат b. Теперь пусть значения рангов будут следующими: r0 = 0, r1 = 1, r2 = 4. Рассчитаем табличные значения для данного случая: n1 = 20 n2 = 10 n3 = 15 Итог a 4 0 0 80 b 1 4 1 75 c 0 1 4 70 Таким образом, в данных условиях побеждает кандидат a. Голосование по правилу Компленда. Данный метод — обобщение голосования по принципу Кондорсе. Введем функцию F (ai ), где ai — это i-ый кандидат. Далее будем попарно сравнивать кандидатов между собой. Рассмотрим двух кандидатов p и q. Если для большинства избирателей p предпочтительнее q, то F (p) = +1, если q предпочтительнее p, то F (p) = −1, если число предпочитающих p и число предпочитающих q равно, то F (p) = 0. Побеждает кандидат, для которого значение функции F максимально. Рассчитаем значения F 14

для нашей задачи. Получим следующие значения: F (a) = −2, F (b) = 2, F (c) = 0. Таким образом, при голосовании данным методом победит кандидат b. Подметим тот факт, что данный метод является обобщением правила Кондорсе, и результаты у обеих процедур совпадают. Голосование по правилу Симпсона. Данная методика голосования также является обобщением процедуры голосования по принципу Кондорсе. При голосовании этим способом каждый кандидат попарно сравнивается со всеми остальными. При каждом сравнении кандидата x с кандидатом y за R(x y) будем обозначать число людей, для которых (x y). Для кандидата x минимальное из чисел R(x y) при попарном сравнении со всеми возможными y называется оценкой Симпсона. В выборах побеждает кандидат, для которого оценка Симпсона максимальна. Рассмотрим это правило на нашей задаче. Построим оценку Симпсона для каждого из трех кандидатов: R(a) = 20, R(b) = 30, R(c) = 20. В ходе голосования побеждает второй кандидат, так как для него оценка Симпсона максимальна. 15

1.2. Математическое моделирование при помощи систем дифференциальных уравнений. Математическое моделирование социально-биологических процессов с помощью систем дифференциальных уравнений активно развивается. Данная методика прогнозирования развития ситуации внутри социума или же иной рассматриваемой системы берет свой исток еще в начале XX века. Речь идет об известной модели Лотки-Вольтерра, известной так же под другим названием "хищник-жертва". Один и тот же результат бы получен обоими учеными независимо друг от друга, одним в 1925 г., а вторым в 1926 г. Будем рассматривать закрытую экосистему. В ней обитает две популяции. Одна из них, жертва, обеспечена всем, что необходимо для нормального функционирования. Вторая, хищник, питается исключительно особями из первой популяции. Пусть a — число особей в популяции жертвы, b — число особей в популяции хищника. Модель Лотки-Вольтерры имеет вид: da =α1 a − β1 ab, dt db = − α2 b + β2 ab. dt где коэффициенты α1 , α2 , β1 , β2 отражают процесс взаимодействия между популяциями хищника и жертвы. Еще одним из ярких примеров успешного математического моделирования процессов, контроль которых, а также вопрос предсказания исхода невероятно важны, является модель профессора Н.Бейли. Она описывает такое опасное явление как эпидемия. Эпидемией называют распространение болезни среди населения, при котором количество заболевших 16

значительно превышает среднестатистические показатели, характерные для рассматриваемой местности. Бейли является создателем нескольких математических моделей эпидемий, но рассмотрим лишь одну из них. Отличительной чертой данной модели является то, что учитывается факт, согласно которому люди, уже заразившиеся инфекцией, могут быть изолированы от общества, что позволяет сократить скорость распространения болезни. Введем следующие обозначения. Под n будем понимать общее рассматриваемое количество людей. Пусть a — группа людей, восприимчивых к болезни, т. е. после контакта с зараженной особью они склонны заразиться. Пусть b — это группа уже зараженных индивидуумов, c — группа удаленных, т.е. люди, которые выздоровели, умерли, получили иммунитет или были изолированы от общества. Затем вводятся несколько коэффициентов, которые описывают взаимодействие между этими группами людей. Коэффициент β характеризует частоту возникновения контактов между индивидами, коэффициент γ, в свою очередь, описывает частоту удаления людей из общества вследствие четырех причин, описанных выше. Система дифференциальных уравнений, описывающих динамику данного процесса, примет вид: da = − βab, dt db =βab − γb, dt dc =γb. dt при начальных условиях (a, b, c) = (a0 , b0 , 0) при t = 0. Данная модель имеет модификацию, в которой рассматривается ситуация, а которой количество восприимчивых людей увеличивается со скоростью δ. Это условие обеспечивает своеобразную периодизацию со17

стояния системы, а именно чередования периодов вспышки эпидемии и ее затишья. Чередования обуславливаются количеством восприимчивых индивидуумов в каждый конкретный момент времени. Количество восприимчивых людей становится меньше из-за их заражения, но при этом увеличивается за счет введенной нами константы δ, описывающей скорость прироста их числа. Однако этот прирост уравновешивается вследствие гибели или изоляции членов общества (т.е. засчет удаленных особей), и, исходя из этого, количество людей в обществе остается неизменным. В итоге система уравнений будет выглядеть следующим образом: da = − βab + δ, dt db =βab − γb. dt Данная система дифференциальных уравнений имеет равновесное положение, то есть существует такое значение переменных системы (a, b), при котором в рассматриваемом социуме перестанут происходить изменения и число здоровых и зараженных индивидов станет постоянным. Для нахождения данной точки приравняем уравнения рассматриваемой системы к нулю −βab + δ = 0, βab − γb = 0. Решая данную системы алгебраических уравнений, получим следующий результат: γ , β δ y0 = . γ x0 = 18

Глава 2. Дифференциальная модель голосования. 2.1. Модель для двух политических партий. Как было показано в главе 1, математическое моделирование с помощью систем дифференциальных уравнений успешно применяется в биологической и социальной сферах. Так же удачно оно может быть использовано в политике и политических процессах: распределении политических сил в стране, избрание членов правительства и органов муниципального управления и многих других. Во многих демократических государствах, таких как США, существует две главенствующие (или правящие) партии, ни одна из которых не имеет значительного перевеса надо другой. В работе [5] индийский профессор Арвинд Мисра описывает модель, представляющую собой систему, состоящую из двух дифференциальных уравнений. Данная модель иллюстрирует распространение влияния двух политических партий, функционирующих в стране. Она применима к странам с двухпартийной системой. С аналогичным успехом данная модель может быть использована в ситуации выборов между двумя кандидатами. Однако жизненный опыт подсказывает, что зачастую выборы проводятся не только между двумя, но и между тремя и большим числом баллотирующихся. Этот факт приводит нас к необходимости развития данной модели и ее адаптации к ситуации выборов между n кандидатами. 19

2.2. Модель для выборов между n кандидатами. Рассмотрим следующую задачу. Пусть N — это количество людей, способных голосовать. Учитываются правила голосования рассматриваемого нами объекта, то есть сюда мы включаем только тех, кто имеет право голоса, например, в России это будут исключительно граждане старше 18 лет. Эта величина является константой на протяжении всей процедуры выборов. Далее мы делим наше множество людей на n + 1 класс: A1 , A1 , . . . , An — это группы людей, которые поддерживают первого, второго и так далее кандидатов соответственно. Также существует группа V , в которую входят граждане, которые на момент времени t еще не определились со своим выбором или склонны воздержаться при проведении голосования. Так как N является постоянной величиной, то очевидно, что A1 , A1 , . . . , An и V в сумме дают N . A1 + A2 + · · · + An + V = N (2.2.1) Будем считать, что в начальный момент времени t = 0 существует некоторый вектор начальных значений, отображающий количество людей, поддерживающих каждого кандидата (A1 (0), A2 (0), . . . , An (0), V (0)), где Ai > 0. Величину Ai будем называть агитационной группой i-го кандидата. Члены этих групп начинают контактировать с неопределившимися в своих предпочтениях людьми и пытаются убедить их проголосовать за кандидата, которого они представляют. Пусть ki — среднее число встреч одного представителя агитационной группы кандидата с представителями группы V в единицу времени, а pi 20

— вероятность при встрече с представителем V убедить его проголосовать за необходимого им кандидата. Коэффициентом βi = ki pi обозначим величину, характеризующую скорость привлечения людей в ряды поддерживающих i-го кандидата Таким образом, скорость привлечения неопределившихся людей из группы V в группу поддержки i-го кандидата равна: βi V Ai N Ai отображает вероятность встречи представителя группы N V с членом агитационной группы i-го кандидата. где величина Однако каждый человек в различной степени может быть подвержен внешнему влиянию, поэтому необходимо учитывать тот факт, что однажды определившийся гражданин способен поменять свое мнение и перейти из одной группы в группу поддерживающих другого баллотирующегося. Исходя их данных предположений, будем учитывать тех людей, которые из-за смены мнения покинут группу поддержки i-го кандидата и перейдут в одну из оставшихся n−1 групп, а также тех людей, которые примкнут из n − 1 группы к нашему i-му кандидату. Для этого введем матрицу размерности n × n состоящую из коэффициентов θij .   0 θ12 . . . θ1n      θ21 0 . . . θ2n      . . . . . . . . . . . .    θn1 θn2 . . . 0 На главной диагонали данной матрицы будут расположены нули, так как человек не может перейти из Ai в Ai . В i-ой строке будут расположены коэффициенты для описания количества людей, которые покидают 21

группу рассматриваемого кандидата, а в j-ом столбце — коэффициенты для учета тех, кто примкнул к ней, покинув группы других. Учитывая все условия, описанные выше, модель примет вид: ∂V A1 A2 An = −β1 V − β2 V − . . . − βn V , ∂t N N N n n ∂A1 A1 A1 X A1 X = β1 V − θ1i Ai + θi1 Ai , ∂t N N i=2 N i=2 (2.2.2) ... n−1 n−1 ∂An An An X A2 X = βn V − θni Ai + θin Ai . ∂t N N i=1 N i=2 Первое уравнение данной системы описывает динамику изменения числа людей среди тех, кто еще не определился со своим выбором. Последующие же n уравнений дают аналогичную информацию, но уже о группах поддержки. Правые части каждого из этих уравнений имеют одинаковую структуру и состоят из трех групп слагаемых. Первая группа описывает людей, которые были привлечены из числа неопределившихся, то есть из группы V . Вторая группа дает информацию о тех людях, которые изменили свое решение и собираются покинуть рассматриваемого i-го кандидата и присоединиться к одному из оставшихся n − 1 кандидатов. Третья же группа описывает обратную ситуацию, то есть тех людей, которые покидают другие группы и присоединяются к рассматриваемому кандидату. Заметим, что система (2.2.2) может быть редуцирована к системе, состоящей из n уравнений. Для этого введем новые переменные a1 , a2 , . . . , an , v: a1 = A1 , N a2 = A2 , N ..., an = An , N v= V . N Теперь ai будут показывать уже не количество людей, состоящих в 22

группе поддержки i-го кандидата, а их долю в общем числе голосующих. В свою очередь v покажет долю неопределившихся в выборе людей. Таким образом осуществляется переход к процентному соотношению в рассматриваемой модели. После проведения данных замен система уравнений (2.2.2) примет вид: ∂v a1 a2 an = −β1 v − β2 v − . . . − βn v , ∂t N N N n n n X X X ∂a1 = β1 (1 − ai )a1 − a1 θ1i ai + a1 θi1 ai , ∂t i=1 i=2 i=2 (2.2.3) ... n n−1 n−1 X X X ∂an = βn (1 − ai )an − an θni ai + an θin ai . ∂t i=1 i=1 i=1 Теперь обратимся к условию (2.2.1). Из него можно сделать вывод, что: V = N − A1 − A2 − · · · − An При переходе к процентной модели производится нормировка, при которой N = 1. Учитывая эти два условия, получим: (2.2.4) v = 1 − a1 − a2 − · · · − an Теперь мы можем сократить нашу модель от системы, состоящей из n + 1 уравнения до системы из n уравнений. Модель примет вид: n n n X X X ∂a1 = β1 (1 − ai )a1 − a1 θ1i ai + a1 θi1 ai , ∂t i=1 i=2 i=2 (2.2.5) ... n n−1 n−1 X X X ∂an = βn (1 − ai )an − an θni ai + an θin ai . ∂t i=1 i=1 i=1 23

2.3. Модель для выборов между тремя кандидатами. Рассмотрим частный случай модели. Будем считать, что в выборах участвует 3 кандидата. Строим модель с процентным соотношением. Очевидно, что она будет состоять из трех дифференциальных уравнений. Переменные a1 , a2 , a3 будут показывать число людей в группе поддержки первого, второго и третьего кандидатов соответственно. Следовательно, число неопределившихся в своем выборе людей будет обозначено как v = 1 − a1 − a2 − a3 Коэффициенты β1 , β2 , β3 будут описывать число людей, привлеченных из группы v членами первой, второй и третьей агитационных групп соответственно. Также введем коэффициенты для учета людей, переходящих из одной группы поддержки в другую: 1. θ12 описывает число людей, переходящих из первой во вторую группу; 2. θ13 описывает число людей, переходящих из первой в третью группу; 3. θ21 описывает число людей, переходящих из второй в первую группу; 4. θ23 описывает число людей, переходящих из второй в третью группу; 5. θ31 описывает число людей, переходящих из третьей в первую группу; 6. θ32 описывает число людей, переходящих из третьей во вторую группу. Таким образом, учитывая все описанные выше обозначения, система уравнений, описывающая ситуацию выборов между тремя кандидатами, 24

примет следующий вид: ∂a1 = β1 (1 − a1 − a2 − a3 )a1 − a1 (θ12 a2 + θ13 a3 ) + a1 (θ21 a2 + θ31 a3 ) ∂t ∂a2 = β2 (1 − a1 − a2 − a3 )a2 − a2 (θ21 a1 + θ23 a3 ) + a2 (θ12 a1 + θ32 a3 ) ∂t ∂a3 = β3 (1 − a1 − a2 − a3 )a3 − a3 (θ31 a1 + θ32 a2 ) + a3 (θ13 a1 + θ23 a2 ) ∂t (2.3.1) Здесь каждое из трех уравнений описывает динамику изменения количества людей в каждой из трех групп поддержки. Для возможности прогнозирования с помощью данной модели попробуем найти ее положение равновесия (или стационарную точку). Стационарная точка (состояние равновесия) - это точка, в которой состояние системы не меняется со временем, т.е. dyi =0 dt где i = 1, 2, . . . , n. Исходя из определения стационарной точки и вида системы (2.3.1) получаем, что для нахождения равновесия системы необходимо решить следующую систему алгебраических уравнений: β1 (1 − a1 − a2 − a3 ) − (θ12 a2 + θ13 a3 ) + (θ21 a2 + θ31 a3 ) = 0, β2 (1 − a1 − a2 − a3 ) − (θ21 a1 + θ23 a3 ) + (θ12 a1 + θ32 a3 ) = 0, (2.3.2) β3 (1 − a1 − a2 − a3 ) − (θ31 a1 + θ32 a2 ) + (θ13 a1 + θ23 a2 ) = 0. Однако при дальнейшем исследовании возникает ряд вопросов. Существует ли решение данной системы уравнений? Будет ли оно единственным? И если да, то выполнение каких условий необходимо для этого? Для ответов обратимся к курсу алгебры и вспомним несколько определений. 25

В первую очередь запишем общий вид системы линейных алгебраических уравнений: a11 x1 + · · · + a1n xn = b1 , ··· ak1 x1 + · · · + akn xn = bk . где n — число переменных, k — число уравнений в системе. Иначе система линейных алгебраических уравнений запишется следующим образом Ax = b, где A — матрица системы, x — вектор неизвестных переменных, b — вектор свобoдных значений. Система линейных алгебраических уравнений является однородной, если все члены вектора b равны нулю. Если хотя бы один из них ненулевой, то система неоднородна. Если к матрице системы приписать вектор свободных знaчений b, то полученная подобным образом матрица называется расширенной матрицей системы алгебраических уравнений. Рангом матрицы называют наибольшее количество линейно-независимых столбцов (строк) данной матрицы или иначе это максимальный порядок миноров с ненулевым определителем. Чтобы установить, имеет система решение или нет, необходимо проверить ее на совместность, а условие совместности в свою очередь нам дает теорема Кронекера-Капелли: Теорема 1. Система линейных алгебраических уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу 26

расширенной матрицы системы: rangA = rang Ã. Кроме того, существует несколько следствий из данной теоремы: 1. Если rangA 6= rang Ã, то система не имеет решений. 2. Если rangA = rang Ã = n, то система имеет единственное решение 3. Если rangA = rang Ã < n, то система имеет бесконечное множество решений. Запишем расширенную матрицу системы:   −β1 θ21 − θ12 − β1 θ31 − θ13 − β1 −β1     θ12 − θ21 − β2 −β2 θ32 − θ23 − β2 −β2    θ13 − θ31 − β3 θ23 − θ32 − β3 −β3 −β3 (2.3.3) Для удобства последующих вычислений рангов и определителей, проведем замены: g1 =θ21 − θ12 − β1 , g2 =θ31 − θ13 − β1 , g3 =θ12 − θ21 − β2 , (2.3.4) g4 =θ32 − θ23 − β2 , g5 =θ13 − θ31 − β3 , g6 =θ23 − θ32 − β3 . Тогда расширенная матрица системы примет следующий вид:   −β g1 g2 −β1  1     g3 −β2 g4 −β2    g5 g5 −β3 −β3 Согласно второму следствию из теоремы 1, для существования единственного решения рассматриваемой системы алгебраических уравнений 27

необходимо, чтобы ранг матрицы системы и ранг расширенной матрицы системы равнялись n = 3. Следовательно, для этого необходимо, чтобы определители следующих четырех матриц (миноров) были не нулевыми. Определитель матрицы системы:

−β1 g1

g3 −β2 g4

g5 g5 −β3

(2.3.5.1) = −β1 β2 β3 + g1 g4 g5 + g2 g3 g6 + β2 g2 g5 + β1 g4 g6 + β3 g1 g3 . Миноры третьего порядка для расширенной матрицы:

−β1 g1 g2

−β2 −β2 g4

−β3 g5 −β3

(2.3.5.2) = −β1 β2 β3 − β3 g1 g4 − β2 g2 g6 − β2 β3 g2 + β1 g4 g6 − β2 β3 g1 .

−β1 −β1 g2

g3 −β2 g4

g5 −β3 −β3

(2.3.5.3) = −β1 β2 β3 − β1 g4 g5 − β3 g2 g3 + β2 g2 g5 − β1 β3 g4 − β1 β3 g3 .

−β1 g1 −β1

g3 −β2 −β2

g5 g5 −β3

= −β1 β2 β3 − β2 g1 g5 − β1 g3 g6 − β1 β2 g5 − β1 β2 g6 + β3 g1 g3 . 28 (2.3.5.4)

Если данное условие выполняется, тогда можно вывести формулы для расчета стационарных точек системы. Для начала запишем систему (2.3.2), учитывая проведенные замены: −β1 a1 + g1 a2 + g2 a3 = −β1 , g3 a1 − β2 a2 + g4 a3 = −β2 , g5 a1 + g6 a3 − β3 a3 + = −β3 . Выразим каждую из неизвестных переменных: g1 a2 + g2 a3 , β1 g2 a1 + g4 a3 a2 =1 + , β2 g5 a1 + g6 a2 . a3 =1 + β3 a1 =1 + Теперь подставим значение a1 во второе и третье уравнения системы: 1 g1 a2 + g2 a3 a2 =1 + g3 1 + + g4 a3 , β2 β1 (2.3.6) g1 a2 + g2 a3 1 g5 1 + + g6 a2 a3 =1 + β3 β1 Выразим a2 из первого уравнения: g3 g2 g3 g4 1+ + + a3 β2 β1 β2 β2 a2 = w где w =1− (2.3.7) g1 g3 β1 β2 Далее подставим (2.3.7) в (2.3.6) и после выразим оттуда a3 : a3 = 1 + g5 g1 g5 g2 g5 g6 + a2 + a3 + a2 β3 β1 β3 β1 β3 β3 g2 g5 g5 a3 − a3 = 1 + + β1 β3 β3 29 g1 g5 g6 + β1 β3 β3 a2

В итоге получим следующую формулу для вычисления a3 : g1 g5 g1 g3 g5 g3 g6 g6 g5 + + + + β3 β1 β3 w β1 β2 β3 w β2 β3 w β3 w a3 = g2 g5 g1 g4 g5 g2 g3 g6 g4 g6 g1 g2 g3 g5 1− − − − − β1 β3 β1 β2 w β1 β2 β3 w β1 β2 β3 w β2 β3 w 1+ Проведем обратный ход тех операций, которые были совершены над системой (2.3.2), и получим формулы для a1 , a2 , a3 . Также проведем замену для упрощения итоговых результатов: g1 g3 g4 g2 g1 g2 g3 a1 =1 + 1+ + + + δ, β1 w β2 β1 w β1 β2 β2 β1 1 g3 g4 g2 g3 a2 = + + + δ, w β2 w β1 β2 w β2 w (2.3.8) a3 =δ, где g1 g5 g1 g3 g5 g3 g6 g6 g5 + + + + β3 β1 β3 w β1 β2 β3 w β2 β3 w β3 w δ= g1 g2 g3 g5 g1 g4 g5 g2 g3 g6 g4 g6 , g2 g5 − − − − 1− β1 β3 β1 β2 w β1 β2 β3 w β1 β2 β3 w β2 β3 w 1+ Таким образом, по формулам (2.3.8) мы можем рассчитать стационарные точки для системы дифференциальных уравнений, описывающих ситуацию выборов между тремя кандидатами. 30

2.4. Устойчивость системы Зачастую получение решений системы дифференциальных уравнений становится крайней сложной задачей, однако при этом существует необходимость выяснения особенностей данных решений: их поведение при изменении начальных параметров, как ведут себя решения по отношению друг к другу, изменяется ли поведение системы в целом. Исследованием данных вопросов занимается теория устойчивости. Решение системы дифференциальных уравнений называется устойчивым, если при небольшом изменении начальных условий поведение решения также мaло изменяется. В связи с тем, что термин "мало изменяется" может быть понят различным образом, существуют разные понятие устойчивости: асимптотическая устойчивость, экспоненциальная устойчивость, устойчивость по Ляпунову и т.д. Рассмотрим систему дифференциальных уравнений: dyi = fi (t, y) dt (2.4.1) Для исследования систем дифференциальных уравнений на предмет устойчивости по Ляпунову применяется метод функции Ляпунова. Он заключается в подборе функции W (t, y), удовлетворяющей определенным свойствам и изучении ее производной в силу рассматриваемой системы. Производной функции W (t, y) в силу системы (2.4.1) называется величина, вычисляемая следующим образом: n ∂W X ∂W ∂W = + Yi (t, y) ∂t ∂t ∂y i i=1 Функция W(t,y) является функцией Ляпунова для рассматриваемой системы, если она обладает следующими свойствами: 31

1. W (t, y) > 0 для всех t = 0; 2. W (0) = 0; 3. Для любого t выполняется: ∂W ≤0 ∂t Теорема 2. (первая теорема Ляпунова). Если для системы (2.4.1) существует функция Ляпунова W (t, y), допускающая знакоотрицательную производную по времени в силу рассматриваемой системы, то нулевое решение данной системы устойчиво по Ляпунову. Теорема 3.(первая теорема Ляпунова о неустойчивости). Если для системы (2.4.1) существует функция W (t, y), которая допускает бесконечно малый высший предел при y → ∞ и обладает знакоопределенной производной в силу системы, и существует некоторая точка (t0 , y0 ), для которой знак функции W (t, y) одинаков со знаком производной данной функции в силу системы, то решение неустойчиво в смысле Ляпунова при t → ∞. Проведем анализ устойчивости методом функций Ляпунова для модели выборов между тремя кандидатами. Запишем саму модель: ∂a1 = β1 (1 − a1 − a2 − a3 )a1 − a1 (θ12 a2 + θ13 a3 ) + a1 (θ21 a2 + θ31 a3 ), ∂t ∂a2 = β2 (1 − a1 − a2 − a3 )a2 − a2 (θ21 a1 + θ23 a3 ) + a2 (θ12 a1 + θ32 a3 ), ∂t ∂a3 = β3 (1 − a1 − a2 − a3 )a3 − a3 (θ31 a1 + θ32 a2 ) + a3 (θ13 a1 + θ23 a2 ). ∂t Будем исследовать нулевое решение. Рассмотрим следующую функцию Ляпунова: W (y) = a21 + a22 + a23 Эта функция удовлетворяет трем необходимым свойствам из определения. Посчитаем производную функции в силу рассматриваемой систе32

мы: ∂W a1 ∂W a2 ∂W a3 dW = + + = dy ∂a1 dt ∂a2 dt ∂a3 dt = 2a21 (β1 (1 − a1 − a2 − a3 ) − (θ12 a2 + θ13 a3 ) + (θ21 a2 + θ31 a3 ))+ +2a22 (β2 (1 − a1 − a2 − a3 ) − (θ21 a1 + θ23 a3 ) + (θ12 a1 + θ32 a3 ))+ +2a23 (β3 (1 − a1 − a2 − a3 ) − (θ31 a1 + θ32 a2 ) + (θ13 a1 + θ23 a2 )) Вспомним, какими свойствами обладают коэффициенты модели: 1. βi > 0, где i = 1, 2, 3; 2. θi > 0, где i = 1, 2, 3 и j = 1, 2, 3; Кроме того, переменные a1 , a2 , a3 также принимают значения больше нуля и в сумме не превышают единицу 0 < a1 + a2 + a3 ≤ 1 Отсюда можем сделать вывод, что каждое из трех слагаемых вида (β1 (1 − a1 − a2 − a3 ) − (θ12 a2 + θ13 a3 ) + (θ21 a2 + θ31 a3 )) (β2 (1 − a1 − a2 − a3 ) − (θ21 a1 + θ23 a3 ) + (θ12 a1 + θ32 a3 )) (β3 (1 − a1 − a2 − a3 ) − (θ31 a1 + θ32 a2 ) + (θ13 a1 + θ23 a2 )) при ai > 0, (где i = 1, 2, 3) принимаeт значения больше нуля. Кроме того, каждое из них умножается на 2a2i , (где i = 1, 2, 3), которые также являются положительными величинами. Следовательно, и их сумма, то есть производная в силу системы, будет положительной. По теореме 3 это говорит о том, что нулевое решение системы неустойчиво. 33

2.5. Численный пример. Возьмем следующие числовые значения коэффициентов: β1 = 0.5, 2 , 22 3 = , 22 β2 = 0.3, 5 , 22 4 = , 22 β3 = 0.8 1 22 2 = 22 θ12 = θ13 = θ21 = θ23 θ31 θ32 Запишем модель для трех кандидатов с данными коэффициентами: 2 5 1 4 ∂a1 = 0.5(1 − a1 − a2 − a3 )a1 − a1 a2 + a3 + a1 a2 + a3 , ∂t 22 22 22 22 ∂a2 2 1 3 2 = 0.3(1 − a1 − a2 − a3 )a2 − a2 a1 + a3 + a2 a1 + a3 , ∂t 22 22 22 22 ∂a3 4 2 5 3 = 0.8(1 − a1 − a2 − a3 )a3 − a3 a1 + a2 + a3 a1 + a2 . ∂t 22 22 22 22 Для нахождения стационарной точки данной системы необходимо решить следующую систему алгебраических уравнений: 5 2 1 0.5(1 − a1 − a2 − a3 ) − a2 + a3 + a2 + 22 22 22 1 3 2 0.3(1 − a1 − a2 − a3 ) − a1 + a3 + a1 + 22 22 22 4 2 5 0.8(1 − a1 − a2 − a3 ) − a1 + a2 + a1 + 22 22 22 4 a3 = 0, 22 2 a3 = 0, 22 3 a2 = 0. 22 Далее необходимо проверить с помощью теоремы 1 существует ли единственное решение данной системы. Для этого сначала проведем замены для удобства вычислений по формулам (2.3.4) и запишем матрицу системы и расширенную матрицу системы:   −0.5 −0.5455 −0.5455     A = −0.2545 −0.3 −0.3455   −0.7545 −0.7545 −0.8 34

  −0.5 −0.5455 −0.5455 −0.5     Ã = −0.2545 −0.3 −0.3455 −0.3   −0.7545 −0.7545 −0.8 −0.8 Теперь по условию теоремы 1 нам необходимо, чтобы ранги этих двух матриц были равны n = 3. Чтобы выяснить, так это или нет, посчитаем определители необходимых миноров по формулам (2.3.5.1)-(2.3.5.4):

−0.5 −0.5455 −0.5455

A1 =

−0.2545 −0.3 −0.3455

= −0.0949

−0.7545 −0.7545 −0.8

−0.5 −0.5455 −0.5455

A2 =

−0.3 −0.3 −0.3455

= −0.2063

−0.8 −0.7545 −0.8

−0.5 −0.5 −0.5455

A3 =

−0.2545 −0.3 −0.3455

= −0.2010

−0.7545 −0.8 −0.8

Все четыре рассматриваемых определителя ненулевые, значит ранги матрицы системы и расширенной матрицы равны трем, и, соответственно, система алгебраических уравнений имеет единственное решение. Вычислим значении положения равновесия по формулам (2.3.8). В результате получим следующие значения: a1 = 0.6844, a2 = 0.2018, a3 = 0.0876. 35

Отметим тот факт, что ai в сумме не дают единицу, т.е. остается еще некоторый процент населения, воздержавшийся от голосования. Вычислим его, исходя из условия (2.2.4): v = 1 − 0.6844 − 0.2018 − 0.0876 = 0.0262 Таким образом получаем, что 2,6% населения склонны воздержаться при голосовании. Проиллюстрируем графически динамику системы: Рис. 1: Выборы между 3 кандидатами На рисунке 2.1 красным цветом отображен график, отражающий изменение количества людей в группе V , желтый график описывает группу поддержки первого кандидата a1 , зеленый отвечает за группу второго кандидата a2 , а синий, в свою очередь, описывает ситуацию с группой третьего кандидата a3 . 36

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

Список литературы 1. Handbook of Social Choice and Welfare, Volume 1/ Edited by Arrow K. J., Sen A. K., Suzumura K.Elvester Science, 2002. P. 176-226. 2. Вольский В. И. "Процедуры голосования в малых группах с древнейших времени до начала XX века". М.: Изд. дом. Высшей школы экономики, 2014. 76 с. 3. Гасратова Н. А., Столбовая М. В., Бойцов Д. С., Степанова Д. С. Математическая модель хищник-жертва на линейном ареале // Молодой ученый. 2014. є11. С. 1-10. 4. Бейли Н. "Математика в медицине и биологии". М.:Изд. "Мир 1970. 321 с. 5. Misra A. K. A simple mathematical model for spread of two political parties // Nonlinear Analysis: Modelling and Control. 2012. Vol. 17, No 3. P. 343–354. 6. Демидович Б. П. "Лекции по математической теории устойчивости". СПб.: Изд. "Лань 2008. 480 с. 38

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв