Algorithm to allocate resources by priority

Question

My problem is the following: Me and my team are moving to another part of the office and we have to decide everybody's place to sit. However, everybody has priorities. I would like to find an algorithm which helps us to distribute the seats in a way that everybody is satisfied. (Or the most of them at least.)

I've started to implement my own algorithm where I ask 3 preferred options (the team consists of 10 people and there are 10 places) from everybody and consider there "seniority" (the length of the time they have spent in the team) as a rank between them.

However, I've stuck without any luck, tried to browse the internet for an algorithm which solves a similar problem but didn't find any.

What would be the best way to solve this? Is there any generally known algorithm which solves this or a similar problem?

Thank you!

Answer 1

What first comes to mind for me is the stable marriage problem. Here's the problem statement for the original algorithm:

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

Please read up on the Gale–Shapley algorithm, which is what I'll adapt for this problem.

Have each worker make a list of their rankings for all the spots. These will be the "men". Then, each spot will use the seniority ranking as their rankings for the "men". The spots will be the "women" in the Gale-Shapley algorithm.

You will get a seat assignment that has no "unstable marriage". Here's what an unstable marriage is:

1. There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and

2. B also prefers A over the element to which B is already matched.

In this context, an unstable marriage means that there is a worker-seat between W1 and S1 assignment such that another worker, W2, has ranked S1 higher. Not only that, S1 has also ranked W2 higher. Since the seats made their list based off the seniority list, it means that W2 has higher seniority.

In effect, this means that you'll get a seating assignment such that no worker has a seat that someone else with higher seniority wants "more".

The bottom of that Wiki article mentions packages in R and Python that have already implemented the algorithm, so it's just up to you to input the preference lists.

Disclaimer: This is probably not the most efficient algorithm. All the seats have the same ranking list, so there's probably a shortcut somewhere. However, it's easier to use a cannon to kill a fly, if the cannon is already written in R/Python for you. Also, this is the only algorithm I remember from uni, so this is the only hammer I have for any nail.

Answer 2

I decided to implement a brute force solution as lots of the comments suggested. So:

1. I asked everybody from the team to give a preference order between the seats (10 to 1, what I use as score the "teamMember-seat" pairings, 10 is the highest score)
2. collected all of the "teamMember-seat" pairings with scores e.g. name:Steve, seat:seat1, score:5 (the score is from the given order from the previous step)
3. generated all the possible sitting combination from these e.g. List1: [name:Steve seat:seat1 score:5], [name:John seat:seat2 score:3] ... [name:X seat:seatY score:X] List2: [name:Steve seat:seat2 score:4], [name:John seat:seat1 score:4] ... [name:X seat:seatY score:X] ... ListX: [],[]...
4. chose the "teamMember-seat" list(s) with the highest score (score of the list is calculated by summing the scores of the "teamMember-seat" pairings)
5. if there are 2 lists with equal scores, then the algorithm choose that one where the most senior team members get the most preferred seats of them
6. if still there are more then one list (combination) the algorithm choose one randomly

I'm sure there are some better algorithms to do this as some of you suggested but I've run out of time.

I didn't post the code since it is really long and not too complicated to implement. However, if you need it, don't hesitate to drop a private message.