Теоретико-игровой анализ процедуры вето-голосования с лидером тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет имени М.В. Ломоносова

ТЕОРЕТИКО-ИГРОВОЙ АНАЛИЗ ПРОЦЕДУРЫ ВЕТО-ГОЛОСОВАНИЯ С ЛИДЕРОМ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Машечкин Алексей Игоревич

Москва 2013

I 4 О КГ 2013

005535580

Работа выполнена на кафедре исследования операций факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

доктор физико-математических наук, профессор Новикова Наталья Михайловна;

доктор физико-математических наук, ведущий научный сотрудник Кукушкин Николай Серафимович;

кандидат физико-математических наук, доцент Романов Дмитрий Сергеевич.

Институт проблем управления им. В. А. Трапезникова РАН

Защита диссертации состоится «15» ноября 2013 г. в 11:00 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК Московского государственного университета имени М.В. Ломоносова http://www.cs.msu.su в разделе «Наука» - «Работа диссертационных советов» -«Д 501.001.44».

Автореферат разослан «14» октября 2013 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь диссертационного совета к. т. н., в. н. с.

В.А. Костенко

Общая характеристика работы

Актуальность темы. Наиболее яркий пример коллективного принятия решений представляют собой выборы. В современной жизни каждый человек, хотя бы раз, но сталкивался с процессом выборов: от выборов старосты класса и до выборов президента страны. Зачастую приходится выбирать не кандидата, который будет проводить ту или иную политику, а конкретное решение - где провести семейный отпуск или встретить с друзьями Новый Год. В общем случае проблема коллективного принятия решений в сложных системах характеризуется различием интересов участников коллектива и в результате - разным пониманием оптимальности решения. Последствия принятия коллективом того или иного решения не равнозначны для членов коллектива или тех групп, представителями которых они являются. Как правило, оценку полезности любого возможного решения для каждого участника не удается оцифровать, но есть информация о предпочтительности для него имеющихся альтернатив - рейтинг всех предложений (естественно, у каждого из лиц, принимающих решение, он свой).

Для формализации данной задачи традиционно используется математический аппарат теории игр, развитый в работах Кондорсе, Неймана и Моргенштерна, Нэша, Эрроу, Воробьева, Гермейера, Мулена, а также Айзермана, Алескерова, Васина, Данилова, Ерешко, Кононенко, Кукушкина, Мазалова, Меньшикова, Морозова, Мохонько, Новиковой, Сотскова и многих других российских и зарубежных ученых.

Как показано в теории игр, обычно применяемые на практике процедуры голосования по правилу большинства (выбор большинством голосов) обладают рядом отрицательных свойств и, в том числе, не гарантируют от принятия наихудшего для меньшинства решения. Предлагаемая работа посвящена не столь дискриминирующей процедуре голосования - голосованию путем открытого наложения вето, т.е. вычеркивания альтернатив. Указанная процедура была предложена в 1978 году Мюллером и состоит в последовательном отводе имеющихся вариантов принятия совместного решения для того, чтобы привести в исполнение единственный оставшийся невычеркнутым вариант. Это может быть выбор одного из кандидатов на управляющую позицию, распределение общего блага, согласование плана развития компании и т.п. Важно заметить, что, помимо учета интересов меньшинства (так как

3

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

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

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

Задачи работы:

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

• Изучить влияние на исход выборов таких факторов, как: очередность голосования, предпочтения партнеров, возможность введения дополнительного игрока и наличие нескольких не упорядоченных по предпочтительности или одинаково предпочтительных вариантов у игроков.

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

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

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

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

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

Для худшего нетривиального случая отношения партнеров к варианту лидера решена соответствующая иерархическая игра п лиц.

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

В явном виде найдены решения для соответствующих вето-голосованию игр трех лиц с неопределенностью.

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

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

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

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

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

Апробация. Результаты работы докладывались на VI и VII Московских международных конференциях по исследованию операций О ЯМ 2010 и (ЖМ 2013, а также на конференциях в МГУ: Ломоносовские чтения (в 2009, 2011 и 2013 годах) и Тихоновские чтения (в 2008,2009 и 2012 годах).

Структура диссертации. Диссертация состоит из введения, трех глав, включающих в себя 10 параграфов, и списка литературы из 104 наименований. Полный объем диссертации составляет 121 страницу.

Основное содержание работы

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

Рассмотрим процедуру выбора на совете директоров компании одного из вариантов инвестирования ее средств. Пусть в процессе выбора обсуждаются (и+1) вариантов решения, причем и из них выдвинуты членами совета директоров, а один соответствует отказу от инвестирования. Голосуют сторонники вариантов инвестирования. Каждый вариант имеет в совете директоров представителя, для которого это решение является наилучшим. У варианта отказа от инвестирования нет продвигающего его в компании, однако этот вариант не обязательно окажется у голосующих на последнем месте, а может представляться более предпочтительным, чем варианты, предлагаемые партнерами.

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

В § 1 дана формальная постановка задачи в терминах теории игр.

Обозначим альтернативы принимаемого решения номерами 1, 2..... п, п+1.

Каждый номер /, кроме и+1, соответствует номеру представителя данного решения г во время голосования, т.е. номеру игрока /. Место /-го игрока по порядку «ветования» будем обозначать через Рассматривается процедура с открытым голосованием, когда игроки накладывают вето последовательно, причем каждый из них знает, запрет на выбор каких альтернатив уже был наложен, и удаляет один из еще не заветованных вариантов. Тем самым, вето может быть наложено на каждый из вариантов решения максимум один раз. При этом перед голосованием все игроки проинформированы о предпочтениях друг друга.

6

В игре, соответствующей голосованию, функции выигрыша имеют вид

и,(х) = Щл(х)),

где п - функция голосования, которая ставит в соответствие набору х = (хь х2,..., х„) стратегий xi голосования, выбранных игроками, вариант решения п(х); и, -отображение множества вариантов решений на числовую ось — задает полезность варианта для /-го игрока.

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

Данная модель принятия решений представима в виде игры в нормальной форме

Г» = <И, {Х,}1СК, {м,},ГЛ. >,

здесь N = {1, 2,..., и} - множество игроков, т.е. голосующих (выбирающих) участников, X, - множество стратегий и и, - функция выигрыша г'-го игрока. Для 1 -го

игрока множество стратегий Хх = У,хЛ, где У, = {2, 3..... и, п+1} - варианты для

ветования 1-м игроком (все множество альтернатив, кроме варианта 1, предложенного им самим), Л = {X: Л^ЛГ | Я.(1)=1} - набор перестановок среди подчиненных игроков, задающих порядок ходов между ними. Для остальных игроков (/ > 2) множество стратегий X/ - это множество отображений из Уц^х ...хУ^., в У„ где У; = {1, 2,..., п, л+1}\ {/, ух{\),..., Ущ-\} - множество действий игрока /, заключающихся в выборе варианта решения, на которое он накладывает вето (и такой вариант уже далее выбывает из рассмотрения), переменная у, соответствует номеру варианта решения, выбранного для ветования ¡-м игроком. Таким образом, стратегия /-го игрока X/ = у,(уц\),..., ущ.О - функция его действий в зависимости от действий уже проголосовавших игроков (с меньшими по порядку ветования номерами), а действие (ход) г'-го игрока - ветование варианта у,. При условии, что игроки пронумерованы по порядку ходов, функция выигрыша г-го игрока запишется как

м,(х) = Щп(х)), л(х) = тс(уъ у2(уО.....у,(уъ...у/л),..., у„(у1,...ху„.1)).

Если же у 1-го игрока нет возможности управлять порядком ходов, то такая игра обозначается через Г„ и отличается от Г^ тем, что стратегия 1-го голосующего

аналогична стратегиям остальных игроков, т.е. Хх = - состоит только из множества вариантов, на которые лидер может наложить вето. По умолчанию в Г„ л(/)= и

Предположим, что для каждого голосующего функции выигрыша заданы не явно, а системой предпочтений, т.е. известны строгие неравенства между значениями функций выигрыша в случае принятия каждого из вариантов. Например, для п=3 Щ1) > ^(а1) > ЩЬ1) > Щс1), а\ Ь\ с1 € {2,3,4}; и2(2) > и2(а2) > и2(Ь2) > Щс2), а2, Ь2, с2 е {1,3,4}; (1)

С/З(3) > Щс?) > иъ{Ъъ) > и3(с\ а\ Ъ\ с3 е {1,2,4}.

Считаем, что все игроки знают предпочтения друг друга и порядок ходов, а также, поскольку Г„ и РЦ являются играми с полной информацией, полагаем, что игроки действуют рационально, т.е. максимизируют свои функции выигрышей, ожидая этого и от партнеров.

В § 2 для иллюстрации основных построений подробно исследован случай п=4.

Также в § 2 сформулировано в общем виде необходимое условие победы варианта 1 в игре Г„ безотносительно к порядку ходов игроков (включая 1-го).

Обозначим через ^ множество вариантов, худших варианта 1 для /-го игрока, с г > 1, через 0(1) - объединение по г из произвольного подмножества I подчиненных игроков, а через К- объединение У, всех подчиненных игроков:

= и К=в({2,...,п}).

Множества Л}, С(Г) и К характеризуют те варианты, которые подчиненным игрокам более важно вычеркнуть, чем вариант 1, в том числе, если часть из них (группа Г) или все они объединяются в коалицию. Применение марьяжной теоремы Холла к набору {,/,},>2 дает следующее

Условие А - для любого подмножества I игроков {2, ..., п} число элементов в объединении У, по < из I не меньше числа игроков в I, т.е. обозначая число знаком |... |,

т\ >п- (2)

В § 3 показано, что при любом порядке ходов в игре Г„ условие А является необходимым условием победы варианта 1 (Утверждение 1).

Данного условия достаточно для наличия взаимно-однозначного соответствия между множеством подчиненных игроков / и вариантов в их ^ для вычеркивания, но отсюда не следует, что им выгодно ветовать именно эти варианты.

Основная часть § 3 посвящена доказательству указанного результата.

Утверждение 2. При возможности управления порядком ходов, т.е. в игре Г„, условие А является достаточным условием победы варианта 1.

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

Вторая глава имеет более технический характер. Она посвящена обратной задаче по отношению к классической постановке задачи поиска выигрывающей альтернативы при фиксированном порядке ходов, рассматриваемой Мюллером и Муленом, и описывает способы построения победного порядка ходов в зависимости от возможных случаев расположения варианта 1 в предпочтениях подчиненных игроков при выполнении необходимого и достаточного условия из первой главы. Причем, поскольку случаи строгого равенства в (2) для 111 Ф п-1 рассматриваются довольно просто (и были изучены в § 3), то построение проводится в предположении, что выполнено следующее

Условие 1: для любой группы I из I < п-1 подчиненных игроков / объединение 0(1) их./, (альтернатив, худших варианта 1) состоит из более I различных вариантов. Для множества вариантов К (худших варианта 1 для всех подчиненных игроков) так и остаются две возможности: | = п-1 к\К\ = п, которые проанализированы отдельно.

В § 4 перечислены все возможные победные порядки ходов для такого случая условия I, когда партнеры наименее расположены к варианту лидера. А именно, предполагается, что у всех подчиненных игроков вариант 1 - на третьем с конца (т.е. (л-1)-м) месте по предпочтительности, отсюда |У2| =—= |Л| = 2. Важным свойством данных игр является то, что при условии 1 все J¡ циклически пересекаются, т.е. при определенной нумерации подчиненных игроков, формально полагая = У2> имеем

|7,ПУ(+1| = 1 для всех / > 1. (3)

Будем использовать для предпочтений подчиненных игроков матричную запись, обозначая /-й строкой профиль предпочтений г'-го игрока (номера вариантов стоят по убыванию их предпочтительности слева направо); все варианты между предложением игрока и вариантом 1, как незначимые для исследования, запишем одной буквой а (без индексов).

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

У матриц на рис. 1 подчерком выделены рациональные стратегии ветования подчиненных игроков (при условии Щ= /)• Видно, что для средней и правой матриц предпочтений 2-му игроку рационально заветовать вариант 1, а для левой матрицы данный порядок ходов - победный.

Г2 а 1 с1 С2 а 1 с1 Г2 а 1 с2 с'Л

3 а 1 с2 с3 3 а 1 с3 с2 3 а 1 с2 с3

4 а 1 с3 с4 и 4 а 1 с4 с3 или 4 а 1 с3 с4

п-2 а 1 с"-3 с"'2 п-2 а 1 с""2 с"'3 п-2 а 1 (Г3 с"-2

п-1 а 1 с"'2 с""' п-1 а 1 с""2 с-' п-1 а 1 с"-' с"'2

1« а 1 с"'' а 1 с""' К? а 1 с"-' о

Рисунок 1. Разновидности матрицы предпочтений при = 2.

Основной результат § 4 состоит в следующей классификации игр Г„ с |У,| = 2.

Утверждение 3. Игры Гл, заданные матрицами предпочтений с рис. 1 с точностью до перестановки вариантов внутри Л где игроки / пронумерованы в порядке ходов между ними, являются победными тогда и только тогда, когда вариант с1 - не худший для п-го игрока или предпочтения подчиненных игроков задаются левой матрицей на рис.1 либо аналогичной с обратной предпочтительностью между вариантами с1 и с2 у 2-го игрока.

Из утверждения 3 вытекает простой способ построения победного порядка ходов в игре Г„ с |У,| = 2 (вообще говоря, не единственный). Занумеруем подчиненных игроков так, чтобы участники с пересекающимися имели соседние номера, получим выполнение (3), т.е. игру с матрицей предпочтений типа представленных на рис. I (с точностью до перестановки вариантов внутри./,). Примем с" = с1.

Алгоритм 1 - построения победного порядка ходов в игре Г^ с матрицей предпочтений, удовлетворяющей условиям утверждения 3.

Обозначим через чР номер игрока, являющийся максимальным из номеров и-подчиненных игроков, для которых вариант с" лучше с"Л. Если такого м> нет или =

2, имеем игру с левой матрицей или аналогичной с перестановкой с1 и с2 в J2, порядок ходов для которой и так победный; при 2< w°<rt циклически переставим подчиненных игроков, чтобы игрок с номером w° оказался на последнем (т.е. п-м) месте по порядку голосования, и этого достаточно для победности порядка ходов по утверждению 3.

В g 5 рассматриваются игры, в которых у одного из игроков (пусть, для определенности, 2-го) позиция варианта лидера выше 3-го с конца предложения.

Раздел 5.1 посвящен анализу случаев, когда у всех подчиненных игроков вариант 1 оказывается 3-м с конца, а у одного - на 4-й позиции с конца. Для каждой такой игры с помощью утверждения 3 построен победный порядок ходов.

В разделе 5.2 строится победный порядок ходов для игр, в которых для 2-го игрока вариант 1 лучше, чем, как минимум, четыре других варианта. Показано, что в

таком случае структура предпочтений игроков L = {3, 4.....п} (при выполнении

условия 1) усложняется: игроки могут быть разбиты на подгруппы tí, внутри которых предпочтения задаются аналогично представленному на рис. 1, a J, для i из разных подгрупп (кроме как для игроков, начинающих подгруппу) не пересекаются. Это, в свою очередь, приводит к невозможности прямого применения утверждения 3 к таким играм, и общая логика построения победного порядка ходов становится более разветвленной.

Определения. Вариант из J¡ будем называть парным к варианту из Jn где ¡Фг, и парным с игроком г (или в группе игроков I), если он находится в пересечении J, и Jr (reí). Вариант назовем непарным (внутри Г), если он принадлежит лишь одному J¡ (среди iеГ). Вариант, принадлежащий J, трех и более различных игроков из L, будем называть повторным.

Занумеруем (и обозначим) игроков из L следующим образом. Присвоим начальные номера игрокам (далее v-м) с множеством Jv = {bv, cv}, состоящим из повторного и непарного внутри L вариантов. Затем по порядку пусть будет номер игрока/с одним непарным внутри L вариантом, худшим варианта 1, а другим -парным. Игроку с парным к f-му вариантом дадим номер (/И). Второй непарный внутри L вариант должен оказаться в Jn у игрока с последним (и-м) номером в группе L. Для остальных номеров i игроков из L (п > i >J) либо будет (см. рис. 1) выполнено J, = {£', с'}, где V 6 Ль а с' 6 JM, (4)

либо выделяются Т подгрупп Ь1, У, ..., Ьт, заданных номерами И (и1 < п2 < ... <пт <п) игроков, для которых удается обеспечить следующие соотношения: 3^ Ьп' е с"' е Л " непарный внутри Ь,

■1*1.1 ={Ъп>*\сп'*'}, 6"М е - повторный, ¡> <п>, с"'*1 е У ,+2, (5)

1,2,..., 7" для игроков»внутри подгруппы У (т.е. ^ < г < л•') справедливо (4).

Далее свойство (4) будем называть цепным, игроков с номерами от/ до и и их парные внутри группы Ь или подгрупп У варианты Ъ\ с' - зацепленными, а непарные внутри Ь варианты у зацепленных игроков и самих игроков с этими вариантами будем называть крайними.

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

Например, для всех матриц на рис. 1: Г = 0,/= 2, Ь' = с1'1 и с" - с1, т.е. цепное свойство выполняется для всех подчиненных игроков. Но в предположении |/г| > 2 получаем возможность Т > 0. При Т> 0 каждая подгруппа I/ начинается с игрока / и

его повторного варианта Ъ' (варианты Ь' могут быть совпадающими для разных У), а кончается игроком п/ и его уникальным вариантом с"' - крайним в Ь. К множеству указанных вариантов будем далее адресоваться как к цепочке вариантов для У. При

этом если в II существует игрок, имеющий повторный вариант, отличный от Ь' игрока 1, то, значит, внутри 11 от зацепленного в ней варианта ответвляется еще одна подгруппа -1А Игроки, не вошедшие в У, 1?, также являются зацепленными между собой, и их множество далее обозначается как Ь°.

Свойство (5), отражающее пересечения J¡ в силу условия 1, задает среди игроков из Ь структуру типа дерева (см. левый граф на рис. 2), вершины которого соответствуют игрокам, а дуги соединяют игроков, имеющих между собой парные внутри Ь варианты. Подгруппы У - как бы ветви дерева (которое на рис. 2 изображено перевернутым), на них дуги соединяют подряд вершины игроков с соседними номерами. Ствол дерева - вертикальная жирная линия на рис. 2 -соответствует множеству игроков Ь°. Наличие ответвления означает существование повторного варианта у первого на ответвлении игрока, в таком случае Т > 0. И тогда для построения победного порядка ходов аналог Алгоритма 1 надо применять для Ь° - ствола дерева. При этом потребуется следующее

12

Условие на нумерацию подчиненных игроков:

если наихудшим для 2-го игрока среди парных с голосующими ранее игроками является парный в Ь вариант Ъг, то г-й игрок находится во множестве а если

- незацепленный вариант с" (или с"), то г1-й (или у-й) игрок оказывается л-м игроком - последним в 1°.

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

Й-1

у

Алг. 2

с=>

Л

1?-1

Р-1 1« г

л»

Алг. 1

У

,1« ,г п*

2 {

5+1

Ш

\vi-l

Рисунок 2. Построение победного порядка ходов

Далее опишем соответствующий алгоритм, по которому осуществляется

перенумерация подчиненных игроков (перед формированием порядка ходов - т.е. их

циклической перестановкой аналогично Алгоритму 1) для выполнения условия на

нумерацию. Алгоритм перенумерации задает переход от левого дерева к среднему на

рисунке: новый ствол - это новая вертикальная жирная линия. Исходные номера

игроков на рисунке проставлены рядом с вершинами. Игроки подгруппы Ь1

обозначены квадратиками, а подгруппы И - ромбиками.

13

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

Рассмотрим в исходной игре все цепочки вариантов для подгрупп V, включая подгруппы V = {у} с / у = п у = V. Обозначим через у/ номер игрока из подгруппы I], следующий за максимальным номером у?1 е I] игроков м>, для которых вариант с" лучше У", а если таких у? в П нет, то у'-ю подгруппу не учитываем. Если найдется подгруппа 1], для которой игрок мР' совпадает с п', то игрока п1 делаем п-м. Если же этот номер для 0-й подгруппы совпал с п, то не меняем исходной нумерации игроков.

Допустим, что не оказалось таких у, чтобы в I! было и>°'/ = п К Если при этом найдется учитываемая подгруппа П, в которой > к между игроками м/ и И в и нет (л*+1)-го, т.е. ответвлений других подгрупп, то выбираем игрока г/ в качестве и-го - образуем 0-ю подгруппу на основе II. В такой нумерации игроков, если применять Алгоритм 1 к новой 0-й подгруппе, то окажется, что у нее нет ответвлений после и>°-го игрока.

В остальных случаях все подгруппы /Д не содержащие ответвлений, по определению являются неучитываемыми. Тогда выберем учитываемую подгруппу И, в которой все (иг+1)-е игроки с номерами, большими м/, соответствуют таким неучитываемым 1?, и образуем 0-ю подгруппу на ее основе. После применения Алгоритма 1 к этой 0-й подгруппе получим, что для всех игроков п?+1, которые ходят ранее 2-го игрока, будет с' хуже Ъ' у каждого г из подгруппы 1?. Если опять подобных 11 нет, то выбираем ту II, в которой все (п?+ 1)-е игроки с номерами, большими V, соответствуют лишь неучитываемым 1?, не имеющим учитываемых ответвлений. Если и таких I/ не найдено, то рассматриваем исходную 0-ю подгруппу.

Предположим, что оказалась выбранной подгруппа II для некоторого у > 0. Найдем наихудший для 2-го игрока вариант из /г п ^ среди номеров И игроков, которые будут голосовать ранее 2-го (т.е. находящихся в подгруппах II с гР+\ или имеющих в IУ номер к > Если найденный вариант принадлежит Л игрока г из подгруппы I? , то соответствующего л^-го игрока (крайнего в I?) делаем п-м. В противном случае п-и становится игрок г{. На рис.2 игрок г из подгруппы I/, поэтому игрок будет перенумерован в и-го (на рис. 2 сохранены исходные номера), т.е.

расположен теперь на стволе дерева - в 0-й подгруппе (это показано графически -ствол выделен вертикальной жирной прямой).

Теперь опишем идею Алгоритма 3 - построения победного порядка ходов в игре Р^ типа (4), (5). Перестановка игроков, находящихся на стволе дерева после перенумерации по Алгоритму 2, соответствует Алгоритму 1 - см. правое дерево на рисунке, т.е. определяется циклической перестановкой игроков 0-й подгруппы так, чтобы последним стал игрок к0-* (= иМ). Заметим, что при перенумерации, заданной Алгоритмом 2, тг'-й и мР1-й игроки расположены в 0-й подгруппе, и что среди вариантов Ьн е о Л для игроков И, которые при указанном порядке ходов голосуют ранее 2-го игрока, худший для 2-го игрока вариант V (или с") также принадлежит У, (или У„) игрока из £°. Тем самым, условие на нумерацию оказывается выполненным.

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

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

В §§ 6-7 анализируются случаи наличия нескольких игроков, у которых место варианта 1 выше 3-го с конца. В этом случае по условию 1 структура связей среди 3, у подчиненных игроков / представима «лесом» - множеством деревьев, аналогичных деревьям на рис. 2. Найдено правило, позволяющее деревья леса, вершины которых переупорядочены как в § 5, «склеить» между собой в один порядок ходов.

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

возможных для коллектива альтернатив по сути, если не вдаваться в их детали, не столь велико (4-5, а не 10). Так что их стремятся укрупнить (отложив нюансы для дальнейшей проработки). При этом члены коллектива объединяются в группы приверженцев каждой агрегированной альтернативы и выдвигают своего выборщика.

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

Формально, такой механизм принятия решений соответствует рассмотренному выше, но теперь другая из принятых гипотез становится дальше от реальности - это гипотеза о строгом порядке среди промежуточных альтернатив. Действительно, если для половины группы, которую представляет выборщик (например, 2-й игрок) вариант 4 лучше варианта 3, а для другой половины - наоборот, то при принятии решений от лица коалиции этот игрок может ориентироваться как на то, так и на другое отношение предпочтительности между этими - чужими для него -вариантами: либо он будет считать их эквивалентными, либо они будут для него несравнимы.

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

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

В разделе 8.1 произведена оценка изменения шансов на выбор предложения 1-го голосующего в зависимости от наличия или отсутствия у него возможности управлять порядком ходов для игры 3-х лиц.

Конкретизированы условия, являющиеся необходимыми и достаточными для победы предложения 1-го игрока в игре Г3 (без управления порядком ходов), на базе утверждения 3. Результаты, по сути, различаются для двух случаев: большей или меньшей благожелательности к варианту 1 со стороны участника, голосующего вторым, по сравнению с вариантом третьего голосующего участника. В итоге все игры Г3 типа (1) распадаются на две группы:

^(1) > ^(а1) > ЩЬ1) > Щс1), а\ Ъ\ с1 е {2,3,4}; (I): и2(1)>и2(3) и2(2) > и2(а2) > и2(Ъ2) > и2(с2), а2, Ъ\ с2 6 {1,3,4}; иъ{3) > и3(а3) > и3(Ь2) > Щс% а\ Ъ\ с3 6 {1,2,4}. (II): 112(3)>и2(1) Следствие 1. Для победы варианта 1 при условии (I) необходимо и достаточно, чтобы он не был наихудшим для 3-го игрока.

Следствие 2. Для победы варианта 1 при условии (II) необходимо и достаточно, чтобы одновременно:

1. вариант 1 не был наихудшим для 2-го игрока и

2. для 3-го игрока вариант 2 являлся наименее предпочтительным. На основании найденных условий получены следующие оценки Утверждение 4. Из 36 случаев соотношений между выигрышами 2-го и

3-го игроков только в 14 побеждает вариант 1, причем, в 12 случаях при условии (I) и в двух - при условии (II).

При наличии возможности управлять порядком ходов действует утверждение 2 (условие А), и 1-й игрок может обеспечить победу своего предложения в 15 случаях. Таким образом, введение управления порядком голосования увеличивает шансы на победу варианта 1-го игрока с 39% до 42%.

В разделе 8.2 рассматривается игра, в которой 1-й игрок имеет возможность ввести дополнительного игрока (4-го, и новый вариант 4, соответственно). Для такой игры получено и доказано следующее утверждение.

Утверждение 5. Если для 2-го и 3-го голосующих вариант 4 хуже варианта 1, то 1-й игрок может без изменения порядка их ходов обеспечить избрание своего варианта в 62.5% случаев.

Если 1-й игрок знает, что его предложение более выгодно, чем новый вариант 4, для 2-го и 3-го игроков вместе или хотя бы для одного из них: 2-го (или 3-го), он может рассчитывать на 44.4% (или 44%). Если же 1-й игрок должен ориентироваться на возможность любого места в предпочтениях 2-го и 3-го игроков предложения нового голосующего, то его шансы на победу в игре с добавочным игроком составляют 30%, что хуже, чем в игре с двумя партнерами.

Полученные результаты показывают, что с точки зрения лидера возможность ввода дополнительного голосующего более выгодна, чем управление порядком ходов, только когда заранее известно, что вариант нового игрока менее предпочтителен, чем предложение 1-го игрока, для 2-го и 3-го игроков одновременно или хотя бы для одного из них (лучше, если для игрока, голосующего вторым).

В § 9 рассмотрены игры Г3 и Г^, соответствующие голосованию путем последовательного наложения вето, при условии нестрогих (неполностью определенных) предпочтений. Показано, что такая ситуация характерна для многокритериальной игры, возникающей в частности из-за наличия выборщиков, наследующих целевые функции участников выдвинувших их групп.

Понятие неполностью определенных предпочтений вводится в разделе 9.1. В реальной ситуации бывает трудно предпочесть один неопгамальный вариант другому, если игрок представляет интересы нескольких участников. В таком случае в предпочтениях игрока может присутствовать неопределенность в собственных интересах, которая предполагает невозможность для 1-го игрока указать более предпочтительный из двух вариантов бис, что далее обозначается как ЩЬ) о и,(с). (К ситуации с неполностью определенными предпочтениями формально относится и неоднозначность функции выигрыша, т.е. существование у нее одинаковых значений.) Подобная неопределенность в предпочтениях голосующего может быть вызвана, в том числе, наличием векторной оценки вариантов.

Например, если каждый вариант оценивается игроком / по двум критериям V и Ш, а каждая из компонент V я Ш вектор-функции выигрыша аналогична функции выигрыша из игры Г3 без неопределенности в предпочтениях, то наличие двух критериев оценки вариантов может не позволить игроку однозначно определить свои предпочтения. Данная модель представима в виде двухкритериальной игры в нормальной форме <Ы, Х„ и,> сХ,= {1,2,3,4} - множеством стратегий игрока /, N =

{1,2,3} — множеством выборщиков и функциями выигрыша и,{х) = и,(тс(х]^с2^с;)) —

где тф^/ЛЛ) — функция голосования, определяющая правила выбора варианта в зависимости от действий игроков, а V,- и Ж, - критерии оценки выбранного варианта игроком г. Переход от указанной игры в нормальной форме к рассматриваемой игре с фиксированным порядком ходов производится независимо от функций выигрыша участников так же, как и в § 1.

Для игры 3-х лиц выведены необходимые и достаточные условия победы варианта 1 (1-го голосующего) в игре с нестрогими предпочтениями, различающиеся для следующих двух (аналогичных рассмотренным в разд. 8.1) случаев предпочтений второго голосующего:

ВД > и,(а1) > и^Ь1) > и,(с1), а\ Ь\ с1 е {2,3,4}; (I): и2(1)>и2(3) и2(2) > и2(а2) ? и2(Ь2) ? и2(с2), а2, Ь\ с2 е {1,3,4};

и3(3) > иг(а3) ? и3фъ) ? иъ{сг), я3, Ъ\ съ е {1,2,4}. (П): и2{Ъ)>и2(\) или и2(3)<>и2(1) Здесь на месте любого из знаков "?" может стоять "о", обозначающее нестрогие предпочтения (отсутствие предпочтительности между вариантами или неопределенность предпочтений).

Утверждение 6. При возможной неопределенности в предпочтениях игроков между чужими (т.е. предложенными другими игроками или «статус кво») вариантами, для победы варианта 1 в предположении (I) необходимо и достаточно, чтобы вариант 1 не был наихудшим для 3-его игрока, ни как единственный, ни в случае неопределенности, т.е.

если и3(а) > ЩЬ) > и3(с) о и3(оГ), то ни с, ни с/не равны 1. Таким образом, условие (I) само по себе является выгодным для 1-го игрока. Утверждение 7. При возможной неопределенности в предпочтениях подчиненных игроков между чужими вариантами, для победы варианта 1 при условии (II) необходимо и достаточно, чтобы одновременно:

1. вариант 1 не был наихудшим ни для 2-го, ни для 3-го игроков, причем как в строгом смысле (единственности), так и в нестрогом смысле (т.е. не может быть неопределенности в двух местах и, если Ща) > ЩЬ) > Щс) о Щс0, то ни с, ни в. не равны 1, г = 2, 3), и

2. для 3-го игрока вариант 2 был наименее предпочтительным (строго или нет).

Объединяя в одно условия (I) и (II) в предположении, что 1-й игрок может выбирать, кто из подчиненных делает ход за ним, получим из утверждений 6 и 7

Следствие 3. В случае возможной неопределенности в предпочтениях игроков между чужими вариантами, для того чтобы 1-й игрок мог обеспечить избрание своего предложения при условии, что он формирует порядок ходов 2-го и 3-го игроков, необходимо и достаточно, чтобы для обоих этих игроков вариант 1 не был наихудшим (как строго, так и нестрого), а для одного из них был строго лучше, чем предложение другого подчиненного игрока.

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

В случае наличия неопределенности в предпочтениях 2-го (или же 3-го) игрока лидер может рассчитывать на победу в 33% (или 35%) случаев. При этом появление возможности управлять порядком ходов увеличивает этот показатель до 36%.

Если по паре несравнимых/равнозначных предложений есть и у 2-го, и у 3-го игроков, то 1-й игрок одерживает победу в 30% случаев (34% при формировании порядка ходов).

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

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

провести более чем в 60% игр. Одновременно с этим, 1-му игроку более выгодна ситуация, когда партнеры по голосованию имеют более строгие предпочтения.

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

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

В Заключении формулируются основные результаты работы.

Результаты, выносимые на защиту

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

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

3. Разработаны методы построения победного порядка ходов при выполнении необходимого и достаточного условия.

4. На примере игр 3-х и 4-х лиц получены оценки увеличения шансов на победу варианта, выгодного 1-му игроку, при наличии у него права формирования порядка ходов. Проведен анализ игры с 4-мя выборщиками в предположении, что 4-го голосующего вводит игрок-лидер.

5. На примере игр 3-х лиц получены оценки шансов на победа' варианта, выгодного 1-му игроку, при возможности наличия нестрогих предпочтений у голосующих (неопределенности или одинаково выгодных вариантов).

Публикации автора по теме диссертации

1. Машечкин А.И., Поспелова И.И. Свойства голосования с правом вето // Прикладная математика и информатика. 2009. Т. 31. С. 83-94. Переиздание: Mashechkin A.I., Pospelova I.I. Properties of voting with veto power // Computational Mathematics and Modeling. 2009. V. 20. № 4. P. 427437.

2. Машечкин А.И. Голосование с правом вето в условиях неполностью определенных предпочтений // VI Московская международная конференция по исследованию операций (ORM2010): Москва, 19-23 октября 2010г. Труды. М.: МАКС Пресс. С. 426-427.

3. Машечкин А.И., Новикова Н.М. Дополнительный игрок в задаче о вето-голосовании // Прикладная математика и информатика. 2012. Т. 40. С. 105— 121.

Переиздание: Mashechkin A.I., Novikova N.M. An additional player in the voting by veto problem // Computational Mathematics and Modeling. 2013. V. 24. № 1. P. 153-166.

4. Машечкин A.M., Новикова Н.М. Условия принятия заданного решения при вето-голосовании // Тихоновские чтения: 29-31 октября 2012. Тезисы докладов. М.: МАКС Пресс. С. 43-44.

5. Машечкин А.И. Оценка шансов принятия решения первого игрока в условиях голосования путем ветования // Вестник МГУ, серия "Вычислительная математика и кибернетика". 2012. № 4. С. 31-36. Переиздание: Mashechkin A.I. Estimating the winning chances of a solution suggested by the first player under conditions of voting by veto // Moscow University Computational Mathematics and Cybernetics. 2013. V. 37. № 1, P. 28-34.

6. Машечкин А.И., Новикова Н.М. Управление порядком ходов при вето-голосовании. I. Условия принятия заданного решения // Известия РАН. Теория и системы управления. 2013. № 1. С. 42-56.

Переиздание: Mashechkin A.I., Novikova N.M. Controlling the order of moves in voting by veto. I. Conditions for making the given decision // Journal of Computer and Systems Sciences International. 2013. V. 52. № 1. P. 66-79.

7. Машечкин A.M., Новикова H.M. Управление порядком ходов при вето-голосовании. II. Алгоритмы построения оптимального порядка // Известия РАН. Теория и системы управления. 2013. № 2. С. 55-82. Переиздание: Mashechkin A.I., Novikova N.M. Controlling the order of moves in voting by veto. II. Algorithms for constructing an optimal order of moves // Journal of Computer and Systems Sciences International. 2013. V. 52. № 2. P. 186-214.

В совместных работах с научным руководителем Новиковой Н.М. принадлежит: в работах [3,4,7] - постановка задачи, в работе [6] - идея доказательства. В работе [1] Поспеловой И.И. принадлежит формулировка многокритериальной игры.

Напечатано с готового оригинал-макета

Подписано в печать 10.10.2013 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 313.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет имени М.В. Ломоносова

04201365365 На пРавах рукописи

Машечкин Алексей Игоревич

ТЕОРЕТИКО-ИГРОВОЙ АНАЛИЗ ПРОЦЕДУРЫ ВЕТО-ГОЛОСОВАНИЯ С ЛИДЕРОМ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук,

профессор Новикова Наталья Михайловна

Москва 2013

ВВЕДЕНИЕ ...........................................................................................................3

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

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

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

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

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

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

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

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

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

Глава 3. ВЕТО-ГОЛОСОВАНИЕ С НЕБОЛЬШИМ ЧИСЛОМ УЧАСТНИКОВ....................................................................................................81

§ 8. Шансы на победу предложения 1-го игрока.................................................................83

§ 9. Неопределенность в предпочтениях игроков................................................................92

§ 10. Случай толерантности лидера....................................................................................108

ЗАКЛЮЧЕНИЕ.................................................................................................113

ЛИТЕРАТУРА...................................................................................................114

ВВЕДЕНИЕ

Достижение коллективного благосостояния на основе выборов уже почти 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] (отражает принцип утилитаризма - каждому агенту соответствует его средний вклад во все коалиции, в которых он состоит) и //-ядро (реализует эгалитаризм - минимизацию неудовлетворенности коалиций), введенное Шмайдлером [91]. В работе [92] было доказано важнейшее свойство

выпуклых игр - вектор Шепли занимает центральное положение в ядре выпуклой игры. Понятие вектора Шепли было обобщено для модели с бесконечным числом игроков в книге Аумана и Шепли [41].

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

Начиная с политической философии Просвещения, установление правил голосования являлось главной этической проблемой. Исследования, направленные на выяснение корректности того или иного порядка проведения голосования, начались во второй половине XVIII века. Авторами первых работ, в которых математически проводилось сравнение различных правил голосования, были Борда [45] и Кондорсе [48]. В [48] был сформулирован так называемый парадокс Кондорсе, заключающийся в том, что коллективное ранжирование вариантов может быть цикличным. Например, было показано, что выбор альтернативы на основе наиболее популярного правила большинства (аксиоматически сформулировано в [72]) может приводить к победе варианта, который при парном сравнении проигрывает любому другому кандидату. Чтобы избежать данной проблемы, Кондорсе предложил ввести ранжирование альтернатив - для любых двух вариантов определяется, сколько голосующих предпочитают одну альтернативу другой. В свою очередь Борда предложил присваивать каждому варианту баллы, увеличивающиеся с ростом позиции, которую занимает альтернатива В гтрдттпитрнияу итлк-пв Кп-эк Г441 пппдппии г.пятшение печупьтятотч ппименения пячпичных

I ' ---- ------ ----X------- ------ I. ■ " J —X----'---- " 1------------ 1 --------—х------------А

методов голосования. Янг [102] сформулировал и доказал теорему, свидетельствующую о преимуществе метода подсчета очков Борды над правилом Кондорсе. В 1951 Эрроу [39] доказал в своей книге один из главных на тот момент результатов теории голосования -теорему о невозможности. Ее суть состоит в том, что при возможности только качественного сравнения исходов (одна альтернатива хуже или лучше другой) не существует способа объединения для трех и более альтернатив, который всегда давал бы логически верный результат. Сравнительный анализ свойств различных процедур голосования и выявленных для них парадоксов в достаточно общей форме проведен в [8].

Существенное влияние на поведение членов коллектива в процессе принятия решений оказывает информированность о предпочтениях партнеров, позволяющая в некотором смысле

предсказывать их стратегии поведения. Фаркуарсон [53] предложил модель, которая исследует расчеты голосующего, использующего для принятия решения эту дополнительную информацию. Игры, которым соответствуют модели такого рода, называют стратегическими. Общая теория игр с учетом информированности игроков была развита в работах Гермейера и его учеников [7, 11, 15, 17, 20-22, 30, 34,36,37].

Многие зарубежные исследователи разрабатывали направление стратегических игр, создавая различные модели для разнообразных процедур голосования. В качестве примеров применения стратегических игр рассматривались Комитеты по жилью и образованию США [86]; Конгресс США [52]; Парламентские выборы 1981 года в Израиле [55]. Фелсенталь [54] доказал, что стратегическое продвижение наименее выгодного варианта может принести игроку больший выигрыш, нежели чем честное недальновидное голосование за наилучшую альтернативу. В [85] были выявлены серьезные основания для использования стратегического поведения в «одобрительных» выборах (когда каждый может голосовать за сколько угодно кандидатов, из которых победит тот, кто наберет больше голосов).

Однако экспериментальные результаты не подтверждали использование игроками оптимальных моделей поведения в стратегических играх. Так, Плот и Левин [84] пришли к заключению, что игроки единообразно следуют недальновидным стратегиям голосования. Аналогичные выводы сделаны в работах [67, 80, 100, 101]. Позднее Ювал [104] (также на основе проведения экспериментальных игр) показала, что выбор в пользу честных недальновидных или стратегических действий зависит от размера группы лиц, принимающих решения. В настоящее время экспериментальные исследования стратегического (сложного) поведения для различных процедур голосования составляют отдельное научное направление [46, 64, 68, 82, 96, 103].

Еще одним значимым аспектом стратегических игр яттяется манипулирование Здесь основополагающую роль играет вывод, полученный Гиббардом [61] и Саттервейтом [89], -невозможно воспроизвести такую процедуру голосования, которая бы была полностью неманипулируемой. В работе Алескерова [3] проводилось сравнение эффективности манипулирования в зависимости от правила голосования для моделей с множественным выбором - необходимостью одновременного выбора нескольких альтернатив. Здесь также вызывает интерес подробное изучение случаев с небольшим (4-5) числом альтернатив [38].

Существенно важной разновидностью стратегических игр являются иерархические игры [11], в частности, игры с лидером [12, 37, 98] и игры с фиксированным порядком ходов [11, 30, 36]. В таких играх использование участниками стратегического поведения обусловлено их информированностью, а также наличием иерархии принятия решений. Иерархия, в свою

очередь, определяет «естественные» способы манипулирования, в том числе, рассматриваемые далее в диссертации.

В работах Гермейера [10-12], Краснощекова [18], Краснощекова и Петрова [19], а также их учеников для анализа моделей принятия решений применяются методы исследования операций. В случаях, когда стратегическая модель поведения партнеров не позволяет однозначно предсказать их стратегию, весомые результаты в исследовании иерархических игр удается получить с использованием принципа гарантированного результата [10, 11] для игрока-лидера.

Кроме того, для повторяющихся игр (в повторяющихся ситуациях), даже если предпочтения партнеров исходно не известны другим игрокам, можно рассчитывать на процедуры типа «нащупывания по Курно» [48] для того, чтобы прийти к тому же исходу, что и при полной информированности. Весь спектр возможностей использования ответных стратегий на действия партнеров и соответствующего учета их рационального поведения при выборе собственных стратегий является предметом современных научных исследований [70].

В предлагаемой диссертационной работе на базе методологии теории иерархических игр и исследования операций изучается задача принятия решений в коллективах с лидером путем последовательного вето-голосования. Процедура последовательного вето-голосования была впервые введена Мюллером [77] и сводится к тому, что п голосующих выбирают одну из (гс+1) альтернатив, последовательно (по порядку голосования) отводя каждый по одному из еще незаветованных вариантов. В работах Мюллера [77], Мулена [75, 76], Сотскова [97] и др. были показаны хорошие свойства такой процедуры, в частности, что результат соответствующей игры - Парето-оптимальный и что нет дискриминации меньшинства большинством. Именно поэтому в диссертации выбран механизм вето-голосования для дальнейшего теоретико-игрового анализа в качестве способа ппинятия пешений пои наличии лидера..

Г 11 * ж

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

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

В данной диссертационной работе модель принятия решений путем последовательного наложения вето анализируется на примере выбора варианта распределения прибыли компании на совете ее директоров (подробнее о голосовании на совете директоров см. [16]). Согласно обследованию 2005 г., в среднем в России совет директоров включал 6-7 человек [14]. Поэтому есть основания полагать, что для такого случая исследуемое сложное равновесие, предполагающее рациональное поведение участников, адекватно реальности. Указанную модельную задачу принятия решений можно сформулировать следующим образом. В процессе выбора п членов совета директоров обсуждают (и+1) вариант решения. Причем п вариантов дальнейшего инвестирования полученных средств выдвинуты самими участниками, а один вариант соответствует отказу от инвестирования - так называемый «статус кво» (аналогичная точка, означающая отказ от распределения некоторого блага, была введена Нэшем [78] и рассматривалась в работах [43, 69, 88]). Голосуют сторонники вариантов инвестирования. Каждый вариант имеет в совете директоров представителя, для которого именно это решение является наилучшим. У варианта отказа от инвестирования нет своего представителя в компании, однако такой вариант не обязательно окажется у голосующих на последнем месте, а может быть более предпочтительным, чем варианты, предлагаемые партнерами.

Далее задача изучается в предположении о неявно заданных функциях выигрыша, т.е. в ситуации, когда индивидуальные предпочтения представляют собой наборы транзитивных бинарных отношений и коллективное решение также описывается бинарным отношением на множестве альтернатив (см. результаты исследований [13, 57, 73, 104]) Данное предположение наиболее соответствует практике принятия решений, поскольку позволяет обойтись без количественных оценок выигрышей участников, которые редко бывают достоверно известны всем.

Будем считать, что принятие итогового решения происходит с помощью процедуры последовательного наложения вето (далее - «ветования»). При этом рассматривается ситуация стратегической игры, когда голосующие моделируют рациональное поведение партнеров. Ясно, что в таком случае порядок голосования играет определяющую роль. Допустим, что есть лидер коллектива (например, председатель совета директоров), и он имеет возможность управлять порядком голосования (в зависимости от предпочтений участников). Как это повлияет на решение? Когда будет выбран вариант лидера? Ответы на эти вопросы даются далее.

Диссертационная работа структурно построена следующим образом. В первой главе для игры п лиц получено необходимое и достаточное условие существования порядка ходов, при котором лидер коллектива (1-й игрок) может обеспечить победу своего варианта при голосовании путем последовательного ветования) [26]. Такой порядок ходов будем называть победным. Данное условие показывает, что, управляя порядком ходов, 1-й игрок добивается победы во всех случаях, когда победа варианта 1 вообще возможна (у подчиненных достаточно вариантов, худших варианта 1, для ветования) по марьяжной теореме Холла [65]. Указанное условие (соответствующее марьяжному условию Холла) гарантирует, что, несмотря на право 1 -го игрока манипулировать процедурой вето-голосования, задавая ее порядок, в результате не может быть выбран вариант, наихудший для какого-либо игрока либо входящий в группу из I вариантов, наихудших для каких-либо / игроков. Тем самым, рассматриваемая процедура голосования не приведет к н