Диссертация (1137313), страница 16
Текст из файла (страница 16)
1 !2 !... !,в котором 11 22 ... обозначает обычное произведение чисел, а не циклический тип.Множество перестановок заданного циклического типа называется классомсопряженности. Число перестановок циклического типа 11 22 ... равно−1 !.108Логическая функция от утверждения ⎧⎪⎪⎨1, если истинно,() =⎪⎪⎩0, если ложно.Биномиальный коэффициент⎧⎪(︃ )︃⎪⎨ ! , ∈ N!(−)!= =⎪⎪⎩ ∈/ N.НОД() – наибольший общий делитель частей разбиения , НОК() – наименьшее общее кратное частей .
Пусть также = НОК().Формула для вычисления количества АН-классов, найденная в [Egecioglu,Giritligil, 2013](︃(, ) =∑︁−1+!)︃−1.−1!Если и ! – взаимно простые числа, то число АН-классов)︃(︃1 + ! − 1.(, ) =! − 1!3.2.2Индексы манипулируемостиВ Главе 1 и 2 были введены такие понятия, как: избиратель, имеющий стимул манипулировать, манипулируемый профиль (Определение 1.3), манипулируемое правило (Определение 1.4), методы расширения предпочтений Leximinи Leximax (раздел 2.2.2), которые будут использоваться и в данной главе. Здесьбудет рассмотрен только случай с полной информацией, а центральное место занимают вероятностные модели.
Кроме того, контекст манипулирования не такважен, и мы рассматриваем общий случай – вероятность некоторого события вразличных вероятностных моделях.109Обозначим за (, , , ) вероятность события в модели при фиксированном числе альтернатив, , и избирателей, . Для того, чтобы вычислитьвероятность события в модели IAC или IANC, необходимо, чтобы это событиене разбивало классы эквивалентности. Иными словами, событие либо происходит во всех профилях класса, либо не происходит ни в одном из них (критерийсобытия должен удовлетворять свойству анонимности или анонимности и нейтральности).
Под выражением « происходит в ()» подразумевается, что происходит во всех профилях предпочтений из ().Рассмотрим теперь вероятность события в различных моделях, а именно, (, , , ) =|⃗ ∈ Ω, : происходит в ⃗ |,(!) (, , , ) = (, , , ) =| ∈ P, : происходит в |,(, )| ∈ Θ, : происходит в |.(, )Если событие – существование избирателя, имеющего стимул манипулировать при правиле (или просто манипулирование при ) и используемаявероятностная модель – IC, то получаем индекс 1 ( , , , ), вероятность манипулирования при полной информации.
Этот индекс в литературеназывается также индексом Нитцана-Келли, и в данной главе будет использовано соответствующее для него обозначение ( , , , ) = (Манипулирование при , , , ).1103.3Оценка расстояния между моделями IC и IANCЗадача этого раздела – оценить максимальную возможную разность вероятностных показателей в моделях IC, IAC, IANC. Эту разность назовем расстоянием между моделями.Определение 3.1.
Расстоянием между вероятностными моделями 1 и 2для избирателей и альтернатив называется величинаΔ1 −2 (, ) = max (| (, 1 , , ) − (, 2 , , )|).Очевидно, что данная функция удовлетворяет аксиомам тождества и симметрии, необходимым для того, чтобы быть функцией расстояния. Выполнениетретьей аксиомы, неравенства треугольника, будет показано в разделе 3.3.3.Так как модель IANC является достаточно новой и малоизученной, в первуюочередь представляет интерес рассмотрение расстояния между IANC и базовоймоделью IC.Δ− (, ) = max (| (, , , ) − (, , , )|) =⎞⃒⎛⃒⃒⃒∑︁∑︁⃒⃒1||⎠⃒ =−= max ⎝⃒⃒(, ) ⃒⃒⃒: происходит в (!): происходит в ⃒⎞⎛⃒⃒⃒)︂(︂∑︁⃒⃒1||⃒⎠.−= max ⎝⃒⃒⃒(!)(,)⃒⃒: происходит в Для любого АН-класса выполнено||1> 0, если || > (||), −(!)(, )||1= 0, если || = (||), −(!)(, )1111||−< 0, если || < (||).(!) (, )Вероятностный показатель в модели IC больше (меньше), чем в модели IANC,если средняя мощность АН-классов, в которых происходит событие , больше(меньше), чем средняя мощность всех АН-классов.
Следовательно, разность вероятностных показателей в модели IC максимальна и положительна, если событие происходит во всех АН-классах таких, что || > (||) и не происходитв таких , что || < (||). Наоборот, разность максимальна и отрицательна,если событие происходит во всех АН-классах таких, что || < (||) и непроисходит в таких , что || > (||). АН-классы , для которых || = (||),очевидно, не влияют на разность вероятностных показателей в моделях.Таким образом,∑︁Δ− (, ) =(︂: ||>(||)||1−(!) (, )⎛=1−∑︁:||≤(||)=∑︁:||≤(||)3.3.11−(, )||− ⎝1 −(!)∑︁:||≤(||))︂=⎞∑︁:||≤(||)||=(!)1⎠=(, )∑︁:||<(||)(︂)︂1||−.(, ) (!)Максимальные и минимальные АН-классыКак было замечено выше, разность вероятностных показателей в моделяхпроисходит от неравной мощности классов эквивалентности. Поэтому в данномразделе исследуются свойства АН-классов, в которых содержится наибольшееи наименьшее число элементов.112Теорема 3.3.1.
(АН-классы с минимальным и максимальным числом элементов) а) Минимальное число элементов в АН-классе равно !. Этот классединственен при ≥ 3. б) Максимальное число элементов а АН-классе равно!!, если и только если ! > .Доказательство. а) Если профиль ⃗ состоит из одинаковых столбцов (индивидуальных предпочтений), то ⃗ = {(0 , ) : ∈ ()} и |⃗ | = !. Поэтому|min | ≤ !!/! = !.
Для любых ∈ () и 1 ̸= 2 невозможно, чтобы(1 , ) ∈ ⃗ и (2 , ) ∈ ⃗ одновременно, так как (⃗ )1 ̸= (⃗ )2 . Поэтому|min | ≥ !!/! = !, и, следовательно, |min | = !.Рассмотрим профиль предпочтений, состоящий из двух столбцов, 1 =(1 , 2 , ..., ) и 2 = (2 , 1 , 3 ..., ). Возьмем = (12)(3)...() и = (12).Тогда |⃗ | = 2 = !.
Поэтому в случае = 2 существует более одного АНкласса с минимальной мощностью.⃗ c ≥ 3 существует по крайней мере два различныхПусть в профиле столбца, и . Пусть ∈ () переставляет столбцы и и оставляет наместе столбец , ̸= , ̸= . Так как не существует такой , чтобы (, ) ∈ ⃗ ,то можно заключить, что |⃗ | < !.Таким образом, |⃗ | = ! при ≥ 3, если и только если 1 = 2 = ... = .Так как все такие профили эквивалентны, то АН-класс с минимальной мощностью единственен.б) Сначала покажем, что из |max | = !! следует ! > . Предположим⃗ , то существуютобратное, |max | = !! и ! ≤ .
Если ! < для некоторого такие , ∈ , что = . Пусть перестановка 1 меняет местами толькостолбцы и . Тогда 0 = (0 , 0 ) ∈ ⃗ и 1 = (0 , 1 ) ∈ ⃗ , значит, |⃗ | > 1и | | < !!. Если ! = , то профиль предпочтений состоит из попарноразличных столбцов всех ! типов. Возьмем любую перестановку порядка ,113например, (1 2 ...), которая разбивает множество ! линейных порядков на(−1)! непересекающихся орбит. Следовательно, если | | = !!, то ! > .Теперь необходимо доказать, что, если ! > , то | | = !!. Предполо-⃗ , состоящего из попарножим, что существуют такие и , что для любого ⃗ , и построимразличных столбцов, |⃗ | ≥ 2.
Возьмем один из этих профилей, множество профилей = {⃗ ′ = (1 , ..., −1 , ′ ) : ′ ∈ () ∖ {1 , ..., −1 }}.Мощность этого множества равна ! − + 1. Согласно сделанному пред-⃗ ∈ , | ⃗ | ≥ 2. Это означает, что существуетположению, для каждого такая (, ) ̸= (0 , 0 ), что не имеет циклов длины 1. Тогда для любого ′ = (1 , ..., ), ( (1) , ..., () ) ∈ {1 , ..., −1 }, где ∈ {1, ..., }, а – порядок перестановки , что, однако, невозможно.
Следовательно, для любых и , существуют профили предпочтений, имеющие только одну нейтральнуюперестановку, (0 , 0 ). Мощность максимального АН-класса, состоящего из таких профилей,| | =!!= !!.1В отличие от АН-классов минимальной мощностью, максимальных АНклассов может быть несколько. Однако вычисление точного их количествапредставляет собой сложную комбинаторную задачу, поэтому мы рассмотримслучай с < ! и дадим интервальную оценку их количества. Воспользуемсямножеством профилей предпочтений, состоящих из попарно различных столбцов, которое обозначим за Ω̃, .
Ясно, что при > ! это множество пусто.˜Количество классов эквивалентности в этом множестве обозначим за (,),114а множество неподвижных точек из Ω̃, для пары перестановок – за ˜ .˜ = {⃗ ∈ Ω̃, : ⃗ = ⃗ }.Лемма 3.1. Количество неподвижных точек из Ω̃, для пары перестановок = (, ) равно|˜ | =⎧⎪∏︀⎪⎨ =0 (! − · ), если 1 = 2 = ... = = ,.⎪⎪⎩0, иначе.где = НОК().Доказательство. Предположим, что для некоторого профиля ⃗ ∈ Ω̃, и па-⃗ = ⃗ . Рассмотрим перестановку , порядок этойры перестановок ∈ , перестановки равен наименьшему общему кратному длин циклов этой перестановки, т.е. НОК() = . После действия столбец (1 , 2 , ..., ) переходит встолбец ( (1) , (2) , ..., () ).
Повторное действие перестановки приведет к( 2 (1) , 2 (2) , ..., 2 () ), и т.д. Наконец, столбец ( −1 (1) , −1 (2) , ..., −1 () ) переходит в (1 , 2 , ..., ).Теперь в некоторой перестановке на множестве избирателей возьмем произвольный цикл (1 , 2 , ..., ). Пусть столбец номер 1 – (1 , 2 , ..., ). Затем, последействия , он становится столбцом номер 2 . В то же время, после действияперестановки столбец 2 становится ( (1) , (2) , ..., () ).
Так как профильявляется неподвижной точкой , столбец номер 2 в профиле до действия перестановок должен быть равен ( (1) , (2) , ..., () ). Аналогично, столбец 2 переходит в столбец 3 , а после действия становится ( 2 (1) , 2 (2) , ..., 2 () ). Сле-⃗ столбец номер 3 равен ( 2 (1) , 2 (2) , ..., 2 () ), и т.д.довательно, в профиле Наконец, столбец переходит в столбец 1 , значит, столбец должен быть равен ( −1 (1) , −1 (2) , ..., −1 () ), чтобы перейти в (1 , 2 , ..., ) после действия .115Так как мы рассматриваем множество профилей, состоящих из попарно различных столбцов, длина цикла (1 , 2 , ..., ), , должна быть равна = НОК(), итак для любого цикла в перестановке .
Иными словами, 1 = 2 = ... = = ,или НОД() = НОК() = .Пусть пара перестановок = (, ) такова, что 1 = 2 = ... = = и состоит из = / циклов. Первый столбец первого цикла перестановки можно выбрать ! способами. Остальные столбцы первого цикла определяются перестановкой . Далее первый столбец второго цикла в можно выбрать! − способами, так как типов столбцов уже использованы в профиле. Первый столбец третьего цикла перестановки можно выбрать !−2 способами ит.д.
Внутри любого цикла не может повторно появиться столбец, уже использованный в профиле, так как разбивает множество линейных порядков на нанепересекающиеся орбиты, и столбцы, переставляемые одим и тем же циклом , составляют эти орбиты.Таким образом, получена точная формула для вычисления количества неподвижных точек из Ω̃, для произвольной пары перестановок = (, )|˜ | =⎧⎪∏︀⎪⎨ =0 (! − · ), если 1 = 2 = ... = = ,.⎪⎪⎩0, иначе.Так как все профили предпочтений из максимальных по мощности АНклассов состоят из попарно различных столбцов в случае ! > , то следующим˜шагом будет посчитать количество АН-классов в множестве Ω̃, , (,).116Теорема 3.3.2.
Для любых и таких, что ! > , количество АН-классовна Ω̃, равно˜(,) =∑︁ ∑︁−1 −1 ((, ))−1∏︁(! − · ),=0∈Π ∈Πгде (, ) – утверждение «1 = 2 = ... = = ».˜ АН-классов на множестве Ω̃, , аДоказательство. Пусть имеется ˜⃗ 1 , ⃗ 2 , ..., ⃗ – их представители. Для любого профиля предпочтений ⃗ вы-полнено |⃗ | · |⃗ | = ||. Теперь просуммируем эти равенства по всем представителям классов˜∑︁⃒ ⃒ ⃒⃒˜ · || ,⃒ ⃗ ⃒ · ⃒ ⃗ ⃒ = =1˜⃒1 ∑︁ ⃒⃒ ⃒⃒ ⃒⃒˜=⃗ · ⃗ ⃒.|| =1⃒⃒⃒⃒⃗ и ⃗ принадлежат одному и тому же АНТак как ⃒⃗ ⃒ = ⃒⃗ ⃒, если классу, то справедливо∑︁ ⃒⃒ ⃒ ⃒⃒⃒⃒ ⃗ ⃒ · ⃒ ⃗ ⃒ =⃒ ⃗ ⃒.⃗ ∈⃗ ˜˜∑︁∑︁∑︁ ⃒⃒ ⃒ ⃒⃒⃒1 ∑︁ ⃒⃒ ⃒⃒11˜⃒⃒⃒⃒⃒⃒ ⃗ · ⃗ =⃗ =⃗ .=|| =1 || =1 ⃗|| ⃗ ∈⃗ ∈Ω̃,Суммарное количество нейтральных перестановок для всех профилей из Ω̃,равно сумме всех неподвижных точек из Ω̃, для всех перестановок⃒∑︁ ⃒ ⃒ ∑︁ ∑︁∑︁ ∑︁∑︁ ⃒⃒⃒˜⃒ ⃗ ⃒ =1=1=⃒ ⃒.⃗ ∈Ω̃⃗ ∈Ω̃ ∈⃗∈ ⃗ ∈˜ 1 ∑︁ ⃒⃒ ˜ ⃒⃒˜=⃒ ⃒.|| ∈117∈Используя результат Леммы 3.1 и обозначив за (, ) утверждение «1 =2 = ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
