Wednesday, February 16, 2011
Fairness in Carpooling
A group of n people decide to form a carpool. Each day a subset of these people will arrive to a (fixed) gathering point and one of them should drive. A method for determining which person should drive on any given day is required. The algorithm should be perceived as fair by all members so as to encourage their continued participation. Before discussing the scheduling algorithm, suggest a criterion for fairness
Subscribe to:
Post Comments (Atom)
1 comment:
When k persons out of n turn up at the meeting point, one will be the driver and the other (k-1) persons will be transported by this driver. So the driver earns (k-1) fairness points.
Every day, the person with the lowest yet-earned number of fairness points will be the driver. If there are several persons having the same lowest score, one of them is chosen at random.
This system is really fair - if only one person turns up (and therefore has to drive), he will not earn fairness points qualifying him for being transported another time. But that is just the situation as if there had been no carpool at all, so he doesn't lose a thing by actually turning up. Turning up at the meeting point is actually a win-win situation for everyone. (and for the environment as well)
Post a Comment