Диссертация (1137313), страница 15
Текст из файла (страница 15)
В работе представлено алгебраическое описание модели, дана формула вычисления количества классов эквивалентности,и предложен алгоритм равномерной генерации классов.Модель IANC интересна тем, что любая «непредвзятая» процедура выбора обладает свойствами анонимности и нейтральности, следовательно, профили предпочтений, принадлежащие одному и тому же классу эквивалентности,будут одновременно либо манипулируемыми, либо нет. То есть, если мы можем сказать, что профиль-представитель класса подвержен манипулированиюсо стороны избирателей, тогда то же самое мы можем сказать и об остальныхпрофилях класса.
Другой пример функции от профиля, обладающей свойствами анонимности и нейтральности – это меры сходства предпочтений в коллективе [37]. Так как количество классов эквивалентности намного меньше количества всех профилей предпочтений, то модель представляет также практическуюценность. Первая величина растет как полином от количества избирателей, авторая – как экспонента (рисунок 3.1).Рисунок 3.1. Количество профилей предпочтений, количество классовэквивалентности в IAC, количество классов эквивалентности в IANC,логарифмическая шкала.102Таким образом, имеется три вероятностные модели, отличающиеся своей интерпретацией. В Главе 1 было рассказано о том, в каких задачах применялась таили иная модель.
Существуют исследования, позволяющие сравнить значенияодних и тех же показателей, вычисленных в различных моделях. Однако нигдене рассматривался вопрос, какова максимальная возможная разность значенийпоказателя, вычисленного в различных моделях для фиксированного числа избирателей и альтернатив. Назовем эту разность расстоянием между моделями.Если бы было доказано, что при некоторых значениях и расстояниемежду какими-либо двумя моделями равно 0, и имеется значение некоторогопоказателя, вычисленного в одной из моделей, то проводить вычисления в другой не имеет смысла, так как они будут равны. С другой стороны, представляетинтерес случай, когда расстояние между моделями достаточно велико, чтобыиндексы манипулируемости правил могли изменить свое положение друг относительно друга.В данной главе рассмотрены оба эти вопроса: аналитически и численно исследовано расстояние между моделями IC, IAC, IANC, а также проведено вычисление индекса манипулируемости для 4 правил коллективного выбора в моделяхIC и IANC с целью сравнить разность индексов в этих моделях с максимальнойразностью.3.23.2.1Определения и теоретическая основаВероятностные моделиДля стилистического единства обозначений множество профилей предпочтений для избирателей и альтернатив, () , в этой главе обозначим за Ω, .Общее количество профилей предпочтений равно |Ω, | = (!) .103Модель независимых предпочтений, ICВсе (!) профилей предпочтений считаются равновероятными.
Другая интерпретация модели: каждый избиратель выбирает свои предпочтения независимо от остальных (нулевая степень взаимозависимости предпочтений в классемоделей Пойа-Эггенбергера).Модель независимых анонимных предпочтений, IACВ модели IAC избиратели считаются неразличимыми, и профили предпочтений, различающиеся только перестановкой избирателей, считаются эквивалентными. Обозначим перестановку на множестве избирателей, элемент симметрической групы (), за , а пререстановку на множестве {1, 2, ..., }, элементсимметрической группы (), – за , 0 и 0 – тождественные перестанов-⃗ под действиемки соответствующих симметрических групп. Образ профиля ⃗ . Группа перестановок () действуетперестановки обозначается за на множестве Ω, и задает его разбиение на непересекающиеся орбиты, иликлассы эквивалентности по анонимности (А-классы),Ω, = 1 ∪ 2 ∪ .
. . ∪ (,) .Любой профиль предпочтений в заданном А-классе может быть взят в качетве его представителя, а все остальные профили класса могут быть полученыпутем перестановки имен избирателей всеми возможными способами.⃗ = {⃗ ∈ Ω, : ∈ ()}.Буквенное обозначение для классов эквивалентности обычно имеет нижнийиндекс, обозначающий номер или представителя класса, однако для простотыможет появляться и без индекса, когда он неважен.104Количество А-классов может быть вычислено как число сочетаний с повторениями из ! типов предпочтений по ,(︃)︃ + ! − 1(, ) =.! − 1Каждому А-классу соответствует один анонимный профиль, и в модели IACпредполагается, что все А-классы равновероятны (из чего следует неодинаковаявероятность для профилей предпочтений).
Множество А-классов обозначим заP,Модель может быть описана с помощью урновой схемы (см. раздел 1.3.1),где после случайного выбора из урны одного из ! шаров, в нее возвращаетсявынутый шар и дабавляется один шар того же типа. Таким образом, возрастаетвероятность в следующий раз выбрать шар того же самого типа, что соответствует большей взаимозависимости предпочтений среди избирателей.Пример 3.1.
Рассмотрим множество Ω2,3 , которое состоит из 8 профилей предпочтений.⎛⎞⎛⎞⎛⎞⎛⎞⎜ ⎟ ⃗⎜ ⎟ ⃗⎜ ⎟ ⃗⎜ ⎟⃗1 = ⎝⎠ , 2 = ⎝⎠ , 3 = ⎝⎠ , 4 = ⎝⎠, ⎛⎞⎛⎞⎛⎞⎛⎞⎜ ⎟ ⃗⎜ ⎟ ⃗⎜ ⎟ ⃗⎜ ⎟⃗5 = ⎝⎠ , 6 = ⎝⎠ , 7 = ⎝⎠ , 8 = ⎝⎠. ⃗1 }, 2 = {⃗2 , ⃗3 , ⃗4 }, 3 =Множество Ω2,3 разбивается на 4 А-класса, 1 = {{⃗5 , ⃗6 , ⃗7 }, 4 = {⃗8 }.⃗1 равна 1/4, а ⃗2 – 1/12.Следовательно, вероятность появления профиля 105Модель независимых анонимных и нейтральных предпочтений,IANCНеразличимыми считаются как избиратели, так и альтернативы. Имеется! перестановок на множестве {1, 2, ..., } и ! перестановок на множестве{1, 2, ..., }. Одновременную перестановку избирателей и имен альтернатив обо⃗ под действием обозначается зазначим за = (, ).
Образ профиля (⃗ ) = (⃗ ) , или ⃗ . Профили предпочтений ⃗1 и ⃗2 , отличающиеся перестановкой избирателей и имен альтенатив (т.е. существует ∈ такая, что⃗1 = ⃗2 ), называются эквивалентными в модели IANC.Таким образом, группа перестановок = ()×(), || = !!, действует на множестве Ω, и задает его разбиение на непересекающиеся орбиты– классы эквивалентности по анонимности и нейтральности (АН-классы).Ω, = 1 ∪ 2 ∪ .
. . ∪ (,) .Аналогично, все элементы АН-класса могут быть получены из профиляпредставителя класса путем действия всех возможных перестановок на этотпрофиль,⃗ = {⃗ ∈ Ω, : ∈ }.Если для заданной перестановки существует профиль, который не меня-⃗ = ⃗ , то ⃗ называетя неподвижнойется под действием этой перестановки, точкой , а называется нейтральной перестановкой для ⃗ .
Введем обозначениедля множества неподвижных точек данной перестановки , = {⃗ ∈ Ω, : ⃗ = ⃗ }.106Множество нейтральных перестановок для заданного профиля предпочтений⃗ называется стабилизатором ⃗ и обозначается за ⃗ ,⃗ = { ∈ : ⃗ = ⃗ }.Среднее число элементов в АН-классе равно∑︀(,)(||) =| |.(, )=1Классы эквивалентности в модели IANC также считаются равновероятными.Множество АН-классов обозначим за Θ, .Пример 3.2. Рассмотрим множество Ω2,3 из предыдущего примера. Ω2,3 раз⃗1 , ⃗8 }, 2 = {⃗2 , ⃗3 , ⃗4 , ⃗5 , ⃗6 , ⃗7 }.бивается на два АН-класса: 1 = {Если рассматривается действие группы перестановок () на множествеА-классов, P, , то множество А-классов само разбивается на орбиты, назовем их нейтральными классами эквивалентности по анонимности, или НАклассами.
Элементами НА-класса являются А-классы, = { ∈ P, : ∈ ()},⃗ ) ∈ Ω, : ∈ ()}. Ясно, что количество НА-классовгде ⃗ = {(равно количеству АН-классов.Стабилизатор А-класса – это подгруппа группы перестановок (),определяемая следующим образомT = { ∈ () : = }.Количество элементов в НА-классе| | = |()|/|T |.107Соответственно, средняя мощность НА-класса рассчитывается как∑︀(,)| |.(, )=1(||) =Количество АН-классовРазбиением числа назовем слабо убывающую последовательность положительных целых чисел = (1 , 2 , 3 , .., ) такую, что (1 ≥ 2 ≥ 3 ≥ ... ≥ ) и 1 + 2 + ... + = , где называется частью . Например, (3,1,1) –разбиение числа 5 на 3 части. Тип разбиения 11 22 ... означает, что имеет частей размера для всех от 1 до .
Например, тип разбиения (3,1,1) – 12 31 .За Π обозначим множество всех разбиений числа .Перестановка на множестве из элементов определяет его разбиение:длины циклов перестановки – части разбиения. Например, для перестановки = (142)(35)(67) циклический тип 22 31 . Пусть перестановка на множестве избирателей задает разбиение ∈ Π , а перестановка на множестве {1, ..., }, ,задает разбиение ∈ Π . Сумма = 1 + 2 + ... обозначает общее количествоциклов в перестановке .Для разбиения определим число = 11 22 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
