[jschafer]

For our Msc course we all have to do one project out of 45 available projects. Each student needs to select 5 projects they would consider doing and rank them according to preference. Then projects will get assigned to students so that there is maximum happiness accross all the students (possibly assigning 'happiness rankings' to 1st, 2nd, 3rd, 4th and 5th choices). There are 45 projects and 33 students, the goal being to assign one project to each student whilst keeping as many students as happy as possible. Is there any sort of program to optimise this allocation of projects? If anyone knows of something (relatively simple) that can solve this problem it would be much appreciated =)

[kenberg]

Let's see if I understand this correctly: Each of the 33 students will indicate what project they would like to work on, then you will divide the students into five groups of six or seven students each, and each group will have a project?


If that is it, the following seems practical: Tell the students that they should list their three top choices and then two alternates. I am guessing, and it would be interesting to see, that you will be able to make up the groups with most of the students having one of their three top choices and all of them having one of of their top five. If students picked randomly this might not be likely but some projects will have broad appeal. If, out of 45 possible assignments, most get one of their top three choices this should make almost everyone reasonably happy.

No doubt other schemes could be tried but any assignment of happiness value will be arbitrary so I would go with simply using some plausible mechanism to give most people something that is satisfactory.

But I will be interested in seeing more sophisticated schemes. We actually use something like what I suggest in a setting of somewhat smaller scale. No heavy complaints.

[jschafer]

Sorry, I may have been a bit unclear by how I phrased it. There are 45 projects, out of which each student needs to select 5 they would be happy to do. In the end only one student will be assigned to one project (and no students for some projects as there are more projects than students). I'll edit the OP to make it clearer.

[TylerE]

How about this:

Have them fill out slips with their choices, in a ranked order. Place the slips in a hat.

Draw a slip at random. That person gets their highest ranked available project. If none of the five listed are available, put it in a seperate stack. Repeat until none are left in the bag.

If you have any in the second stack (If you're really lucky you won't!) Then those people get to pick for the list of remaining projects, in the order their slip was chosen.

I make no claims that this is optimal, but it seems fair (at least in the aggregate) and has the advantage of being easy to do.

[WellSpyder]

I like TylerE's solution. Anything based more explicitly on assigning a value to each person getting their first, second, third, choice etc and seeking to maximise the overall value runs the risk of distorting choices. For example, if I know my first choice is likely to be semi-popular, I may have an incentive to ensure my other choices are all from the popular category rather than the unpopular category, to maximise the chances that I will get my first choice.

[nigel_k]

I like TylerE's solution too and nobody needs to list their top five choices. Just randomly assign each student a number from 1 to 33. Whoever gets 1 picks first and so on. It's not optimal because the last person might be left with no project they like but some projects that are other people's second choice. But it is very simple and I think quite close to optimal.

For an optimal solution, I don't know what is best. Brute force would definitely take too long. I would start by counting up the number of unique projects chosen in any of the top five choices. If it is close to 33 then you have to start by assigning any of the projects that were chosen by exactly one person. If it is close to 45 you can start by trying to give as many people as possible their first or second choice.

Also, one of the projects should be to design a solution for this exact problem. That way you won't have to worry about it next year.

[hrothgar]

This looks like a fairly standard linear programming problem...

MathWorks produces some good software to solve these sorts of problems. (If your at a University, there is a good chance that you have free access to MATLAB)

The following online text book has a good introduction to the topic:

http://www.mathworks.com/moler/lu.pdf

[awm]

It's a weighted bipartite matching problem. It can be solved efficiently by an application of minimum-weight flow. Efficient solutions to this type of optimization problem are an area of continuing study in computer science theory; there are a number of good approaches and faster algorithms are being designed all the time. I'm not going to summarize the state of the art approaches here (see i.e. "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein for an introduction to this area).

Hrothgar is right that this can be approached via linear programming; however there are much simpler and faster algorithms available.

[Cascade]

hrothgar, on 2011-February-07, 14:16, said:

This looks like a fairly standard linear programming problem...

MathWorks produces some good software to solve these sorts of problems. (If your at a University, there is a good chance that you have free access to MATLAB)

The following online text book has a good introduction to the topic:

http://www.mathworks.com/moler/lu.pdf

I think we need integer solutions - a solution like 0.2 of each of your five choices probably wouldn't be ideal.

Which makes it an integer programming problem.

[awm]

Fortunately, matching-based linear programs are unimodular and always produce integral optimum solutions. Obviously this is not true of linear programs in general.

[barmar]

Isn't this the stable marriage problem?

[helene_t]

I would start by computing a "popularity" measure for each of the 45 projects and a "pickyness" measure of each student, based on the popularity of each student's choices.

Then I will first assign all projects that have been rated 1 by only one student to that student, and subsequently, among all projects that have been rated 1 by more than one student, assign the least popular one to the most picky of all students that had that project rated 1.

Continue doing this until the 1-ratings are exhausted, then continue with 2-ratings etc.

But as AWM says, this is a well-known problem so there is probably some free software out there that will do it in some clever way.

Ideally, the algorithm should
- give as little scope as possible to manipulation, i.e. students boosting their chances by being dishonest about their 2nd choice. My guess would be that all non-ridiculous algortihms are subject to some degree of manipulation but some will be less manipulatable than others, in some sense.
- be deterministic, i.e. not rely on monte carlo heuristics.

[awm]

barmar, on 2011-February-08, 00:04, said:

Isn't this the stable marriage problem?

No, because the projects do not have preference lists over the students.

[y66]

I like TylerE's solution. It is straightforward and pretty optimal in terms of understandability to kids, fairness and fun.

[kenberg]

It seems to me that the problem needs some further definition.

Thought experiment: You have three students. One algorithm provides two of the students with their first choice and the third student with his third choice. Another algorithm provides one student with his first choice and the other two students with their second choice. Which algorithm would be judged to be the better?

Of course with three students the algorithm would be to write down all the possibilities and see which you (perhaps invoking some subjectivity) think best. But for more students it seems to me you have to decide whether you prefer an algorithm that gives, say, 25 of the 33 students either their first or second choice but gives some students their fourth or even fifth choice to an algorithm that gives no one anything worse than their third choice but gives far fewer students their first choice. When I have done such things I have put a premium on having no one seriously unhappy even if that means fewer people are ecstatic. But it's a choice.

After such choices are made by a human, it would not surprise me at all that MatLab has a program for it. This doesn't sound like a problem no one has faced before.

[blackshoe]

The best algorithm gives me my first choice. All else is irrelevant.