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

**Fairness in scheduling**, by Miklos Ajtai, Jim Aspnes, Moni Naor , Yuval Rabani, Leonard Schulman and Orli Waarts. J. of Algorithms, vol 29, Nov 1998, pp. 306-357.

An axiomatic treatment of the requirement from a fairness criterion is given inAvailable: abstract , postscript , gzipped postscript .

- Moni Naor,
, Postscript , gzipped Postscript . PDF**On Fairness in the Carpool Problem**

**Slides for a lecture on the subject: pps
**