# Expected behavior of an algorithm to minimize rankings

Suppose $$n$$ students have preferences over $$n$$ different notebooks. Their preferences can be represented with a square matrix of size $$n$$ where each column is a different permutation of the vector $$[1:n]$$, where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.

For example, such allocation in the problem below

  1    2    2
2    1    3
3    3    1


would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.

My two questions are the following. If the matrix with preferences is chosen uniformly at random, what is the expected sum of rankings in the assignment that minimizes the sum of rankings?

Second, I can answer this question by running a simulation, but is there a known algorithm that efficiently finds the allocation that minimizes the sum of rankings?

Idea: In the best-case scenario, this sum is $$n$$. In the worst-case scenario, where each column is identical, the sum is $$n(n+1)/2$$. The expectation over all possible cases must be somewhere in between.

• Doesn't the allocation 1,2,3 have value 1+1+1=3? Apr 9, 2021 at 18:02
• @YuvalFilmus Each column, not row is the preference of one student. Apr 9, 2021 at 18:54
• But $1,2,3$ is the diagonal. Apr 9, 2021 at 18:55
• – D.W.
Apr 27, 2021 at 23:24

Finding the minimum matching is known as the assignment problem, and it has efficient solutions.

Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his "Case I". Parviainen showed that the expected value is between $$\frac{\pi^2}{6} n$$ and $$2n$$, and his simulation results suggest an intermediate value $$cn$$, where $$c \approx 1.830$$. See also the survey by Krochmal and Pardalos, Random assignment problems.

• Wikipedia summarizes the known algorithms. There are libraries implementing some of them. Apr 12, 2021 at 9:31
• Thanks. Just to make sure I get it: even as the number of students grows, the expected ranking of the notebook they each get is CONSTANT and around 1.83? This is remarkable that does not depend on n!
– fox
Apr 12, 2021 at 9:56
• It is quite amazing. One way to see it is that if you keep only a short prefix of each ranking, then you can still find a matching of almost maximal size. Apr 12, 2021 at 10:34
• Sorry for bothering, but are you familiar with any results regarding the expected maximum ranking? This is, what is the ranking realized for the worst student? We know on average is 1.8, but for the worst it seems 6.44 for 100 students and 7.04 for 200 students. Any idea on a theoretical result for this?
– fox
Apr 27, 2021 at 10:59
• If you’re interested in a different question, how about asking it as a new post? Apr 27, 2021 at 11:01