Диссертация (1137313), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Количество максимальныхпо мощности НА-классов обозначим за (, ).Рисунок 3.4. Множество НА-классов для = 3 и = 4.Следующая теорема показывает, что доля максимальных НА-классов в общем числе НА-классов, а также доля А-классов, содержащихся в максимальныхНА-класссах, в общем числе А-классов стремится к 1 при → ∞ и → ∞.! (,) (,)Теорема 3.3.3. а) lim→∞ !(,) = 1 и lim→∞ (,) = 1 (,) (,)б) lim→∞ (,)= 1 и lim→∞ (,)= 1.125Доказательство. 1) Докажем сначала, что(, )(, )= 1 и lim= 1.→∞ !(, )→∞ !(, )lim(, )= (, )/!(, )⎛(︃)︃(︃)︃⎞∑︁/ + !/ − 1 ⎠⎝! · 1 ! + − 1 + !−1=!! − 1!/ − 1∈Π ∖{(1,1,...,1)}⎛∑︁= (, )/⎝(, ) + !∈Π ∖{(1,1,...,1)}Обозначим сумму в знаменателе за(︃)︃⎞/ + !/ − 1 ⎠−1.!/ − 1 , где∑︀∈Π ∖{(1,1,...,1)}(︃)︃/ + !/ − 1 = −1для ∈ Π ∖{(1, 1, ..., 1)}.!/ − 1Тогда(, )∑︀(, ) + !∈Π ∖{(1,1,...,1)}=1+1∑︀∈Π ∖{(1,1,...,1)}!(,).Предположим, что / – натуральное число, и биномиальный коэффициентненулевой!!=·(, )(︀/+!/−1)︀!/−1(︀!+−1)︀!−1=! (/ + !/ − 1)!(! − 1)!!·.

(!/ − 1)!(/)!(! + − 1)!2) Пусть фиксировано, а → ∞! (/ + !/ − 1)!(! − 1)!!·=→∞ (!/ − 1)!(/)!(! + − 1)!lim!(! − 1)!(/ + !/ − 1)!!lim= (!/ − 1)! →∞ (/)!(! + − 1)!126=!(! − 1)!!(/ + !/ − 1)!lim·= (!/ − 1)! →∞(/)!(! + − 1)!=!(! − 1)!(/ + 1) · ... · (/ + !/ − 1)lim= 0. (!/ − 1)! →∞( + 1) · ... · (! + − 1)Теперь зафиксируем значение , а → ∞! (/ + !/ − 1)!(! − 1)!!·=→∞ (!/ − 1)!(/)!(! + − 1)!lim=!! (/ + !/ − 1)!(! − 1)!lim·,(/)! →∞ (!/ − 1)!(! + − 1)!! (/ + !/ − 1)!(! − 1)! !(/ + !/ − 1)!(! − 1)!·<.(!/ − 1)!(! + − 1)!(!/ − 1)!(! + − 1)!!(/ + !/ − 1) · ... · (!/)!(/ + !/ − 1)!(! − 1)!= lim=→∞ (! + − 1) · ... · (! + 1)!→∞(!/ − 1)!(! + − 1)!lim(/ + !/ − 1)· ...→∞(! + − 1)= lim...

·1(!/)·= 0.(! + − /) (! + − / − 1) · ... · (! + 1)Следовательно,! (/ + !/ − 1)!(! − 1)!!·= 0.→∞ (!/ − 1)!(/)!(! + − 1)!lim3) Теперь просуммируем ! /(, ) по всем разбиениям изΠ ∖{(1, 1, ..., 1)} и таким, что / – натуральное число. Обозначим это множество разбиений за Π′ . Количество элементов в Π′ меньше или равно количеству элементов в Π ∖{(1, 1, ..., 1)}. Далее, |Π ∖{(1, 1, ..., 1)}| < ( − 1)! для ≥ 4, а для = 3 |Π ∖{(1, 1, ..., 1)}| = ( − 1)! = 2.

Оценим(/ + !/ − 1)(!/)1· ... ··≤(! + − 1)(! + − /) (! + − / − 1) · ... · (! + 1)≤(/ + !/ − 1)(!/)111· ... ··≤<.(! + − 1)(! + − /) (! + 1)(! + 1) !127Следовательно,∑︁∈Π′ !( − 1)!≤.(, )!Так как lim ( − 1)!/! = 0,→∞lim→∞∑︁∈Π′ ∑︁ !!= 0 и lim= 0,→∞(, )(,)∈Π′(, )(, )∑︀∑︀= 1 и lim= 1,→∞ (, ) + !→∞ (, ) + !lim∈Π′ ∈Π′ (, )(, )= 1 и lim= 1.→∞ !(, )→∞ !(, )lim4) Далее доказательство приведено для → ∞, доказательство для → ∞аналогично.!(, ) − (, )= 0,→∞!(, )lim!(, ) − (, ) ((, ) − (, ))!/2≥,!(, )!(, )((, ) − (, ))!/2(, ) − (, )= 0 и lim= 0,→∞→∞!(, )(, )lim (, )= 1.→∞ (, )limНаконец,! (, ) ! (, )≤,!(, )(, )! (, )= 1.→∞ (, )limСледствие 3.2. Расстояние между моделями IAC и IANC, Δ− (, ),стремится к нулю при → ∞ или → ∞.128Доказательство.

Δ− (, ) может быть вычислена как разность двухкомпонент: 1) доля НА-классов , мощность которых превосходит среднюю,(||); 2) доля А-классов, которые принадлежат НА-классам с мощностью более средней. Предположим, множество { : || > (||)} состоит из 1 НАклассов мощностью ! и содержащих 1 А-классов, 2 НА-классов мощностью!/2 и содержащих 2 А-классов, 3 НА-классов мощностью !/3 и содержащих 3 А-классов, и т.д. ТогдаΔ− =1122−+−+ ....(, ) (, ) (, ) (, )Далее доказательство приведено для → ∞, доказательство для → ∞аналогично.По Теореме 3.3.311! (, )= 1 и lim= lim= 1.→∞ (, )→∞ (, )→∞ (, )lim∀ ≥ 2(, ) − 1(, ) − 1≤,≤.(, )(, )(, )(, )(, ) − 1(, ) − 1= 0 и lim= 0.→∞→∞(, )(, )lim= 0 и lim= 0.→∞ (, )→∞ (, )∀ ≥ 2 limНаконец,(︂lim Δ− = lim→∞→∞)︂1122−+−+ ... = 0.(, ) (, ) (, ) (, )Таким образом, модели IAC и IANC становятся все ближе и ближе друг кдругу. Оценим теперь степень их близости.129Для вычисления расстояния необходимо знать количество НА-классов таких, что || > (||).

Если существуют такие НА-классы, что || > (||),кроме максимальных, имеющих мощность !, то они могут иметь мощность!/2. Если !/2 > (||), то!>2(︃∑︁)︃⧸︃||(, ) ⇒(︂∑︁:||<!)︂(, )|| < !− (, ) .2(3.1)Количество максимальных НА-классов можно оценить следующим образом(, ) −!(, ) − (, )!(, ) − (, )< (, ) < (, ) −.!/2! − 1(3.2)Нижняя граница соответствует случаю, когда все немаксимальные НАклассы имеют мощность !/2, верхняя – когда все немаксимальные НА-классысостоят из одного элемента.Вычисления показывают, что при числе избирателей ≤ 100, числе альтернатив ≤ 20 и оценке (, ) по формуле (3.2), условие (3.1) не выполняется, так как (, )/2 − (, ) принимает отрицательные значения. Следовательно, только максимальные НА-классы имеют мощность больше среднеймощности НА-класса при указанных ограничениях. Учитывая результат Теоремы 3.3.3 о том, что доля максимальных НА-классов стремится к 1, можнопредположить, что утверждение верно и для больших и .Тогда расстояние вычисляется какΔ− (, ) =! (, ) (, )−.(, )(, )130Используя верхнюю границу для (, ) из (3.2), получим!(, ) − (, )Δ− (, ) < (, ) −! − 1(︂)︂ (︂)︂!1−.(, ) (, )(3.3)Вычисления полученной оценки для различных и показывают, что расстояние Δ− (, ) принимает значения менее 0,02, если > 10 или > 10, и менее 0,01, если > 15 или > 15.

Подставляя верхнюю оценку внеравенство (3.2), получимΔ− (, ) − 0, 02 < Δ− (, ) < Δ− (, ) + 0, 02.(3.4)Таким образом, значения расстояния Δ− (, ) становятся все ближек значениям Δ− (, ). Последние могут быть легко вычислены при помощи метода Монте-Карло случайной генерации представителей А-классов. Нарисунке 3.5 представлены результаты приближенного вычисления расстоянияΔ− (, ), которые, в силу (3.4) можно рассматривать и как приближенные значения расстояния Δ− (, ).Рисунок 3.5. Приближенные значения расстояния Δ− (, ).По графикам видно, что с увеличением количества избирателей расстояниемежду IC и IAC приближается к 1, а при увеличении количества альтернатив131– к нулю.

Таким образом, при возрастании числа альтернатив все три модели,IC, IAC и IANC приближаются друг к другу, и, следовательно, значения любыхвероятностных показателей в этих моделях будут равны. В то же время, расстояние между базовой моделью, IC, и двумя другими, IAC и IANC, возрастаетпри увеличении числа избирателей, и в этом случае вероятностные показатели вIAC и IANC могут сильно отличаться от IC. Если событие склонно появляться в профилях с большой (малой) однородностью предпочтений, то показателив IAC и IANC будут превышать (ниже, чем) соответствующие показатели в IC.3.4Степень манипулируемости правил коллективного выбора в моделях IC и IANCВ данном разделе будет показано, как меняется значение вероятностного показателя при переходе от модели IC к модели IANC на примере индекса манипулируемости ( , , , ).Рассматриваются следующие правила коллективного выбора:1.

Правило относительного большинства.2. Правило одобряющего голосования с квотой = 2.3. Правило Борда.4. Процедура Блэка.Для работы с множественным выбором использовались методы расширенияпредпочтений Leximin и Leximax (см. раздел 2.2.2). Количество альтернатив = 3, количество избирателей 3 ≤ ≤ 30.

Для упрощения вычисления индексов в модели IC генерировалось все множество анонимных профилей, затемдля каждого анонимного профиля строился представитель соответствующего132А-класса, результат (1 или 0, имеет ли хотя бы один избиратель стимул манипулировать в данном профиле или нет таких избирателей) умножался на мощность А-класса. Для проведения экспериментов в модели IANC использовалсяалгоритм равномерной генерации представителей АН-классов, предложенныйв [9].Результаты вычислительных экспериментов представлены на графиках, рисунки 3.6-3.11.Рисунок 3.6. Индекс манипулируемости ( , , 3, ) при Leximin.Рисунок 3.7.

Индекс манипулируемости ( , , 3, ) при Leximin.133Рисунок 3.8. Разность индексов манипулируемости ( , , 3, ) и ( , , 3, ) при Leximin.Процедура Блэка оказалась наименее манипулируемой среди рассматриваемых четырех процедур в обеих вероятностных моделях. Наиболее манипулируемое правило (для большинства рассматриваемых значений ) в модели IC– правило относительного большинства, в то время как в модели IANC – правило одобряющего голосования. Таким образом, при изменении вероятностноймодели изменилась относительная манипулируемость правил.В большинстве случаев показатели манипулируемости в модели IANCснизились по сравнению с моделью IC.

Это видно по разности индексов ( , , 3, ) − ( , , 3, ), проиллюстрированной на рисунках3.8., 3.11. Однако для правила одобряющего голосования в некоторых случаяхиндекс манипулируемости даже возрос. Это объясняется тем, что для этого правила при 3 альтернативах манипулируемыми часто являются такие профили, вкоторых наблюдается большая степень однородности предпочтений избирателей, а значит, мощность соответствующих им АН-классов мала.

Характеристики

Список файлов диссертации