Диссертация (1137313), страница 17
Текст из файла (страница 17)
= = », получим∑︁∏︁1˜(! − · НОК()).(,) =((, ))|| ∈=0⃒⃒⃒ ˜ ⃒Так как ⃒ ⃒ зависит только от циклического типа перестановок (, ), можно взять сумму по всем возможным разбиениям и и умножить каждое слагаемое на количество перестановок из () с разбиением и количествоперестановок () с разбиением , т.е. −1 ! и −1 !, соответственно. Итак,−1∑︁ ∑︁∏︁1−1−1˜(, ) = ! · ! · ((, ))(! − · ) =!! ∈Π ∈Π =0=∑︁ ∑︁−1 −1 ((, ))−1∏︁(! − · ).=0∈Π ∈ΠРезультат Теоремы 3.2.2 дает возможность построить оценку для количествамаксимальных по мощности АН-классов.Следствие 3.1.
Для любых и таких, что ! > , выполнено:а) количество максимальных по мощности АН-классов удовлетворяет следующему неравенству2(! − 1)!̃︀̃︀− (,) ≤ (, ) ≤ (,);(! − )!!б) если > и – простое число, то количество максимальных по мощности˜АН-классов равно (,).Доказательство. а) Правая часть неравенства очевидна, так как профилипредпочтений из максимального АН-класса всегда состоят из попарно раличных столбцов при ! > . Общее количество профилей предпочтений, состоя118щих из попарно различных столбцов равно|Ω̃, | = ! · (! − 1) · ... · (! + 1 − ) =(!)!.(! − )!В то же время, это количество неподвижных точек в Ω̃, для тождественнойперестановки.
Так как для тождественной перестановки утверждение (, )˜верно, то (!)!/(! − )! входит в сумму !!(,). Остальные слагаемыесоставляют!!∑︁ ∑︁−1 −1 ((, ))−1∏︁(! − · ) −=0∈Π ∈Π(!)!.(! − )!Так как множества ˜ пересекаются, то количество профилей предпочтений, имеющих более одной нейтральной перестановки не больше числа˜!!(,) −(!)!.(! − )!Тогда количество профилей, имеющих только одну нейтральную перестановку, не меньше числа)︂(︂2(!)!(!)!(!)!˜˜− !!(,) −=− !!(,).(! − )!(! − )!(! − )!Разделив получившееся выражение на !!, получим оценку снизу для числамаксимальных классов эквивалентностиmax (, ) ≥2(! − 1)!˜− (,).(! − )!!б) Если – простое число, то содержит либо один цикл длины , либо циклов длины 1.
В первом случае НОК() также равно , но мы предположили,что > , значит, первый случай невозможен. Во втором случае только тождественная перестановка является нейтральной для любого профиля из Ω̃, .119Следовательно, Ω̃, включает в себя только профили из максимальных АНклассов, и(! − 1)!˜(,) = max (, ) =.(! − )!!3.3.2Оценка максимальной разности для малых значенийВ данном разеделе будут использованы теоретические результаты о мощности и количестве максимальных и минимальных АН-классов для полученияоценки расстояния между моделями IC и IANC.Как было упомянуто ранее, разность вероятностных показателей в моделях происходит из неодинаковой мощности классов эквивалентности. Проиллюстрируем это при помощи диаграммы на рисунке 3.2.
По оси абсцисс отложены 24 АН-класса для случая 3 альтернатив и 4 избирателей. Высота каждогостолбца равна мощности соответствующего АН-класса. Горизонтальная линия,пересекающая столбцы, обозначает среднюю мощность АН-класса.Рисунок 3.2. Множество АН-классов для = 3 и = 4.Чтобы вычислить расстояние между моделями IC и IANC, необходимо посчитать количество и суммарную мощность либо а) всех АН-классов, количествоэлементов в которых превосходит среднюю мощность АН-класса; либо б) всех120Таблица 3.1. Значения ˜ () для 3 ≤ ≤ 10 3 4 5 6 78910˜ 4 7 14 33 85 238 710 2244АН-классов, мощность которых ниже средней мощности.
Так как минимальныйАН-класс всегда единственен, и разнообразие АН-классов, мощность которыхниже средней, достаточно большое, путь б) для оценки расстояния представляется очень трудоемким. С другой стороны, для значений , ограниченныхсверху некоторым числом, только максимальные по мощности классы находятся выше линии средней мощности, что значительно упрощает задачу оценкирасстояния между моделями.Обозначим за ˜ () то значение количества избирателей, начиная с которогоне только максимальные АН-классы превышают по мощности (||) для заданного значения .
Следовательно, для таких и , что < ˜ () необходимоопределить только количество максимальных АН-классов.Таблица 3.1 показывает значения ˜ () для 3 ≤ ≤ 10.Таким образом, для случая < ˜ () расстояние между моделями IC и IANCможет быть вычислено по формуле(︂)︂!1Δ− (, ) = (, )−.(!)−1 (, )Из таблицы видно, что для рассматриваемых значений ˜ () меньше, чем!.
Тогда, используя оценку количества максимальных АН-классов из Следствия 3.1, получаем интервальную оценку расстояния между моделями IC иIANC.(︂)︂ (︂)︂2(! − 1)!!1˜− (,) ·−≤ Δ− (, ) ≤! − )!!(!)−1 (, )121˜≤ (,) ·(︂!1−(!)−1 (, ))︂Если же и таковы, что < < 2 и – простое число, то точноезначение расстояния вычисляется по формуле)︂1!˜−.Δ− (, ) = (,)(!)−1 (, )(︂Посчитаем оценку Δ− (, ) для ≤ 10 и ≤ 10.
В случае трехальтернатив точные значения Δ− (, ) могут быть легко получены спомощью полного перечисления АН-классов. В случае четырех альтернативи 7 ≤ ≤ 10 для оценки Δ− (, ) применялся алгоритм случайнойгенерации АН-классов, предложенный в [9]. В каждом из 10000 сгенерированных представителей АН-классов вычислялась мощность соответствующего ему класса, затем подсчитывалось количество и суммарная мощность техАН-классов , для которых || > (||).
В остальных случаях применяласьполученная интервальная оценка для Δ− (, ). Согласно расчетам, для ≥ 4 длина интервала составляет не более 0,022. Графики на рисунке 3.3иллюстрируют результаты вычислений, каждая точка представляет собой середину интервала.Как видно из представленных графиков, расстояние между IC и IANC увеличивается с ростом числа избирателей во всех случаях, кроме = 3, = 8.При увеличении числа альтернатив расстояние, напротив, уменьшается.
Ужепри ≥ 6 оно становится менее 0,1. В то же время, если максимальная разность вероятностных показателей достаточно высока, то это может послужитьпричиной существенных изменений при переходе от модели IC к модели IANC.К примеру, может измениться степень манипулируемости правил относительнодруг друга, как будет показано в разделе 3.4.122Рисунок 3.3. Оценка расстояния между моделями IC и IANC для ≤ 10 и ≤ 103.3.3Сравнение моделей IC, IAC, IANC в асимптотикеВ данном разделе добавляется к сравнению модель IAC, занимающая в некотором смысле промежуточное положение между IC и IANC. Сначала будетрассмотрено расстояние между IAC и IANC и его асимптотическое поведение,затем представлены результаты анализа расстояния между IC и IAC, и, наконец, сделаны выводы о том, как выглядит расстояние между IC и IANC длязначений и за пределами ограничений, указанных в предыдущем разделе.Покажем выполнение неравенства треугольника для Δ1 −2 (, ) следующей леммой.Лемма 3.2.
Для любых трех вероятностных моделей 1 , 2 , 3 выполняетсянеравенствоΔ1 −2 (, ) + Δ2 −3 (, ) ≥ Δ1 −3 (, ).Доказательство. Пусть 1 , 2 и 3 будут события, максимизирующие абсолютную разность вероятностных показателей в моделях 1 и 2 , 2 и 3 , 1123и 3 , соответственно, т.е.1 = arg max(| Pr(, 1 , , ) − Pr(, 2 , , )|),2 = arg max(| Pr(, 2 , , ) − Pr(, 3 , , )|),3 = arg max(| Pr(, 1 , , ) − Pr(, 3 , , )|).Если абсолютное значение разности максимально для некоторого события1 , то оно максимально и для противоположного события, 1 . Поэтому безпотери общности можно предположить, что значения разности вероятностныхпоказателей в моделях положительны во всех трех случаях.
Далее,Pr(3 , 1 , , ) − Pr(3 , 3 , , ) == Pr(3 , 1 , , ) − Pr(3 , 2 , , ) + (Pr(3 , 2 , , ) − Pr(3 , 3 , , )).Pr(3 , 1 , , ) − Pr(3 , 2 , , ) ≤≤ Pr(1 , 1 , , ) − Pr(1 , 2 , , ) = Δ1 −2 (, ),Pr(3 , 2 , , ) − Pr(3 , 3 , , ) ≤≤ Pr(2 , 2 , , ) − Pr(2 , 3 , , ) = Δ2 −3 (, ).Следовательно,Δ1 −3 (, ) = Pr(3 , 1 , , ) − Pr(3 , 3 , , ) ≤≤ Δ1 −2 (, ) + Δ2 −3 (, ).124Применяя неравенство треугольника несколько раз, получим|Δ− (, ) − Δ− (, )| ≤ Δ− (, ) ≤≤ Δ− (, ) + Δ− (, ).Теперь необходимо оценить расстояние Δ− (, ). Для этого рассмотрим множество НА-классов 1 , ..., (,) .Очевидно, что минимальное возможное число перестановок в равно 1,поэтому| | =|()|!=≤ !.| || |На рисунке 3.4 показано множество НА-классов и их мощность для случая = 3, = 4. Высота столбца, соответствующего некоторому НА-классу, показывает количество содержащихся в нем А-классов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
