Автореферат (1137312), страница 4
Текст из файла (страница 4)
Максимальные значения I1 (Copeland, 1Winner, 3, n) стремятся к1.∙Максимальные значения I1 для правила одобряющего голосования с квотой 2 соответствуют ФПИRank.При алфавитном правиле устранениянесравнимости это правило защищено от манипулирования при ФПИ1Winner.Послетеоретическогоанализаивычислительныхэкспериментов,представленных в разделе 2.4, можно сделать вывод о том, что вероятностьманипулирования нельзя рассматривать как основной индекс манипулируемости в случае неполной информации, так как это может привести к неправильной интерпретации результатов.
Действительно, близкая к 1 вероятностьманипулирования означает, что практически всегда в большом коллективенайдется хотя бы один избиратель, для которого манипулирование будет хотябы с очень малой вероятностью, но более выгодно, чем голосование искренне.При этом в большом числе случаев манипулирование не приведет к успеху,так как степень влияния отдельного избирателя крайне мала. Чтобы учестьэти аспекты, необходимо рассмотреть другие показатели манипулируемости.В разделе 2.5 вводятся в рассмотрение следующие два индекса. ПустьI2– вероятность того, что в случайно выбранном профиле хотя бы один изби-ратель имеет стимул манипулировать и его манипулирование успешно в этомпрофиле.
Пустьπ(~P)W Niπ(~P)′(P̃i ) = {~P−i∈ Wi′: CF (~P) EPi CF (P̃i , ~P−i)}.– множество тех профилей информационного множества избирателя i, в которых манипулирование при помощи стратегиизультату. Пусть15P̃iприведет к худшему ре-π(~P)W Siπ(~P)′′(P̃i ) = {~P−i∈ Wi: CF (P̃i , ~P−i) EPi CF (~P)}.– множество профилей информационного множества избирателя i, в которыхманипулирование при помощи стратегииP̃iприведет к успеху. Определиминдекс I2 .I2 (CF , π, m, n) = |{~P ∈ L(A)N : ∃i ∈ N ∃P̃i ∈ L(A),π(~P)W Niπ(~P)(P̃i ) = 0/ & W Sin(P̃i ) ̸= 0}|/(m!)/.Другое свойство манипулирования при неполной информации: количество профилей из информационного множества избирателя, где манипулирование приводит к успеху, может быть очень малым по сравнению с мощностью всего информационного множества. Чтобы его учесть, введем переменную, измеряющую стимул к манипулированию для каждого избирателя,stimulus(i, ~P, π(~P)).Тогдаstimulus(i, ~P, π(~P)) =π(~P)|W Si (P̃i )|maxP̃i ∈L(A) |W π(~P) | , еслиизбирательiiимеет стимул0, иначе.I3 (CF , π, m, n) =∑~P∈L(A)Nманипулировать при ФПИπ,max (stimulus(i, ~P, π(~P))/(m!)n .i∈NИндекс I3 (CF , π, m, n) можно интерпретировать как агрегированный показатель стимула избирателей к манипулированию.CF сильно вычислимо изI2 (CF , π, m, n) = I3 (CF , π, m, n) = I1 (CF , Pro f ile, m, n).Далее индексы I2 and I3 рассматриваются только дляТеорема 2.5.1.
Если правилоФПИπ,топравила от-носительного большинства, как наиболее типичного и простого примераправила коллективного принятия решений. Результат следующей теоремыпротивопоставляется результату Теоремы 2.4.2 и дает представление обасимптотическом поведении индекса стимула к манипулированию,I3 ,пристремящемся к бесконечности числе избирателей.limn→∞ I3 (m, n,Winner, Plurality) = 0 при Leximin иlimn→∞ I3 (m, n, 1Winner, Plurality) = 0 при алфавитном правилеТеорема 2.5.2. а)Leximax; б)устранения несравнимости.Рассмотрим предложенные два индекса для правила относительногобольшинства в серии вычислительных экспериментов, сделанных в MATLAB.160.60.80.50.60.40.40.30.20.20.124681012141618020246а) ФПИ-Rank10.50.40.60.30.40.20.20.12468101214101214161820161820б) ФПИ-Winner0.8081618020246в) ФПИ-1Winner8101214г) ФПИ-WMG10200I2I1I3Рисунок 2.
Значения I1 , I2 и I3 для правила относительного большинства приалфавитном правиле устранения множественности выбораПримеры графиков, иллюстрирующих результаты вычислений, представлены на рисунке 2.ИндексыI2иI3почти всегда строго меньше, чемI1 .Кроме того, дляФПИ-Rank, ФПИ-Winner и ФПИ-1Winner разность I1 и двух других индексовувеличивается с ростомn.В большинстве случаев индекс стимула к манипулированию,I3 ,дляФПИ-Winner ниже, чем для ФПИ-Rank (а в случае алфавитного правила устранения несравнимости наименьшие значенияI3соответствуют ФПИ-1Winner). Это показывает, что уменьшение информативности не приводитк увеличению манипулируемости, если принимается во внимание величинастимула избирателей к манипулированию. Наиболее значительная разница виндексах I1 и I3 соответствует ФПИ-1Winner при алфавитном правиле устранения несравнимости – более, чем 0.75 дляn ≥ 10.Наконец, если правило коллективного выбора не вычислимо из ФПИπ,как в случае правила относительного большинства и ФПИ-WMG, то ин-декс успеха манипулирования и индекс стимула к манипулированию имеютдовольно низкие значения, и при увеличении числа избирателей могут рассматриваться как совсем незначительные.17Раздел 2.6 посвящен описанию комплекса программ, разработанногодля вычисления индексов манипулируемостиI1 , I2иI3 .Исходные коды эле-ментов программного комплекса приведены в Приложении В.Третья глава посвящена исследованию разности индексов манипулируемости в различных вероятностных моделях.В разделе 3.1 обсуждаются свойства анонимности и нейтральности,которые являются основными аксиомами в теории коллективного выбора.
Вмодели IANC профили предпочтений, отличающиеся перестановкой избирателей и (или) перестановкой имен альтернатив, считаются эквивалентными.Получающиеся в результате классы эквивалентности считаются в этой модели равновероятными.Представители классов эквивалентности в модели IANC могут рассматриваться как «типы» коллективных предпочтений, поэтому минимизируя индекс вероятности манипулирования в модели IANC, мы фактическиищем правило, минимизирующее количество «типов» предпочтений коллектива, допускающих манипулирование.В разделе 3.2 даны определения и обозначения, дано формальное описание вероятностных моделей IC, IAC, IANC и определение индекса манипулируемусти в различных вероятностных моделях.В разделе 3.3 введено понятие расстояния между верятностными моделями и показано, как может быть вычислено расстояние между моделямиIC и IANC.Определение 3.1.
Расстоянием между вероятностными моделямиM2дляnизбирателей иmM1иальтернатив называется величина∆M1 −M2 (m, n) = max (|Pr(E, M1 , m, n) − Pr(E, M2 , m, n)|).EВ подразделе 3.3.1 подробно рассмотрена алгебраическая структураклассов эквивалентности в модели IANC, доказаны теоремы о мощности максимальных и минимальных классов эквивалентности, дана оценка для количества максимальных классов.Подраздел 3.3.2 посвящен построению оценки расстояния между ICи IANC для малых значенийmиn.Показано, в каких случая разность ин-дексов близка к нулю, а в каких достаточно велика, чтобы быть причинойизменений в относительной манипулируемости правил коллективного выборапри переходе от IC к IANC.В подразделе 3.3.3 показано, что для функции расстояния между вероятностными моделями выполняется неравенство треугольника.18M1 , M2 , M3Лемма 3.2.
Для любых трех вероятностных моделейвы-полняется неравенство∆M1 −M2 (m, n) + ∆M2 −M3 (m, n) ≥ ∆M1 −M3 (m, n).Далее исследовано асимптотическое поведение максимальной разности индексов в модели IAC и IANC.Следствие∆IAC−IANC (m, n),3.2.Расстояниемеждустремится к нулю приn→∞моделямиилиIACиIANC,m → ∞.Сравнение моделей IAC и IANC позволяет также понять, что происходит с расстоянием между IC и IANC,∆IC−IANC (m, n), когда число избирателейстремится к бесконечности.
Применив неравенство треугольника, получим|∆IC−IAC − ∆IAC−IANC | < ∆IC−IANC < ∆IC−IAC + ∆IAC−IANC .(1)m и n показывают, чтоменее 0,02, если m > 10 илиВычисления полученной оценки для различныхрасстояниеn > 10,∆IAC−IANC (m, n)и менее 0,01, еслипринимает значенияm > 15илиn > 15.Подставляя верхнюю оценку внеравенство (1), получим∆IC−IAC (m, n) − 0, 02 < ∆IC−IANC (m, n) < ∆IC−IAC (m, n) + 0, 02.Таким образом, значения расстоянияближе к значениям∆IC−IAC (m, n).∆IC−IANC (m, n)(2)становятся всеПоследние могут быть легко вычисленыпри помощи метода Монте-Карло случайной генерации представителей Аклассов.
На рисунке 3 представлены результаты приближенного вычислениярасстояния∆IC−IAC (m, n)для числа альтернатив от 3 до 9 и числа избирате-лей от 10 до 120, которые, в силу неравенства (2) можно рассматривать и какприближенные значения расстояния∆IC−IANC (m, n).Обратим внимание на то, что в некоторых случаях максимальная разность индексов очень близка к единице, и это означает, что показатели степени манипулируемости в рассматриваемых моделях могут сильно отличаться.В разделе 3.4 описан эксперимент и приведены результаты вычисления индекса манипулируемости для четырех правил коллективного выборав IANС для двух лексикографических методов расширения предпочтений,Leximin и Leximax. Показано, как отличаются индексы манипулируемости вмоделях IC и IANC.Таким образом, данное теоретическое исследование отвечает на вопрос, какие различия в показателях манипулируемости могут существоватьв моделях IC, IAC и IANC и позволяет избежать сложных вычислений в19Рисунок 3.
Максимальная разность индексов манипулируемости в моделях IC и IANC.модели IANC в силу того, что в большинстве случаев значение индекса манипулируемости в модели IANC не будет отличаться от индекса в IC илиIAC.Рассматриваемая модель интересна тем, что любая «непредвзятая»процедура выбора обладает свойствами анонимности и нейтральности, следовательно, профили предпочтений, принадлежащие одному и тому же классу эквивалентности, будут одновременно либо манипулируемыми, либо нет.Соответственно, если мы можем сказать, что профиль-представитель классаподвержен манипулированию со стороны избирателей, тогда то же самое мыможем сказать и об остальных профилях класса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
