Incremental cost sharing: Characterization by coalition strategy-proofness

Each one of n users consumes an idiosyncratic commodity produced in indivis ible units. The n commodities are jointly produced by a central facility an d total cost must be shared by the users. A "sequential stand alone mechanism" shares costs incrementally according t o a fixed ordering of the users: the first user always pays stand alone cos t, the second pays the stand alone cost of the first two users minus that o f the first and so on. If the second derivatives of costs are of a constant sign, such a method yields a unique strong equilibrium at every profile of convex preferences in the game where each user chooses his own demand. Thi s equilibrium, in turn, defines a coalition strategy-proof social choice fu nction. Under decreasing marginal costs and submodular costs, the sequential stand alone mechanisms are almost characterized by these properties; the only exc eption is the binary demand case teach agent consumes zero or one unit) whe re a rich family of cost sharing methods (the Shapley value among them) yie lds a coalition strategy-proof equilibrium selection. Under increasing marg inal costs and supermodular costs, coalition strategy-proofness characteriz es a richer family of cost sharing methods: they give out one unit at a tim e while charging marginal costs, with the users taking turns according to a sequence fixed in advance. These methods contain serial cost sharing as a limit case.