Курсовая работа: Модель экспертной оценки
1. Содержательная постановка задачи
Задание, которое относится передо мной в данной курсовой работе, – обеспечить процесс выборов, то есть конечное множественное число N избирателей должно избрать одного кандидата из конечного множественного числа А. Обязательным условием есть избрание единственного кандидата. Для простоты допустим, что индивидуальные мысли (или преимущества) не допускают случаи безразличия. Каждая такое преимущество есть произвольным линейным порядом на А (то есть полное транзитивное и асимметричное бинарное отношение). Это предположение не приводит к существенным потерям всеобщности.
Формально правило голосование решает задачу коллективного принятия решения, у которой несколько индивидуальных агентов (избирателей) должны совместно выбрать один из нескольких результатов (также званых кандидатами), относительно которых их мысли расходятся.
Правило голосования являет собой систематическое решение, которое во всей полноте опирается по индивидуальным мнениям. Обозначим через L(А) множественное число линейных порядков на А, тогда правило голосование является отображением L(А) N в А. То, что правило голосования может быть определено для любой мыслимой конфигурации преимуществ, выражает фундаментальный принцип свободы мыслей: каждый избиратель имеет право ранжировать кандидатов любым образом. Однако в некоторых моделях голосования, которые содержат экономические переменные или неопределенные результаты, можно допускать, что преимущества избирателей удовлетворяют некоторому общему условию. Это особенно удобно при стратегическом анализе голосования и при агрегации преимуществ.
Правило голосования выбирает кандидата на основе поставленных в известность порядковых преимуществ и только на основе этих преимуществ. В этом существенное отличие от моделей, в которых деньги и другие продукты позволяли осуществлять произвольно малые компенсации для агентов. Голосование не допускает уступку между двумя кандидатами иначе, чем за счет возможного избрания третьего кандидата.
Пусть дано как контрольный пример следующий профиль для 9 избирателей и 5-ти кандидатов:
| 1 | 4 | 1 | 3 |
a b c d e | c d b e a | e a d b c | e a b d c |
В каждом столбце кандидаты расположенные в порядке уменьшения их значимости для каждой группы избирателей. То есть, для первого столбца (группы избирателей, которая состоит из одного человека) можно определить преимущества следующим образом: группа избирателей, которая состоит из одного лица, считает кандидата а наилучшим. На втором месте они ставят кандидата b, на третьем месте c и так далее аналогично кандидаты ранжированы в каждой группе.
Задание: определить единственного победителя выборов.
Существуют много способов определения победителя. Они будут описаны и соответствующим образом сравнены в следующих разделах.
Отметим сейчас, что дана курсовая работа посвященная рассмотрению и воплощению в программу метода Копленда и сравнению полученного результата с результатом за методом Борда.
Определим правило Копленда.
Сравним кандидата а с любым другим кандидатом x. Начислим ему +1 , если для большинства а лучше за x, -1, если для большинства x лучше за а , и x , x ¹a , получаем оценку Копленда для а . Избираем кандидат, названный победителем за Коплендом, с наивысшей такой оценкой.
В данном правиле не указано, что делать в том случае, когда найдутся два или больше кандидаты с одинаковой оценкой Копленда. Допустимо, что изберется тот кандидат, имя и фамилия которого стоит ближайшее по списку. Это предположение нарушает правило нейтральности, но, как будет доказано в следующих разделах, каждое правило голосования Копленда является наиболее наглядным и легким для компьютерной реализации.
Правило Борда : каждый избиратель сообщает свои преимущества, ранжируя p кандидатов от наилучшего к наихудшему (безразличие запрещается). Кандидат не получает очки за последнее место, получает одно очко за предпоследнее место и так далее, получает p-1 очков за первое место. Побеждает кандидат с наибольшей суммой очков. Он называется победителем по Борду. Здесь так же не указывается, что делать при равенстве очков, то есть также может нарушаться условие нейтральности.
Охарактеризуем выше поставленную задачу.
Ее критерием качества является максимизация оценки Копленда (Борда).
Ограничениями выступают преимущества избирателей и их ранжирования кандидатов. Как будет указано дальше, фактически нужно налагать также ограничение и на количество избирателей и количество кандидатов. Однако это ограничение не является существенным, так как всегда при голосовании можно провести деление на округа.
За уровнем сложности это есть задача Р-типа. Время решения данной задачи составляет t0 =a0 +a1 x+… +an xn і зависит от количества групп избирателей и количества кандидатов.
Нахождения победителя по правилам Копленда и Борда являются самыми простыми за своей структурой, оптимальные по Парето, анонимные, нейтральные (если не указывать, что делать при равенстве очков). Кроме того, правило Борда также удовлетворяет аксиоме участия и пополнения (они будут рассмотрены в следующем разделе).
Оптимальность по Парето:
Если кандидат а для всех лучший от кандидата b, то b не может быть избран.
Анонимность:
Имена избирателей не имеют значения – если два избирателя поменяются голосами, то результат выборов не изменится.
Нейтральность:
Имена кандидатов не имеют значения. Если мы поменяем местами кандидатов а и b в преимуществе каждого избирателя, то результат голосования изменится соответственно (если раньше выбирался а, то теперь будет выбираться b и наоборот; если выбирался некоторый х, отличающийся от но и b, то он же и будет избран).
Монотонность:
Допустимо, что а выбирается (среди победителей) при данном профиле и профиль изменяется только так, что положение а улучшается, а относительное сравнение пары любых других кандидатов для любого избирателя остается неизменным. Тогда а как и раньше будет избран (опять среди победителей) для нового профиля.
2. Формальная постановка задачи
Приведем еще раз задачу данной курсовой работы: используя профиль преимуществ избирателей, определить единственного победителя из множественного числа заданных. Должна существовать возможность проверки корректности задания профиля. Ограничениями на задачу является отсутствие безразличия и ранжировки кандидатов в строгом порядке. Опишем методы голосования, которые могут использоваться для решения данной задачи и наведем ряд основных определений и теорем.