How do I figure out how to divvy out these projects?

January 22, 2013 4:16 PM

I have roughly 20 people who each need a project. I have 27 projects and don't want anyone to share a project. I let the people pick their top five projects and rank them so I know who wants what. What is the best (easiest...) way for me to fairly figure out who should get what project so that the most people get their top choice, or at least one of their top choices?

This isn't some homework problem, I promise. I am teaching a class and have 20 poster topics I want my students to do and I gave them 27 options, and now I don't know what to do with all these "vote" sheets they handed back to me...

posted by pwb503 to education (8 answers total)

Well, I'd start by working backwards - if there is a topic that only one person ranked as #1, there you go. If you have more than seven topics no one wants, that's a problem I'm not sure how you solve.
posted by dpx.mfx at 4:25 PM on January 22

First- you need to accept that some people will probably get assigned a project that's not one of their top picks. This depends on the specifics, but generally the distribution of top projects will be quite uneven.

Here's what I would do: Make a spreadsheet- the exact layout depends on how you think, but you want to see the projects and the project ratings- maybe you do 5 rows for project 1 and each is a rating- like project 1 1st choice, project 1 2nd choice, etc etc...

Then you go through peoples cards, and mark down their initials in the columns that apply to their choices. Then you would use a grouping/summary function to see the projects that have the highest/lowest ratings.

You want to assign the lowest rated projects 1st. So project 14 had only 1 person rate it as their 1st choice, then assign it to that person... if project 6 had 11 people rate it as their first choice, it should be assigned much later.
posted by sarahnicolesays at 4:27 PM on January 22 [1 favorite]

Also- if you have to give more than a handful of people a project thats not in their top 5, I would switch the system so that there are less (or few overall) people getting their top project. It seems more fair to me that everyone be a little disappointed and not get their pick. For future reference, A good way of doing this is to have an equal number of votes per project, and people cast their votes in a random or arbitrary order.
posted by sarahnicolesays at 4:30 PM on January 22 [1 favorite]

Put the students in random order - Use excel or pick them out of a hat or just alphabetize by the third letter of their last name (which isn't really random, but okay).

First student gets his first choice.
Next student gets his highest available choice.
And so on.
If none of the person's five choices are available, they'll need to pick from the remainder.

At worst - someone is going to get on of the choices in his top 20%. Don't sweat this more than you need.
posted by 26.2 at 4:51 PM on January 22 [3 favorites]

First, you need everyone to rank all projects, not just their top 5. But you still run into the problem where everyone returns the same ranking, which merely tells you what the project popularity is but does not tell you who to assign the projects to.

So you either do the ranking, find the outliers (projects desired by only 1 person), then assign the rest based on random selection from all those who were the most interested in a project (e.g. 5 ppl liked project #3, then choose one of them randomly).

Normally in this situation, you give up on anything fancy and assign projects randomly (which is truly fair), then let the students do any project-trading if they wish.
posted by jpeacock at 4:53 PM on January 22

In theory this is a 'hard' problem, something like the famous traveling salesman problem, and you could do a lot of tricky programming work to find the best, most optimal solution, blah blah blah.

However, you don't need the best, most optimal solution--you just need a quick & easy 'good enough' solution. Here it is.

1. Number 27 spots with the numbers 1-27. (Maybe 27 post-it notes or something.)

2. Shuffle your votes sheets so they are in a random order (for fairness)

3. Go through all of the vote sheets and place them on the number of their highest vote that is not yet taken. (Example: Someone voted for 3,5,7,12,14. So you put it on Spot 3. Next vote sheet is 3,7,11,14,21--Spot 3 is taken so you put it on Spot 7. Next vote sheet is 3,7,8,12,15--Spots 3&7 are taken so you put it on Spot 8. Etc.)

4. When you get done (or perhaps even before--if someone has voted for 5 choices that are already taken by previous vote-sheets) you will see some results that you consider sub-optimal. These are people who have their 4th or 5th choice or maybe don't fit anywhere at all. For these, do a simple swap*--if this person has their 5th choice or whatever, look at their 1st, 2nd, & 3rd choices & see if you can swap one of them to make the 5th choice person better off & the other person not too much worse off.

(Example: Vote Sheet in Spot 20 has choices 1,2,4,6,20 (has their 5th choice). Vote Sheet on Spot 2 has 2,20,4,23,1 (has their 1st choice). So you swap them--now they both have their 2nd choice.)

5. Make a few swaps until you are satisfied.

6. Write down the results--You're done.

The super-high-powered mathematical theory that makes this work, is the fact that you can get from any configuration to any other by repeated swaps of two elements. You start out with a pretty decently optimal configuration (by putting each sheet on its highest available choice) and then since you are an intelligent person, you'll be able to move it to a pretty optimal state by just doing a few swaps. Keep swapping until your swap doesn't seem to be making things any better and you pretty much are guaranteed to have a somewhat optimal solution.

You'll be able to get this done start to finish just by sorting out the papers this way, in a shorter amount of time than it would take you to type them into an Excel spreadsheet or any other such fancy techno-solution.

*You could also do a 3-swap or 4-swap or two if you can see one that works for all parties
posted by flug at 4:55 PM on January 22 [2 favorites]

This is an Assignment Problem. It can be solved easily using the solver tool in excel. The cost of giving a poster to a student is the rank (1,2,3,4,5). The constraints are that each student can have only 1 poster, and each poster can have only 1 student.
posted by mataboy at 5:43 PM on January 22 [3 favorites]

Post it notes and ten minutes of moving things around. I figured this would be easier with a computer but I am so glad I didn't waste any time entering all that data....
posted by pwb503 at 6:05 PM on January 24