Fwd: FW: suggestion for elective allotment

[kashyap garimella]

Hi all,

Can you help in making a better algorithm for HS course allocation?

Problem: Each student will give preference of the courses. The courses have a limit on number of students they take.

Crude requirement: We need to minimize the sum of the preferences allocated.
Better requirement: The variance of the allocation should be less.

Can we modify the stable marriage problem to solve this?

I am very sure that this problem is NP. Therefore we have to come up good heuristics to solve it.

Something to read on:
http://en.wikipedia.org/wiki/Pareto_efficiency
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.4035

Thanks,
Kashyap

---------- Forwarded message ----------
From: devesh yamparala <dev...@gmail.com>
Date: Sat, Nov 13, 2010 at 8:55 PM
Subject: Fwd: FW: suggestion for elective allotment
To: iitm...@googlegroups.com


Hi everyone
   I have recently written a letter to the head of HSS dept with some complaints.
the main complaints were
1) very little time to consider options
2) no source of information (especially b-tech
3) the allotment algorithm is not really good.( i included this in the complaint because last time when i asked the office for the algorithm they said it is randomly picking a paper and assigning the course.
and this time when i asked they said they group the people in sets of 50, generate random numbers for them and then allot the courses)

So they replied back to me asking if i had any better allotment algorithm.

So if some of you also have some solid implementable ideas do tell me if you want them to be heard by HSS dept.


Devesh

[Arun Chaganty]

Hey,

> Can you help in making a better algorithm for HS course allocation?

Nice :-).

> Problem: Each student will give preference of the courses. The courses have
> a limit on number of students they take.
>
> Crude requirement: We need to minimize the sum of the preferences allocated.
> Better requirement: The variance of the allocation should be less.
>
> Can we modify the stable marriage problem to solve this?
>
> I am very sure that this problem is NP. Therefore we have to come up good
> heuristics to solve it.

Agreed. However, I'm starting to lose my fear/respect for NP problems.
I think we could use a good ILP solver that will probably give us good
results anyways.

Cheers,
--
Arun Tejasvi Chaganty
http://arun.chagantys.org/

[Arijit Banerjee]

Hey

The first part can be modeled as a minimum cost maximum flow problem for which there are algorithms which run in polynomial time. Don't know about reducing the variance though.

The graph construction would look like this:
Keep a source and sink vertex , as well as vertices for each student and HS course.
Between the source and each student , draw an  edge of capacity 1 and cost 0 .
Between each HS course and the sink , draw an edge of capacity limit of the number of students it takes and cost 0 .
For every student, draw edges connecting him to each HS course he has chosen with capacity 1 and cost his preference number for the course.

Since every student has to be allotted a course, we need a maximum flow in this graph. The minimum cost maximum flow will minimize the sum of preferences.

[Anubhav Bhattacharjee]

I had mailed the most obvious heuristic to Kashyap - here it is in case anybody wants to discuss -
 
assuming total no. of seats offered = no. of students & no. of seats in each course is fixed.
1. identify least popular course
2. allot seats into least popular course based on preference (higher preference (better rank) gets priority)
3. repeat for next (least popular course) course
implementation of the same is pretty ob right?

Minimizes the maximum dissatisfaction.

Regards
Anubhav

--
Anubhav Bhattacharjee
Dual Degree Student
IIT Madras

[Pranesh Srinivasan]

The key thing here is not the algorithm, but the metric itself.

I do know, for example, that the minor allotment is based on
minimising regrets (which is equal to minimising the sum of
preferences), but people werent happy.

Even the old mess regn was based that way, and people "claimed" it to
be unfair, and screwed up. Vimal wrote it himself, so I dont think the
implementation or the design would have been incorrect. Surprisingly,
after moving to this useless FCFS thingy (where I have to wake up at 5
in the morning), people are happy.

So, what is it we want? Let us answer that question first. :-)

--
Pranesh

[Anubhav Bhattacharjee]

Hey - First come first serve is fair - if you want a mess that bad - you wake up at 5 and get it :P
The only thing is - can we implement HS registrations that way? :)

and yeah I agree that the metric is more important than the algo.
1. minimizing the max "regret"
2. minimizing the "sum" of preferences

anything else ?

Regards
Anubhav

[Pranesh Srinivasan]

See, the problem with these max regret, and min preferences and stuff,
is that one guy can get BADLY screwed so that four others get a better
choice.

In a discussion with Vijay Kartik, that I had just now, he rightly
pointed this out, and also cited someone (name with-held :-P) who got
his 11th choice instead of Economics, his 1st choice, so that 3 other
students could get Economics (which was their 4th choice).

This (I believe) was why Vimal, implemented the mess thing as a
stepwise allocation:

Try to assign first preferences to everyone. In case of failure,
randomly allot to as many people as possible. Then try to assign
second preferences to everyone. In case of failure, randomly allot ...

In otherwords, randomly shuffle (using the Knuth shuffle or some such
thing), the list of students, and for each person allocate the first
among his options that is still open.

Period.

No?

--
Pranesh

[Arijit Banerjee]

  In the case of a random shuffle, the people unlucky enugh to be at the end of the list after the shuffle will end up getting their last preferences anyway. So how is this method of allocation any better?

[Anubhav Bhattacharjee]

Minimizing max regret means that you're minimizing the number of people getting low choices (the opposite of the example you described). The algo I'd put in the mail actually achieves this goal. To repeat -

1. You identify which is the least popular course (based on sum of preference numbers filled in by students for a particular course) -
   
2. some students (and I'm assuming this) need to fill the seats in that course (as - again an assumption - total number of seats = no. of students and no. of seats per course is fixed) - so you start filling that course with students who have given it the highest preference.
   
3. After the course is filled - repeat the procedure with remaining students and courses.

(The most popular course gets filled up last)

Regards
Anubhav

[Vijay Karthik]

Obviously everyone cannot be satisfied with their choices. There are some least preferred courses but someone or the other has to get it. This algo will make sure that if you didnt get ur first n preferences, then whoever got them would have also had them in their first n preferences.

[Sheshank Dudyala]

we can make the old _algorithm_ better by exponentially penalizing with increase in the allocated preference and try to decrease that error.

Here is what i propose:

create a neural network and try to minimize the total error by exponentially penalizing.
and also add "|max_students per course - currently allocated students|" to objective function with very high coefficient

after you learn this ANN, allocate the course which each student gets through this ANN for his preference set.

any opinions?

(we were not able to penalize exponentially using OR type modeling )

--
Sheshank Dudyala
+91-9790862130

[Sanjith G]

I have(know) nothing much to say about the algorithms. But as regarding the metric, consider the mess why FCFS is fair and agreeable to many is because it rightly reflects how keen you are to get a proper mess. Many do not care as to whether they get this or that, and they are not too bothered anyway. 

In the HS allotment, similarly many people randomly put their choices(maybe due to lack of info or whatever). But, there are a few who are really interested in a few and who only want to do that because or else it is a waste of a course. The least regret metric will not reflect this. For example, in the case someone mentioned. The guy who missed Econ. could have had much more interest in getting it than many who got it allotted. And you could end up actually reducing the regret of someone who does not really bother. 

Maybe instead of having a ranking of 1,2,3 and so on, you could ask people to put in more than one choice with the same rank? So people who do not really differentiate between X & Y could give both the same rank. And now if you minimise regret it might work better?

On Sun, Nov 14, 2010 at 9:45 PM, Arijit Banerjee <arij...@gmail.com> wrote:

[Sheshank Dudyala]

Can it not happen that a course which is least preferred by many people *is not taught*
and students be redistributed among the other courses..
why are we assuming that  \sum(seats is all courses) == total number of students ?

[Anubhav Bhattacharjee]

Wow!

ok I have just 1 idea about how to make the minimize max regret algo better -
in case of a tie while choosing either students or courses in that algo - check for better performance in the other.
e.g. - if you have to choose between 2 students for a course - check who has given higher preference to the next most unpopular course.

and I like Sanjith's idea of changing the inputs to the ranking algo

[Anubhav Bhattacharjee]

@ Shashank - that usually (I think maths dept does something like that) does not happen coz the courses and profs are decided prior to handing out the lists (to the best of my knowledge) and you have upper limits on class size.

[Sheshank Dudyala]

I agree with Sanjith..  that there preference order form 1,2,3 ... doesn't convey the interest properly..

My suggestion would be to ask people why they want one course that badly.. and write a para or two about their future plans after they take up that course.
and what do they look upon to achieve from that course.
and ask profs to choose students only based on that passage.

--
Sheshank Dudyala
+91-9790862130

[Prashant Vasudevan]

like above comment. :)

--
You have received this mail.

[devesh yamparala]

well .... good to see all this discussion happening ...
if anyone is wondering who I am , I am the unlucky guy who got pained becos he got his 11th option instead of economics and is getting pained still becos his HS course sucks :)

After considering all these suggestions I have decided to mail them only the following two procedures ...
1)The one in which we consider everyone's first options and then randomly allocate to some of them if there are more students than seats in the class.

I am planning to choose this because i feel this will make it look more fair since if i don't get my first option i no one else who wanted it less than me got it.
also i feel there has to be some randomness in the allotment because if we consider any other algo like the minimisation algo then after some analysation the options will be exercised by the students in a way so as to beat the algo
example : If i prefer economics first and a course like Sanskrit as my fourth option but i know that sanskrit will be the least preferred ..... then my chances of getting my first option are increased if i keep sanskrit at the bottom rather than at fourth position.
Hence i advocate for some randomness where you cannot guess the outcome at all.

2)I give FCFS a shot ... but i don't think they'll really consider this.

Devesh

[Vimal]

Hey

Late entry into this discussion.

On 14 November 2010 08:07, Pranesh Srinivasan <spra...@gmail.com> wrote:
>
> This (I believe) was why Vimal, implemented the mess thing as a
> stepwise allocation:
>
> Try to assign first preferences to everyone. In case of failure,
> randomly allot to as many people as possible. Then try to assign
> second preferences to everyone. In case of failure, randomly allot ...

No; that's not what Vivek and I proposed. We did propose minimise
max-regret after we thought about minimising sum of regrets. Attached
is the code; the flow code was taken from some online source. (Rename
to .gz...)

And with minimise max-regret, I don't think any guy can be badly
screwed, in the sense that his allotted choice won't be "far" from his
top choice; you aren't minimising the 99th percentile, you're
minimising max. I guess you can game the system using this. :P Maybe
someone can try and see adversarial cases and come up with something
robust*.

I think the interesting property of the min-max algo was that out of
all solutions that maximise the max-regret, the sum of regrets would
get minimsed..

I talked to GS also about it and they had some heuristics. I've
attached the code that the senior who implemented it had given me. If
you're enthu about understanding it, please go ahead. :P

Depending on the nature of the data, as Slinky suggested, an ILP
formulation might just be fast enough.

*No matter how robust, the guy who implements it can insert special cases. :P

--
Vimal

[Vimal]

On 19 November 2010 00:09, Vimal <j.v...@gmail.com> wrote:
>>
>> Try to assign first preferences to everyone. In case of failure,
>> randomly allot to as many people as possible. Then try to assign
>> second preferences to everyone. In case of failure, randomly allot ...
>

IIRC, That's what Ramanathan did. He also took into account previous
months' regrets as some sort of priority.

--
Vimal

[sivaramakrishnan]

Hey,

I just saw this thread (I browse archives on this group once in a while).

One thing I would like to point out is that whatever metric it is, should preferably take into account the allotment of all 3 HS electives. That will help spread out the chance of a single person getting screwed over by bad luck. I saw this happen today when HS allotments came out. Some guys got their first preference all three times, while some have never obtained anything in their top five choices.

The point I want to make is, we not just want an algorithm to perform well on average, but also that it's behaviour deviate from average as little as possible... i.e. kinda like precision more important than accuracy. The number of times we use the algorithm(in case of HS or Minor allotments) is too small for average behaviour to emerge in a robust manner. Some algorithm might be doing a good job on average, but it's useless if it has a wide distribution, with some people striking gold mines and others striking just mines.

Regards,
Siva

[sivaramakrishnan]

Something else I'd like to add is that the data set here (elective preferences) for HS electives is almost always going to be highly biased. This is because of a combination of thick-headedness by the HS dept while deciding courses to be offered, and sheep mentality of students while choosing electives. (Sheep mentality comes up from everyone wanting that course that either looks good on the resume, or is easy.)

The algorithm must have good(read : stable & close to average) performance given such data, and not just for generic input data. What is the best you can do if (say) 70% of the batch hands in the nearly same preference list. It seems that in such a case, it's unavoidable that someone will get screwed over.

Regards,
Siva