Assignment problem or something else?

Question

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.

The question:

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.

More context:

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.

Scenario A:

• Alice gets 1st choice
• Bob gets 1st choice
• Charlie gets 3rd choice

Scenario B:

• 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?

Answer 1

General remarks

You don't seem clear yet on what it is you're trying to optimize. As such, this question is not well-posed and not solvable. The first step in such situations is for you to figure out an objective function that measures how happy you are with a given solution. That formalizes the specification of what you want. Until you can do that, it's not reasonable to expect a computer to find what you want when you're not even sure what exactly you want. Only once you have such a characterization of what you're seeking does it make sense to ask for an algorithm to solve it.

There are several things you might be trying to optimize. I'll answer for two of them.

Maximizing the total happiness

Suppose we imagine that there is some amount of happiness that occurs if you match a group to a project, and we want to find an assignment that maximizes the sum of happinesses.

This can be solved by finding a maximum matching in a bipartite graph. You have one vertex for each group and one vertex for each project, and an edge between a group and a project that describes the utility/reward if that group is assigned to that project. Then, use any standard algorithm for maximum bipartite matching, such as the Hungarian algorithm.

I'd suggest that you don't think of this in terms of ranked preferences (your #1 preferred project, your #2 choice) but rather in terms of ratings (e.g., I'd be 100 units of happiness if I'm assigned this project, 50 units of happiness for that one, etc.). Ratings are more powerful and encode more information than rankings: given ratings, you can infer what the rankings would be if you wanted, but it also contains extra information about how much more I prefer my #1 choice over my #2 choice. This can lead to a better solution. It does require people to provide more information about their preferences, but that additional information might lead to a better solution, so it seems worthwhile.

Maximum bipartite matching is a special case of the assignment problem, so you could also view this as an instance of the assignment problem: you can convert rewards to costs by negating the value (so a utility/reward of $10$ corresponds to a cost of $-10$), then running an algorithm for the assignment problem.

Maximizing the least-happy group

Alternatively, suppose you measure how happy you are with an assignment overall by how happy is the unhappiest group.

Then this too can be solved by maximum matching. A simple approach is to use binary search: guess a threshold $t$, build a bipartite graph with an edge from a group $g$ to a project $p$ if $g$ would have happiness $\ge t$ if assigned to $p$. (Ignore all other pairs $g,p$ that yield less happiness.) Then check whether there is a perfect matching in this group. If yes, then it is possible to find an assignment that assures all groups have happiness $\ge t$; if not, then it is impossible. Finally, do binary search on $t$ to find the largest $t$ for which such an assignment exists. The running time will be the time to find a perfect matching (e.g., using the Hungarian algorithm), multiplied by a logarithmic factor (for the binary search).

There may be faster algorithms, but this one is conceptually simple to understand.