## 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