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.