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

Избирательная система — это совокупность правовых норм, определяющих, каким образом итоги голосования избирателей трансформируются в результаты выборов. Проблема организации правильной избирательной системы обсуждается математиками с XVIII века, когда выборы только начинали становиться универсальным способом избрания кандидатов. Свой вклад в их решение внесли Жан Шарль де Борда [1], Ж.А. Кондорсе [2], К. Мэй [3], а американский математик Кеннет Дж. Эрроу [4] был удостоен Нобелевской премии по экономике. Существует множество различных правил голосования, таких, как голосование открытое и закрытое, голосование с правом вето, одно- и двухступенчатое голосование. В данной статье будет рассматриваться голосование по правилу большинства с решающим голосом первого игрока в случае равенства.

• II.    Формализация

Для формального исследования процедуры выборов используется математический аппарат теории игр (см. [5]).

Определение 1. Пусть N — фиксированное конечное множество — модель некоторого сообщества, членов которого будем обозначать индексом i = 1 , 2 , ..., n . Игрой в нормальной форме называется совокупность, содержащая множество N и для каждого i из N содержит:

• — множество стратегий X i , чьи элементы обозначаются через x i ,

• — функцию выигрыша u i , являющуюся отображением из X n = X 1 х ... х X n в $ . Элемент x = ( x i ) _{i G} N из множества X n называется исходом игры.

Игроки i независимо и одновременно выбирают любые стратегии x i Е X i . После того как каждый игрок выбрал свою стратегию, определяется исход x и выигрыши U i ( x ) игроков i = 1 , 2 , ..., n .

Определение 2. Стратегия x i игрока i доминирует стратегию y i в игре в нормальной форме Г = ( X i ,u i ,i Е N ), если

( Vx-i Е X-iUi(yi,x—i) < Ui(xix-i),

( Bx-i Е X-iUi(yix-i) < Ui(xix-i), где

^X - i = ® j e N \ i ^X j .

Стратегия x называется недоминируемой, если не существует стратегии y , которая доминирует x . Множество всех недоминируемых стратегий обозначается через D i (Г).

Определение 3. Стратегия x i игрока i виг-ре Г = ( X i , u i , i Е N ) называется доминирующей, если

V y i Е X i V x — i Е X - i U i ( x i ,x — i ) >  U i ( y i ,x - i ) .

Множество всех доминирующих стратегий i -го игрока обозначим через D i (Г).

Определение 4. Для игры в нормальной форме Г = ( X i , U i , i Е N ) последовательное исклю-

ТРУДЫ МФТИ. — 2010. — Том 2, № 1(5) чение доминируемых стратегий означает построение последовательностей

Xi = X0 D Xi1 D ... D Xi D Xi +1 D ... Vi G N,

где Xi +1 = Di(Xj; uj; j G N).

Игра называется разрешимой по доминированию, если существует такое целое t , что для всех i функция выигрыша u i не зависит от x i на X _N ^t , то есть

Vxi, yi G Xi, x-i G X-iUi(Xi,x-i) = Ui(yix-i).

Рассматривается игра трёх лиц N = { 1 , 2 , 3 } — выборы одного из кандидатов { a, b, с } . Игроки голосуют одновременно в закрытую, а победителем считается кандидат, определяемый по правилу большинства. Игроки представляют на выборах интересы различных групп, и в случае равенства голосов решающим считается голос первого игрока, представляющего интересы на выборах наибольшей по численности группы заинтересованных людей.

Таким образом, в данной игре три игрока N = { 1 , 2 , 3 } имеют множества стратегий X i = { a, b, с } при i G N . Предположим, что игроки проголосовали за кандидатов x 1 ,x 2 ,x 3 . В этом случае избирается кандидат, определяемый правилом:

п ( x 1 , x 2 ,

^x 3 ) = |

x2, x1 ,

если x 2 = x 3 , иначе .

Функции полезности игроков определяются как U i ( x 1 , x 2 , x 3 ) = и_г ( п ( x 1 , x 2 , x 3 ), где U i ( y ) — значение функции полезности от избрания кандидата y для i -го игрока.

Пусть значения функций полезности от избрания кандидатов заданы следующим циклическим образом:

U i ( a ) < U i ( b ) < U i ( с ) ,

U 2 ( b ) < U 2 ( с ) < U 2 ( a ) , U з ( с ) < U з ( a ) < U з ( b ) .

Если игроки не информированы о предпочтениях других игроков и каждый из них проголосует за наилучшего для себя кандидата, то по правилам голосования кандидат c будет объявлен победителем.

В условиях полной информированности ситуация будет другой. Первый игрок на первом этапе разрешения по доминированию имеет ровно одну доминирующую стратегию — голосовать за кандидата c. Действительно, если второй и третий игроки проголосуют за разных кандидатов, то голос первого игрока определит кандидата-победителя, а если второй и третий игроки проголосуют за одного кандидата, то первому игроку все равно, за кого именно голосовать. На первом шаге второй игрок может исключить доминируемую стратегию — голосовать за наихудшего для себя кандидата b, а третий игрок — за кандидата c. На втором этапе исключения по доминированию второй игрок, понимая, что первый игрок проголосует за кандидата c, имеет доминирующую стратегию — голосовать за a. Поскольку первый и второй игроки исключили на первом шаге стратегию b, то третий игрок имеет доминирующую стратегию — голосовать за кандидата a. Таким образом, в условиях полной информированности будет выбран кандидат a — наихудший для первого игрока. Этот результат получил название Парадокса Кондорсе [6]. Право первого игрока разрешать спорные ситуации оказывается его слабым пунктом, потому что оно даёт возможность другим игрокам сразу предвидеть его стратегический выбор.

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

Предположим, что функции полезности игроков заданы следующим образом:

U i ( a ) = 0; U i ( b ) = 25; U i ( с ) = 50;

U 2 ( b ) = 0; U 2 ( с ) = 8; U з ( a ) = 16;

U з ( с ) = 0; U з ( a ) = 17 , 5; U з ( b ) = 35 .

В игре, когда игроки голосуют не одновременно, а по очереди, объявляя свой выбор другим игрокам, наилучший гарантированный результат первого игрока существенно зависит от порядка ходов. В частности, если первым голосует и объявляет свой истинный выбор второй игрок, следующим объявляет первый игрок, а последним — третий игрок (далее для краткости будем обозначать порядок действий игроков набором их номеров вида 2-1 -3), первый игрок получает наилучший для себя результат — избрание кандидата с . В трёх случаях 2-3-1, 3-1-2 и 3-2-1 первый игрок не может получить гарантированный выигрыш, больший 0, а в двух оставшихся вариантах 1-2-3 и 1-3-2 может рассчитывать лишь на половину своего наибольшего выигрыша, то есть избрание кандидата b . Таким образом, узнав о проведении выборов по указанным правилам, первый игрок должен каким-либо способом (побочные платежи, право выбора порядка голосования на основе поддержки наибольшей группой) убедить проводить открытое голосование в порядке 2-1-3. Очевидно, что это может у него не получиться.

• III.    Постановка задачи

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

В этом случае игра в нормальной форме описывается следующим образом: G = < Zi; Vi; N >, i e N; N =  {1, 2, 3}. Стратегией игро ка является определение величины предложений другим игрокам на первом этапе, а также выбор кандидата для голосования на втором: Zi = Pi x Xi; Pi = (pjy piky) — вектор платежей i-го игрока j-му и k-му только с одной отличной от нуля компонентой; pj y > 0; pik y > 0; j = k = i; Xi = {a, b, c}.

Функция полезности игрока определяется как сумма входящих побочных платежей от других игроков и пользы от избрания кандидата-победителя за вычетом исходящих побочных платежей другим игрокам:

V i ( X i ,X j ,X k ) = p ja ( X i ) + p ka ( X i ) + p i,b ( X i ) +

+Pk,b (Xi ) + Pj,c (Xi ) + Pk,c (Xi ) + Ui (П (Xi ,Xj ,Xk )) -

-Pk,a (Xk ) — Pj,a (xj ) — Pik,b (Xk ) — Pij,b (xj ) — Pik,c (Xk ) —

-Pj,c (Xj ),

Другими словами, наилучший гарантированный результат 2-го этапа для игрока k есть его наибольший гарантированный выигрыш от предложения P k , то есть значение его функции полезности от точки сложного равновесия (минимальное из таких значений при неединственности сложного равновесия), если игра разрешима по доминированию, а иначе — его наибольший гарантированный выигрыш при условии использования всеми игроками стратегий из множества недоминируемых стратегий на последнем этапе разрешения по доминированию. Аналогично определяются наилучшие гарантированные результаты (НГР) 2-го этапа других игроков.

Наибольший гарантированный выигрыш k -го игрока есть наибольший по P k НГР 2-го этапа, то есть такое значение НГР 2-го этапа, что при других стратегиях предложения побочных платежей k -го игрока НГР 2-го этапа не превосходит этого значения:

Sk (Pi,Pj) =sup Wk(Pi,Pj ,Pk).

P k

Наибольший гарантированный выигрыш игрока j определяется как результат применения наилучшей гарантированной стратегии предложения побочных платежей с расчётом, что k -й игрок применит самую невыгодную для j -го игрока стратегию из оптимальных для себя:

S j ( P i ) =

sup min    Wj(Pi,Pj ,Pk),

Pj Pk e Argmax Wk если sup Wk достигается, sup lim      Wj (Pi ,Pj ,Pk),

Pj Pk — максимиз .Wk иначе.

Аналогично определяется наибольший гарантированный выигрыш игрока i .

• IV.    Задача

  где

  
  

  U i ( X 1 ,X 2 ,X 3 ) = U i ( П ( X 1 ,X 2 ,X 3 )) ,

  
  

  P ^j,y ^{( X} i ) = ।

  
  

  0 ,

  p i^j,y ,

  
  

  если     y = X i ,

  если     y = X i .

  
  

  Предположим, что при порядке ходов i — j — k игрок i сделал предложение P i , а игрок j — предложение P j . Наилучший гарантированный результат (НГР) 2-го этапа для игрока k при его предложении P k определим как

  
  

  W k ( P i ,P j ,P k ) =

  
  

  max

  
  

  II

  
  

  min V k ( P i ,P j ,P k ,d ) , d e D

  —^ , иначе

  
  

  D — непусто

  
  

  max min

  X k e D k ( X i ,X j ) e D i X D j

  
  

  V k ( P i ,P j ,P k ,X i ,X j ,X k

  
  

  ) .

  
  

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

  Получены значения наибольшего гарантированного выигрыша для всех игроков в каждом из шести случаев порядка предложения побочных платежей. Оказалось, что результат рассматриваемой модифицированной игры G (игра трёх лиц типа Г1 [8]) также зависит от порядка предложений. В вариантах 1-2-3, 1-3-2, 2-1-3 наибольший гарантированный выигрыш первого игрока равен 33, в варианте 2-3-1 равен 35, а в вариантах 3-1-2 и 3-2-1 равен 25. Ни в одном из случаев право первого игрока определять кандидата-победителя при равенстве голосов не даёт ему возможности получить максимальный результат — избрание кандидата c .

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

  
  

проектов b и c . Предположим также, что изначально проекту c отдавал предпочтение 51 участник, а проекту b - 50. От каждого проекта был выдвинут представитель, который должен представлять интересы поддерживающих этот проект граждан при проведении голосования за проект. Представитель, выражающий интересы наибольшего числа граждан, получает привилегию решающего голоса. В соответствующей игре, даже с учётом возможности обмениваться денежными платежами, побеждает проект c , и его представитель получает максимальный выигрыш. Чтобы избежать этого результата выборов, представитель группы поддержки проекта b помогает выдвинуть третий проект a на голосование. Пусть проект a интересен лишь одному участнику, поддерживающему проект c ,и 15 участникам, поддерживающим проект b . В таком случае в пяти вариантах порядка предложения побочных платежей представитель кандидата b гарантированно получает выигрыш, равный 2, и лишь в одном случае его наибольший гарантированный выигрыш равен 0.

Работа выполнена по программе государственной поддержки ведущих научных школ (коды проектов НШ-693.2008.1, НШ-2982.2008.1).