5

As a result of changes in the company, we have to rearrange our sitting plan: one room with 10 desks in it. Some desks are more popular than others for number of reasons. One solution would be to draw a desk number from a hat. We think there is a better way to do it.

We have 10 desks and 10 people. Lets give every person in this contest 50 hypothetical tokens to bid on the desks. There is no limit of how much you bid on one desk, you can put all 50, which would be saying "I want to sit only here, period". You can also say "I do not care" by giving every desk 5 tokens.

Important note: nobody knows what other people are doing. Everyone has to decide based only on his/her best interest (sounds familiar?)

Now lets say we obtained these hypothetical results:

#  | Desk# >| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
1  | Alise  | 30 | 2  | 2  | 1  | 0  | 0  | 0  | 15 | 0  | 0  | = 50
2  | Bob    | 20 | 15 | 0  | 10 | 1  | 1  | 1  | 1  | 1  | 0  | = 50
   ...
10 | Zed    | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | = 50

Now, what we need to find is that one (or more) configuration(s) that gives us maximum satisfaction (i.e. people get desks they wanted taking into account all the bids and maximizing on the total of the group. Naturally the assumption is the more one bade on the desk the more he/she wants it).

Since there are only 10 people, I think we can brute force it looking into all possible configurations, but I was wondering it there is a better algorithm for solving this kind of problems?

Georgy Bolyuba
  • 8,355
  • 7
  • 29
  • 38
  • 1
    May be related to http://en.wikipedia.org/wiki/Stable_marriage_problem – polygenelubricants Jun 11 '10 at 13:13
  • 2
    I think in practice you might want something more like minimum-disappointment rather than maximum satisfaction. Or at least some combination. – Doug McClean Jun 11 '10 at 13:27
  • @Doug: thanks for the hint :). It is possible – Georgy Bolyuba Jun 11 '10 at 14:08
  • @Doug: Giving it a second thought, I am not sure how minimum-disappointment is different from its maximum satisfaction. – Georgy Bolyuba Jun 11 '10 at 14:43
  • Or if you really want to make it interesting, add an extra round of bidding which reveals your assignment and the winning bid for each of the other desks. You could make the second round optional or mandatory, but it may result in a better overall result. – Grembo Jun 11 '10 at 14:44
  • I think it is different, imagine a reduced case. 3 chairs, 3 people, 10 points each. Person A: 3 6 1, B: 6 3 1, C: 8 0 2. Max satisfaction is C B A = 8 + 6 + 1 = 15. Min disappointment is A B C = 6 + 6 + 2 = 14. I suspect there are probably more interesting examples with more people. There has to be research on this, but I have no idea where. – Doug McClean Jun 11 '10 at 15:33

2 Answers2

3

You seem to be looking at the Assignment Problem which can be solved using Hungarian Algorithm. This is a well researched problem and you will probably find code on the web, ready to use.

In your case you can use cost = 50 - bid and use the above (any solution to assignment problem).

  • 1
    I am, frankly, amazed by your culture. It seems every time a question in algorithms is asked you just happen to know the name of the problem! – Matthieu M. Jun 11 '10 at 18:10
  • @Matthieu: I will take that as a compliment :-) Thanks! I guess the reason is that I am really interested in algorithms. Hopefully, I will still be able to remember all this in 5 years. Also, people usually ask some version of an already solved problem here, so that helps. –  Jun 11 '10 at 18:24
  • @Matthieu: anyone can google problems like this. It's answers like [this (link)](http://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element/2955527#2955527) that are truly impressive. – BlueRaja - Danny Pflughoeft Jun 11 '10 at 22:00
  • Yes I agree :) Especially since I did a double take on this post... gone too long without maths :) – Matthieu M. Jun 12 '10 at 13:58
0

Even faster, if you have Excel you should have a version of SOLVER available as well. Just set up your bid matrix (10x10 with bids), assignment matrix (10x10 with 0/1 assignments), use sumproduct(bids,assignments) to calculate the value of an assignment, make that your objective function, and add constraints so the there's only one assignment of people to desks and desks to people. Make sure you have the options> "linear model" box checked and "assume non-negative" and solve away ! I just set up a sample 10x10 problem - seems to work OK.

Grembo
  • 1,223
  • 7
  • 6