2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't think this is answerable, because I don't see a clear specification of what you want. "there's a lot of subjectivity in what constitutes acceptable tradeoffs" - if so, the problem is not a computer science problem. You need to figure out what you want (the problem specification) before it makes sense to ask for an algorithm to compute the solution you want. Are you perhaps asking for a solution that maximizes the happiness of the least-happy team? $\endgroup$ – D.W. Jan 12 at 3:25
  • $\begingroup$ I see what you're saying. I'm trying to think of a better way to define the most desirable solution. I'm visualizing plotting the assignments on a number line by preference. So there would be 8 points. Best solution is that they're all at 1, of course. Barring that, the best solution is the one where the cluster has the narrowest margin from left to right AND the greatest weight on the left side of the line (1-4). So a solution where a lot of the points cluster around 3 and a few cluster around 6 is better than one with a big cluster at 1 but a point at 8. Is that a clearer definition? $\endgroup$ – tmoore82 Jan 12 at 17:03
  • $\begingroup$ No, it's not clearer. Examples aren't a substitute for a general specification. It seems you are trying to specify two objective functions you want to simultaneously maximize. But you probably can't simultaneously maximize both, because typically the maximum for the first will be less than the maximum for the second -- so part of the heart of this is figuring out how you want to trade off between those two competing but incompatible desires. We can't tell you that; only you know what you want. $\endgroup$ – D.W. Jan 12 at 19:23
  • 1
    $\begingroup$ I still wonder if perhaps you value the overall solution according to the happiness of the least-happy team, and that's what you want to maximize. It seems consistent with the examples you've given so far. $\endgroup$ – D.W. Jan 12 at 19:24
  • $\begingroup$ I definitely do want to maximize the happiness of the least happy team. That's a great way to put it. I have a little hesitation about "dragging down" the group as a whole. I'm trying to define the tradeoff, but i'm falling short, it seems. Still thinking about it. Are there examples of solving for maximizing the happiness of the least happy team? What would that look like? $\endgroup$ – tmoore82 Jan 13 at 2:31
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer! I think I follow what you're saying about rankings vs ratings. But wouldn't it still solve for the most groups to get the highest utility even if one group gets the least? In other words, if 7 groups get their 100 choice and one group gets their 60 choice, that's subjectively less acceptable than if some groups sacrifice their 100 choice to 90 so the last group can get up to 80. I can imagine the totals adding up the same under the Hungarian Algorithm. Does that make sense? $\endgroup$ – tmoore82 Jan 11 at 20:45
  • 1
    $\begingroup$ @tmoore82, It doesn't make sense to me. I think you need to edit your question to specify exactly what is the objective function you want to maximize or what is the precise definition of what constitutes an acceptable or optimal solution. Without that, I don't think the question is answerable, as the problem is not well-posed. Given your example, I would have said that they are not altrustic; altruistic would be the best outcome overall for the group, even if some have to sacrifice. So it's not clear to me what kind of solution you desire. $\endgroup$ – D.W. Jan 11 at 23:58
  • $\begingroup$ Yes. That's right. The best outcome overall for the group, even if some have to sacrifice. That's a great way to put it. I'll edit the question and see if I can make that more clear. Thank you so much. That's really helpful language. $\endgroup$ – tmoore82 Jan 12 at 0:09
  • $\begingroup$ Yet in your example 7*100+60 sounds to me like a better outcome overall than 7*90+80, so something doesn't seem to add up for me here. I look forward to your edit. $\endgroup$ – D.W. Jan 12 at 0:11
  • 1
    $\begingroup$ @tmoore82, perhaps you want to minimize the gap between the happiest and unhappiest team, rather than maximize the total utility? If so, I suggest editing the question to ask how to minimize that objective function. Be warned that the best way to minimize the gap might involve making everyone unhappy, so be sure that that is actually the criterion you want to optimize... $\endgroup$ – D.W. Jan 12 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.