Voting Systems

VotingSystems.linq

void Demo<T>(IEnumerable<IEnumerable<T>> ballots, int seats, IEqualityComparer<T> comparer = null)
{
    var elections = new Dictionary<string, Tuple<IElection<T>, ITieBreak<T>[]>>
    {
        ["STV"] = Tuple.Create<IElection<T>, ITieBreak<T>[]>(
            new SingleTransferableVoteElection<T>(),
            new ITieBreak<T>[]
            {
                new BordaCountTieBreak<T>(),
                new ApprovalCountTieBreak<T>(),
                new RandomTieBreak<T>(),
            }),
        ["Approval"] = Tuple.Create<IElection<T>, ITieBreak<T>[]>(
            new ApprovalVoteElection<T>(),
            new ITieBreak<T>[]
            {
                new RandomTieBreak<T>(),
            }),
        ["Borda"] = Tuple.Create<IElection<T>, ITieBreak<T>[]>(
            new BordaCountElection<T>(),
            new ITieBreak<T>[]
            {
                new ApprovalCountTieBreak<T>(),
                new RandomTieBreak<T>(),
            }),
    };

    elections.Select(kvp => new
    {
        kvp.Key,
        Outcomes = Enumerable.Range(0, Samples).Select(_ => string.Join(", ", kvp.Value.Item1.Elect(ballots, seats, kvp.Value.Item2, comparer))).GroupBy(g => g).Select(g => new { g.Key, Count = g.Count() }),
    }).Dump();
}

public class BallotCollection<T> : List<T[]>
{
    public new void Add(params T[] votes)
    {
        base.Add(votes);
    }
}

public class TieBreakComparer : IComparer<int[]>
{
    public static readonly TieBreakComparer Instance = new TieBreakComparer();

    public int Compare(int[] a, int[] b)
    {
        if (object.ReferenceEquals(a, b))
        {
            return 0;
        }
        else if (object.ReferenceEquals(a, null))
        {
            return -1;
        }
        else if (object.ReferenceEquals(b, null))
        {
            return 1;
        }

        var minLength = Math.Min(a.Length, b.Length);
        for (var i = 0; i < minLength; i++)
        {
            int comp;
            if ((comp = a[i].CompareTo(b[i])) != 0)
            {
                return comp;
            }
        }

        return a.Length.CompareTo(b.Length);
    }
}

public interface ITieBreak<T>
{
    IDictionary<T, int> Score(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null);
}

public class RandomTieBreak<T> : ITieBreak<T>
{
    public IDictionary<T, int> Score(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        return ballots.SelectMany(ballot => ballot).Distinct(comparer).ToDictionary(b => b, b => StaticRandom.Next(), comparer);
    }
}

public interface IElection<T>
{
    T[] Elect(IEnumerable<IEnumerable<T>> ballots, int seats, IList<ITieBreak<T>> tieBreaks, IEqualityComparer<T> comparer = null);
}

public class ApprovalVoteElection<T> : IElection<T>
{
    public static Dictionary<T, int> CountVotes(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        return ballots
            .SelectMany(ballot => ballot.Distinct(comparer))
            .GroupBy(g => g, comparer)
            .ToDictionary(g => g.Key, g => g.Count(), comparer);
    }

    public T[] Elect(IEnumerable<IEnumerable<T>> ballots, int seats, IList<ITieBreak<T>> tieBreaks, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var score = ApprovalVoteElection<T>.CountVotes(ballots, comparer);
        var tieBreakScores = tieBreaks.Select(tieBreak => tieBreak.Score(ballots, comparer));
        return score
            .OrderByDescending(kvp => kvp.Value)
            .ThenByDescending(kvp => tieBreakScores.Select(tieBreakScore => tieBreakScore[kvp.Key]).ToArray(), TieBreakComparer.Instance)
            .Take(seats)
            .Select(kvp => kvp.Key)
            .ToArray();
    }
}

public class ApprovalCountTieBreak<T> : ITieBreak<T>
{
    public IDictionary<T, int> Score(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null)
    {
        return ApprovalVoteElection<T>.CountVotes(ballots, comparer);
    }
}

public class BordaCountElection<T> : IElection<T>
{
    public static Dictionary<T, int> ScoreVotes(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var candidates = ballots.SelectMany(ballot => ballot).ToSet(comparer);
        return ballots.Select(ballot =>
        {
            var remaining = new HashSet<T>(comparer);
            remaining.UnionWith(candidates);

            var scores = new Dictionary<T, int>(comparer);
            foreach (var candidate in ballot)
            {
                if (!scores.ContainsKey(candidate))
                {
                    remaining.Remove(candidate);
                    scores[candidate] = remaining.Count;
                }
            }

            return scores;
        }).Aggregate((a, b) =>
        {
            foreach (var kvp in b)
            {
                a.Increment(kvp.Key, kvp.Value);
            }

            return a;
        });
    }

    public T[] Elect(IEnumerable<IEnumerable<T>> ballots, int seats, IList<ITieBreak<T>> tieBreaks, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var score = BordaCountElection<T>.ScoreVotes(ballots);
        var tieBreakScores = tieBreaks.Select(tieBreak => tieBreak.Score(ballots, comparer));
        return score
            .OrderByDescending(kvp => kvp.Value)
            .ThenByDescending(kvp => tieBreakScores.Select(tieBreakScore => tieBreakScore[kvp.Key]).ToArray(), TieBreakComparer.Instance)
            .Take(seats)
            .Select(kvp => kvp.Key)
            .ToArray();
    }
}

public class BordaCountTieBreak<T> : ITieBreak<T>
{
    public IDictionary<T, int> Score(IEnumerable<IEnumerable<T>> ballots, IEqualityComparer<T> comparer = null)
    {
        return BordaCountElection<T>.ScoreVotes(ballots, comparer);
    }
}

public class SingleTransferableVoteElection<T> : IElection<T>
{
    public T[] Elect(IEnumerable<IEnumerable<T>> ballots, int seats, IList<ITieBreak<T>> tieBreaks, IEqualityComparer<T> comparer = null)
    {
        comparer = comparer ?? EqualityComparer<T>.Default;
        var ballotsCopy = ballots.Select(b => b.ToList()).ToList();

        while (true)
        {
            var scores = ballotsCopy.SelectMany(b => b).Distinct(comparer).ToDictionary(b => b, b => 0, comparer);
            foreach (var ballot in ballotsCopy)
            {
                if (ballot.Count > 0)
                {
                    scores.Increment(ballot[0]);
                }
            }

            var tieBreakScores = tieBreaks.Select(tieBreak => tieBreak.Score(ballotsCopy, comparer));

            if (scores.Count <= seats)
            {
                return scores
                    .OrderByDescending(score => score.Value)
                    .ThenByDescending(kvp => tieBreakScores.Select(tieBreakScore => tieBreakScore[kvp.Key]).ToArray(), TieBreakComparer.Instance)
                    .Select(score => score.Key)
                    .ToArray();
            }

            var minScore = ballotsCopy.Count;
            var losers = new HashSet<T>(comparer);
            foreach (var score in scores)
            {
                if (score.Value < minScore)
                {
                    minScore = score.Value;
                    losers.Clear();
                    losers.Add(score.Key);
                }
                else if (score.Value == minScore)
                {
                    losers.Add(score.Key);
                }
            }

            var loser = losers
                .Select(l => new
                {
                    Loser = l,
                    TieBreaks = tieBreakScores.Select(s => s.TryGetValue(l)).ToArray(),
                })
                .OrderBy(l => l.TieBreaks, TieBreakComparer.Instance)
                .Select(l => l.Loser)
                .First();

            foreach (var ballot in ballotsCopy)
            {
                ballot.RemoveAll(b => comparer.Equals(b, loser));
            }
        }
    }
}