Open space sitting optimization algorithm

Question

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?

Answer 1

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).

Answer 2

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.