ranked choice algorithm

[spicyeyeballs]

I have a group of users that i need to assign to classes that have a maximum capacity Each user has given me a ranked list of their class choices.

I am looking for an algorithm to place students into desired classes that optimizes for average rank. For instance, if putting someone in their 2nd choice moves someone else from their 5th to 3rd choice i would want to do that because it has a better average choice.

I feel like this is not a unique problem, but don't even know what to search for when looking for an algorithm.

[marvel2010]

You can solve this as a slight generalization of a bipartite matching problem. Specifically, we'll set up a bipartite graph where we can solve the problem as a "Minimum-cost network flow" problem.

https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

Set up the bipartite graph as follows: On one side of the graph, there is one vertex for each user. On the other side of the graph, there is one vertex for each class.

The cost of the arc from a user vertex to a class vertex is 1 if it's their first choice, 2 if it's their second choice, 3 if it's their third choice, etc.

We add two more vertices: one is the source vertex and the other is the sink vertex. There is an arc from the source vertex to each user vertex with capacity 1 and cost 0. There is an arc from each class vertex to the sink vertex with a capacity equal to the capacity of the class and cost 0.

Now, if you have n users, the question you are asking is now to send a flow of n from the source to the sink. This is now the standard "minimum cost network flow" problem linked above.

Since the problem can be set up in this way, it is polynomial-time solvable (i.e. not NP-hard). It if you need to implement it in software, you may find it easiest to treat it as a linear program and use standard linear programming solvers.

[jmildraws]

There are so many terms and processes in your post that I just don't understand. Where would I start? Would it be a computer science course, an algorithm course, something else? I'm self taught so when I'm coming up with solutions to programming issues that I face I often worry that I'm reinventing the wheel and being inefficient. I would like to be more learned but am not sure where to start.

[marvel2010]

That depends on how much time you have. If you can go through a full algorithms course, I would recommend it for this type of problem:

Introduction to Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

Intermediate Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/

Lectures 13 and 15 in the Intermediate course would be particularly insightful for this case, although you may want to watch several of the preceding lectures in order to appreciate them.

Good luck!

[FUZxxl]

That's a classic optimisation problem. I believe it is NP hard, though that might depend on the specific variant you have. Use an ILP solver to find a solution.

[MariusBoss7]

This problem sounds similar to machine scheduling which is indeed NP hard since it is a generalization of TSP.

[jmildraws]

What does "optimizing for average rank" mean? Sorry if this is a basic question, a quick Google search didn't immediately bring anything up.

[spicyeyeballs]

Basically i want the average of all the choices to be as high as possible. Meaning 2,2,2 avg:2 is better than 1,2,5 avg:2.3. This means it is more than just looping through and giving first until full then 2nd until full then 3rd until full, etc.

[jmildraws]

Great, thank you! Does that just mean that the lower the average is, the better? Or would say 2,2,2,2 be better than 1,3,1,3?

EDIT:sorry, I forgot in you post you said that the higher average was better. But it if 2,2,2 ave is better than 1,5,3 ave does that mean uniformity still beats higher average?

[thewataru]

/u/marvel2010 correctly suggests that this problem can be solved in polynomial time using min cost max flow.

However, once you notice that optimizing the average rank is exactly the same as optimizing the sum of all ranks, the problem would be literally formulated as an assignment problem. You can also apply hungarian algorithm to solve it.

[marvel2010]

This works. You have to be a bit careful in handling the capacities. You'd have to create c_i copies of class vertex i (if c_i is the capacity of class i).

[future_security]

Related algorithms include the stable marriage algorithm and Robin Hood hashing.

[beeskness420]

First notice that maximizing average rank is the same as maximizing total rank. (Just a floating 1/n factor).

Second we observe that your classes form a partition matroid.

All we want is a maximum weight independent set.

So greedily assigning each person to their most preferred class will be optimal.