Набор Шварца
редактировать
В системах голосования, набор Шварца представляет собой объединение всех компонентов набора Шварца . Компонент множества Шварца - это любое непустое множество S кандидатов, такое что
- Каждый кандидат внутри множества S попарно не побежден каждым кандидатом вне S; и
- Нет непустого подходящего подмножества из S, удовлетворяющего первому свойству.
Набор кандидатов, который удовлетворяет первому требованию, также известен как недоминируемый набор .
Набор Шварца обеспечивает единый стандарт оптимального выбора результатов выборов. Системы голосования, которые всегда выбирают кандидата из набора Шварца, соответствуют критерию Шварца . Набор Шварца назван в честь политолога Томаса Шварца.
Содержание
- 1 Свойства
- 2 Сравнение множеств Смита
- 3 Алгоритмы
- 4 Методы соответствия
- 5 См. Также
- 6 Ссылки
- 7 Внешние ссылки
Свойства
- Множество Шварца всегда непусто - всегда есть по крайней мере один компонент множества Шварца.
- Любые два отдельных компонента множества Шварца не пересекаются.
- Если есть победитель Кондорсе, это единственный член множества Шварца. Если в наборе Шварца только один член, это, по крайней мере, слабый победитель Кондорсе.
- Если компонент набора Шварца содержит несколько кандидатов, все они находятся в цикле пути битов друг с другом, вершина цикл .
- Любые два кандидата, которые находятся в разных компонентах множества Шварца, попарно связаны друг с другом.
Сравнение множеств Смита
Множество Шварца тесно связано и всегда является подмножеством набора Смита . Набор Смита больше, если и только если кандидат в наборе Шварца попарно связан с кандидатом, которого нет в наборе Шварца. Например, если
- 3 избирателя предпочитают кандидата A, а не B, а не C,
- 1 избиратель предпочитает кандидата B, а не C, а не A,
- 1 избиратель предпочитает кандидата C, а не A, а не B,
- 1 избиратель предпочитает кандидата C, а не B, а не A,
тогда у нас A попарно побеждает B, B попарно побеждает C, и A связывается с C в их попарном сравнении, что делает A единственным членом множества Шварца., а набор Смита состоит из всех кандидатов.
Алгоритмы
Набор Шварца можно вычислить с помощью алгоритма Флойда – Уоршалла за время Θ (n) или с версией Алгоритм Косараджу во времени Θ (n).
Методы соответствия
Метод Шульце всегда выбирает победителя из набора Шварца.
См. Также
Литература
- Уорд, Бенджамин (1961). «Правило большинства и распределение». Журнал разрешения конфликтов. 5 (4): 379–389. doi : 10.1177 / 002200276100500405. При анализе последовательного принятия решений, основанного на правиле большинства, описывает множество Смита и множество Шварца, но, по-видимому, не понимает, что Шварц набор может состоять из нескольких компонентов.
- Schwartz, Thomas (1970). «О возможности рациональной оценки политики». Теория и решение. 1 : 89–106. doi : 10.1007 / BF00132454.Вводит понятие набора Шварца в конце статьи как возможную альтернативу максимизации при наличии циклических предпочтений как стандарт рационального выбора.
- Шварц, Томас (1972). «Рациональность и миф о максимуме». Нет. Нет, т. 6, № 2. 6 (2): 97–117. doi : 10.2307 / 2216143. JSTOR 2216143.Дает аксиоматическую характеристику и обоснование набора Шварца как возможного стандарта для оптимального, рационального коллективного выбора.
- Деб, Раджат (1977). «О правиле Шварта». Журнал экономической теории. 16 : 103–110. doi : 10.1016 / 0022-0531 (77) 90125-9.Доказывает, что множество Шварца - это множество недоминируемых элементов транзитивного замыкания парного отношения предпочтения.
- Шварц, Томас (1986). Логика коллективного выбора. Нью-Йорк: издательство Колумбийского университета. ISBN 0-231-05896-9.Обсуждает набор Смита (названный GETCHA) и набор Шварца (названный GOCHA) как возможные стандарты для оптимального рационального коллективного выбора.
Внешний links