The Allocation problem, assigning students to sessions

Topic: 

This is a challenge to blog readers to come up with (or find examples in practice) of good systems to allocate students to parallel sessions based on their preferences. I've just concluded one round of this, and the bidding system I built worked OK, but is not perfect.

The problem: Around 80 students. On 10 days over 4 weeks they will be split into 3-5 different parallel sessions on those days. Many sessions have a cap on the number of students, and more students will have them as a 1st choice than can fit. Some sessions can take many students and won't fill up. The students can express their preference as ranking, or with numeric values.

This is known in the literature as the Allocation problem, and there are various approaches, though none I found seemed to fit just right, either being easy to code or having existing running code. But I am keen on pointers.

The goals:

  • Maximize student satisfaction/minimize disappointment. Giving a student their 1st choice is good. Giving 3rd or 4th choices is bad.
  • The system must be easy for the students to understand and use.
  • Fairness. This has many meanings, but ideally mismatches that can't be avoided should be distributed. If somebody gets a 4th choice one day, they perhaps should have a better shot at a 1st choice on another day.
  • It's nice if there's a means of applying penalties to students who violate rules, sneak into sessions etc. Academic violations can result in less chance at getting your 1st choice.
  • It should be flexible. Sessions may have to be changed or many not fully finalize until a week before the session.
  • It is nice to handle quirks, like duplicated sessions a student takes only once, but where the student might have preferences for one of the instances over another. There may also be pre-requisites, so only students who take one session can have the sequel.
  • Things change and manual tweaking can be advised.

Rank sessions in order, 1st come, 1st served

This was used in the prior year. Much like a traditional sign-up sheet in some ways, students could indicate their choices in order. If more students had a session as 1st choice than would fit, the ones who filled out their form first got in. This gave priority over all 10 days and so it was changed to rotate each week to distribute who was first in line.
Problems: It's arbitrary. It either means a scrum to sign-up or is unfair. It's a bit of work to arrange things. It doesn't allow students to express that in some cases there is a big difference between their 1st and 2nd choice, and sometimes little difference at all.

Uniform price auctions

The next year, students were given 1000 points, and could place bids. On each day they would win only one session. Winners all pay the same price -- the bid of the lowest-bidding winner. If a session does not fill up, the lowest winner is zero, and the session is free. Ties are resolved at random.

Bidding was done in 4 week periods, so students would do 2-4 per week and then learn what they paid.

Advantages:

  • Bidding system lets students express their desires finely. If they don't win a session because everybody else bid more, it's very clear and very fair. Done properly it avoids bidder's remorse. (Or so it would seem. Some students complained that they didn't understand it and thus it was not fair.)
  • Uniform price auctions (sometimes mistakenly called Dutch auctions) are generally viewed as the best way to allocate multiple identical items, if they are done properly. Bidders must understand they should bid their true maximum price, and not try to be too strategic. In theory this is easier to understand, but in practice...

Problems:

  • Inexperience with uniform price and 2nd price sealed bid auctions causes trouble. Even though thanks to eBay and Google they are the most common type of auction in the world, by far.
  • Sessions are still allocated in series. You must save up your points if you want to use them on later sessions, but it's hard to predict how many points you will actually spend, and what others will spend. Unlike money which has a continuing value, these points are useless at the end of the bidding.
  • The final session bidding is all about how many points you have left (you should bid all of them on your 1st choice, all but 1 on 2nd choice and so on.) This means those who didn't spend many points get their pick of the final day, which is not unintended. Students may bid a percentage of their remaining points rather than an absolute number to account for the lack of knowledge of how many they spent in the earlier rounds.
  • All these systems are somewhat chaotic in implementation. Once you have filled a session, those who lose the session must will then be applying their bids to their 2nd choice for that day, which can then displace people who were previously winning in that 2nd choice. In theory that might loop back but in practice it doesn't seem to get too bad.

Here are some other methods, not yet tried:

Simple point distribution

A proposed system, not yet tried. Students just allocate their 1000 points over all the sessions. Winners of any session are the highest bids.

Advantage: Simple and not time-based. You can allocate to each day as you wish, not based on what you spent on prior days.

Disadvantage: Points misused are just lost. If your 2nd choice is also valuable you will use up a lot of points on that single day. You might lose most of your races and get nothing but 2nd and 3rd choices if you spread evenly while others use focus.

Use of non-linear optimization methods

Any non-bidding approach, including both ranking and scoring, can be used as inputs to a large binary variable non-linear optimizer. This optimizer would be tasked with minimizing student pain, which is to say students being assigned workshops they hate. Such an approach might be best done over all 10 days, but could be re-applied each week.

The main problem with this is that it's opaque. The optimization routines are large and complex and the result of a great deal of research, but students may not understand that the optimizer gave them a lousy choice because it gave several other students a first choice. It can also suffer from the local maximum problem, where there might be a better maximum somewhere else.

Scale-less bidding

It's possible to do bidding without saying one has a fixed number of points. Instead, one can let students put any weights on their bids they like. Each day, you would sum up all the bids from the student, and then divide each bid by that sum to work out what fraction of their remaining points should be bid. This assures that the fact that students don't know how many points they have after intermediate rounds does not cripple their bidding ability. However, they can get confused when they don't understand just what it was they bid.

Lessons from bidding

  • With a uniform price auction, most bidders pay for less than they bid. So most students found they paid a lot less than they expected. At first, they also bid low, not understanding the rule that you should bid your true pain point.
  • After 3 weeks and 6 of the days, most students still had 3/4 of their points left, some had all 1,000 left.
  • Even after the last day, many students will end up with lots of points left. In fact, it's inherent in the uniform price auction that even if everybody bids 100% only a few will use up all their points. Having points left is a sign you didn't do as well as you might have, unless you truly were most happy with non-scarce sessions.
  • Tie-breaking is always difficult. Random tie braking is fair, but ideally you might want to round-robin it so that anybody who loses a tie-breaker lottery then has a better chance of winning a future one, so everybody wins one tie at the end, ideally. This level of complexity I didn't want to code.
  • In spite of many warnings, many students bid late, and some not at all. The late bidders, it was ruled, would not displace people who bid on time, which called for lots of manual tweaking, though it could have been coded in. Frankly I didn't expect after the lesson of the first week that people would keep bidding late (especially since the system allowed them to bid multiple times and it would take the last one) but they did.

So, do any readers have suggestions on good solutions to this problem, or pointers to working tools? We can use them next year. Alas, perfect solutions not understood by the students are not perfect.

Comments

Unless it's specifically an economics/games/strategy environment, people can get frustrated learning new competitive-allocation-bidding systems.

To keep it simple, I'd suggest something like a sports draft, where the students are like teams, and the session slots like players. Let students rank their choices, then cycle through each student in turn, granting their highest-ranked still-satisfiable preference each round, until all slots/preferences are exhausted. Then, as an escape hatch, let people trade spots among themselves.

From week to week, you can vary the selection order, so everyone is in the 'top quartile' of early-selectors at some point.

Further possible refinements:

• conditionals in the ranking order: lower-ranked items that auto-cancel if a particular higher-ranked item was granted

• more precedence order variation: pick in first-to-last then last-to-first order in alternating rounds (eg Catan initial placement); grant subsequent week orderings based on how many unavailable choices were missed previously, etc.

It's fairly easy to understand, from other sports/gaming round-selection procedures. A simple honest ranking of preferences should yield good results for most participants without requiring too much gaming/calculation. It's also easy to mix-in extra conditions, for example by slotting absolute musts before the selection-process begins, skip unsatisfiable preferences/conflicts in rank order when they come uo, giving some people extra/fewer 'picks' per round, etc.

Perhaps this is roughly what you meant by your original "Rank sessions in order, 1st come, 1st served" description, though when you suggest the order was based on who filed their forms first, or that someone had priority "for all 10 days", it sounds like your process might have been different.

If you want to add an economic aspect to ranked-selection-assignment-rounds, you could let people purchase their relative ordering, perhaps via chits that (in the later rounds) they earn from having missed their top choices earlier.

The problem with what happened last year was that the tiebreaker wasn't announced, and people did not realize there was any special urgency to signing up, so giving 1st choice to those who signed up first was somewhat arbitrary. Cycling it helped a bit, so the "1st point" was 25% down the list each week, but it was not satisfactory and a lot of work. The auctions show a large difference in preference. For example, in many cases the auction bids will look like 200, 3, 2, 1 -- meaning the student really wants their 1st choice and has only a minor opinion on the latter choices. This is in fact an incorrect bid, though a common one. Bids like 3 will not win any session in which there is contention, so this bid really means "If I don't get my 1st choice, put me in something that didn't fill up in this order of preference."

Students had a lot of trouble understanding the correct bid which is to also bid decently high, if not quite as high, on 2nd and 3rd choices, and even to bid decently on sessions with low probability of filling because the actual auction price will be low. (I even allowed students to define a different ranking order from their bid amount order, but only one student only availed himself of that.)

If I were running a 'draft', I'd give zero weight to earlier signups. Their 'draft order' would be random (but repeated in subsequent rounds of the same draft, and then changed for the next bank of selections a later week); there are no ties because only one person (via their ranked-list) makes a 'pick' at a time: their place in the order. The draft process only occurs after all ranked-lists are submitted.

Refinements:

• if you announce the draft-order beforehand, and post-draft trades are allowed, people may be a bit more strategic in their rankings, based on their estimations of what will be available at their pick. They might even pick something they don't truly want, simply because they know it has trade value. But these effects shouldn't be very strong, if they're undesirable, and if the draft-order is seeded after initial rankings some in they're impossible. (At least until the later weeks, when people who had been late in the early draft-orders know they'll be early.)

• if you can't hold the selection process for the submission of all rankings, you could either punish those who submitted no rankings with only being allowed to pick empty slots after it's all over, or be merciful by synthesizing for them an 'average' ranking ballot, and then include that in the draft (either from round 1 or some lag). Then they may get a few oversubscribed slots (and then be free to trade them if they aren't what they wanted).

I think anything that's novel-to-the-participants or involves bidding/allocating currency could confuse and discourage those who least like those sorts of games/negotiations. A round-robin pick-one-thing-at-a-time process is familiar enough (from sports, table games, and folk-split-the-diverse-loot techniques) there shouldn't be too many negative surprises.

There are two goals which may sometimes not match here.

You do want simplicity, so people understand how it works.

But you also want clarity and finality. Students get upset when they lose, and while most people will objectively agree that random is fair, they can still get angry at having had bad luck. That's why I went to bidding. It's very clear, and very clearly fair, when you see that the people who won all bid more than you. That's also the problem with non-linear optimization. The result may be more fair (or more optimal by whatever criteria we optimized) but it's not always obvious why. With bidding, the students are upset at losing but blame themselves. Though sometimes they blame themselves for not understanding things well enough.

An ideal system both is easy to understand and has clear results which the student feels were under their control. My original plan had been to just have people lay out all their weights, and pay what they bid. I think that's less fair, because in such auctions you get annoyed that two people who got the same thing paid a radically different price, and also you get annoyed if you paid a lot for a session that nobody else was competing for. it leads to a lot of bidder's remorse and strategic bidding. I selected the uniform price auction as it is well regarded as an answer to those things.

If all 10 days are done at once, then you can make the rule that all 40 amounts must sum to 1,000 for example, and so you just apportion your points. Or you can require that the largest bids on all 10 days sum to 1,000, though that means once you have decided to bid 200 on your 1st choice for a day, you will bid 199, 198 etc. on the others as there is no cost to it in spite of your true desires. You do need to make and enforce a rule about no two bids on the same day being the same, as even with many suggestions, students still did this a lot.

I wrote an algorithm to solve this problem for a festival that had a lot of workshops for people to take. The solution had assets and weaknesses, but the best idea I cam up with was modelling pain. Every time a student didn't get his first choice, his pain went up. If he didn't get his second choice, even more pain. Then, for subsequent classes, people who had more pain were given preferential treatment. At the end, everyone had approximately the same amount of pain.

You want the students to honestly reveal their preferences. A simple price auction system will reduce the gains to strategic voting in the absence of having a lot of information of the other bidders' preferences and more reliably reveal the preferences between the different weeks.

But there is a disadvantage that you don't list which is that my preferences in one week may be altered by which sessions I'm assigned to in other weeks. Not knowing the scheduling, possibly some students prefer to have their session at the same time, whichever time that may be. Since all sessions are resolved at one time there's no way for a student to modify their bids based on which sessions they win.

Also, one disadvantage of all your bidding systems is that it doesn't take into account the difference of level of preferences between different students: one student may have a much stronger preference for their first choices and another may be nearly indifferent but they are each as likely to get the same number of first choices. Probably it's too difficult, but allowing students to sell their votes to each other would raise total expected welfare (with only two bidders in the auctions it would unambiguously raise welfare but with multiple bidders one can construct cases where this doesn't happen if the different bidders have different marginal values of money).

PS probably the multi-round auction system used to allocate radio spectrum is the way to go but just a little bit too complicated :-)

I might be wrong, but while reading your initial description, I was reminded of my favorite condorcet replacement for our current first-past-the-post vote counting system for political elections: The Schulze method (FKA Cloneproof Schwartz Sequential Dropping)

http://en.wikipedia.org/wiki/Schulze_method

There may be additional internal ties that that misses, but...

The first thing to look at would be: why are sessions filling up? Is it just that the room is too small? Can you move the most popular lecture to a larger room? Can you videoconference the lecturer to a second room? Can you clone the most popular sessions and run them multiple times on separate days?

The second thing: if you're collecting all this advance information anyway, a good idea would be to first identify which students want which sessions, and second work out which sessions should be parallel with each other. (And only third start assigning students to sessions.) If there's a large population which wants to attend both Session A and Session B, you should make sure Session A and Session B don't happen simultaneously. This is probably NP-hard to solve optimally, but you could do okay with a greedy algorithm, or just have a human stare at it for half an hour.

As to assigning students to rooms: rather than asking them to bid points, you might allow them to go to real-world effort to improve their chance of getting admitted. For example: "If there's a specific session you want to attend, optionally submit a 50-word paragraph when you sign up describing something you did related to the session topic. If you really want to attend, send us a 60-second home video showing something you did that's related to the session topic. If the session fills up, people who submitted videos get priority, and people who sent us paragraphs get second priority."

Add new comment