3
$\begingroup$

The problem I want to solve is my residential building's garage choices.

There will be a random distribution of parking spaces. I thought that it would be better if each person writes down which spaces they want in order of preference, and then their priority of picking a parking slot is randomized. For instance:

  • Person a chooses: p3, p5, p1, p2, p4
  • Person b chooses: p3, p1, p2, p4, p5
  • Person c chooses: p1, p3, p2, p5, p4
  • Person d chooses: p1, p5, p2, p3, p4
  • Person e chooses: p2, p3, p4, p5, p1

Then we would simply randomize the persons a thru e and it would be easy to define who would get what.

I want to use Google Forms to gather people's choices of priorities. Then I would randomize the order of choosing using random.org. And then I want to use Google Sheets to give the best spot to each person.

This mock-up data set has only 5 persons and 5 parking spots. The real life data set has 100 persons and 100 parking spots.

Gathering data is simple, randomizing is also easy. I’m having troubles coming up with the formula that would check what has already be chosen, return the best available spot for that person, and then jump to the next.

It seemed simple, but I tried a bit with vlookup (and it would lead to a enormous clumsy formula) and I have had poor success with index / match.

Improve this question
$\endgroup$
7
  • $\begingroup$ If you guys seem that this question is inadequate to this forum, could you please help me finding a better place for it? $\endgroup$
    – Heleno Paiva
    May 23, 2022 at 11:51
  • $\begingroup$ Note that if there are 100 spaces and 100 people, each picking their top 5 is no guarantee that they will each get one of their preferred spaces. $\endgroup$
    – Luke Sawczak
    May 23, 2022 at 20:06
  • $\begingroup$ @LukeSawczak oh! Sorry for my lack of proper explaining the problem; I intend that each person ranks ALL 100 spots according to their preference. This way we will have a list with 100 persons and each person will have 100 ranked options. $\endgroup$
    – Heleno Paiva
    May 24, 2022 at 0:18
  • 1
    $\begingroup$ here's an alternative to luke's - this one picks everyone's first choice first, filling in duplicates with the second choice (and so on, for each choice). ideally it'd do at least a bit better, since it tries to pick as many first choices as possible (/tries to pick the first choices all at once). note that for this approach you would need 100 columns of formulas though... $\endgroup$
    – somebody
    May 24, 2022 at 0:35
  • $\begingroup$ @somebody Nice idea. But I think it comes to more or less the same thing -- except that without the random order, the top people will definitely come out better. Swapping their order is similar to doing this but just putting different people on top. But it would be interesting to compare the scenarios between these two algorithms and see which get better "scores" for satisfying people's highest possible picks. $\endgroup$
    – Luke Sawczak
    May 24, 2022 at 2:21

3 Answers 3

Reset to default
4
$\begingroup$

I do not know how to do this on Google Spreadsheets either, but there is an algorithm (Gale Shapley Algorithm for Stable Matching problem) that has runtime of $O(n^2)$ which is much better than $O(n!)$ for the other answer, and is also optimal.

For details, see https://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithmic_solution and https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm.

The Gale–Shapley algorithm involves a number of "rounds" (or "iterations"):

In the first round, first a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her.

In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, she rejects her current provisional partner who becomes unengaged). The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).

This process is repeated until everyone is engaged.

In your problem, the "unengaged man" are the people without a parking lot assigned, and "unengaged woman" are the parking lots.

Improve this answer
$\endgroup$
2
  • $\begingroup$ in what way do garages "prefer" one occupant over another? how would that part of the system work? $\endgroup$
    – Esther
    May 23, 2022 at 21:00
  • 1
    $\begingroup$ @Esther that is a more specific case of the general algorithm. In this case, we assume all garages "prefer" every occupant equally. That is, the case "if she prefers this man over her current provisional partner" never occurs (just skip the check). Alternatively, we can assume each garage prefers person 1 the most, then person 2, then person 3, etc. It does not matter with the context in the OP's question. $\endgroup$
    – krbcaypwd
    May 23, 2022 at 21:14
3
$\begingroup$

The problem can be seen like this: the goal is to assign a spot $s_i$ to every person $p_j$, with $1 \leq i \leq N$ (number of spots) and $1 \leq j \leq M$ (number of persons).

I'm rusty about combinatorials, but if I'm not mistaken this means that an assignment is an ordered sequence of $M$ elements chosen among $N$ without repetition. Thus this a permutation without repetition and the total number of possible assignments is:

$$\frac{N!}{(N-M)!}$$

If $M=N$ this is the same as regular permutation: $N!$

The brute-force solution would be write a code which enumerates all the possible assignments and assigns a score to each of them based on the preferences. For example this score could assign 10 for every person who has their first choice satisfied, 9 if they have their 2nd choice satisfied, ... until 0 if none of their 10 top choices is satisfied. After calculating this score for every possible assignment, the solution which obtains the maximum score is optimal: it satisfies the highest number of people with their most prefered option. Of course the scoring is very important, for example a more heavy penalty might be counted when somebody has none of their preference satisfied.

This requires a bit of programming, I don't think this is doable with Google Sheets only (at least I don't know how).

Even with programming, this is going to be tricky with $N=100$, because $100!\approx 9.10^{157}$...

For this kind of problem I would normally recommend a genetic algorithm, which should be able to find a local optimum much faster than the brute-force version. It's a bit advanced of course.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh this quite a formidable thinking! But there are two points to consider: 1- there is 100 persons and 100 parking spaces. So: there is no chance of not having any parking space. Everybody will have one. 2- there will a random drafting. I’m not seeking the ideal solution. There will be a randomization: there is no alternative to it by now. I just want to make the process faster. Last time this whole ordeal was made with pen and paper anda huge ballot. Can you believe it? $\endgroup$
    – Heleno Paiva
    May 23, 2022 at 17:29
2
$\begingroup$

Here's a sheet I made that does it for you.

Parking Space Allotter

The strategy:

  1. Column A is a person's name.
  2. Columns B-F are that person's top choices in order.
  3. Column H picks a random sort order for that person. (There is no collision detection, but with only 100 people, the chances of collision are very slim. You can also regenerate the sort order if needed.)
  4. Columns J-O are a copy of Columns A-F, but sorted according to the sort order.
  5. Column Q is the space allotted to that person. Essentially, the first person gets their top pick. The next person gets the highest pick that has not already been picked.

As I noted in a comment, with 100 people, 100 spaces, and only 5 picks, it's possible for people not to get any of their picks. For example, if six people A,B,C,D,E,F choose the same top 5 picks 1,2,3,4,5, A will get 1; B=2; C=3; D=4; E=5; and person F will not be able to get one of their picks. If some spots in your lot are clearly more desirable than others, this is not an unlikely scenario.

The "algorithmic" solution is to make everyone order their picks for all 100 spaces, but that's unfeasible. :)

  1. Column R assigns a random unallotted space to the person if they could not get one of their picks. (I have not implemented this at time of writing... Happy to have people's suggestions.)

Two more minor notes:

  • In the wild, you would want to protect some ranges to ensure people can only change their own picks and interact with nothing else. You might even want to create a separate spreadsheet where you collect the picks, and then copy them in here yourself.

  • This is an XY challenge, but while Google Sheets can allot spaces like this, it can't really optimize the distribution. For that you would want to go for a programming language so you can do more complex scenario-testing. Some scenarios are better than others as judged by how many people get their preferred picks, so a purely random order may not be optimal. I actually just did some work in Python allotting club membership to students from my school in such a way as to optimize the number of students getting into their highest possible picks; the algorithm is quite involved, but if you're interested, you can read about it here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I have just glanced at your reply- I think this is the right track! Will check on it tomorrow. The other answers were incredible! But I reckon they were way too advanced to a simple task. $\endgroup$
    – Heleno Paiva
    May 24, 2022 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.