The partition bargaining problem

Consider the problem of partitioning n items among d players where the utility of each player for bundles of items is additive; so, player r has utility for item i and the utility of that player for a bundle of items is the sum of the 's over the items i in his/her bundle. Each partition S of the items is then associated with a d-dimensional utility vector V^S whose coordinates are the utilities that the players assign to the bundles they get under S. Also, lotteries over partitions are associated with the corresponding expected utility vectors. We model the problem as a Nash bargaining game over the set of lotteries over partitions and provide methods for computing the corresponding Nash solution, to prescribed accuracy, with effort that is polynomial in n. In particular, we show that points in the pareto-optimal set of the corresponding bargaining set correspond to lotteries over partitions under which each item, with the possible exception of at most d(d-1)/2 items, is assigned in the same way.