А.А. Иванов (ИПУ РАН, НИУ ВШЭ)

Эффективные вычислительные схемы

расчета манипулируемости

процедур агрегирования

Аннотация:

Рассматриваются алгоритмы оценки степени манипулируемости процедур агрегирования. Рассматривается 27 известных процедур агрегирования для случаев Impartial Culture и Impartial Anonymous Culture. Рассматривается 6 индексов манипулируемости, включая классический индекс Нитцана-Келли. Показывается, что за счёт оптимизации алгоритмов возможно вычислить индексы манипулируемости для случаев 3, 4 и 5 альтернатив при количестве участников голосования от 3 до 100. Оценивается алгоритмическая сложность отдельных процедур агрегирования и всех вычислений. Рассматривается архитектура разработанного программного обеспечения.