What is the make everybody happy voting algorithm?

Question

I am looking for a voting algorithm that selects winners based on a combination of the majority of votes and the number of votes.

Real life example:

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

We don’t want to strictly choose the top 3 winners by popularity because there may be a minority of employees who can only have 1 (for any reason), and we would like to give them a special allowance as much as possible.

Given the following voting result, here are the results that we would like to provide to the algorithm.

I am looking for an algorithm that makes such a rating. If you can at least specify the name of what I'm looking for, that would be a big help, as I could better look for it. :)

Thanks!

Answer 1

You may consider generalizing the Hall marriage theorem and / or the assignment problem .

The idea for this paradigm is to create a bipartite graph, where the nodes are people and cereals, with the edge between the person p and the grain c , if p voted for c . The goal is to select 3 cereals so that the graph obtained by removing all other cereals is

• (everyone will eat at least one of the selected cereals) and

• maximizes the minimum / average degree of each person (maximizes the minimum / average happiness)

Instead, you might think of it as a problem of maximum coverage . In this case, you have sets C1,C2,...,Cm , where Ci is a set of people who like grain i . For example, if you took cereals and people in the order shown 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 Ci is a subset of {1,2,...,n} . The goal is to find k sets so that the combining power is maximized. If there are several solutions, choose the one that minimizes the power of intersections (minimizes the amount that one person dominates) or maximizes the number of repetitions of the least frequent element (maximizes the happiness of the least happy person).

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

However, you look at this, you have an NP problem, but there are well-known algorithms for solving them (check out the wikipedia articles for links).

Answer 2

There is no perfect voting system - see http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem . Various attempts have been made to overcome this by bending the rules, including http://en.wikipedia.org/wiki/Range_voting .

One idea, close to the voting range, is to give everyone 12 votes and let them distribute them as they see fit. If you assume that people who have several options distribute their 12 votes in the same way - 12x1 or 6x2 or 4x3 or 3x4 - then I think that you will get the desired result, and Lucky Charms will receive a total of 10 votes and getting the rest more than that.

Answer 3

If the number of cereals is small, you can consider your problem as a problem with a subset and brute force to find which configuration gives the most “joy”

 var max_happyness = -INF for every subset {c1, c2, c3} of C: max_hapyness = max(max_happyness, happyness(i1,i2,i3)) 

You still have the problem of determining the appropriate function of happiness. For example, you can choose the function of happiness, which as a first priority calculates the number of people who can eat any food. Then, as a second priority, the number of people who love two cereals, and then those who love three cereals, etc.

Pros: If you can determine the function of happiness, this gives a guaranteed best result.

Cons:. You must be able to determine the function of happiness.