Метод Шульце

Основная идея эвристики пути — концепция косвенных побед, так называемых путей.

Если при парном сравнении кандидат C(1) побеждает C(2), кандидат C(2) побеждает C(3), кандидат C(3) побеждает C(4), …, и C(n − 1) побеждает C(n), то мы можем говорить, что существует путь от кандидата C(1) к кандидату C(n). Чем больше голосующих предпочитают первого кандидата второму кандидату, тем сильнее победа первого над вторым. Силой пути C(1), …, C(n) является слабейшая парная победа одного кандидата над другим в этой последовательности.

Другими словами:

• Предположим, что d[V, W] — число голосующих, которые строго предпочитают кандидатуру V кандидатуре W.
• Путь — это последовательность кандидатур C(1), …, C(n), где d[C(i), C(i + 1)] > d[C(i + 1), C(i)] для всех i = 1, …, n − 1.
• Сила пути C(1), …, C(n) — это минимум d[C(i), C(i + 1)] для всех i = 1, …, n − 1, где C(i) — позиция номер i с начала пути; d[A, B] — количество человек, поставивших кандидата A выше на одну или несколько позиций, чем кандидата B, при этом, если определён рассматриваемый путь, то имена кандидатов могут заменяться их позициями в данном пути.

Силой сильнейшего пути p[A, B] от кандидатуры A к кандидатуре B называется максимум значений силы всех возможных путей от кандидатуры A до кандидатуры B. Если пути от кандидатуры A к кандидатуре B не существует, то p[A, B] принимается равной нулю.

Кандидат A побеждает кандидата B косвенно, если выполняется любое из двух следующих условий:

• Сила сильнейшего пути от кандидата A к кандидату B сильнее, чем сила сильнейшего пути от кандидата B к кандидату A.
• Существует путь от кандидата A к кандидату B, а пути от кандидата B к кандидату A не существует.

Косвенные победы удовлетворяют условию транзитивности. Это означает, что если кандидат A косвенно побеждает кандидата B, а кандидат B косвенно побеждает кандидата C, то кандидат A также побеждает кандидата C косвенно.

В эвристике пути используется следующая процедура построения графа путей предпочтения и определение силы путей:

Путём силы p от кандидата X до кандидата Y называется последовательность кандидатур C(1), …, C(n) со следующими пятью свойствами:

1. C(1) принимается равным X.
2. C(n) принимается равным Y.
3. Для всех i от 1 до n − 1: d[C(i), C(i + 1)] > d[C(i + 1), C(i)].
4. Для всех i от 1 до n − 1: d[C(i), C(i + 1)] ⩾ p.
5. По крайней мере для одного i из диапазона от 1 до n − 1: d[C(i), C(i + 1)] = p, где p — сила пути от кандидата X до кандидата Y, то есть p[X, Y].

Кандидатура A является возможным победителем тогда и только тогда, когда p[A, Z] ⩾ p[Z, A] для каждой другой кандидатуры Z.

Жирным выделены значения d[X, Y] > d[Y, X]. Как видно из таблицы, в этом примере каждому кандидату предпочитается другой кандидат — имеет место парадокс Кондорсе. Однако сила предпочтения различается. Предпочтение, отдаваемое кандидату A перед кандидатом B, больше предпочтения, отдаваемого кандидату C перед кандидатом A.

Кандидат A лучше кандидата B, который лучше кандидата С, который лучше кандидата A… Здесь нарушается транзитивность и нет победителя по критерию Кондорсе. Однако, для установления победителя в подобных случаях можно одну за другой отбрасывать самые слабые из сильных путей, в данном случае начав с d[C, A] = 64^{[прояснить]}, в результате чего победителем будет признан кандидат А^{[прояснить]}.

Рассмотрим выборы, на которых 45 избирателей голосуют за пять кандидатов: A, B, C, D, E. Голоса распределились следующим образом:

5 ACBED (то есть 5 избирателей поставили A выше C, C выше B, B выше E, а E выше D),

5 ADECB,

8 BEDAC,

3 CABED,

7 CAEBD,

2 CBADE,

7 DCEBA,

8 EBADC.

Сила пути — это сила его слабейшего звена (критическое звено). Пути, каждый переход в которых удовлетворяет d[X, Y] > d[Y, X] можно построить, пользуясь следующими кусочками последовательностей AC, AD, BA, BD, CB, CE, DC, EA, EB, ED.

Следующая таблица показывает сильнейшие пути от кандидата X к кандидату Y. Критическое звено сильнейшего пути подчёркнуто.

По методу Шульце будет провозглашён победителем кандидат E, так как p[E, X] ⩾ p[X, E] для любого другого кандидата X.

Так как 25 = p[E, A] > p[A, E] = 24, кандидат E лучше, чем кандидат A.

Так как 28 = p[E, B] > p[B, E] = 24, кандидат E лучше, чем кандидат B.

Так как 28 = p[E, C] > p[C, E] = 24, кандидат E лучше, чем кандидат C.

Так как 31 = p[E, D] > p[D, E] = 24, кандидат E лучше, чем кандидат D.

Так как 28 = p[A, B] > p[B, A] = 25, кандидат A лучше, чем кандидат B.

Так как 28 = p[A, C] > p[C, A] = 25, кандидат A лучше, чем кандидат C.

Так как 30 = p[A, D] > p[D, A] = 25, кандидат A лучше, чем кандидат D.

Так как 29 = p[C, B] > p[B, C] = 28, кандидат C лучше, чем кандидат B.

Так как 29 = p[C, D] > p[D, C] = 28, кандидат C лучше, чем кандидат D.

Так как 33 = p[B, D] > p[D, B] = 28, кандидат B лучше, чем кандидат D.

Таким образом, метод Шульце приводит к следующему порядку кандидатов: E > A > C > B > D.

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

Метод Шульце представляет собой развитие идеи альтернативного голосования, которое применяется при выборах в различные органы власти Австралии, Новой Зеландии, Папуа — Новой Гвинеи, Фиджи, Ирландии, США, а также в ряде политических партий, неправительственных организаций и т. д.

• Markus Schulze, Tiebreakers, Subcycle Rules, август 1998 г.
• Markus Schulze, Maybe Schulze is decisive, август 1998 г.