Турнирное решение

Избирательные системы
Часть серии " Политика"

Множественность / мажоритарность Множество Мажоритарной Единый голос без права передачи Ограниченное голосование Множественность в целом (голосование за блок) Общий билет Многократное голосование Два раунда Исчерпывающее голосование Рейтинговые / преференциальные системы Мгновенный сток (альтернативное голосование) Условное голосование Метод Кумбса Методы Кондорсе ( методы Коупленда , Доджсона , Кемени – Янга , Минимакс , Нансона , ранжированные пары , Шульце , Альтернативный Смит ) Позиционное голосование ( счет Борда , метод Науру / Даудалла , Евровидение ) Баклин голосование Первичная избирательная система Оклахомы Преференциальное блокирующее голосование Кардинальные / ступенчатые системы Оценка голосования Утверждающее голосование ( единые первичные ) Комбинированное одобрительное голосование Обычное суждение Голосование одобрения удовлетворенности Решение большинства ЗВЕЗДНОЕ голосование
Пропорциональное отображение Партийный список ( открытые списки , закрытые списки , локальные списки ) Самые высокие средние ( д'Ондта , Сент-Lague , Хантингтон-Hill ) Наибольший остаток ( Hare , Droop , Imperiali , Hagenbach-Bischoff ) Пропорциональные формы рейтингового голосования Единственный передаваемый голос ( Грегори , Райт ) CPO-STV Schulze STV Пропорциональные формы одобрительного голосования Пропорциональное одобрительное голосование Последовательное пропорциональное одобрительное голосование Бипропорциональное распределение Голосование справедливым большинством Взвешенное голосование Прямое представительство Интерактивное представление Жидкая демократия
Смешанные системы Смешанный пропорциональный Дополнительная система участников Параллельное голосование (смешанное мажоритарное) Скорпион Бонус за большинство Альтернативное голосование Плюс Двухчленный пропорциональный Пропорционально между городом и деревней
Другие системы и родственная теория Кумулятивное голосование Биномиальное голосование Голосование по доверенности Делегированное голосование Случайный выбор ( жеребьевка , случайное голосование ) Сравнение избирательных систем Теория социального выбора Теорема Эрроу Теорема Гиббарда – Саттертуэйта. Теория общественного выбора
Политический портал
v т е

Решением турнира является функцией , которая отображает ориентированный полный граф с непустым подмножеством его вершин . Неформально это можно рассматривать как способ найти «лучшие» альтернативы среди всех альтернатив, которые «соревнуются» друг с другом в турнире. Турнирные решения берут начало в теории социального выбора , ^[1]^[2]^[3]^[4], но также учитывались в спортивных соревнованиях , теории игр , ^[5] многокритериальном анализе решений , биологии , ^[6]^[7] рейтинг веб-страниц , ^[8] и дуэльные бандитские задачи . ^[9]

В контексте теории социального выбора турнирные решения тесно связаны с функциями социального выбора C1 Фишберна ^[10] и, таким образом, стремятся показать, кто из всех кандидатов лучший.

Турнир по 4 вершин: ,

{\ Displaystyle А = \ {1,2,3,4 \}}

{\ Displaystyle \ succ = \ {(1,2), (1,4), (2,4),}

{\ Displaystyle (3,1), (3,2), (4,3) \}}

Определение [ править ]

Турнира (график) является кортеж , где находится множество вершин (называемых альтернатив ) и является Connex и асимметричное бинарное отношение над вершинами. В теории социального выбора бинарное отношение обычно представляет собой попарное сравнение альтернатив между альтернативами. ${\ displaystyle T}$ ${\ Displaystyle (А, \ succ)}$ ${\ displaystyle A}$ ${\ Displaystyle \ succ}$

Турнирное решение - это функция, которая отображает каждый турнир на непустое подмножество альтернатив (называемое набором выбора ^[2] ) и не различает изоморфные турниры: ${\ displaystyle f}$ ${\ Displaystyle Т = (А, \ succ)}$ ${\ displaystyle f (T)}$ ${\ displaystyle A}$

Если - изоморфизм графов между двумя турнирами и , то

{\ displaystyle h: A \ rightarrow B}

{\ Displaystyle Т = (А, \ succ)}

{\ displaystyle {\ widetilde {T}} = (B, {\ widetilde {\ succ}})}

{\ displaystyle a \ in f (T) \ Leftrightarrow h (a) \ in f ({\ widetilde {T}})}

Примеры [ править ]

Типичные примеры турнирных решений: ^[1]^[2]

Метод Коупленда
Верхний цикл
Набор Slater
Двухпартийный набор
Непокрытый набор
Набор банков
Минимальный комплект покрытия
Установлено равновесие турнира

Рекомендации

^ a b Ласлиер , Ж.-Ф. (1997). Турнирные решения и голосование большинством . Springer Verlag.
^ a b c Феликс Брандт; Маркус Брилл; Пол Харренштейн (28 апреля 2016 г.). «Глава 3: Турнирные решения» (PDF) . У Феликса Брандта; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча (ред.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 978-1-316-48975-8.
^ Брандт, Ф. (2009). Турнирные решения - расширения максимальности и их применение в процессе принятия решений . Докторская диссертация на факультете математики, информатики и статистики Мюнхенского университета.
^ Скотт Мозер. «Глава 6: Правило большинства и турнирные решения». В JC Heckelman; Н.Р. Миллер (ред.). Справочник по социальному выбору и голосованию . Эдгар Элгар.
^ Фишер, округ Колумбия; Райан, Дж. (1995). «Турнирные игры и позитивные турниры». Журнал теории графов . 19 (2): 217–236. DOI : 10.1002 / jgt.3190190208 .
^ Аллесина, S .; Левин, JM (2011). «Конкурентная сетевая теория видового разнообразия» . Труды Национальной академии наук . 108 (14): 5638–5642. DOI : 10.1073 / pnas.1014428108 .
^ Ландау, HG (1951). «Об отношениях доминирования и структуре обществ животных: I. Влияние присущих им характеристик». Вестник математической биофизики . 13 (1): 1–19. DOI : 10.1007 / bf02478336 .
^ Феликс Брандт; Феликс Фишер (2007). «PageRank как слабое решение турнира» (PDF) . Конспект лекций по информатике (LNCS) . 3-й Международный семинар по Интернету и сетевой экономике (WINE) . 4858 . Сан-Диего, США: Спрингер. С. 300–305.
^ Сиддарта Рамамохан; Арун Раджкумар; Шивани Агарвал (2016). Дуэльные бандиты: от победителей Кондорсе до общих турнирных решений (PDF) . 29-я конференция по системам обработки нейронной информации (NIPS 2016) . Барселона, Испания.
Перейти ↑ Fishburn, PC (1977). «Функции социального выбора Кондорсе». Журнал СИАМ по прикладной математике . 33 (3): 469–489. DOI : 10.1137 / 0133030 .

[:0-1] Ласлиер , Ж.-Ф. (1997). Турнирные решения и голосование большинством . Springer Verlag.

[BrandtConitzer2016-2] Феликс Брандт; Маркус Брилл; Пол Харренштейн (28 апреля 2016 г.). «Глава 3: Турнирные решения» (PDF) . У Феликса Брандта; Винсент Конитцер; Улле Эндрисс; Жером Ланг; Ариэль Д. Прокачча (ред.). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 978-1-316-48975-8.

[3] Брандт, Ф. (2009). Турнирные решения - расширения максимальности и их применение в процессе принятия решений . Докторская диссертация на факультете математики, информатики и статистики Мюнхенского университета.

[4] Скотт Мозер. «Глава 6: Правило большинства и турнирные решения». В JC Heckelman; Н.Р. Миллер (ред.). Справочник по социальному выбору и голосованию . Эдгар Элгар.

[5] Фишер, округ Колумбия; Райан, Дж. (1995). «Турнирные игры и позитивные турниры». Журнал теории графов . 19 (2): 217–236. DOI : 10.1002 / jgt.3190190208 .

[6] Аллесина, S .; Левин, JM (2011). «Конкурентная сетевая теория видового разнообразия» . Труды Национальной академии наук . 108 (14): 5638–5642. DOI : 10.1073 / pnas.1014428108 .

[7] Ландау, HG (1951). «Об отношениях доминирования и структуре обществ животных: I. Влияние присущих им характеристик». Вестник математической биофизики . 13 (1): 1–19. DOI : 10.1007 / bf02478336 .

[8] Феликс Брандт; Феликс Фишер (2007). «PageRank как слабое решение турнира» (PDF) . Конспект лекций по информатике (LNCS) . 3-й Международный семинар по Интернету и сетевой экономике (WINE) . 4858 . Сан-Диего, США: Спрингер. С. 300–305.

[9] Сиддарта Рамамохан; Арун Раджкумар; Шивани Агарвал (2016). Дуэльные бандиты: от победителей Кондорсе до общих турнирных решений (PDF) . 29-я конференция по системам обработки нейронной информации (NIPS 2016) . Барселона, Испания.

[10] Перейти ↑ Fishburn, PC (1977). «Функции социального выбора Кондорсе». Журнал СИАМ по прикладной математике . 33 (3): 469–489. DOI : 10.1137 / 0133030 .