I am redesigning a system by which conference participants can choose which track they want to attend. Participants express their track preferences arranging them in order and submitting them at a certain recorded time (which is useful for prioritizing earlier submissions). Each track also has a different quota and some participants have a restricted set of choices because they do not meet the requirements for attending that track (in this case, they do not speak the language required). Assuming there are enough quotas so that these restrictions can be met, how would you go about finding an efficient allocation of participants?

My first approach at a solution involves filling each track quota with participants who selected it as first choice, in the order of their submission. Once I complete that quota, I remove the track from the choice set (so some participants who could not get into their first choice now have a second chance at getting into their second) and go over those choices too, in order of submission.

I am afraid that this algorithm is not going to reach an efficient result (I am thinking in terms of Pareto optimality here, but other criteria can be considered) and, arguably worse, it can lead to some participants unable to get into any track due to language restrictions.

Can you suggest improvements to this approach to guarantee that these two key objectives are met (that a solution is found where every participant is assigned a track, and that this solution is efficient) or point towards literature where similar problems are discussed?

  • 1
    It's hard to define Pareto optimality in this case since you have no way of knowing what the true utility functions of your clients are. Should we assume that a solution is "more optimal" if it results in more people getting their 1st choice, and ties broken are broken in favor of more people getting their 2nd choice, and so on? (if so the naive algorithm you're using might already be optimal) – Ixrec May 21 '16 at 18:04
  • I meant that no two participants would prefer to switch places with each other. Perhaps it's not possible with ordinal utility, in which case such a strong optimality requirement could be relaxed. – Federico B. May 21 '16 at 18:27
  • That definition probably works if you assume all participants get signed up for the same number of tracks in the end, but if some people get nothing and others get the one track everyone wants then it gets fuzzy again. You did say to assume there are enough, but if we can simply give everyone their first choices there's no problem to solve here...yeah, it's hard to be truly unambiguous about this sort of thing. How about this: can you describe a specific scheduling outcome your current algorithm might produce which you would consider suboptimal? Then we might be able to help avoid it. – Ixrec May 21 '16 at 18:31
  • Yes, I am assuming that tracks are exclusive (you cannot get more than one track assigned) and that there are enough spaces so that everyone can get one, even with restrictions taken into account, but not enough so that everyone can get their first choice. – Federico B. May 21 '16 at 20:08
  • One of the problems with my current algorithm is that it doesn't prioritize submission times enough. Consider subjects A, B, C, D submit their choices (X,Y,Z), (Y,X,Z), (Y,X,Z), (X,Z,Y) for tracks with quotas (X,2), (Y,1), (Z,1). With my current algorithm D gets X (first choice) while C gets Z (third choice). I would like to avoid that. Perhaps iterating over subjects and assigning them the first of their choices that has spaces available before moving on to the next subject is better. – Federico B. May 21 '16 at 20:25

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.