search

daffidwilde / matching

A package for solving matching games
https://daffidwilde.github.io/matching/
MIT License
149 stars 42 forks source link

Matching with weighted capacities #141

Open rawls238 opened 1 year ago

rawls238 commented 1 year ago

I’m wondering if there is a possibility to have different “students” have different weights? For instance, in a matching problem where a student can take half a slot or a full slot [depending on their preferences], is this supported by the library?

daffidwilde commented 1 year ago

Hi @rawls238 👋

Thanks for opening this issue.

That is not something you can do in matching right now, but I would be interested to know if you get anywhere with it. While I was developing this package during my PhD, I was helping my department assign dissertations to final-year students and came across this very problem. In their case, fourth-year MMath student projects were worth double the credits of a BSc project, and supervisor capacities were defined by the credits of their students. In the end, they found a reasonable solution via linear programming.

I'm not sure whether the game-theoretic maths falls out nicely for a weighted student-project allocation (wSA) problem. In the simplest case I can think of, where students are integer multiples more than others, wSA can be reformulated as an instance of SA with ties in supervisor-project preferences. As far as I'm aware, there is no "nice" algorithm for finding a stable matching to such a problem.

I may be wrong, and if you find something or come up with an idea, I would heartily welcome a pull request.