On Fairness in the Carpool Problem

Moni Naor

Abstract:

Consider the carpool problem suggested by Fagin and Williams (IBM Journal of Research and Development, vol. 27, 1983): a set of n people form a carpool. On each day a subset of the people arrive and one of them is designated as the driver. Fagin and Williams defined a notion of fair share for participants (the FW share). We provide an axiomatic characterization of the fair share and show that the FW share is the unique one satisfying these requirements. We define a coalitional game where the Shapley Value is the FW share.

Postscript , gzipped Postscript , PDF

A related question is how to schedule the drivers so that the number of times each participant drives is as close as possible to their FW share. This question is addressed in:

M. Ajtai, J. Aspnes, M. Naor, Y. Rabani, L. Schulman and O. Waarts, Fairness in Scheduling, J. Algorithms 29(2): 306-357 (1998).   Abstract, Postscript, gzipped Postscript, PDF.

Slides for a related lecture: pps

Back to On-Line Publications

Back to the Puzzler

Back Home