Теоретико-игровой анализ процедуры вето-голосования с лидером

• Автор: Машечкин, Алексей Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 121 с. : ил.

ВВЕДЕНИЕ

Глава 1. УСЛОВИЯ ПОБЕДЫ РЕШЕНИЯ ЛИДЕРА

§ 1. Формальная постановка задачи

§ 2. Случай 4-х голосующих

§ 3. Условия победности игры Гп

Глава 2. ПОСТРОЕНИЕ ПОБЕДНОГО ПОРЯДКА ХОДОВ

§ 4. Наименее расположенные к варианту лидера партнеры

§ 5. У одного подчиненного место варианта лидера выше 3-го с конца

§ 6. Вариант 1 выше (п-2)-го места у нескольких, но не всех, игроков.

§ 7. Предложение лидера выше (п-2)-го у всех игроков

Глава 3. ВЕТО-ГОЛОСОВАНИЕ С НЕБОЛЬШИМ ЧИСЛОМ УЧАСТНИКОВ
§ 8. Шансы на победу предложения 1-го игрока
§ 9. Неопределенность в предпочтениях игроков
§ 10. Случай толерантности лидера
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Достижение коллективного благосостояния на основе выборов уже почти 250 лет является предметом множества научных исследований [1-3, 5, 6, 8, 13, 24, 40, 45, 47, 49, 50, 60, 63, 66, 81-83, 88, 94], начиная с работ Борды и Кондорсе, включая Пигу и Дальтона и вплоть до наших дней. В 1950-м году Нэш [78] предложил использовать функции коллективного выбора, максимизация которых предоставляет возможность выбрать наиболее справедливый из достижимых исходов, оптимизируя все функции полезности одновременно. Отметим, что основными являются две концепции распределения общественного блага - утилитаризм (каждый из агентов максимизирует свое благосостояние) и эгалитаризм (выравнивание индивидуальных полезностей).
Другим витком развития исследований в области теории принятия решений стали кооперативные игры, в которых результат рассматривается не только с точки зрения его выгодности для всего множества игроков, но и для коалиций, состоящих лишь из части игроков (коалиция может состоять и из одного участника, принимающего решения). Основоположниками теории кооперативных игр были Нейман и Моргенштерн [79]. Ключевым понятием кооперативных игр является ядро игры - множество таких распределений полезностей, при которых каждая коалиция получает, как минимум, столько же, сколько в сумме получили бы все ее участники, действуя в одиночку. В частности, в модели, в которой игроки могут объединяться в коалиции в целях минимизации своих затрат, ядро игры может трактоваться как принцип отделения: коалиция никогда не заплатит сумму, превышающую затраты в случае ее самостоятельного действия. Понятие ядра было введено Джиллисом [62]. Впоследствии свойства и возможности применения понятия ядра к широкому кругу задач были рассмотрены в работах Аумана и Шепли [41, 42], Шубика [95], Дебре и Скарфа [51, 90], Фоули [58, 59], Мулена [74], Воробьева и его учеников [4, 9] (в частности, Бондаревой было получено и доказано необходимое и достаточное условие непустоты ядра), Морозова и его учеников [31 -33] и многих других математиков и экономистов. Причем важное значение имело изучение игр с небольшим число игроков (например, для случая 3-5 участников см. [31, 36]).
Аналогично концепции функции коллективного выбора для некооперативных игр, финальной задачей теории кооперативных игр является установление таких методов решения, которые для каждой задачи находили бы единственное распределение полезностей - значение игры. Наиболее распространенными операторами значений стали вектор Шепли [93] (отражает принцип утилитаризма - каждому агенту соответствует его средний вклад во все коалиции, в которых он состоит) и 1У-ядро (реализует эгалитаризм - минимизацию неудовлетворенности коалиций), введенное Шмайдлером [91]. В работе [92] было доказано важнейшее свойство

выпуклых игр - вектор Шепли занимает центральное положение в ядре выпуклой игры. Понятие вектора Шепли было обобщено для модели с бесконечным числом игроков в книге Аумана и Шепли [41].
Тем не менее, несмотря на обилие теоретических результатов, не редки примеры, когда члены коллектива не в силах договориться о коллективном выборе, а надо принимать совместное решение. В этом случае, если набор возможных альтернатив известен, участники соглашаются выбирать одну из них путем голосования. Термин «голосование» традиционно пошел от способа принятия решения по принципу «кто кого перекричит». Однако при этом осознавалась необходимость выработки правил голосования, в частности, легитимности выбора, определения круга выборщиков и т.п.
Начиная с политической философии Просвещения, установление правил голосования являлось главной этической проблемой. Исследования, направленные на выяснение корректности того или иного порядка проведения голосования, начались во второй половине XVIII века. Авторами первых работ, в которых математически проводилось сравнение различных правил голосования, были Борда [45] и Кондорсе [48]. В [48] был сформулирован так называемый парадокс Кондорсе, заключающийся в том, что коллективное ранжирование вариантов может быть цикличным. Например, было показано, что выбор альтернативы на основе наиболее популярного правила большинства (аксиоматически сформулировано в [72]) может приводить к победе варианта, который при парном сравнении проигрывает любому другому кандидату. Чтобы избежать данной проблемы, Кондорсе предложил ввести ранжирование альтернатив - для любых двух вариантов определяется, сколько голосующих предпочитают одну альтернативу другой. В свою очередь Борда предложил присваивать каждому варианту баллы, увеличивающиеся с ростом позиции, которую занимает альтернатива в предпочтениях игроков. Блэк [44] проводил сравнение результатов применения различных методов голосования. Янг [102] сформулировал и доказал теорему, свидетельствующую о преимуществе метода подсчета очков Борды над правилом Кондорсе. В 1951 Эрроу [39] доказал в своей книге один из главных на тот момент результатов теории голосования -теорему о невозможности. Ее суть состоит в том, что при возможности только качественного сравнения исходов (одна альтернатива хуже или лучше другой) не существует способа объединения для трех и более альтернатив, который всегда давал бы логически верный результат. Сравнительный анализ свойств различных процедур голосования и выявленных для них парадоксов в достаточно общей форме проведен в [8].
Существенное влияние на поведение членов коллектива в процессе принятия решений оказывает информированность о предпочтениях партнеров, позволяющая в некотором смысле

= л-2, то (л-2)-й игрок не заветовал с"'2, т.е. либо он поступил не рационально, либо заведовал с"'3 и с"'3 был для него хуже с”'2 (вариант 1 в четвертой ситуации уже был заветован), и тогда, так же, как было показано для третьей ситуации, независимо от порядка вариантов в ^ игроков с меньшими п-2 номерами, вариант 1 проигрывает. В случае меньших і оказывается, что (л-2)-й игрок заветовал с"'2 при зачеркнутом варианте с"’3, который не заветовал бы (л-З)-й игрок, если бы этот вариант был у (и-2)-го на последнем месте, и т.д. Получаем, что с}Л лучше с1 для всех игроков с номерами у < /, но для і-го игрока с'л хуже с'. Поэтому г'-й игрок ветует с1'1, а с‘ остается. Далее, каким бы ни было расположение вариантов у игроков с номерами, меньшими /, вариант 1 проигрывает.
Чтобы сложилась вторая ситуация, вариант с"'2 должен был заветовать (л-2)-й игрок. Это ему выгодно, если с"'3 заветован или не на последнем месте, так как после его хода вариант с"'2 остается незаветованным. Вариант с"'3 будет заветован, если он на последнем месте у (л-З)-го игрока или вариант с"4 заветован. И так до 3-го игрока, который должен заветовать с3, если этот вариант - не последний для 4-го игрока. Если же с3 хуже для 4-го игрока, чем с4, то 3-му игроку выгодней заветовать вариант 1, предвидя поведение 4-го, что уже не даст сложиться второй ситуации.
В результате, можем утверждать, что в общем случае, если с1 - худший для п-го игрока, для победности игр типа (10) критична предпочтительность варианта с'л перед с' в ./„ где с'*1 Є Jl.і, с' Є 7,+і (сумма в индексе взята по модулю п-1). А именно если указанный порядок нарушен у /-го игрока, і > 3, но для всех игроков / с / > / он не нарушался, то игра не будет победной. Таким образом, если вариант с1 - нехудший для п-го игрока, то игра (10) - победная при любых остальных J,. Если с1 - худший для п-го игрока, но с”’1 - нехудший для (л-І)-го игрока, то игра - непобедная при любых остальных J,. Если с1 - худший для п-го игрока и спЛ - худший для (п-
1^-10 И1 риКсЦ Ни С — НсХуДШЙЙ ДЛЯ {її—2)-ГО йГрОКа, ТО йГра — КСПОбсДНаЯ IIрИ ЛЮбыХ
остальных J,. Если с1 - худший для л-го игрока и с"'1 - худший для (л-І)-го игрока, и сп~2 -худший для (и-2)-го игрока, но с"'3 - нехудший для (и-З)-го игрока, то игра - непобедная при любых остальных J,. И далее, как только хотя бы для одного і, меньшего п, указанная предпочтительность меняется, игра перестает быть победной, т.е. левая в (10) игра оказывается единственной победной. Утверждение доказано.
Покажем, что циклической перестановкой игроков по порядку ходов можно получить победную игру. В утверждении 3 сказано, что в случае если вариант с1 - худший для п-го игрока, то для победности игр типа (10) критична предпочтительность варианта с'л перед с' в где с'л Є ■/,.), с' Є У,+1 (сумма в индексе взята по модулю л-1). Теперь если для /-го участника с'-1 хуже с', то рассмотрим такого игрока с максимальным номером / и, циклически переставляя