Carpooling games

We define a new carpooling game (or more generally a task completion game) as an extension of the cost-sharing game and propose optimization algorithms to find stable allocations, i.e. match players to carpools and determine the distance they traveled. The game key features include: coalition size is restricted, optimal matching of players to carpools should be partition-feasible, cost depends not only on the carpool, but on the driver as well, solution is Pareto-efficient: nobody drives more than alone. If utility is transferable, transfers are determined as the nucleolus. We determine optimal solutions as well as suggest heuristics for large problems that ensure close-to-optimal solutions.