Fairness in Carpooling

Answer and more questions

There is a way to schedule the drivers so that each participant gets his or her fair share. Start with any schedule and suppose that not all the participants get their fair share. Then we partition them into those that drove more than their fair share (Group F), those that drove less than their fair share (Group P) and those that drove exactly their fair share (Group Q). Note that it cannot be the case that Groups F or P are empty, since the sum over all participants of the difference between the fair load and the actual one is zero. Consider the following directed graph: each node corresponds to a participant and there is a directed edge between any two participants such that there is a day where the head drove the tail took a ride. There must be directed path from a node in the set F to a node in the set P (going perhaps through group Q). Reschedule so that all the tails drive instead of all the heads. The sum over the group P of the difference between the fair load and the actual one has decreased by one by this operation and from the integrality assumption it did not go below zero. Therefore we can repeat the above procedure only a finite number of times before all the participants get their fair load.

Having seen that the fair load can be guaranteed when everyone's timetables are given in advance, the natural question is what happens when the participants do not commit ahead of time to the days they will show up. Our goal is to minimize the maximum unfairness, i.e. the largest (among all participants) absolute value of the difference between the fair load an the actual one. Suggest an scheduling rule where the unfairness is as small as possible, in particular, bounded as a function of the number of participants and not the number of days. Again, an easier problem is what happens when each day only two people show up.

Solution and references

Back to the criterion

Back to the Puzzler page