2
$\begingroup$

I have an assignment problem where I need to assign resources to consumers. Each consumer has a list of resources it'd like to acquire, ordered by preference, and each consumer can have at most one resource. I'd like to find a mapping from the resources to the consumers that tries to satisfy each consumer's preferences.

The twist on the classic assignment problem here is that I'm not necessarily interested in an algorithm which produces the optimal solution. Rather, I'm interested in an algorithm that's simple enough a lay person could do it in their head, or at least part of it in their head at a time.

See, my resources and consumers are embedded in a (hex) grid where a resource and a consumer have to be on adjacent cells to be matched, so the graph is really quite sparse. An ideal algorithm would only use "local" information, such as information about a cell and its neighbors.

An added wrinkle is that whatever algorithm should produce a stable result regardless of the choice of ordering the resources and consumers, either their inherant ordering or an algorithm-chosen ordering. So just walking down the list of consumers from first to last, either their actual ordering or an invented ordering, giving them each their first pick of the remaining resources won't work, because the final assignments might change under a different ordering.

As an example of a possible algorithm, I could assign a resource only if there is exactly one consumer that wants that resource as its first choice, otherwise it doesn't get assigned. Certainly not perfect but it meets all the requirements above while giving a reasonable matching.

Are there any other algorithms worth considering here, or any relevant literature to read?

New contributor
Jay Lemmon is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • $\begingroup$ "explainability" is related to the black-box problem in modern ML, but instead of trying to explain to a software engineer we're aiming even lower and trying to explain to a lay person, and not just explain, but have a lay person make accurate predictions about what the results are going to be. An explainable solution is likely also a suboptimal solution, so there needs to be some wiggleroom on that account. 2. A randomly imposed ordering isn't going to predictable to a lay person. 3. I wasn't aware of the stable marriage problem; I'll see if there's relevant ideas I can use. $\endgroup$ – Jay Lemmon Jul 20 at 11:56
  • $\begingroup$ More like an algorithm that is simple enough you could run it in your head. $\endgroup$ – Jay Lemmon Jul 20 at 18:13
  • $\begingroup$ I've reworded the question. Is it clearer now? $\endgroup$ – Jay Lemmon Jul 21 at 0:04
  • 1
    $\begingroup$ Looks great! A quick check: if you sort the consumers by lexicographic order, then walk down them from first to last and assign each their first pick of the remaining resources, it sounds like that satisfies all of the stated requirements. If you're not happy with that solution, maybe check whether there are any other requirements? $\endgroup$ – D.W. Jul 21 at 0:26
  • $\begingroup$ I specifically call that out: "An added wrinkle is that whatever algorithm should produce a stable result regardless of the ordering of the resources and consumers. So just walking down the list of consumers from first to last giving them each their first pick of the remaining resources won't work." $\endgroup$ – Jay Lemmon Jul 21 at 21:43

Your Answer

Jay Lemmon is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.