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.