# Online tool to match up individuals with their top choice of a list

August 17, 2014 8:20 AM Subscribe

I'm teaching a class, and I am requiring my students to give a presentation on a topic. I'll have a set of topics drafted, and I want to avoid presentations on the same topic. My thinking is to ask each student to rank their preferences and then try to give each student their highest-ranked topic.
Is there an online tool that helps me do this? The SurveyMonkey type polling websites and google docs allow me to collect ranked choices, but they don't help me match up the highest-ranked choice of all my respondents.
Make sense? In the end I'd like to be able to say "Some people chose the same topic, so they got their next-highest topic where possible."
Thanks in advance for any ideas!

I was a Greek Life Advisor on a college campus, and I have done things like this MANY times!! I am on my phone so can't get super detailed with this so MeMail me and I can help you problem solve. First step is to set up a form that time stamps all submissions so you can say first come first served (and avoid playing favorites). You have that dump into a spreadsheet where each column is a persons choice. (So across the top of the page: Name, 1st Choice, 2nd, 3rd, Timestamp). When it's time to do assigning you sort by 1st Choice column, then By Timestamp. See who got it submitted first (if there is more than one) and assign that topic. Remove those students from the list completely by cutting and pasting their line onto a second spreadsheet. Once all the non matching first choices have been taken off the list sort by the second column and repeat.

Give everyone at least 24 hour notices before the form goes live so they can prepare to submit. This avoids complaining that they didn't get the email and couldn't get their first choice.

MeMail me and we can walk through it later tonight.

posted by MultiFaceted at 1:30 PM on August 17, 2014 [1 favorite]

Give everyone at least 24 hour notices before the form goes live so they can prepare to submit. This avoids complaining that they didn't get the email and couldn't get their first choice.

MeMail me and we can walk through it later tonight.

posted by MultiFaceted at 1:30 PM on August 17, 2014 [1 favorite]

This is an assignment problem! This might be a little more technical than you were looking for, but there are several different optimization techniques that have been developed to solve this type of problem. Usually they'll be stated in terms of "jobs" and "cost;" in this case the jobs are the topics and the cost is the amount each student will dislike doing that particular presentation - for example, you could say a student doing their first choice presentation has a cost of one, while a student doing their fourth choice presentation has a cost of four. When you put it this way, there are plenty of online tools to help you optimize your students' happiness.

This is one of the first ones that came up in google. You'll need to manually enter your students' choices, but after that it should tell you, using all the unbiased purity of math, which topics to match up to which students. Matrix size is the number of students. Then, just assign each student to be M1, M2... and each topic to be J0, J1... etc, enter their rankings in the matrix, and you're good to go.

posted by exutima at 8:14 PM on August 17, 2014 [1 favorite]

This is one of the first ones that came up in google. You'll need to manually enter your students' choices, but after that it should tell you, using all the unbiased purity of math, which topics to match up to which students. Matrix size is the number of students. Then, just assign each student to be M1, M2... and each topic to be J0, J1... etc, enter their rankings in the matrix, and you're good to go.

posted by exutima at 8:14 PM on August 17, 2014 [1 favorite]

Presumably, if you're having students give presentations, you don't have too many students, so just eyeballing and randomly breaking ties will probably work.

However, you will be unsurprised to learn that this sort of problem has been studied by mathematicians! In the version where people simply have sets of outcomes that they are equally happy with (e.g., Anne would be happy to present on any of Banking, Cooking, or Dental Hygiene), it's essentially Hall's Marriage Theorem (and there are algorithms) ; in the version where there are rankings, it's the Gale-Shipley Theorem. The AMS had a really nice feature column discussing these theorems and various algorithms.

posted by leahwrenn at 1:53 PM on August 18, 2014

However, you will be unsurprised to learn that this sort of problem has been studied by mathematicians! In the version where people simply have sets of outcomes that they are equally happy with (e.g., Anne would be happy to present on any of Banking, Cooking, or Dental Hygiene), it's essentially Hall's Marriage Theorem (and there are algorithms) ; in the version where there are rankings, it's the Gale-Shipley Theorem. The AMS had a really nice feature column discussing these theorems and various algorithms.

posted by leahwrenn at 1:53 PM on August 18, 2014

It sounds like you want to optimize the number of students that get their highest ranked choice. You can do this yourself using pieces of paper. Write a piece of paper for each topic and one for each student:

1. Next to each topic, put all the students that chose that topic as their first choice.

2. If a topic has 0 students, put that topic aside for now.

3. If a topic has 1 student, then that student gets that topic. Write that down and discard those pieces of paper.

4. For topics with more than one student, choose a student randomly. Then that student gets that topic. Write that down and discard that topic and student. Put all other students aside for now.

5. Keep going until you've gone through all the topics.

Now you're left with topics nobody wanted as their first choice and students who didn't get their first choice. Repeat the procedure above using the students

If there's still topics and students left, go to the third choice. Or stop at some point and match them up randomly.

posted by vacapinta at 7:23 AM on August 19, 2014

1. Next to each topic, put all the students that chose that topic as their first choice.

2. If a topic has 0 students, put that topic aside for now.

3. If a topic has 1 student, then that student gets that topic. Write that down and discard those pieces of paper.

4. For topics with more than one student, choose a student randomly. Then that student gets that topic. Write that down and discard that topic and student. Put all other students aside for now.

5. Keep going until you've gone through all the topics.

Now you're left with topics nobody wanted as their first choice and students who didn't get their first choice. Repeat the procedure above using the students

*second*choices.If there's still topics and students left, go to the third choice. Or stop at some point and match them up randomly.

posted by vacapinta at 7:23 AM on August 19, 2014

You are not logged in, either login or create an account to post comments

A brute-force method would be to make a spreadsheet that has columns for the name, 1st choice, 2nd choice, and 3rd choice. Sort by 1st choice, change the choice's cell's background color of everybody except those who choose the same as someone else, then sort on the 2nd choice column and change the background on cells of those who don't have a color in the 1st choice column, then do the 3rd choice column if any are remaining.

posted by rhizome at 9:53 AM on August 17, 2014