How to give away a limited number of items as fairly as possible?

October 27, 2005 7:20 PM

How to give away a limited number of items as fairly as possible?

I work for an organisation which sometimes gives away free books, CDs and stuff to people on a mailing list who write in and ask for them. (Long story, and no, you can't join, sorry!)

Say we have 20 books to give away. We send out that list and thirty people write in and say "I would like Book A please" etc.

I've asked them to state a preference, to make it easier. So what they do is actually say "I would like, in order of preference, Book A, Book B or Book C".

So now I've got twenty books, and thirty people asking for them.

If the matrix looked like this, there'd be no problem:

Item    1st        2nd        3rd
--------------------------------------
Book A  Person 1   Person 3   Person 4
--------------------------------------
Book B  Person 4   Person 1   Person 3
--------------------------------------
Book C  Person 2   Person 5   Person 2 
--------------------------------------
Book D  Person 3   Person 4   Person 5
--------------------------------------
Book E  Person 5   Person 2   Person 1

(Hope that comes out OK in your browser. Looks OK on preview. Monospaced font will line everything up.)

Because in that perfect world, there are five books and five people and everyone's got a first choice which is nobody else's first choice.

What happens of course is more like this:

Item    1st        2nd        3rd
--------------------------------------
Book A  Person 1   Person 3   Person 4
                   Person 2   Person 2
                              Person 7
--------------------------------------
Book B  Person 4   Person 1   Person 3
        Person 2
        Person 5
        Person 3
        Person 6
        Person 7
        Person 8
--------------------------------------
Book C             Person 5
                   Person 6
--------------------------------------
Book D             Person 4   Person 5
                   Person 8   Person 6
--------------------------------------
Book E             Person 1   Person 8
                   Person 7   
--------------------------------------

with lots of people nominating popular items, lots of "holes", and more people than items.

What would be your strategy for maximum happiness here? In other words, what's the best way to make sure the greatest number of people get their highest-number choice?

posted by AmbroseChapel to grab bag (11 comments total)

I'm confused by your 2nd set of sample data:
Person 2 has chosen book A as both their 2nd and 3rd choice?
Person 3 has chosen book B as both their 1st and 3rd choice?
Person 1 has two 2nd choices?
...Am I reading the data wrong?
posted by juv3nal at 7:52 PM on October 27, 2005

Take the first email. Go down their choices in priority order until you find a book you still have. Give them the book and delete their email. Repeat until you run out of books.

This prioritizes those who are speedy, but that is considered a fair metric for this kind of thing and makes your life a lot easier.
posted by smackfu at 7:57 PM on October 27, 2005

After you took the trouble to type out those charts, I hate to say it, but smackfu's answer is fairest and by far simplest.

You could also keep a spreadsheet of the people on your mailing list, then track some "score" of how often they get what they want. For instance, if they get their first choice, say that's 3 points, second choice 2 points, third choice 1 point, then hand things out so that people with the lowest amount of points get what they want first until things equalize.

But that's still pretty lousy. Go with first come, first served instead.
posted by Hildago at 8:19 PM on October 27, 2005

Book A - Person 1
Book C - Person 5
Book D - Person 4
Book E - Person 7
Book B - random drawing betwee people 2,3,6,8
posted by croutonsupafreak at 8:56 PM on October 27, 2005

I have to do this kind of thing when assigning students in classes to their top choices in groups. It's important to me that they get (if possible) something on their list because I want them to be invested and interested in the topic.

I have them give me their top five choices on 3X5 cards (the more choices, the more of a likelihood you'll give them something they want) and then I separate them out into stacks by their first choice. There are lots of holes - sometimes no one wants a particular group as their first choice. So I go through the piles with lots of people and see if any of those had something in their second or third pick and put them in that catagory. You often have to eyeball it, but I find the process also lets me get a better feel for what is popular and what isn't.

Once you've spent a bit of time with it, when person F lists as their number 5 choice a less popular group, guess what - they get it! Because they at least listed it.
posted by mulkey at 8:59 PM on October 27, 2005

I'm assuming you thought of sending them out in order of first come first served basis. For your example I'd choose:

A = 1 (1st)
E = 7 (2nd)
C = (5 or 6) (2nd)
D = 8 (2nd)
B = 2, 3, 4, (5 or 6) (1st choice)

none = 3 people

2 people will have their 1st choice (the maximum possible with the rest will having their 2nd choice).

That's assuming that their 1st choice will make them a lot happier than their 2nd choice (where they might be indifferent and were forced to rank). Perhaps you can allow them to have a tie for 1st choice, 2nd choice etc. to show that they'd be just as happy with book B as with a different book.

I'd also keep track of which choice they received in previous months. You could also inform people that you're keeping track so that if they really don't want anything they should specify that they don't want anything (and increase their chances of getting something they want later on).

You could also set up a sort of bidding / auction style attempt. Give everyone 100 points for the entire year. Ask them how much points they'd bid for each item. Award the item to the highest bidder, when they run out of points no more items for them. Can also have a system to reward people who aren't bidding (maybe like a bank account - say 5% a month). This might only work well if you have similar items of comparable quality to give away each time.
posted by curbstop at 8:59 PM on October 27, 2005

How I came at that:

1. For the book that only one person put as first choice, let him/her have it.

2. Once you eliminate that person from the running for other books, you know you have Person 7 wanting book E more than anybody else. Let him/her have it.

3. For the remaining books that nobody chose as first choice, randomly choose between the people who put it down for second place.

4. Award the extremely popular Book B to one of the people who put it down as first preference and hasn't been given a book yet. Make your selection of the winner through a random drawing.
posted by croutonsupafreak at 9:00 PM on October 27, 2005

Sorry, juv3nal is quite right, there are some errors in my second table. The point is still the same though.
posted by AmbroseChapel at 10:23 PM on October 27, 2005

And I should also have said, I particularly don't want to use first-come, first-served as a criterion because there are big disparities between the people's access to email.

But I do like Hildago's idea of adding "how well they made out last time" as a criterion. That tends to maximise happiness over time, if not for any particular mailout.
posted by AmbroseChapel at 10:31 PM on October 27, 2005

Ask them all to rank their preferences. They have to rank them all (if they can't be bothered, they don't deserve a free book).

Sample of 5 people ranking 5 books:

P1: 1, 2, 3, 4, 5
P2: 1, 3, 2, 5, 4
P3: 1, 5, 4, 2, 3
P4: 2, 1, 3, 4, 5
P5: 4, 3, 1, 2, 5

Now assign a value to each book. Each 1st place vote is worth 5 points (the value of a 1st place vote is equal to the number of items), 2nd place vote is worth 4 points, etc. The 5 books are valued 21, 16, 17, 13, 8.

Now determine the average value and total value of all the books by multiplying each book's value by its relative place in the value order. E.g., book 1 is 21 x 5, book 3 is 17 x 4, book 2 is 16 x 3, book 4 is 13 x 2, book 5 is 8 x 1. Total is 255; average is 255/5 or 51.

Now go back to each person's book ranking and weight each ranking by the book's value (e.g., multiply the book's value by the rank value -- rank 1 is 5 points, rank 2 is 4 points, etc.). The list would look like this:

P1: 105, 64, 51, 26, 8
P2: 105, 48, 68, 13, 16
P3: 105, 16, 34, 52, 24
P4: 84, 80, 51, 26, 8
P5: 42, 48, 65, 52, 8

Now look for values that are closest to the average. P1's third choice (book 3) is worth 51 points, which is the average, so that person gets book 3. Eliminate that book and that person from the grid and repeat. (Note that person 4's 3rd choice was also worth 51 points. See below for tiebreakers.) P3's second choice (book 4) is worth 52 points, so give him book 4 and eliminate both the book and P3 from the grid. Continue until all books and/or people have been eliminated. The final distribution would be P1: book 3, P2: book 2, P3: book 4, P4: book 5, P5: book 1.

It's obvious that the distribution is affected by who comes first in the list when you're looking for scores close to average. If two people have the same point value for a combination of desire x book popularity, the one higher up the list will be chosen. However, by keeping a running total of the value of the received items, you can move those with lower cumulative scores higher on the list. After this round, the cumulative scores would look like:

P1: 51
P2: 48
P3: 52
P4: 8
P5: 42

The next giveaway, list the people in reverse order of their cumulative points so that they get any tiebreakers.

This method will drive each person's total gifts to an average that is a function of their preference for an item and the overall popularity of that item. A person is not likely to get his first choice unless that choice is very unpopular; the last choice is also not likely unless that choice is very popular.

As you can see, a large number of people and/or items will make this unwieldy. You will be driven to a spreadsheet or database program very quickly as the population grows.
posted by forrest at 12:52 AM on October 28, 2005

Randomize. Give book A randomly to someone from the group that ranks it higher than any other group of people do. Give book B randomly to someone from group of people who rank it higher than any other group of people do.

Don't worry about keeping track of anything. Maybe this time someone gets two books, and someone else gets none. Okay. Next time the situation might reverse. In expectation, people get books they value relatively highly with equal probability.
posted by ROU_Xenophobe at 5:49 AM on October 28, 2005