Манипулируемость процедур голосования

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

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

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

сования может зависеть от того, каким образом произведено это разбиение, а также от того, в какой последовательности  подмножества  предъявляются избирателям (манипулирование с помощью изменения агенды);

— путем введения  в  исходное  множество  вариантов дополнительных вариантов,  которые сами,  быть  может, в коллективный выбор не попадают, однако присутствие их в избирательном бюллетене «оттягивает» на себя часть

голосов избирателей, изменяя тем самым коллективный выбор;

— путем объединения избирателей в группы и последующих действий с вариантами,  выбранными группами избирателей.

Вместе с тем избиратели также могут влиять па процесс выработки коллективного решения различными способами:

—  путем искажения своего истинного индивидуального упорядочения

(для процедур типа УВ) или своего индивидуального выбора (для процедур типа

ВВ)  с целью получения  более  приемлемого  для данного  избирателя коллективного решения;

—  с  помощью расширения состава  избирателей  (избиратель может

привлекать  к  голосованию  дополнительных  избирателей,  индивидуальные предпочтения которых совпадают с его предпочтениями);

— в некоторых случаях возникает такая парадоксальная ситуация, когда

избирателю выгоднее не принимать участия в голосовании,  так  как  отказ  от голосования ведет к избранию более предпочтительного для него варианта. Такой способ называется манипулированием с помощью неявки.

Проблемы манипулируемости процедур голосования рассматриваются в этой  главе,  посвященной  свойствам  процедур  голосования,  так  как

подверженность процедуры тому или иному виду манипулирования является важной характеристикой процедуры голосования.

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

6.5.1. Манипулирование, осуществляемое организатором голосования. В любой процедуре голосования (как типа УВ, так и типа ВВ) на «вход» процедуры поступает предъявление X, а в результате действия процедуры на

«выходе» вырабатывается коллективный выбор Y*. При поступлении на «вход» процедуры различных предъявлений X ⊆  А на «выходе» вырабатываются соответствующие  данным  X  коллективные  выборы  Y*  ⊆  X.  Так  возникает

коллективная  функция  выбора  Y*  =  С*(Х).  Далее  будет  показано,  что

возможность манипулирования выбором со стороны организатора голосования и, наоборот, защищенность процедуры голосования от такого манипулирования,

целиком определяются свойствами этой функции выбора.

Ниже будут подробно рассмотрены два случая манипулирования.

1.  Пусть  при  поступлении  на  «вход»  процедуры  исходного предъявления  X  на «выходе»  процедуры  вырабатывается коллективный

выбор Y*, который не устраивает организатора голосования. Тогда организатор голосования  может  разбить  предъявление  X  на  подмножества  и,  изменяя

последовательность  предъявления этих подмножеств вариантов избирателям, организатор может добиться выработки более желательного для себя коллективного выбора.

2. Организатор голосования может воздействовать на коллективный выбор

путем добавления в исходное предъявление X новых вариантов.

Случай 1. В этом случае исходное предъявление X разбивается организатором  голосования  на  подмножества  X1  Х2,  …,  Xк.  Каждое подмножество предъявляется избирателям порознь, и из каждого подмножества X1, … …, Xк на основании того же агрегирующего правила осуществляется коллективный  выбор Y*1, .., Y*к.  Вы151

бранные так из всех подмножеств варианты объединяются и вновь предъявляются избирателям для выбора. Варианты, выбранные на этом втором этапе, объявляются окончательным коллективным выбором Y*.

Пусть процедура голосования реализует коллективную функцию выбора

С*(Х). При разбиении X на подмножества X1, . . ., Xк возникает функция выбора

которая может отличаться  от  функции  выбора С*(Х). Здесь возможны две ситуации.

1.  Существует такое число к и такое разбиение Х, …. .., Xh, что возникающая коллективная функция выбора С*’,отличается от С*.

2.  При любом к и любом разбиении функции коллективного выбора

С*’ и С* совпадают:

  (6.1)

Условие (6.1) и означает как раз, что манипулирований описанным способом невозможно. Условие это введено американским ученым Чарльзом Плоттом и

названо  свойством  независимости  от  пути,  т.  е.  от  способа  разбиения предъявления X на подмножества.

Справедливо следующее утверждение. Для того чтобы функция выбора С*(Х) удовлетворяла условию (6.1), необходимо и достаточно, чтобы она удовлетворяла  одновременно  как  свойству  наследования  Н,  так  и  свойству

отбрасывания О.

Таким образом, основные характеристические свойства Н и О совместно гарантируют  защищенность  процедур  голосования  от  манипулирования

указанным способом. Иначе говоря, защищены от манипулирования этим способом все процедуры голосования, которые реализуют коллективные выборы, принадлежащие в пространстве функций выбора пересечению областей Н и О, и только такие функции.

Случай 2. Рассмотрим теперь манипулирование голосованием путем добавления в предъявление X дополнительных вариантов. Присутствие этих дополнительных вариантов может повлиять на коллективный выбор. Обозначим

множество добавленных вариантов через Z. Добавленные варианты могут попадать в выбор из расширенного предъявления Х’(Х’ = X U Z), но при оценке манипулируемости на них внимания не обращают, а интересуются лишь том, изменится ли и как изменится состав вариантов из X, попавших в коллективный выбор из X, по сравнению с составом вариантов, коллективно выбираемых из X.

Процедура голосования не манипулируема путем добавления ложных вариантов Z, если выполнено условие:

если X ⊂ X’, то С*(Х) = Х ∩С*(Х’).  (6.2)

Наряду с этим условием запишем два вспомогательных условия, которые отличаются от (6.2) тем, что последнее  равенство  заменяется  на  нестрогие включения:

если X ⊂ X’, то С*(Х) ⊇Х ∩С*(Х’). (6.2’)

если X ⊂ X’, то С*(Х) ⊆ Х ∩С*(Х’).  (6.2’’)

Легко проверить, что условие (6.2") совпадает со свойством монотонности

М функций выбора, учитывая, что С*(Х) ⊆  X, а условие (6.2′) совпадает со

свойством наследования Н. Таким образом область {(6.2)}, выделяемая условием

(6.2)  в пространстве  функций выбора

{(6.2)} = ((6.2′)} ∩ {(6.2")} = М ∩ Н = S,

так как область М ∩  Н совпадает с областью сумматорных функций выбора S. Напомним, что функции выбора из области S являются «тривиальными» в том смысле, что  все  варианты из  А  как  бы  исходно разделены на  «хорошие» и

«плохие», и выбор сводится к выделению «хороших» вариантов из предъявления

X  ⊆  А.  Таким  образом,  от  манипулирования  указанным  выше  способом

защищены  только  процедуры  голосования,  генерирующие  функции  выбора,

удовлетворяющие свойству S.

Изменим теперь трактовку понятия манипулируемости процедуры голосования при добавлении в предъявление дополнительных вариантов. В этом

случае  процедура  считается  манипулируемой,  если  сами  добавляемые  к  X

варианты Z в выбор из расширенного множества X U Z не попадают, однако за счет добавления «ложных» вариантов Z к X состав вариантов, попадающих в

выбор из X’ = X U Z изменился по сравнению с выбором из X. Процедура неманипулируема, если такого изменения не происходит, т. е.

если X ⊆ X’ и C*(X’) ∩ Z = ∅, то С*(Х) = С*(Х’).  (6.3)

Непосредственно видно, что условие (3) в точности совпадает со свойством отбрасывания О.

Таким образом, все функции выбора удовлетворяющие свойству О, и только такие функции, защищены от рассматриваемого здесь способа манипулирования.

Обратим внимание на тот факт, что характеристические свойства функций выбора М, Н, С, О, S ранее вводились для того, чтобы описать логику индивидуального я коллективного выбора, а условие замкнутости обеспечивало перенесение  этих  требований  с  логики  индивидуального  выбора  па

коллективный выбор. Установленные выше факты показывают, что характеристические свойства важны и с иной точки зрения: в этих терминах может быть сформулировано требование защищенности процедуры голосования от

манипулирования со стороны организатора процедуры.

Дополним теперь приведенные выше общие соображения анализом одной распространенной процедуры  голосования:  он  позволяет  установить  условия

защищенности от манипулирования в иных терминах.

Рассмотрим процедуру голосования типа УВ, которая называется методом парных  мажоритарных  сравнений.  Предполагается,  что  каждый  из  N

избирателей (для простоты предполагается, что N—нечетно) в качестве индивидуального упорядочения имеет строгое упорядочение Pi вариантов из множества X. Рассмотрим процедуру, при которой варианты из множества X предъявляются избирателям попарно в определенном порядке. Победителем в каждой паре считается тот вариант, который признало лучшим (по сравнению с другим вариантом из этой пары) согласно своим предпочтениям большинство

избирателей. Победитель этой пары сравнивается со следующим вариантом и т. д. до тех пор, пока все варианты из множества X не будут перебраны. Процесс останавливается, когда каждый вариант из X хотя бы один раз (согласно установленному порядку) участвовал в парном сравнении. Согласно процедуре мажоритарных парных сравнений в качестве коллективного выбора У* объявляется победитель в последнем попарном сравнении.

Покажем, что в случае использования такой процедуры голосования существенным  является  порядок,  в  котором  варианты  из  множества  X

‘предъявляются для  попарного сравнения. Упорядоченный список  вариантов,

указывающий, в какой последовательности они предъявляются для организации описанных выше парных сравнений, называется  агендой  (от  английского  слова  agenda — повестка дня).

Рассмотрим в общем виде условие манипулируемости (со стороны организатора голосования) процедуры парных мажоритарных сравнений. Для

того чтобы разъяснить причину возможности манипулирования с помощью агенды,  рассмотрим  вновь  вспомогательный  мажоритарный  граф  М,  где

варианты  служат  вершинами  графа,  а  направленная  дуга  от  вершины  х  к вершине  у  проводится  в  том  случае,  если  больше  половины  избирателей считают, что х лучше у по своим индивидуальным упорядочениям. В случае, когда число избирателей N нечетно, такой граф М всегда асимметричен и полон.

Напомним, что вершиной-доминантой мажоритарного графа (пли победителем по Кондорсе) называется такая вершина, к которой не подходят дуги от других вершин графа или, что то же самое в силу асимметричности и

полноты графа,— от которой идут дуги ко всем другим вершинам графа М. Очевидно, вершина-доминанта, если она существует, является единственным коллективно  выбранным  вариантом  в  рассматриваемой  процедуре  парных

мажоритарных  сравнений.  Далее,  назовем  цикл  в  мажоритарном  графе доминирующим циклом, если к вершинам этого цикла не подходят дуги от вершин, не входящих в этот цикл.

В силу асимметричности и полноты мажоритарного графа в рассматриваемом случае возможен только какой-либо один из следующих двух случаев.

И1

И2

И3

x

z

y

y

x

z

z

y

x

Рис. 6.12

1. В мажоритарном графе М имеется доминирующий цикл. В этом случае манипулирование с помощью агенды возможно. Покажем это па примере.

Пример  6.1.  Пусть  имеется  три  избирателя,  профиль  предпочтений которых относительно вариантов из множества X = {x, у, z} представлен на рис.

6.12. Рассмотрим такую агенду: х, у, z, т. е. на первом этапе х сравнивается с y, а

затем победитель этого парного сравнения сравнивается с z. Как видно из профиля предпочтений избирателей, х предпочтительнее у для избирателей И1 и И2, т. е. х является победителем этого парного сравнения. Далее при сравнении x с  z оказывается, что z предпочтительнее, чем х для избирателей И2  и И3, т. е. вариант z является коллективным выбором при данной агенде, т. е. Y* = {z}.

Рассмотрим теперь другую агенду: х, z, у. Тогда при парном сравнении х и

z побеждает z, а при парном сравнении z и у выбирается у, т. е. Y* = {‘у}.

Наконец, рассмотрим агенду у, z, х. При сравнении у и z побеждает у, а при сравнении у и х побеждает х, т. о. Y* = {‘х}.

Итак,  рассмотрев  три  различные  агенды  (т.  е.  три  различных  порядка

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

2. В мажоритарном графе М имеется вершина-доминанта (победитель по

Кондорсе). При этом манипулирование с помощью агенды невозможно, так как при любой агенде выбирается этот вариант. Однако в этом случае организатор

голосования  может  воспользоваться  иным  способом  манипулирования.

Например, он может добавить в предъявляемое множество X дополнительный

(«ложный»)  вариант  такой,  что  на  расширенном  множестве  вариантой,

включающих этот ложный вариант, победителя

И1

И2

И3

И4

И5

x

z

y

z

z

z

z

z

x

x

y

x

x

y

y

а)  z  б)  y

Рис. 6.13

по Кондорсе уже не будет, образуется цикл и манипулирование становится возможным. Поясним это на примере.

Пример  6.2.  Пусть  имеется  пять  избирателей,  индивидуальные упорядочения которых относительно вариантов из  множества X  =  {‘х,  у,  z}

представлены на рис. 6.13, а. В этом случае при любой агенде вариант z является победителем по процедуре парных мажоритарных сравнений, что следует из рассмотрения мажоритарного графа, представленного на рис. 6.13, б. Следовательно, манипулирование с помощью агенды невозможно.

В этом случае организатор голосования для того, чтобы обеспечить возможность манипулирования с помощью агенды, может добавить в предъявление  X  =  {‘х,  у,  z},  дополнительный  вариант  v  такой,  что  на

мажоритарном графе  возникает  доминирующий  цикл.  Возникновение

а)  б)

Рис. 6.14

такого цикла дает организатору голосования возможность, манипулируя с помощью агенды, сделать коллективно выбранным любой вариант, входящий в этот  доминирующий  цикл.  Введение  такого  дополнительного  варианта  v показано на рис. 6.14, а. Заметим, что в этом случае введение дополнительного варианта не изменило индивидуальные предпочтения избирателей относительно вариантов x, у и z. Мажоритарный граф имеет теперь вид,

изображенный на рис. 6.14, б. В доминирующий цикл входят все варианты х, у, z

и v.

Добавление дополнительного («ложного») варианта создает возможность манипулирования не только в случае процедуры парных мажоритарных сравнений; манипулирование осуществляется и в процедурах, вообще не связанных с агендой.

Продемонстрируем этот способ манипулирования.

Пример 6.3 (процедура Борда). Пусть для определения коллективного выбора профиль индивидуальных упорядочений избирателей изображен на рис.

6.15, а. Согласно этой  процедуре  в  коллективный

157

выбор попадают варианты х и у. Однако если в исходное множество вариантов добавить такой вариант v, что профиль примет вид, изображенный на рис. 6.15, б, то У* = {‘у}. Таким образом, «ложный» вариант v, добавленный в исходное множество, сам в коллективный выбор не лопал, но изменил его.

6.5.2. Манипулирование со стороны  избирателя. Выше в разделе 6.5.1

рассматривалась защищенность процедур голосования от манипулирования со стороны организатора голосования. В этом разделе мы кратко рассмотрим некоторые вопросы, связанные с манипулированием со стороны избирателя.

В некоторых процедурах голосования может оказаться, что избирателю

выгоднее, получив избирательный бюллетень, сообщить не свое истинное решение о перечисленных в бюллетене вариантах, а некоторое иное «ложное» решение, так что в результате коллективное решение оказывается для него лучшим. Так, например, в процедурах типа УВ избиратель может сообщить вместо своего истинного некоторое ложное упорядочение с тем, чтобы в результате оказался коллективно выбранным вариант, лучший по его истинному упорядочению.

Важнейшим  результатом  в  области  манипулирования  голосованием  со стороны избирателя является теорема, авторами которой являются А. Гиббарт и

М. Саттервайт. В работах этих авторов [46, 80] рассматриваются процедуры типа УВ при предположении, что от избирателей поступают строгие упорядочения (нет равнозначностей вариантов), а коллективно выбирается в точности один

вариант. Делается основное предположение, что избиратели никак не стеснены, т. е. что любое упорядочение вариантов может быть представлено в качестве индивидуального упорядочения. Теорема Гиббарта — Саттервайта утверждает, что в этой ситуации любая процедура голосования, кроме «диктаторской», не

защищена от манипулирования со стороны избирателя. (Диктаторская процедура

— это процедура, при которой существует такой избиратель, что при любом предъявлении X A коллективно выбирается вариант, лучший в индивидуальном

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

плюралитарная, процедура Борда и др.

Сложнее обстоит дело в том случае, когда избиратель имеет возможность предоставить слабые упорядочения, т. е. допускаются равнозначности, или если коллективный выбор может состоять более, чем из одного варианта. Основная трудность в таких случаях состоит в том, каким образом может быть формализовано понятие «лучшие для данного избирателя». Результаты [70, 71], полученные в этом направлении, исходят из предположения, что помимо упорядочения вариантов у каждого избирателя существует упорядочение, заданное  на  всех  подмножествах  вариантов  из  предъявления.  Такое упорядочение используется для того, чтобы доопределить понятие «лучшее для избирателя множество вариантов». Здесь также получены результаты, показывающие, что свойством манипу-лируемости обладает большинство процедур голосования.

Задача существенно усложняется в том случае, когда вводятся какие-либо ограничения на характер предпочтений избирателей. В частности, процедуры типа ВВ могут быть рассмотрены как процедуры типа УВ с таким ограничением, что каждый, избиратель осуществляет свой выбор из предъявления X, т. е. фактически вырабатывает нестрогое упорядочение вариантов, состоящее из двух слоев: выбранные и невыбранные варианты. Для процедур тина ВВ удалось установить лишь достаточное условие неманипулируемости со стороны избирателей — оно состоит в том, что процедура голосования должна удовлетворять  характеристическому  условию  монотонности.

В последние годы интенсивно развивается подход к решению задачи о неманипулируемости процедур голосования с использованием аппарата теории игр. В терминах этой теории условие защищенности от манипулирования со стороны избирателей связывается с существованием некоторых равновесий в таких играх (например, равновесий Нэша). Вопросы применения этого аппарата выходят за рамки данной книги.

В этом разделе мы приведем лишь некоторые примеры стратегического поведения избирателей.

Пример 6.4. Пусть имеет место та же процедура парных мажоритарных сравнений и тот же профиль индивидуальных упорядочений избирателей, что и в

примере 6.1 (рис. 6.12). Единственным отличием является то, что агенда зафиксирована: х, у, z, и не может быть изменена. Агенду х, у, z удобно изобразить в виде дерева (рис. 6.16). На первом этапе (верхний уровень) на основе предпочтений избирателей происходит выбор между

х и у, а на втором этапе (нижний уровень) выбор между z и одним из двух вариантов: х или у — в зависимости от того, какой вариант выбран из пары (х, у).

Рис. 6.10

Предположим теперь, что каждому избирателю известны предпочтения других избирателей. Рассмотрим поведение избирателя в этих условиях. Если избиратели голосуют в соответствии со своими предпочтениями, то при агенде (х, у, z) будет выбран вариант z, т. е. Y* = {z}. Вариант z является наименее предпочтительным для избирателя И1. Поэтому,  зная  индивидуальные предпочтения других избирателей, избиратель И1 может изменить свое упорядочение па (запишем его в строку): И1  (у, х, z), что приведет к тому, что коллективный выбор изменится: Y* = {у}, а вариант у является уже вторым (а не третьим, как z) в истинном упорядочении избирателя И1. Таким образом, давая неверную информацию о своих предпочтениях (т. е. голосуя стратегически), избиратель может добиться более удовлетворительного для себя коллективного решения.

Пример  6.5.  Одним  из  неожиданных  способов  манипулирования  со стороны избирателя является изменение избирателем коллективного выбора в благоприятную для себя сторону путем отказа от участия в процедуре голосования. Покажем это на примере. Пусть зафиксирована агенда, и пусть голосование осуществляется путем попарных мажоритарных сравнений, а победителем процедуры объявляется победитель последней пары. Агенда изображена па рис. 6.17, а, а профиль предпочтений избирателей — на рис. 6.17, б. В случае равнозначности двух вариантов преимущество имеет вариант, стоящий раньше в агенде (лексикографический способ разбиения равнозначностей). В данном примере при предъявлении пары {х, у} побеждает вариант у. Во втором туре при предъявлении {у, z} побеждает у, Y* ={у}.

Пусть теперь избиратель И1 не явился на голосование. Тогда профиль индивидуальных упорядочений избирателей примет вид, изображенный на рис.

6.18.  При  использования той  же  агенды  (рис.  6.17,  а)  теперь  в  паре  {х,  у}

выбирается уже вариант х (в силу указанного выше способа разбиения равнозначности), а из пары {х, z} вы160

(бирается вариант z, т. е. Y* = {z}. Таким образом, в случае, когда избиратель И1

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

И1

И2

И3

И4

И5

И6

И7

z

z

x

x

z

y

y

y

y

y

y

x

z

y

x

x

z

z

y

x

x

а)  б)

Рис. 6.17

коллективный выбор состоял из варианта у (второго в его индивидуальном упоорядочении), а когда он не участвовал в голосовании, в коллективный выбор попал наиболее предпочтительный для него вариант z. Итак, отказ избирателя от участия в голосовании может привести к выбору наиболее предпочтительного для него варианта.

И2

И3

И4

И5

И6

И7

z

x

x

z

y

y

y

y

y

x

z

z

x

z

z

y

x

x

Рис. 6.18

Пример  6.6.  Типичным  примером  манипулирования  со  стороны избирателя  является  так  называемая  «покупка  голосов».  В  этом  случае

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

Действительно, на практике такой способ манипулирования нередко приводит к желаемому результату. Однако возможны ситуации, когда такая «покупка голосов» приводит к обратному эффекту.

В качестве примера рассмотрим профиль предпочтений 6 избирателей, приведенный на рис. 6.18. Как было показано выше в примере 5, в коллективный выбор при указанной на рис. 6.17, а агенде попадает вариант z.

Пусть избиратель И2  привлек к участию в голосовании еще одного избирателя, имеющего такие же предпочтения относительно вариантов х, у, z, что и И2 — избирателя И1 (рис. 6.17, б). Но тогда в коллективный выбор вместо наиболее предпочтительного для И2 варианта z после присоединения «близнеца» (избирателя И1) коллективно оказывается выбранным вариант у.

Как видно из примеров 6.5 и 6.6, манипулирование с помощью «неявки» и

с помощью «покупки голосов» в некотором смысле являются двойственными.

Материал взят из книги Голосование в малых группах: процедуры и методы сравнительного анализа (Вольский В.  И.,  Лезина  З. М.)