На недавних выборах в Нью-Йорке использовалось ранжированное голосование. В этом примере показано, как можно найти победителя на выборах с ранжированным голосованием.

[example]

 

 

 

 

 

 

 

 

Что такое ранжированое голосование?

При ранжированном голосовании (также известном как голосование с ранжированным выбором или преимущественное голосование) каждый избиратель ранжирует кандидатов по первому, второму, третьему и другим вариантам. Чтобы определить победителя, вы повторяете эти шаги:

  1. Для каждого избирателя найдите кандидата с наивысшим рейтингом, который все еще участвует в выборах, и добавьте один к его подсчету.
  2. Если кандидат набрал более 50% от общего числа голосов, то этот кандидат становится победителем.
  3. Если ни один из кандидатов не набрал более 50% от общего числа голосов, вы находите кандидата (-ов) с наименьшим количеством голосов и исключаете их из списка.

Вы повторяете эти шаги, пока не найдете победителя.

Обратите внимание, что вы можете исключить несколько кандидатов в одном туре, если они имеют одинаковое наименьшее количество голосов.

Также возможно окончание вничью. Это происходит, если два или более кандидата делят голоса ровно поровну. Например, если имеется 3000 бюллетеней и три оставшихся кандидата, каждый из которых имеет ровно 1000 голосов, то вы не можете определить последнего кандидата на место, которого нужно исключить.

И исключение нескольких кандидатов в одном туре, и ничья очень маловероятны при большом количестве избирателей.

Также обратите внимание, что если есть N кандидатов, то может быть не более N — 1 раундов. Во время каждого раунда выбывает как минимум один кандидат, поэтому после N — 1 раундов может остаться не более одного кандидата. (Часто победитель бывает раньше.)

Почему?

Вы можете прочитать о плюсах и минусах ранжированого голосования в Википедии и других местах, но есть одно важное преимущество. Ранжированое голосование позволяет избежать распыления голосов на аналогичных кандидатов. Например, предположим, что на выборах четыре кандидата, трое из которых (Андерсон, Бейкер и Кэмпбелл) имеют схожие платформы мира и гармонии, а один из которых (Занто) совершенно другой, выступая на платформе завоевания мира. Теперь предположим, что 71% людей предпочитают платформу мира и гармонии, и голоса составят: 24% Андерсона, 21% Бейкера, 26% Кэмпбелла и 29% Зантоса.

В системе множественного голосования, где побеждает кандидат с наибольшим количеством голосов, Зантос выиграет, даже если 71% избирателей выступят против платформы «завоевание мира».

Есть несколько способов избежать исхода, при котором победит кандидат от меньшинства. У вас может быть второй тур выборов между двумя самыми популярными кандидатами. В этом примере Кэмпбелл выиграет. Обратите внимание, что это тоже может быть не «лучший» результат, если все избиратели Бейкера предпочтут Андерсона в качестве второго варианта. В этом случае большинство могло бы предпочесть Андерсона Кэмпбеллу, но, по крайней мере, они имеют некоторый вклад во второй тур.

Ранжированое голосование — еще одна стратегия решения этой проблемы. Это также имеет то преимущество, что вы можете проводить раунды, не возвращаясь к урне для голосования, что требует дополнительного времени и усилий.

Избирательный класс

В примере используется следующий класс Ballot для хранения вариантов выбора избирателя.

public class Ballot
{
    // Choices holds the candidate numbers in ranked order.
    public int[] Choices;
    public Ballot(int num_candidates)
    {
        Choices = Extensions.RandomArrangement(num_candidates);
    }

    // Find this ballot's top non-disqualified choice.
    public int TopChoice(bool[] disqualified)
    {
        for (int i = 0; i < disqualified.Length; i++)
        {
            int candidate = Choices[i];
            if (!disqualified[candidate]) return candidate;
        }
        return -1;
    }
}

Массив Choices содержит индексы кандидатов в рейтинге избирателя. Например, если массив содержит 1, 3, 2, 0, то первый выбор избирателя — кандидат 1, второй выбор — кандидат 3 и так далее.

Метод TopChoice возвращает лучший выбор избирателя с учетом массива, показывающего, какие кандидаты были дисквалифицированы в предыдущих раундах. Например, disqualified [2] верен, если кандидат номер 2 был исключен.

Этот метод просто перебирает выборы избирателя в порядке ранжирования. Когда он находит кандидата, который не был исключен, он возвращает индекс этого кандидата.

Метод не должен упускать из виду кандидата, потому что, как вы увидите, программа не исключит всех кандидатов.

Подведение итогов голосов

Когда вы нажимаете кнопку Tab, выполняется следующий код.

private void btnTabulate_Click(object sender, EventArgs e)
{
    int num_ballots = Ballots.Length;
    int num_candidates = Ballots[0].Choices.Length;
    int needed_to_win = (int)(num_ballots / 2.0 + 1);

    lvwVotes.Columns.Clear();
    lvwVotes.Columns.Add("Round");
    for (int i = 0; i < num_candidates; i++)
    {
        lvwVotes.Columns.Add("Can " + i.ToString());
    }
    lvwVotes.Columns.Add("Notes");
    lvwVotes.Items.Clear();

    // Make an array indicating which
    // candidates have been disqualified.
    bool[] disqualified = Enumerable.Repeat(false, num_candidates).ToArray();

    // Repeat rounds until we have a winner.
    // Note that there can be at most num_candidates - 1 rounds,
    // and round num_candidates - 1 could end in an exact tie.
    for (int round_num = 0; round_num < num_candidates - 1; round_num++)
    {
        // Count the votes.
        int[] votes = new int[num_candidates];
        foreach (Ballot ballot in Ballots)
        {
            // Add to this ballot's top candidate's total.
            votes[ballot.TopChoice(disqualified)]++;
        }
        // Display the totals.
        ListViewItem item = new ListViewItem(round_num.ToString());
        for (int candidate = 0; candidate < num_candidates; candidate++)
        {
            if (disqualified[candidate])
                item.SubItems.Add("---");
            else
                item.SubItems.Add(votes[candidate].ToString());
        }
        lvwVotes.Items.Add(item);

        // See if there is a winner.
        int winner = -1;
        for (int candidate = 0; candidate < num_candidates; candidate++)
        {
            if (votes[candidate] >= needed_to_win)
            {
                winner = candidate;
                break;
            }
        }

        if (winner >= 0)
        {
            // We have as winner!
            item.SubItems.Add(winner.ToString() + " wins!");
            break;
        }

        // Find the smallest vote total(s).
        string notes = "";
        int max_votes = int.MinValue;
        int min_votes = int.MaxValue;
        for (int i = 0; i < num_candidates; i++)
        {
            if (!disqualified[i])
            {
                if (votes[i] < min_votes) min_votes = votes[i];
                if (votes[i] > max_votes) max_votes = votes[i];
            }
        }

        if (min_votes == max_votes)
        {
            // We have a tie.
            item.SubItems.Add("Tie");
            break;
        }

        // Disqualify last place candidate(s).
        for (int i = 0; i < num_candidates; i++)
        {
            if ((!disqualified[i]) && (votes[i] == min_votes))
            {
                disqualified[i] = true;
                notes += ", x" + i.ToString();
            }
        }
        notes = notes.Substring(2);

        item.SubItems.Add(notes);
    }
}

Код получает количество бюллетеней и кандидатов, а также подсчитывает количество голосов, необходимых для победы. Это число составляет половину от общего числа голосов плюс один.

Затем программа очищает элемент управления lvwVotes ListView и создает в нем столбцы для представления кандидатов и последний столбец Notes.

Затем код инициализирует дисквалифицированный массив, чтобы ни один кандидат не был дисквалифицирован. Затем он входит в цикл для проведения раундов голосования.

Во время каждого раунда программа перебирает объекты избирательного бюллетеня, выбирает их предпочтительного кандидата и увеличивает счет этого кандидата.

Затем код перебирает кандидатов и отображает их счетчики в элементе управления lvwVotes ListView. Если кандидат исключен, программа отображает -.

Затем код определяет, был ли победитель, проверяя, получил ли какой-либо кандидат необходимое количество голосов. Если есть победитель, программа отображает номер победившего кандидата и выходит из цикла раундов.

Если победителя нет, код перебирает кандидатов и находит наибольшее и наименьшее количество голосов, полученных любым кандидатом.

Если наибольшее и наименьшее количество голосов совпадают, тогда все оставшиеся кандидаты имеют одинаковое количество голосов, поэтому голосование заканчивается в равенство. Программа сообщает об этом и выходит из цикла обходов.

Если у нас нет равных, программа снова перебирает кандидатов и дисквалифицирует тех, кто набрал наименьшее количество голосов. Если будет много голосов, то, вероятно, это будет только один кандидат. Если несколько кандидатов имеют одинаковое наименьшее количество голосов, они будут удалены вместе.

Программа отображает краткое сообщение с указанием кандидатов, которых она удалила.

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

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

Заключение

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

Как всегда, загрузите пример, чтобы увидеть дополнительные сведения, например о том, как работает пользовательский интерфейс и как программа генерирует случайные бюллетени. Обратите внимание, что элемент управления ListView не может обрабатывать огромное количество элементов, поэтому не пытайтесь отобразить 1 миллион бюллетеней. Если вы хотите поэкспериментировать с огромным количеством избирателей, измените код, чтобы он не отображал их всех.