The Problem: There is a pool of N options and there are N users, and each user is assigned exactly one option, and each option is assigned to exactly one user (no repeats on either side). Each user submits a ranked list of the options, ranking them from 1-N. The algorithm aims to assign each user an option so that the average rank of the assigned option in that user's ranked list is minimized across all users.
The Theoretical Approach: So the exhaustive, comprehensive solution would be to would cycle through each possible arrangement of the N options across the N users, and to determine which arrangement leads to the lowest sum of ranks from each user's respective list. However, this is an N! problem, and it quickly becomes impractical to solve computationally.
My Question: Since the theoretically perfect approach is unrealistic from a computational perspective (would take hours of computation or a powerful computer for even something like N=30), I'm asking if there's any algorithms or approaches that can get me the optimal or near optimal distribution of options across users with a realistic amount of computation. Maybe some sort of sampling or filtering could return the near-optimal approach with a large reduction in the number of total operations? I don't think there's any way to arrive at the optimal solution without brute force, but something near-optimal could be sufficient.
**EDIT: ** While solving this problem computationally is unrealistic, the problem I described is known as the House Allocation problem. The "fairest" solution to this, which is Pareto-optimal, is the Serial Dictatorship approach, described at these links: https://jeremykun.com/2015/10/26/serial-dictatorships-and-house-allocation/ https://en.wikipedia.org/wiki/Random_serial_dictatorship
This problem is similar to the Stable Marriage problem, as mentioned in comments, with the difference being that only one side ("users") has any preference of the other side ("options"). The "options" side has no ranking system of "users". This appears to be termed the House Allocation problem, described in this post.
My initial consideration was that this problem could be theoretically solved (given infinite computing), by cycling through each possible arrangement of pairings ("users" to "options") and selecting the arrangement that minimized the sum (or mean) of the ranks that each user was matched to. However, that appears to be somewhat misguided, and the "fairest" way to solve this problem is to achieve a pareto-optimal condition (described in the post). Pareto-optimal refers to a set of pairings where there is no other pairing that would satisfy both conditions:
In simpler words, pareto-optimality is achieved when no one can be made happier without making someone else less happy. This is logically the "fairest" setup that can be achieved.
The algorithm to best solve this is a Serial Dictatorship, or more likely a Random Serial Dictatorship (initial order of "users" is randomized so that no preference is given in the selection order).
A (random) serial dictatorship works by going down the (randomized) list of "users" and assigning each "user" their top-ranked "option" from the available pool. The selected "option" is then removed from the pool.
It's easy to see why this is the fairest approach - when it comes turn to pick (or be assigned), each "user" will make the best possible decision available, meaning that no one will regret the decision they made and want to swap.
Interestingly, my seemingly complicated problem was solved by a simple approach of "everyone takes turns picking from the pool"