4
$\begingroup$

I have $n=6*10^4$ people which should be sorted into groups. Each person has a list of up to 20 preferences according to which they should be assigned, and a score for each group (a real number). There are $\approx2*10^3$ groups, each taking $5 \leq k_{group} \leq 250$ people at most.

Imagine a following scenario: Each person expresses a list of preferences for groups, in order, from 1 up to 20 - sort of a wishlist to which group they'd like to be admitted to. For each group, each person has a separate score, and each group has its own scale, but points are always nonnegative (e.g. for one group it's 0-100, for the other it's 0-400). Just to be clear: preference 1 is 'higher' than preference 20, and score 100 is higher than score 0. Each group has a minimum score of $s_{group}$ and everyone whose score for that group is $\geq s_{group}$ is admitted.

Admitting to the group is done in order of the preference list. Say a person has a preference list $(A, B)$ (so only two preferences) and he/she has scored $p_A$ and $p_B$ points respectively. If $p_A \geq s_A$, person is admitted to the group $A$. Else if $p_B \geq s_B$ person is admitted to the group $B$. (In case of more preferences, more else ifs go here.) Else, person is left unassigned.

The problem is, how to find the highest $s_{group}$ for every group so that it will take exactly $k_{group}$ people? In case such $s_{group}$ doesn't exist because not enough people have that group on their preference lists and the group cannot possibly reach $k_{group}$ members, so $s_{group}$ remains undefined (-1 or whatever). In any other case, $s_{group}$ will be equal to someone's score, and that person will be admitted to that group. Apart from the mentioned case, assume such $s_{group}$ exists, i.e. it won't happen that two people share the same score and are exactly at the cutoff point.

Have a look at the example (written in json-like syntax with stripped quotes for readability):

input:

{
groups: [
    A: {k=2}
    B: {k=2}
    C: {k=5}
],

people: [
    person1: {
        preferences: [A, B, C],
        scores:      [2, 4, 5]
    },
    person2: {
        preferences: [B, A],
        scores:      [1, 5]
    },
    person3: {
        preferences: [C, A, B],
        scores:      [1, 5, 3]
    },
    person4: {
        preferences: [A, B],
        scores:      [1, 4]
    },
    person5: {
        preferences: [A,   B,   C],
        scores:      [0.5, 0.1, 5]
    },
    person6: {
        preferences: [B, A],
        scores:      [0, 0.2]
    }
]
};



result:

{
groups: [
    A: {
        admitted: [person1, person4],
        s=1 //if picking s to be highest possible, valid values are 0.5<s<=1 (person5 is 'next in line')
    },
    B: {
        admitted: [person2, person5],
        s=0.1 //if picking s to highest possible, valid values are 0<s<=0.1 (person6 is 'next in line')
    },
    C: {
        admitted: [person3],
        s=-1 //this remains unfilled, so finding s so the group has exactly k members is impossible - there aren't enough people who have C as a preference
    }
]
};

--

Having an instance for each person-preference pair, sorting it according to the score tied to the particular reference and assigning people to groups in that order ignores the preference order, so it's not a correct solution. With an edit to disregard the previous placement in case I encounter a higher-positioned preference for the same person, I 'unadmit' previously (wrongly) admitted person and by modifying that group I might have changed the outcome for every person which has come between making the mistake and recognizing it (by taking up space where I shouldn't) and drifted from the correct solution.

I have tried to reinterpret this as a variation of Stable Marriage Problem, but it seemed different enough.

It's not homework nor a competition problem and I'm working with real-world data so handling of pathological cases is of no particular importance to me. Also I'm not looking for a running time measured in milliseconds, but it should be reasonable (i.e. $O(n^3)$ is probably too slow).

$\endgroup$
  • $\begingroup$ @D.W. I couldn't really figure out the goodness score. Since there are no answers, I have taken the liberty to rewrite the question so it asks for a cutoff point instead of the actual assignment (some comments here are now invalid) - having a cutoff point is just one small step behind from the actual assignment and it can be done trivially after it, but I often found it difficult to think about the problem in those terms. However, it seems that it is easier to understand the problem when stated this way. Tell me if there are still unclear points or if you find the previous version better. $\endgroup$ – Luke Sep 28 '17 at 18:17
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles Sep 28 '17 at 18:19
  • $\begingroup$ What do you mean by "the highest $s_\text{group}$ for each group"? There might not be an answer. For example: We might be able to have a $s_\text{group}$ value of 1 for group A and 2 for group B; or 2 for group A and 1 for group B; but not 2 for both. In that case there does not exist a highest $s_\text{group}$ for each group. So what do you want to have happen in that case? $\endgroup$ – D.W. Sep 28 '17 at 22:31
  • $\begingroup$ @D.W. $s_{group}$ is a distinct value for every group (hence the "for each group"). So $s_{A}$ (or, as you put it $s_{group}$ for group A) $=1$ and $s_{B}=2$ could be a valid solution. I'm looking for those values, so the algorithm should provide $(s_A, s_B, \ldots, s_Z, \ldots)$. In the same vein, $p_A$ is different for each group for each person. So if there are $n$ groups and $m$ users, there are $n \cdot m$ $p$s given as an input (along with $m$ preference lists, for each person) and I seek $n$ $s$s for the output. $\endgroup$ – Luke Sep 28 '17 at 22:53
  • $\begingroup$ @D.W. Alright, I understand, but I don't think both $(1,2)$ and $(2,1)$ can be valid solutions. The group needs to have exactly $k$ members, so if I'm not mistaken it will have a cutoff point somewhere between the admitted person with the lowest score and the one which could've been admitted in case the group had space for $k+1$ members. In that case, there are infinitely many solutions, so the "highest possible" requirement was just to make it unique, but in case you can find any you should trivially be able to find the one which I'm looking for. I did miss one other case - edited the q $\endgroup$ – Luke Sep 29 '17 at 10:32

Your Answer

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

Browse other questions tagged or ask your own question.