Answer and references
A natural scheduling algorithm is the greedy one: of the subset of people who show up, the one whose difference between the fair share (so far) and actual share is the smallest is chosen as the driver. Ties are broken at random. It can be shown (see ref. below) that the maximum unfairness of this algorithm is (n-1)/2. A simpler case to analyze is when there are two people every day. Here we can analyze the local greedy algorithm: for each pair of participants X & Y the algorithm keeps track of the difference between the number of times X has driven and Y has driven on the days where X & Y showed up together. The one who has driven less on those days will drive the next time they are teamed. The maximum unfairness of this algorithm is (n-1)/2, no matter how ties are broken. However, consider the following tie breaking scheme (assume that X > Y are numbers between 1 and n): if X-Y < n/2 than X drives first and otherwise Y drives first. The maximum unfairness here is (n-1)/4 and this is the best possible.
The carpool problem was first considered in a paper by Fagin and Williams,
who suggested the fairness criterion and the greedy algorithm: A fair
carpool scheduling algorithm, IBM Journal of Research and Development,
vol. 27, 1983, pp. 133-139. An analysis of the greedy and local algorithms
in deterministic and probabilistic settings can be found in
An axiomatic treatment of the requirement from a fairness criterion is given in
Available: abstract , postscript , gzipped postscript .
Slides for a lecture on the subject: pps
Back to the carpool question
Back to the Puzzler page