My primary goal with this question is to identify the type of problem I have so I know what solution to pursue. I think it's either an instance of the assignment problem or the fair item allocation problem, though I can also envision a solution that involves a variation on the stable marriage problem.
Is there an existing definition of the assignment problem where the solution is not to get as many people as possible their #1 option, but to get the group as a whole the highest preference level of assignments? In other words, the important thing is not that "as many agents as possible get their highest preference." An agent will sacrifice a higher preference for a slightly lower one if it means that another agent will move up to a higher preference.
Example: Alice would not swap her 1st preference for her 8th so that Bob can get from his 7th to his 6th. But Alice would swap her 1st for her 3rd if it means Bob gets from his 8th to his 4th.
Obviously, there's a lot of subjectivity in what constitutes acceptable tradeoffs, but I'm thinking about ways to define and account for that.
If I visualize it as ships in a harbor, the ideal solution is one where it's a calm day, no movement on the water. Everybody is at the same level--hopefully at high tide. :) Solutions that are more stormy, where some or a lot of ships are up while others are down, are less desirable, even if the average level among them is high.
I think the term for what I'm not looking for is rank-maximal allocation. I can't find the term for the solution I do want. But this may just be a gap in my understanding.
I'm coming to these as a layman, so I'm lost in some of the formal notation and theory, though the concepts are generally clear enough. This is very much a "down the rabbit hole" situation for me. My wife has an event at work where she has to assign groups to projects. She usually does it by hand, and she asked me if there's a program to do it. I said, "There must be." Now that I know how much I don't know, I'm looking for a nudge in the right direction. :)
Here's my scenario: 8 groups, 8 projects. Each group can have one project, each project one group. Each group submits an ordinal preference for which project they would like to have (1 for the most preferred, 8 for the least). The goal is to find the best combination of assignments for the groups as a whole.
To give a simple hypothetical example. The following two scenarios are available.
- Alice gets 1st choice
- Bob gets 1st choice
- Charlie gets 3rd choice
- Alice gets 2nd choice
- Bob gets 2nd choice
- Charlie gets 2nd choice
All of the agents will agree that Scenario B is preferable. No one gets their 1st choice, but no one has to accept their 3rd.
The assignment problem is a good fit except, as I understand it, the solutions all value giving as many agents as possible their #1 choice, or finding the "lowest cost" solution. So solutions to the assignment problem would find Scenario A above to be the better solution. In my scenario, the best solution may not include anyone getting their 1st choice. All agents would gladly trade their first choice for their second or third if it means another agent gets to move up from a low preference to a higher preference.
This Q&A made me look at the stable marriage problem, but the issue I run into there is that the projects have no preferences. So I thought, well, maybe I can do SMP with indifference, where one side is completely indifferent. But my gut tells me that's the same thing as the assignment problem. I need the suitors to care about each other's outcomes almost as much as their own.
My next stop was the fair item allocation problem. I think this might be closer to what I'm looking for, but I struggled to understand all the different fairness criteria. It felt more complex than the problem I'm trying to solve, though I may be underestimating my problem.
I'm tempted to use this Hungarian Algorithm solver. My gut is that it would be highly likely to produce an acceptable solution. My problem is that I can't stop thinking about whether or not there's a more optimal solution.
I think with my level of knowledge here, my trying to cook up hypotheticals might just be more confusing. But I'll try to reemphasize the standard the ideal solution would meet, barring everyone getting their 1st choice:
- gap between "best" (most preferred) and "worst" (least preferred) assignment is as close to 0 as possible
- maximum number of assignment possible are "highly preferred" (say in the 1-4 range)
- it is acceptable to grow the gap to increase highly preferred assignments up to a point -- we can thin the cluster to shift its preference value higher, but we don't want to drop anyone too far.
The solution I'm thinking of now would be something like this: use the Hungarian Algorithm to get the rank-maximal allocation, then implement some kind of a swap meet where each agent considers his neighbor to see if a trade would result in a better overall outcome. I don't want to go too far down that path if I'd be ignoring a better solution. Or if the Hungarian algorithm is the solution and it's just a matter of getting over my own mental blocks. :)
Which type of problem do I actually have? Other than that I can't stop thinking about this?