Fairness in Carpooling

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.

Available: abstract , postscript , gzipped postscript .

An axiomatic treatment of the requirement from a fairness criterion  is given in

Slides for a lecture on the subject: pps