WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«УДК 519.6 ОБОБЩЕНИЕ МАРЬЯЖНОЙ ТЕОРЕМЫ ХОЛЛА ДЛЯ ЗАДАЧИ УПРАВЛЕНИЯ ПОРЯДКОМ ВЕТО-ГОЛОСОВАНИЯ Н.М. Новикова Вычислительный центр им. А.А. Дородницына РАН Россия, 119333, ...»

8326

УДК 519.6

ОБОБЩЕНИЕ МАРЬЯЖНОЙ ТЕОРЕМЫ

ХОЛЛА ДЛЯ ЗАДАЧИ УПРАВЛЕНИЯ

ПОРЯДКОМ ВЕТО-ГОЛОСОВАНИЯ

Н.М. Новикова

Вычислительный центр им. А.А. Дородницына РАН

Россия, 119333, Москва, Вавилова ул., 40

E-mail: N_Novikova@umail.ru

А.И. Машечкин

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

Россия, 119991, Москва, Ленинские горы, 1

E-mail: a.mashechkin@gmail.com Ключевые слова: иерархические игры, вето-голосование, управление порядком ходов, теорема Холла о свадьбах, марьяжное условие Холла, необходимое и достаточное условие существования победного порядка ходов, условия победы выделенного варианта Аннотация: Настоящий доклад посвящен установлению соотношений между марьяжным условием Холла (существования системы различных представителей подмножеств) в задаче о свадьбах и необходимым и достаточным условием наличия в иерархической игре, моделирующей выборы путем открытого последовательного вето-голосования, такого порядка ходов, при котором побеждает выделенный кандидат. Вторая задача возникает при возможности управления порядком наложения вето при голосовании, например в коллективе с лидером, в случае полной информированности. Для того чтобы подчеркнуть разницу между двумя задачами, в докладе рассмотрено небольшое обобщение задачи о свадьбах (введена возможность предпочтений между женихами) и доказано соответствующее небольшое усиление результата Холла.


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

1. Введение Рассмотрим игру n лиц Гn, соответствующую процедуре выборов путем открытого голосования с помощью последовательного наложения вето. Подобная процедура была впервые предложена Мюллером [1] и затем в разных вариантах изучалась Муленом [2], Сотсковым [3], Ювал [4], Кукушкиным [5] и другими исследователями. О месте права вето в голосовании и выборах см., например, в [6].

В самом простом варианте предположим, что n игроков И1,..., Иn, выбирают одного из n+1 кандидатов К0, К1,..., Кn, поочередно вычеркивая любую из еще не вычеркнутых альтернатив – единственный оставшийся кандидат считается выбранным (победившим). Здесь все игроки видят,какие альтернативы остались к их ходу. Предположим также, что им известны функции предпочтений друг друга на множестве кандида

–  –  –

тов, и пусть эти предпочтения строгие, т.е. для любых Кi, Кj (где i, jN = {1,..., n}, i j) каждый игрок может сказать, какая кандидатура для него лучше (и другие игроки знают его отношение предпочтения).

Рассматриваемая игра Гn относится к иерархическим играм (играм с фиксированным порядком ходов) [7] и в данных условиях в ней существует сложное равновесие по теореме Куна (см. например в [8]). Понятно, что конкретное значение равновесия зависит от последовательности вычеркивания кандидатур, т.е. от порядка ходов игроков.

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

Обозначим через Ji множество таких кандидатов Кj, которые хуже К0 для игрока Иi.

Тогда если для некоторого порядка ходов кандидат К0 соответствует сложному равновесию, то I, N = {1,..., n}.

I N J (1) i iI По аналогии с [9] нетрудно доказать, что условие (1) является также достаточным для существования порядка ходов, при котором в исследуемой игре победит кандидат К0. Соответствующий порядок ходов будем называть победным.

Теперь рассмотрим задачу о свадьбах [10]. Допустим, что имеется n девушек И1,..., Иn и n юношей. У каждой девушки Иi есть список Ji тех юношей, за любого из которых она согласна выйти замуж. Спрашивается, в каком случае каждую девушку удается выдать замуж (естественно, за своего юношу), не противореча ее согласию? По теореме Холла [10] условие (1) – марьяжное условие Холла в сделанных предположениях – является необходимым и достаточным для положительного ответа на вопрос в задаче о свадьбах.

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

2. Анализ возможности применения теоремы Холла в задаче о вето-голосовании при фиксированном порядке ходов Марьяжное условие Холла является необходимым и достаточным для существования системы различных представителей для набора множеств {Ji}i1, т.е. системы n различных между собой элементов – по одному в каждом множестве Ji, где все Ji суть подмножества одного и того же множества кандидатов {Кi}i1. Однако, чтобы применить это условие в задаче о вето-голосовании, где игроки должны вычеркнуть n различных между собой кандидатов, следовало бы показать, что при победе кандидата К0 игроки Иi вычеркивают кандидатов из своих Ji (для всех iN). Тогда можно было бы сопоставить списки допустимых для девушек женихов в задаче о свадьбах и кандидатов для вычеркивания в задаче о вето-голосовании и воспользоваться результатом о необходимости из марьяжной теоремы Холла. Но, к сожалению, указанное свойство, как правило, не выполняется. Приведем пример для игры трех лиц Г3, когда одной из рациональных стратегий игрока является вычеркивание кандидата, лучшего К0.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

ВСПУ-2014 Москва 16-19 июня 2014 г.

Пусть профиль предпочтений в игре задан матрицей (2), строки которой соответствуют игрокам, пронумерованным по порядку ходов, а элементы в строках обозначают кандидатов, упорядоченных по убыванию их предпочтительности для данного игрока, (2) К1 К2 К0 К3 К2 К0 К3 К1 К3 К0 К1 К2.

Если первый игрок вычеркнет кандидата К3, то второй игрок вычеркнет К1, и выиграет кандидат К0, а если первый игрок вычеркнет кандидата К0, то второй игрок вычеркнет К1 и выиграет кандидат К3, что хуже для первого игрока, т.е. такой его ход не рационален. Но если первый игрок вычеркнет кандидата К2, то второй игрок вычеркнет К3, и опять выиграет кандидат К0, значит, вето К2 столь же выгодно первому игроку, сколь и вето К3. Более того, если первый игрок вычеркнет К1, то также выиграет кандидат К0. Получается, что первому игроку не обязательно ограничивать себя наложением вето на кандидатов из J1. Аналогично и второму игроку, если, к примеру, И1 вычеркнул К3, не обязательно вычеркивать К1, а можно вычеркнуть К2 (не рационально лишь вето К0). Единственно, кто всегда должен вычеркивать альтернативу, худшую К0, это игрок, делающий последний ход (если ему выгодно другое, то кандидат К0 не побеждает).

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

Утверждение 1. Если кандидат К0 оказался не вычеркнутым в игре Гn, введенной в разделе 1, то существует система различных представителей для набора множеств {Ji}i1 в этой игре.

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

Простое прямое доказательство утверждения 1 авторам не известно. Другая возможность – получить утверждение 1 как следствие утверждения 2 о необходимости условия (1) для победы К0 (см. ниже) и марьяжной теоремы Холла. Авторы полагают, что легче доказать напрямую необходимость условия (1) в задаче о вето-голосовании, чем обосновать возможность применения для этого теоремы Холла.





Утверждение 2. Если кандидат К0 оказался не вычеркнутым в игре Гn, введенной в разделе 1, то в этой игре выполнено условие (1).

Прямое доказательство утверждения 2, не опирающееся на утверждение 1, дано в Приложении. (Подчеркнем, что если доказать утверждение 1, то утверждение 2 можно получить по теореме Холла, а если доказать вышеупомянутое усиление утверждения 1, то и без ее использования – по аналогии с доказательством утверждения из [11].) Из утверждения 2 следует, что условие (1) является необходимым для существования такого порядка вето-голосования, при котором побеждает кандидат К0. В следующем разделе покажем, что достаточность условия (1) для существования указанного порядка не вытекает из марьяжной теоремы Холла.

–  –  –

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

Утверждение 3. Необходимым и достаточным условием наличия требуемого в задаче о счастливых свадьбах порядка их проведения является условие (1).

Доказательство утверждения 3. Необходимость следует из марьяжной теоремы Холла [10]. Достаточность докажем аналогично [10] по индукции. В случае n = 1 утверждение очевидно. Предположим теперь, что достаточность условия (1) верна для всех случаев k n. При выполнении условия (1) для n девушек и юношей может быть так, что каждым r (0 r n) девушкам нравятся более чем r юношей, а может быть, что каким-то нравятся ровно r юношей.

В первом случае одна девушка может первой выйти замуж за того, кто ей нравится больше всех, и тогда условие (1) по-прежнему будет выполняться, но уже для (n – 1) девушек и (n – 1) юношей. Действительно, пусть каждым r (0 r n) девушкам нравятся более чем r юношей. Один из этих юношей, возможно, был тот, кто женился на первой девушке. Но без него есть еще, по крайней мере, r неженатых юношей, которые нравятся r девушкам. Таким образом, после женитьбы любой пары остается (n – 1) девушек и (n – 1) юношей, для которых верно условие (1). По предположению индукции, их всех можно счастливо (т.е. в требуемом порядке) поженить.

Во втором случае имеется r n девушек, которым нравятся ровно r юношей. По предположению индукции, есть способ счастливо выдать замуж этих девушек за тех r юношей, которые им нравятся. Тогда сыграем эти свадьбы сначала. Покажем, что остальных девушек тоже можно счастливо выдать замуж за оставшихся юношей. Рассмотрим любых s из оставшихся (n – r) девушек. Этим s девушкам плюс r замужним девушкам должны нравиться по крайней мере (r+s) юношей по условию (1). Так как r замужним девушкам не нравятся другие юноши кроме тех r, с которыми они состоят в браке, то s девушкам должны нравиться другие юноши, не те, что женаты. Поэтому оставшиеся (n – r) девушек могут счастливо заключить брак с неженатыми юношами в силу выполнения и для них условия (1). Тем самым, всех можно счастливо поженить.

Утверждение 3 доказано.

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

3.2. Задача управления порядком ходов при вето-голосовании в случае отсутствия информации о предпочтениях партнеров Сформулируем аналог утверждения 3 для задачи управления порядком ходов при вето-голосовании (поскольку аналог не будет верен, рассмотрим его в форме гипотезы).

Гипотеза. При выполнении условия (1) найдется порядок вето-голосования в игре Гn, введенной в разделе 1, при котором побеждает кандидат К0 и каждый игрок накладывает вето на худшего для себя из оставшихся не вычеркнутыми к его ходу кандидатов.

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

Следующий пример игры Г3 показывает, что это не так.

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

(3) К1 К0 К2 К3 К2 К0 К1 К3

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

ВСПУ-2014 Москва 16-19 июня 2014 г.

К3 К0 К1 К2.

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

А именно, если игроки пронумерованы в порядке ходов, то игроку И1 рационально вычеркивать не кандидата К3, а кандидата К0; если игроков И1 и И2 переставить между собой по порядку ходов, то рациональный игрок И2 (на своем первом ходе) может вычеркнуть вариант К1 (или К2), но не К3; и если игроков И1 и И3 переставить по порядку ходов по отношению к их номерам, то рациональный игрок И3 (на своем первом ходе) не вычеркнет вариант К2. Аналогично при замене порядка ходов игроков И2 и И3 и затем любых перестановках игрока И1.

Тем самым, гипотеза не верна, а выполнено Утверждение 4. Условие (1) не является достаточным для существования победного порядка ходов в игре с не информированными о профиле предпочтений друг друга игроками.

В итоге получили разные результаты о достаточности марьяжного условия Холла для двух обсуждаемых задач, поэтому утверждение из [9] о достаточности условия (1) для существования победного порядка ходов в игре с информированными об интересах друг друга игроками не следует напрямую из теоремы Холла.

Отметим также, что в задаче о счастливых свадьбах имеется простой алгоритм для построения порядка счастливых свадеб. Сначала ставятся свадьбы всех девушек, имеющих единственного юношу в списке, затем – с одним неженатым юношей в списке. На каждом шаге рассматривается минимальное число r m, для которого существует r девушек, в объединении списков которых – ровно r неженатых юношей. Для девушки с минимальном номером из числа r рассматриваемых играется свадьба с первым юношей в ее списке.

В силу утверждения 4 для задачи о вето-голосовании такого простого способа авторам найти не удалось (предлагаемые алгоритмы построения победного порядка ходов см. в [11]).

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

Авторы выражают благодарность Ф.Т. Алескерову и Н.С. Кукушкину за многочисленные обсуждения, инициализировавшие постановку рассмотренной задачи.

Приложение. Прямое доказательство утверждения 2 Предположим, что утверждение 2 верно для всех Гk с k n, докажем для Гn. И допустим противное, т.е. что выиграл кандидат К0, но в игре Гn не выполнено условие (1).

Тогда найдется множество I = {i1, i2,..., im} индексов m игроков, у которых у всех вместе меньше m альтернатив, худших кандидата К0, т.е. |G(I)| m, где знак |...| обозначает число элементов в множестве, а G(I) – объединение Ji по iI. Рассмотрим минимальное по включению такое I, и пусть Иt – первый по порядку ходов игрок с индексом из I. К его ходу, если бы не осталось кандидатов в G(I), на коих не наложено вето, то он должен был бы вычеркнуть либо кандидата К0, либо лучшего для себя, чем К0, когда он уверен, что кандидата К0 вычеркнут и без него. Таким образом, указанная ситуация

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

ВСПУ-2014 Москва 16-19 июня 2014 г.

возникнуть не может. Поэтому у Иt есть выбор: вычеркнуть кандидата из G(I), на кого еще не наложено вето, либо кандидата К0, либо лучшего для себя, чем К0. Если Иt – не первый игрок, то начиная с его хода возникла игра Гk с k n, для которой (по предположению индукции) следует, что кандидат К0 победить не может, из-за нарушения условия (1). Действительно, в этой игре присутствуют все игроки из множества I, а кандидатов, худших К0 для них, могло остаться лишь меньше, чем исходно было в G(I), так что условие (1) заведомо не выполняется. Значит, Иt – первый игрок и после его хода возникнет игра Гk с k n, в которой на одного игрока из I меньше.

Если игрок Иt вычеркнет кандидата из G(I), то в оставшейся игре будет на один вариант из G(I) меньше, т.е. условие (1) снова не выполняется и кандидат К0 не выигрывает. Заметим, что, за счет выбора минимального I, при исключении произвольного i из I условие (1) уже должно выполняться, откуда |G(I\{i})| = m – 1, G(I\{i}) = G(I) и любой вариант из Ji принадлежит G(I\{i}), в частности, для i= t. Отсюда с помощью того же индукционного шага нетрудно показать, что когда Иt вычеркивает кандидата из G(I), то в оставшейся игре выигрывает кандидат, не входящий в G(I), т.е. лучший кандидата К0 для всех i из I. Действительно, на основании соответствующего предположения индукции победит кандидат, лучший К0 для всех i из I\{t}. Но в силу равенства G(I\{t}) и G(I) получим требуемое условие.

Если же игрок Иt вычеркивает кандидата не из G(I), то либо в оставшейся игре выиграет кандидат К0 и придем к противоречию с оптимальностью поведения игрока Иt (который мог вычеркнуть кандидата из G(I) и получить победу кандидата, лучшего К0), либо кандидат К0 не выигрывает и придем к противоречию с исходным предположением. Полученное противоречие завершает шаг индукции. А поскольку для игр Г2 и Г3 необходимость условия (1) очевидна и также непосредственной проверкой убеждаемся, что при невыполнении условия (1) для этих игр в них побеждает кандидат, лучший К0, то утверждение 2 доказано.

Список литературы

1. Mueller D.C. Voting by veto // Journal of Public Economics. 1978. Vol. 10. P. 55-75.

2. Moulin H. Prudence versus sophistication in voting strategy // Journal of Economic theory. 1981. Vol. 24. P.

398-412.

3. Sotskov A.I. Vetoing in social choice with blockings // Mathematical social sciences. 1994. Vol. 27. P. 203Yuval F. Sophisticated voting under the sequential voting by veto // Theory and Decisions. 2002. Vol. 53. Р.

343-369.

5. Kukushkin N.S. Acyclicity of improvements in finite game forms // International Journal of Game Theory.

2011. Vol. 40, Issue 1. P. 147-177

6. Алескеров Ф.Т., Ордешук П.С. Выборы. Голосование. Партии. М.: Академия, 1995. 210 с.

7. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976. 328 с.

8. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985. 200 с.

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

10. Hall P. On Representatives of Subsets // Journal of the London Mathematical Society. 1935. Vol. 10, No. 1.

P. 26-30.

11. Машечкин А.И., Новикова Н.М. Управление порядком ходов при вето-голосовании. II. Алгоритмы построения оптимального порядка // Известия РАН. Теория и системы управления. 2013. № 2. С. 55

–  –  –





Похожие работы:

«ПРОГРАММНЫЕ СИСТЕМЫ: ТЕОРИЯ И ПРИЛОЖЕНИЯ ISSN 2079-3316 № ?, 2014, c. ??–?? УДК 519.612.2 Р. А. Ахметшин, И. И. Газизов, А. В. Юлдашев Комбинированный подход к построению параллельного предобуславливателя для решения задачи фильтрации углеводородов в пористой среде на гра...»

«Министерство образования Республики Беларусь БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра физики ЛАБОРАТОРНАЯ РАБОТА № 2.18 ПОЛЯРИЗАЦИЯ СВЕТА Минск 2005 ЛАБОРАТОРНАЯ РАБОТА № 2.18 ПОЛЯРИЗАЦИЯ СВЕТА Теория явления Поляризация света. Как изв...»

«УДК 378.147(07) ББК 74.580.253я73 С89 Электронный учебно-методический комплекс по дисциплине "Информационнокоммуникационные технологии в образовании" подготовлен в рамках инновационной образовательной программы "Информатизация и автоматизированные системы управления", реализованной в ФГОУ ВПО СФУ...»

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

«ДОКЛАДЫ БГУИР № 1 (13) ЯНВАРЬ–МАРТ УДК 621.396 ПРОЕКТИРОВАНИЕ ЦИФРОВЫХ ПРИЕМНЫХ УСТРОЙСТВ И.И. ЗАБЕНЬКОВ, Н.Н. ИСАКОВИЧ, С.Л. ЖДАНОВ, Д.А. ЕНЬКОВ, А.И. ЗАБЕНЬКОВ Белорусский государственный университет информатики и радиоэлектроники П. Бровки, 6,...»

«Министерство образования Республики Беларусь Учреждение образования "БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ" УТВЕРЖДАЮ Проректор по учебной работе д.т.н., профессор _А.А.Хмыль "12" _июня_ 2013 г. ПРОГРАММА...»

«Министерство образования Республики Беларусь Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ УТВЕРЖДАЮ ПРОГРАММА вступительного экзамена в магистратуру по специа...»

«1 Пояснительная записка Данная рабочая программа разработана на основе следующих нормативных документов:1. Закон РФ "Об образовании";2. Федеральный базисный учебный план для образовательных учреждений РФ от 09.03.2004 № 1312;3. Государственный образовательный стандарт основного общего и ср...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.