2
$\begingroup$

I'm searching for a simple algorithm to allotment a real estate unit for the customer based on the customer preferences like the following table.

Each customer has a priorities and we should allocate a unit for each customer, what is the name of this algorithms type to cover all scenarios.

enter image description here

$\endgroup$
  • $\begingroup$ This seems like a simple assignment problem. $\endgroup$ – dkaeae Jan 23 at 8:45
  • $\begingroup$ Also, from your question it is not clear why a greedy algorithm would not work (e.g., one could just go through the table line for line, always picking the first available option: A-U1, B-U5, C-U6, D-U2, E-U3). What exactly are you trying to maximize/minimize (if anything)? $\endgroup$ – dkaeae Jan 23 at 8:47
  • $\begingroup$ What do you mean by "covering all scenarios"? Are you interested in variants of this problem? If so, which? $\endgroup$ – Discrete lizard Jan 23 at 16:39
  • $\begingroup$ @dkaeae Your 'greedy strategy' is also known as the Serial Dictatorship algorithm. It is a bit 'less fair' variant of the random serial dictatorship algorithm I describe in my answer, since customer A gets beneficial treatment over E. $\endgroup$ – Discrete lizard Jan 23 at 17:41
  • $\begingroup$ @Yousra Does each unit also have priorities among the customers? For example, say, U1. The customers who prepare to pay higher for U1 than other customers will be ranked higher from the view of U1. So, you could have an another priority table where the first column is a list of units and each row is the customers listed in the descending order of preference. $\endgroup$ – Apass.Jack Jan 24 at 14:58
1
$\begingroup$

This problem is sometimes called the room assignment problem or the hospital/university admissions problem. The standard approach here is to use the Random Serial Dictatorship algorithm (RSD). This algorithm is very simple, but has nice properties and even is the only algorithm (where I call algorithms that provide the same output the 'same algorithm') that has all these properties.

The RSD algorithm is as follows: pick a customer at random and assign to that customer the most preferred unit that is still available. Then, pick another customer that has not been picked yet and repeat this procedure until all customers are assigned.


This algorithm has the following nice properties:

  1. Pareto optimality: We want the assignment to be 'efficient' somehow, in the sense that we as much as we can give the users what they want. One way to look at this is to call an assignment 'bad' if any number customers can redistribute their units such that at least one of them has a better unit and none of them have a worse unit. If an assignment is not 'bad', then it is Pareto optimal.

    It is a straightforward exercise to verify that the RSD algorithm is indeed Pareto optimal.

  2. Strategy proofness: We want that there is no way that customers can 'cheat the system' by lying about their preference. Formally, we say that a customer $c$ can successfully manipulate if there is a fake preference profile $P'_c$ such that the algorithm gives a strictly better unit according to the true preference profile $P_c$ than $c$ would get if $c$ would report their true preference $P_c$. If there is no possible way for any customer to manipulate, the system is called strategy proof.

    It is easy to see that RSD is strategy proof: we only look at the preference profile of $c$ when it is their turn to choose. But then, lying only means that they might pick something that has a lower preference than all available units! So, $c$ cannot manipulate.

  3. 'Fairness' We want also to be somewhat fair, in the sense that every customer should have 'equal opportunity' to get their preferred unit. But, there are limits here. We cannot demand that each user has equal probability to get their best result: Suppose we have 100 customers and all but one customer prefers unit 1 most, but the final customer prefers unit 2. Then whatever assignment mechanism we make, if we want Pareto optimality, the final customer has a higher probability to get their most preferred unit.

    In RSD, the randomized portion is there to enforce some sort of equal treatment. We cannot treat everyone the same, but at least everyone has the same chance to be first to pick their favorite, as to be second, third, etc.

$\endgroup$
1
$\begingroup$

This is not an answer.

This post is used to show that the problem in the question is not the same as the stable marriage problem. There are three differences.

  • The number of customers might not be the same as the number of units. However, there is an asymmetrical version of stable marriage problem as described here. So this is not a critical difference.
  • Each customer may not have ranked all units. However, it can be understood each customer ranks all units not explicitly ranked lower than all units ranked. So this is not a critical difference.
  • None of the unit ranks the customers at all. In stable marriage problem, each man ranks all women while each woman ranks all men. This is an important difference that makes every algorithm for stable marriage problem not applicable directly for the current situation.

    • We could assign a random (strict) ranking (and possibly different) of customers to each unit. Now we can apply any algorithm for stable marriage problem to our customers and units.
    • We could assume that all units rank all customers indifferently. We can then find super-stable or strongly-stable "marriage" between customers and units.

    Although we could assign rankings of the customers to the units so as to apply the algorithms for stable marriage problem, it adds an extra dimension of condition as well as probably extra steps in the solution algorithms. It might/should be better that the problem and its solution is kept as it is, agnostic to any rankings of the customers by the units.

(This post could be changed to an answer should the question be updated with the addition of a priority table by units.)

$\endgroup$
  • $\begingroup$ Note that if you want your assignment procedure to be both Pareto optimal and strategy free, any algorithm to do so would be a more complicated version than the (random) serial dictatorship algorithm. However, I suspect that this procedure is not Pareto optimal, unless you have some specific way to select 'preferences' of the units over customers. Maybe setting the same preference to each unit yields the same result as a serial dictatorship? $\endgroup$ – Discrete lizard Jan 24 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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