Search code examples
algorithmvoting

What is the "make everyone happy" voting algorithm?

I'm looking for a voting algorithm that picks the winners based on combination of majority of votes and number of votes.

Real life example:

Our company has a cereal bar. We have room for 3 different cereals. We want to allow our employees to vote on which cereals they want.

We don't want to strictly pick the top 3 winners based on popularity because there may be a minority of employees who can only eat 1 particular cereal (for whatever reason) and we'd like to give them special allowance as possible.

Given the following vote outcome, here is the results we'd like the algorithm to give us.

Vote scenario and desired outcome

I'm looking for an algorithm that does this kind of ranking. If you can at least provide the name of what I'm looking for that would be a big help as I could search for it better. :)

Thanks!

Solution

  • You may want to consider generalizations of Hall's marriage theorem and/or the assignment problem.

    The idea for this paradigms is to create a bipartite graph where the nodes are people and cereals, with an edge between person p and cereal c if p voted for c. The goal is to select 3 cereals such that the graph resulting from removing all other cereals is

    1. connected (everyone will eat at least one of the selected cereals), and

    2. maximizes the minimum/average degree of each person (maximizes min/avg happiness)

    You could instead think about this as a Maximum Coverage Problem. In this case, you have sets C1,C2,...,Cm where Ci is the set of people who like cereal i. For you example, taking the cereals and people in the order listed in the table, you have

    C1 = {1,5}
C2 = {2}
C3 = {1,4,5}
C4 = {3,5}

    Let n be the number of people, so that Ci is a subset of {1,2,...,n}. The goal is to find k sets such that the cardinality of the union is maximized. If multiple solutions exist, choose the one that minimizes the cardinality of intersections (minimizes the amount by which one person dominates) or maximizes the number of times the least frequent element is repeated (maximizes the happiness of the least happy person).

    For this example, there smallest k for which all elements are covered is k=3 and it gives the unique solution C2,C3,C4.

    However you look at it, you have an NP-problem, but there are known algorithms to solve them (check the wikipedia articles for references).