I need some insight for the following problem:
There are 100 girls and 100 guys. The girls each have their individual preference list for which guy they’d like to marry. Each list contains all 100 guys in the order of the girl’s preference. We’d like to match them up as well as we can according to their preferences. To measure how well we’re doing, we assign each match a number: the number of the guy on the girl’s preference list. So if a girl gets to marry her 2nd choice, for example, we assign the number two. We’d like to keep the sum of numbers for all the matches as small as possible. What is the number we’ll get in the worst case?
Due to the symmetry, the guess is that the answer is $5050$ which is attained at all girls having same preferences, however I am not sure how to prove that. I've tried both backward induction (how does the last girl choose, how the second last one does) and forward induction (what if there are only 1 girl, 2 girls etc) however no firm proof yet. I think the argument also may be of the kind: by deviating from the profile when all the girls have the same preference list, we necessarily decrease the number.
If the preferences are all the same, the score will be $1+2+3+\cdots+100=5050$ for any matching. I claim that, for arbitrary preferences, we can always find a matching whose score is no greater than $5050$.
Namely, order the girls, and let each girl in turn take her favorite available guy. (This may not be the optimal procedure, but we don't care.) The $n$th girl gets one of her $n$ favorite guys (since at most $n-1$ of them have been taken), so her score is at most $n$, and the total score is at most $1+2+3+\cdots+100=5050$.