Диссертация (1137313), страница 19
Текст из файла (страница 19)
С возрастаниемчисла избирателей этот эффект сглаживается, так как профили с высокой од-134Рисунок 3.9. Индекс манипулируемости ( , , 3, ) при Leximax.Рисунок 3.10. Индекс манипулируемости ( , , 3, ) при Leximax.нородностью предпочтений составляют очень малую долю в общем количествепрофилей.Значения разности индексов принимают наибольшие значения для правилаотносительного большинства.
Манипулирование более характерно для профилей с ничьей (множественным выбором) или ситуацией близкой к ничье. Дляправила относительного большинства близкая к ничье ситуация не возникаетв профилях с высокой однородностью предпочтений, так как в этом случаепобедитель чаще всего единственен.135Рисунок 3.11. Разность индексов манипулируемости ( , , 3, ) и ( , , 3, ) при Leximax.Таким образом, при определении степени маниулируемости правила выборвероятностной модели имеет значение, так как результаты могут отличаться нетолько количественно, но и качественно.3.5Заключение по Главе 3В данной главе:∙ введено понятие расстояния между вероятностными моделями как максимальной возможной разности вероятностных показателей в моделях, описана математическая модель для IC, IAC и IANC;∙ рассмотрена алгебраическая структура классов эквивалентности в моделиIANC (АН-классов), найдены мощности максимальных и минимальных АНклассов, дана оценка для количества максимальных АН-классов;∙ дана интервальная оценка для расстояния между моделями IC и IANC длямалых значений количества альтернатив и избирателей;136∙ доказано, что функция расстояния между вероятностными моделями удовлетворяет неравенству треугольника;∙ доказано, что расстояние между моделями IAC и IANC стремится к нулю, если количество альтернатив или количество избирателей стремится кбесконечности;∙ вычислена оценка расстояния между IAC и IANC и между IC и IAC;∙ показано, что все три вероятностные модели сходятся в одной точке приувеличении количества альтернатив, а при увеличении количества избирателей модели IAC и IANC удаляются от модели IC;∙ вычислены индексы манипулируемости для четырех правил в модели IANCдля числа избирателей от 3 до 30;∙ показано, что при изменении вероятностной модели может измениться относительная манипулируемость правил.137ЗаключениеОсновной вопрос теории коллективного выбора – какими свойствами обладает та или иная процедура и в каких задачах ее применение приведет в наилучшему результату.
В данной работе сделан подробный обзор литературы, посвященной изучению свойства манипулируемости правил. Диссертация продолжает исследование данного вопроса, но рассмотривает принципиально новый подход – учитывается влияние неполноты информации, доступной избирателям.В модели используется простая и реалистичная предпосылка: избирателям известны результаты опроса, проводимого перед голосованием.Если некоторое свойство не выполняется для данного правила (как, например, неманипулируемость для многих правил), используется статистическийанализ: подсчитывается доля возможных ситуаций, в которых наблюдается нарушение свойства. В таких случаях важное значение имеет то, какая используется вероятностная модель. Другим направлением исследования диссертационной работы является анализ влияния вероятностной модели на результатыстатистического анализа свойств правил коллективного выбора. В работе данподробный анализ максимально возможной разности индексов для трех основных вероятностных моделей: IC, IAC и IANC.Основные результаты работы заключаются в следующем.1.
Подготовлен аналитический обзор исследований по оценке степени манипулируемости правил коллективного выбора, впервые на русском языке138предтавлены и обобщены результаты по теме вычислительной сложностиманипулирования.2. Впервые исследована степень манипулируемости правил коллективного выбора в условиях неполной информации, предложены три индекса, позволяющие проанализировать влияние неполноты информации на подверженность правил манипулированию со стороны избирателей.3. Сформулированы и доказаны теоремы о равенстве вероятности манипулирования в условиях полной и неполной информации, об асимптотическомповедении индекса вероятности манипулирования, о неманипулируемостиправила Коупленда, о равенстве индексов успеха манипулирования и стимула к манипулированию индексу вероятности манипулирования при полнойинформации, об асимптотическом поведении индекса стимула к манипулированию.4.
Разработан и реализован алгоритм вычисления предложенных индексов манипулируемости при различных типах публичной информации. Создан комплекс программ для проведения вычислительных экспериментов для шестинаиболее популярных правил коллективного выбора.5. Впервые решена задача оценки максимальной разности в вероятностныхмоделях, сделаны теоретические доказательства и численные эксперименты. Показано, при каких условиях один и тот же индекс, вычисленныйв разных вероятностных моделях, будет иметь практически одни и те жезначения, а в каких случаях абсолютная разность значений индекса приближается к 100%.6. Впервые получены оценки индекса манипулируемости для правил коллективного выбора в модели IANC.139Результаты исследования дают основу для дальнейшего развития математической модели манипулирования в условиях неполной информации.
В частности, представляет интерес модель, в которой предварительный опрос проводится не по всем избирателям, а по некоторому их подмножеству, и, такимобразом существует неопределенность относительно результата агрегированияистинных предпочтений.Кроме того, остается открытым вопрос о вычислительной сложности манипулирования при неполной информации, выраженной в виде результатов предварительного опроса. Ответ на него может дать новые результаты о защищенности правил от манипулирования.140Литература1.
Gibbard A. Manipulation of voting schemes: a general result / A. Gibbard //Econometrica: journal of the Econometric Society. – 1973. – Vol. 41. – No. 4. –P. 587-601.2. Satterthwaite, M.A. Strategy-proofness and Arrow’s conditions: Existence andcorrespondence theorems for voting procedures and social welfare functions /M.A. Satterthwaite // Journal of economic theory. – 1975. – Vol. 10. – No. 2. –P. 187-217.3. Алескеров Ф.Т., Курбанов Э.
О степени манипулируемости правил коллективного выбора //Автоматика и телемеханика. – 1998. – №. 10. – С. 134-146.4. Алескеров, Ф.Т. Оценка степени манипулируемости известных схем агрегирования в условиях множественного выбора / Ф.Т. Алескеров, Д.С. Карабекян, P.M. Санвер, В.И.
Якуба // Журнал новой экономической ассоциации. – 2009. – №. 1-2. – С. 37-61.5. Aleskerov, F. On the Degree of Manipulability of Multi-Valued Social ChoiceRules / F. Aleskerov, D. Karabekyan, R.M. Sanver, V. Yakuba // HomoOeconomicus. – 2011. – Vol. 28. – No. 1/2. – P. 205-216.6.
Pritchard, G. Exact results on manipulability of positional voting rules / G.Pritchard, M.C. Wilson //Social Choice and Welfare. – 2007. – Vol. 29. – No. 3.– P. 487-513.1417. Guilbaud, G.T. Les théories de l’intérêt général et le problème logique del’agrégation / G.T. Guilbaud // Revue économique.
– 2012. – Vol. 63. – No.4. – P. 659-720.8. Kuga, K. Voter antagonism and the paradox of voting / K. Kuga, H. Nagatani// Econometrica: Journal of the Econometric Society. – 1974. – Vol. 42. – No.6. – P. 1045-1067.9. Eğecioğlu, Ö. The Impartial, Anonymous, and Neutral Culture Model: AProbability Model for Sampling Public Preference Structures / Ö. Eğecioğlu,A.E. Giritligil // The Journal of Mathematical Sociology. – 2013. – Vol. 37. –No. 4. – P.
203-222.10. Conitzer, V. Dominating Manipulations in Voting with Partial Information / V.Conitzer, T. Walsh, L. Xia // Proceedings of the Twenty-Fifth AAAI Conferenceon Artificial Intelligenc. – 2011. – Vol. 11. – P. 638-643.11. Reijngoud, A. Voter response to iterated poll information / A. Reijngoud, U.Endriss // Proceedings of the 11th International Conference on AutonomousAgents and Multiagent Systems. – 2012.
– Vol. 2. – P. 635-644.12. Bartholdi, J.J. The computational difficulty of manipulating an election / J.J.Bartholdi, C. A. Tovey, M.A. Trick // Social Choice and Welfare. – 1989. – Vol.6. – No. 3. – P. 227-241.13. Плиний Младший. Письма Плиния Младшего / Книги I–X. Сер. Литературные памятники. – М.: Наука, 1983. – 407 с.14. Алескеров, Ф.Т. Выборы. Голосование. Партии / Ф.Т. Алескеров, П.
Ортешук. – М.: Академия, 1995. – 208 с.15. Maskin, E. Implementation theory / E. Maskin, T. Sjöström // Handbook ofsocial Choice and Welfare. – 2002. – Vol. 1. – P. 237-288.14216. Bartholdi, J.J. How hard is it to control an election? / J.J. Bartholdi, C.A.Tovey, M.A. Trick //Mathematical and Computer Modelling. – 1992. – Vol.
16.– No. 8-9. – P. 27-40.17. Faliszewski, P. A richer understanding of the complexity of election systems /P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, J. Rothe // Fundamentalproblems in computing: Essays in honor of Professor Daniel J. Rosenkrantz. —2009. – P.
375-406.18. Blin, J.M. Strategy-proofness and single-peakedness / J.M. Blin, M.A.Satterthwaite // Public Choice. – 1976. – Vol. 26. – No. 1. – С. 51-58.19. Barbera, S. Strategy-proof voting schemes with continuous preferences / S.Barbera, B. Peleg // Social choice and welfare. – 1990. – Vol. 7. – No. 1. –P.
31-38.20. Kelly,J.S.Strategy-proofnessandsocialchoicefunctionswithoutsinglevaluedness / J.S. Kelly //Econometrica: Journal of the EconometricSociety. – 1977. – Vol. 45. – No. 2. – P. 439-446.21. Gärdenfors, P. Manipulation of social choice functions / P. Gärdenfors // Journalof Economic Theory. – 1976. – Vol. 13. – No. 2. – P. 217-228.22. Barbera S. The manipulation of social choice mechanisms that do not leave “toomuch” to chance / S. Barbera // Econometrica. – 1977. – Vol.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
