E-mail:Loshkarevs@mail.ru
Исследование и реализация алгоритмов голосования для формализации знаний в экспертных системах


Системы голосования де Кондорсе и метод Борда

Системами голосования первым заинтересовался французский ученый маркиз де Кондорсе (1743-1794). Он сформулировал принцип или критерий, позволяющий определить победителя в демократических выборах ([3]). Принцип де Кондорсе состоит в следующем: кандидат, который побеждает при сравнении один на один с любым из других кандидатов, является победителем на выборах.

Согласно де Кондорсе, справедливое определение победителя возможно путем попарного сравнения кандидатов (вариантов решения проблемы) по числу голосов, поданных за них. Принцип де Кондорсе предлагался как рациональный и демократический. Однако вскоре маркиз де Кондорсе столкнулся с парадоксом, получившим впоследствии его имя.

Рассмотрим пример: пусть нам даны три варианта решения проблемы: А, В и С, голоса экспертов, в количестве 60 чел, распределились, как в табл. 1

Таблица 1: распределение голосов (парадокс Кондорсе)
Число голосующих Предпочтения
23 А>В>С
17 В>С>А
2 В>А>С
10 С>А>В
8 С>В>А

Сравним предпочтения по отношению к парам вариантов. Берем А и С: тогда А предпочитают 23+2=25; С по сравнению с А предпочитают: 17+10+8=35. Следовательно, С предпочтительнее А (С -> А ) по воле большинства. Сравнивая попарно аналогичным образом А и В, В и С, получаем: В -> С (42 против 18), С -> А (35 против 25) и А-> В (33 против 27). Следовательно, мы пришли к противоречию, к нетранзитивному отношению А -> В -> С -> А . Столкнувшись с этим парадоксом, Кондорсе выбрал "наименьшее зло", а именно то мнение, которое поддерживается большинством голосов (избранным следует считать А).

Отметим еще одну процедуру голосования (]3[) из множеств предложенных: метод Борда. Согласно этому методу, результаты голосования выражаются в виде числа баллов, набранных каждым из вариантов решения. Пусть число вариантов равно n. Тогда за первое место присуждается n баллов, за второе - n-1, за последнее - один балл.

Таблица 2
Число голосующих Предпочтения
23 А>С>B
19 В>С>А
2 С>A>B
16 С>B>A

Применим метод Борда к приведенной табл. 2. Подсчитаем число баллов для каждого варианта:

А: 23*3+19*1+16*1+2*2=108;

В: 23*1+19*3+16*2+2*1=114;

С: 23*2+19*2+16*2+2*3=138.

В соответствии с методом Борда вариант С является лучшим.

Таблица 3: распределение голосов (метод Борда)
Число голосующих Предпочтения
31 А>С>B
12 В>С>А
17 С>B>A

Однако с методом Борда, как и с принципом Кондорсе, возникают проблемы. Предположим, что результаты голосования в выборном органе представлены в приведенной ниже табл. 3. Подсчитав баллы в соответствии с методом Борда, получим: А = 124,В = 103, С = 137. В соответствии с методом Борда лучшим следует объявить С. Однако в данном случае явным победителем является вариант А, набравший абсолютное большинство голоса: 31 из 60.

Приведенные примеры позволяют понять, что парадоксы при голосовании не возникают лишь в случае, когда победитель определяется по принципу абсолютного большинства голосов. Однако такой случай нетипичен для большинства выборов в демократических странах. Обычно число вариантов решения больше, чем два, и редки случаи, когда кто-то из них сразу же получает поддержку абсолютного большинства избирателей.

Интересно, что парадоксы голосования сохраняются и при введении двух туров и условий, что во второй тур выходят два варианта, набравшие большинство голосов. Обратимся к табл. 1, составленной Кондорсе. В соответствии с предпочтениями, во второй тур выходят А (23 голоса) и В (19 голосов), после чего побеждает А. Однако при небольшом усилении первоначальной позиции А: предпочтения двух экспертов (3-я строка) выглядят как А -> В -> С , во второй тур выходят А (25 голосов) и С (20 голосов), после чего побеждает С. Ясно, что такой результат голосования противоречит здравому смыслу.

На главную...





Литература

  1. "Современные проблемы науки" (www.ulstu.ru) 12/11/2003

  2. Орлов А.И. Организационные методы управления наукой и статистика объектов нечисловой природы. - Тезисы докладов Всесоюзного симпозиума "Медицинское науковедение и автоматизация информационных процессов". - М., 1984

  3. О.И. Ларичев. Теория и методы принятия решений. М., "Логос", 2000 г.

  4. Д.Б.Коптобенко. Альтернативы для будущего пенсионера-журнал "Главная книга"2003 г.

  5. В. Липский Комбинаторика для программистов. Издательство "Мир", 1988 г.

  6. "Структура психологического знания" (http://expert.psychology.ru/) 15/12/2003

  7. Введение в экспертные системы, 3-е издание (http://www.williamspublishing.com/Books/sci_ExpertSystems.html) 02/01/2004

  8. "Структура экспертных систем" (http://www.referat.su/refs_new/18977/ref_part_0.shtml) 02/01/2004


СамГАСА,Самара 2004