Набор Смита - Smith set

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

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

Характеристики

Множество Смита существует всегда и четко определено. Существует только один наименьший доминирующий набор, поскольку доминирующие множества вложены и непусты, а набор кандидатов конечен.
Набор Смита может иметь более одного кандидата либо из-за попарных связей, либо из-за циклов, например, в Парадокс Кондорсе.
В Кондорсе победитель, если таковой существует, является единственным членом множества Смита. Если слабые победители Кондорсе существуют, то они входят в набор Смита.
Набор Смита всегда является подмножеством взаимное большинство -предпочтительный набор кандидатов, если таковой существует.^[1]

Сравнение наборов Шварца

В Набор Шварца, известный как Обобщенная аксиома оптимального выбора или GOCHA, тесно связан и всегда является подмножество набора Смита. Набор Смита больше тогда и только тогда, когда кандидат в наборе Шварца имеет попарную связь с кандидатом, которого нет в наборе Шварца.

Набор Смита может быть построен из набора Шварца путем многократного добавления двух типов кандидатов до тех пор, пока такие кандидаты не перестанут существовать вне набора:

кандидаты, имеющие попарные связи с кандидатами в наборе,
кандидаты, которые побеждают кандидата в наборе.

Обратите внимание, что кандидаты второго типа могут существовать только после добавления кандидатов первого типа.

Альтернативная формулировка

Любой бинарное отношение ${ displaystyle R}$ на съемочной площадке ${ displaystyle A}$ может генерировать естественный частичный порядок на ${ displaystyle R}$ -цикл классы эквивалентности набора ${ displaystyle A}$ , так что ${ displaystyle xRy}$ подразумевает ${ Displaystyle [х] geq [у]}$ .

Когда ${ displaystyle R}$ это Beats-or-Ties бинарное отношение на множестве кандидатов, определяемых ${ displaystyle x}$ Beats-or-Ties ${ displaystyle y}$ если и только если ${ displaystyle x}$ попарные поражения или ничьи ${ displaystyle y}$ тогда полученный частичный порядок - это порядок побития или ничья который является общий заказ. Набор Смита - это максимальный элемент порядка выигрыша или ничьей.

Алгоритмы

Набор Смита можно рассчитать с помощью Алгоритм Флойда-Уоршолла во время Θ ${ Displaystyle (п ^ {3})}$ . Его также можно рассчитать с помощью версии Алгоритм Косараджу или же Алгоритм Тарьяна во время Θ ${ Displaystyle (п ^ {2})}$ .

Его также можно найти, создав матрицу попарного сравнения с кандидатами, ранжированными по их количеству попарных побед минус попарные поражения ( Метод Коупленда ранжирование), а затем поиск самого маленького верхнего левого квадрата ячеек, который может быть покрыт так, чтобы все ячейки справа от этих ячеек отображали попарные победы. Все кандидаты, названные слева от этих ячеек, входят в набор Смита. (Это работает, потому что Коупленд ранжирует кандидатов так, что кандидаты из набора Смита имеют больше очков, чем кандидаты из набора Смита.^[2])

Пример: предположим, что кандидаты A, B и C находятся в наборе Смита, каждый попарно побеждает другого, но все 3 попарно побеждают D и E. A, B и C будут помещены в верхние 3 ряда (предположим, что они расположены в таком порядке для этого примера) таблицы попарного сравнения, и тогда будет видно, что, покрывая все ячейки от «A бьет A» (ячейка, сравнивающая A с собой) до «C бьет C», все ячейки справа (ячейки, сравнивающие A, B и C с D и E) будут показывать попарные победы, тогда как меньший набор ячеек не может этого сделать, поэтому A, B и C будут в наборе Смита.

Пример использования рейтинга Коупленда:

Потери и связи выделены жирным шрифтом.
	А	B	C	D	E	F	грамм
А	---	Победить	Терять	Победить	Победить	Победить	Победить
B	Терять	---	Победить	Победить	Победить	Победить	Победить
C	Победить	Терять	---	Терять	Победить	Победить	Победить
D	Терять	Терять	Победить	---	Галстук	Победить	Победить
E	Терять	Терять	Терять	Галстук	---	Победить	Победить
F	Терять	Терять	Терять	Терять	Терять	---	Победить
грамм	Терять	Терять	Терять	Терять	Терять	Терять	---

A проигрывает C, поэтому подтверждается, что все кандидаты от A до C (A, B и C) входят в набор Смита. Есть один матч, в котором кандидат, уже подтвержденный как участник набора Смита, проигрывает или связывает кого-то, еще не подтвержденного как участник набора Смита: C проигрывает D; таким образом подтверждается, что D входит в набор Смита. Теперь есть еще один такой матч: D связывается с E, поэтому E добавляется в набор Смита. Поскольку все от A до E превзошли всех кандидатов, еще не подтвержденных для принадлежности к набору Смита, теперь подтверждено, что набор Смита находится от A до E.

Смотрите также

внешняя ссылка

Примеры алгоритмов вычисления множества Смита

[1] ttp://dss.in.tum.de/files/brandt-research/dodgson.pdf

[2] Это связано с тем, что каждый кандидат в наборе Смита может быть побежден или равным только попарно другими членами набора Смита, в то время как каждый кандидат, не входящий в набор Смита, побежден каждым членом набора Смита.

[1]

[2]