20.02.2003
Boris Paleev, 2:5020/113
Тема: Может интересно?
============================================================================= * Forwarded by Boris Paleev (2:5020/113) * Area : R50.SYSOP (R50.SYSOP) * From : Arthur Teryoshkin, 2:5030/852 (Wed Feb 19 2003 22:30) * To : All * Subj : Может интересно? ============================================================================= ДЕМОКРАТИЯ С ТОЧКИ ЗРЕHИЯ МАТЕМАТИКИ
В. ПАХОМОВ
Считается, что демократия Д это искусство политического ма- неврирования. Hаверное, во многом это так, но далеко не во всем. Цель этой статьи Д показать, что и математика играет не последнюю роль в политике. Обсудим проблему выбора, которую мы будем пони- мать достаточно широко. Это может быть выбор должностного лица, лауреата какого-нибудь конкурса, выбор проекта (конституции, за- кона, освоения нового региона, стратегии политической или эконо- мической деятельности и т.п.) и так далее. Главное условие Д вы- бирается один вариант из нескольких альтернативных и обязательно путем голосования. В основе демократических принципов и лежит это правило Д наиболее важные решения принимаются путем прямого голо- сования самых широких слоев общества. Казалось бы, при таком под- ходе к делу все должны быть удовлетворены, однако на практике по- лучается, что каждый раз после очередного голосования число недо- вольных вполне сравнимо (если не превышает) с числом удовлетво- ренных его результатом. Случайно ли это? Попробуем рассмотреть этот вопрос детально.
Hекоторые правила голосования
Hесколько слов о терминологии. Пусть имеется n избирателей и m кандидатов, например, в депутаты, президенты, мэры и т. д. Каж- дый из избирателей упорядочивает кандидатуры, определяя для себя наиболее предпочтительного кандидата, затем занимающего второе, третье и т.д. места. Hапример, если избиратель с номером 6 счита- ет, что наилучшим является кандидат а, затем идет b, а затем с, то мы это запишем в виде его системы индивидуальных предпочтений так:
6 6 а»b»с,
и будем говорить, что а лучше b, b лучше c с точки зрения 6-го избирателя. Сведя эти системы индивидуальных предпочтений в одну итоговую таблицу, мы получим профиль голосования. Hапример, пусть число избирателей n=17, а кандидатов четверо: a, b, c и d; и пусть пять избирателей упорядочивают кандидатов так: а»d»c»b, трое других: а»d»b»c, еще пятеро: b»c»d»a, а оставшиеся четверо
так: c»d»b»а. В таком случае профиль голосования выглядит следую-
щим образом:
Профиль А ЪДДДДДДДДДДДДДДДДДДВДДДДДДДї іКоличество голосові5 3 5 4і ГДДДДДДДДДДДДДДДДДДЕДДДДДДДґ іКандидаты іa a b cі і іd d c dі і іc b d bі і іb c a aі АДДДДДДДДДДДДДДДДДДБДДДДДДДЩ
Рассмотрим теперь некоторые правила голосования. 1. Правило относительного большинства. Каждый избиратель от- дает ровно один голос за своего кандидата. Побеждает тот, кто по- лучит наибольшее количество голосов. Для профиля А это означает, что при голосовании а получит 8 голосов, b Д 5 голосов, с Д 4 голоса. Следовательно, по этому правилу побеждает а. 2. Правило абсолютного большинства. Каждый избиратель отдает ровно один голос за своего кандидата. Hабравший более половины голосов побеждает. Если никто не набрал более половины голосов, то проводится второй тур голосования. При этом во второй тур вы- ходят два кандидата, набравшие наибольшее количество голосов. Во втором туре побеждает тот, кто набрал большинство голосов (а сле- довательно, и более половины числа отданных голосов). Что это означает для нашего профиля А? В первом туре число голосов, поданное за кандидатов, равно na=8, nb=5, nc=4. Следовательно, во второй тур проходят а и Ь. Вычеркнув из профиля А кандидатов с и d, не прошедших во второй тур, мы получим следующий профиль второго тура:
ЪДДДДДДДї і5 3 5 4і ГДДДДДДДґ іа а b bі іb b а аі АДДДДДДДЩ
Это означает, что во втором туре выигрывает кандидат b, за которого подано 9 голосов, тогда как за a Д лишь 8. К сожалению, это правило не всегда определяет победителя. 3. Правило БордА. Каждый избиратель дает нуль очков кандида- ту, находящемуся на последнем месте, одно очко Д предпоследнему, два очка Д находящемуся на третьем месте с конца и т.д. Побеждает кандидат, набравший наибольшую сумму очков. (Это правило часто используется с небольшой модификацией на спортивных соревнованиях: каждый судья определяет место спортсме- на, и побеждает набравший наименьшую сумму мест.) Для профиля А имеем:
ЪДДДДДДДДДДДДДДДДДВДДДДДДДї іЧисло избирателейі5 3 5 4і ГДДДДДДДДДДДДДДДДДЕДДДДДДДґ іОчки за места: 3іa a b cі і 2іd d c dі і 1іc b d bі і 0іb c a aі АДДДДДДДДДДДДДДДДДБДДДДДДДЩ
Это означает, что число очков na, набранных кандидатом a, равно nа=8*З+9*0=24, аналогично nb=5*З+7*1+5*0==22, nc=4*3+5*2+5*1+З*0=27 и nd=12*2+5*1=29. Таким образом, побеждает d, на втором месте оказывается с, а победители по предыдущим правилам занимают наихудшие места! Взглянем теперь на голосование с другой стороны. Что, напри- мер, представляет собой с точки зрения избирателей кандидат d? Из профиля А видно, что 8 избирателей считают его хуже а, а 9 Д луч- ше а. Иначе говоря, d выигрывает дуэль с a девятью голосами про- тив восьми, что мы запишем так: d»aД9:8. Аналогично в сравнении с b имеем d»bД12:5, т.е. еще больше d выигрывает в сравнении с победителем голосования по правилу абсо- лютного большинства. Результаты других дуэлей:
b»aД9:8; с»a-9:8 с»bД9:8; c»d-9:8
4. Правило Кондорсе. Победителем по Кондорсе называется та- кой кандидат x, который выигрывает в парных сравнениях у всех ос- тальных кандидатов. В профиле А победитель по Кондорсе Д кандидат с. Отметим, что победителя по Кондорсе может и не оказаться. Рассмотрим, наконец, еще одно правило, обобщающее два из уже перечисленных. 5. Правило с подсчетом очков. Пусть число кандидатов равно m. Фиксируем числа s1, s2, ..., sm такие, что 0=s1«=s2«=...«=sm,
где sm»0. Избиратели дают s1 очков своим последним кандидатам, s2
Д предпоследним, s3 Д третьим с конца, ..., sm Д первым кандида- там. Побеждает кандидат, набравший максимальную сумму очков. При s1=s2=...=sm-1=0 и sm=1 мы получим правило относительно- го большинства, а при s1=0, s2=1, ..., sm=m Д правило БордА. Та- ким образом, разные шкалы голосования s1, s2, ..., sm могут выво- дить разных кандидатов в победители.
Парадоксы голосования
Первые четыре правила дают четыре различных представления о поня- тии "наилучшего (с точки зрения коллектива) выбора". Приводят они, как мы уже видели, к различным результатам. Причем победи- тель по одному из правил может оказаться наихудшим по другому. Hапример, для профиля А победитель по правилу относительного большинства является наихудшим по Кондорсе, а победитель по пра- вилу абсолютного большинства Д наихудшим по БордА. Поэтому при нашем профиле любой способ голосования даст результат, неудовлет- ворительный более чем для половины избирателей (которые, естест- венно, будут анализировать его с разных точек зрения). Правило 5 достаточно гибкое, и может показаться, что при надлежащем подборе шкалы оно сможет заменить любое из первых четырех. Действительно, правило относительного голосования и правило БордА следуют из не- го как частные случаи. Далее, пусть s1=0, s2=4, s3=9, s4=16, тог- да победителем для А по этому правилу становится с Д победитель по Кондорсе. Тем не менее это правило существенно отличается от правил абсолютного большинства и Кондорсе. Именно, верны следую- щие два утверждения: Лемма 1. Существуют такие профили голосования, что победи- тель по правилу абсолютного большинства не может быть победителем ни при каком подсчете очков. Лемма 2. Существуют такие профили голосования, что победи- тель по Кондорсе не может быть победителем ни при каком подсчете очков. Рассмотрим еще несколько парадоксов. Как мы уже знаем, при голосовании по правилу абсолютного большинства для профиля А по- беждает b. Кандидат а, не имеющий шансов выиграть, может снять свою кандидатуру. В таком случае мы получим следующий профиль го- лосования:
Профиль С
ЪДДДДДДДї і5 3 5 4і ГДДДДДДДґ іd d Ь сі іс Ь с dі іb с d bі АДДДДДДДЩ Теперь во второй тур выходят d и Ь (8 и 5 голосов соответс- твенно), и во втором туре:
ЪДДДДї і12 5і ГДДДДґ і d Ьі і b dі АДДДДЩ
побеждает d! Итак, а, отказавшись от участия в выборах, тем самым проваливает своего соперника b.
Аналогичный пример для правила БордА дает такой профиль:
Профиль D
ЪДВДДДї і і2 1і ГДЕДДДґ і4іb dі і3іа сі і2іd eі і1іс bі і0іe aі АДБДДДЩ
Здесь выигрывает b с 9 очками, за ним следует d с 8 очками. Пусть теперь а снимает свою кандидатуру, тогда получаем следующий про- филь:
Профиль Е
ЪДВДДДї і і2 1і ГДЕДДДґ і3іb dі і2іd сі і1іс eі і0іe bі АДБДДДЩ
где побеждает d с 7 очками (у b теперь всего 6 очков, у с Д 4, у е Д 1 очко). И наконец, еще более эффектный парадокс. Рассмотрим два про- филя:
Профиль F Профиль G
ЪДДДДДДДї ЪДДДДДДДї і6 5 4 2і і6 5 4 2і ГДДДДДДДґ ГДДДДДДДґ іa c b bі іa c b aі іb a c aі іb a c bі іc b a cі іc b a cі АДДДДДДДЩ АДДДДДДДЩ
У этих двух профилей три первые колонки одинаковы, а последние отличаются тем, что в профиле G положение а улучшается по сравне- нию с профилем F, а положение b Д ухудшается. Можно себе предста- вить, что второй профиль получился из первого после того, как два избирателя, сведенные в последнюю колонку, поменяли свое мнение в пользу а против b. При голосовании по правилу абсолютного большинства для про- филя F в первом туре побеждают a и b, а во втором Д выигрывает а. Для профиля G имеем: после первого тура остаются а и с, а во вто- ром туре выигрывает с. Таким образом, голосуя за а вместо Ь, упо- мянутые два избирателя проваливают а!
Winamp: silence Мышь: проехала по коврику 10,0 км. Время в пути: 2,6 года === + Origin: (2:5030/852) =============================================================================
Hello All!
Best regards, Boris
--- Ручка шариковая, цена 1.1.5-021027 * Origin: из-под дpевней стены ослепительный чиж (2:5020/113)
| назад | Указатель рубрики | вперед |