728
C.-J. Haake et al.
which we denote by M. Let Bi denote the bundle assigned to player i; then
PiAιbi<Bi)¼ M.
Regardless of the total cost C of the joint venture, the utilitarian assign-
ment B endogenously bundles the objects of K, while acknowledging the ad-
ditional restrictions, and assigns these bundles to the individual players.7 If
there are no additional restrictions on the bundles, the utilitarian assignment
is easy to implement when preferences are additively separable: simply assign
each object to the player who values it most (if there are several, choose one
player arbitrarily). However, in general assignments will be complicated by the
additional restrictions specifying how bundles are to be created. When bundles
are given exogenously, we call an assignment e‰cient if no re-assignment of
the bundles yields a larger sum of bids. The utilitarian assignment thus allo-
cates given bundles e‰ciently among players.
We characterize a utilitarian allocation as envy-free if no player values the
bundle of any other player (net of its cost) higher than her own bundle (net
of its cost):
U ðBi ; c ) b Ui 'В ; Cj ); i; j A I :
We wish to determine an envy-free pricing of utilitarian bundles, with prices
that sum to the total cost C of the joint venture,such that no player pays more
than she thinks her bundle is worth. The procedure described in the next sec-
tion will accomplish this, if we impose the following additional requirement.
Assumption 3. The sUm of eaCh player’s bids for all the bUndles of a Utilitarian
assignment is at least equal to the total cost, i.e., ∑2j¼1 bi^Bj') b C, Ei a I.
Assumption 3 can be seen as an individual qUalifiCation Constraint for each
group member. If the objects to be distributed are assigned across several
players, then player i is qualified if, by teaming with other players of identical
preferences, this group of players would be able to afford the joint venture. As
the procedure will show, the qualification constraint is not required to produce
envy-freeness, but it guarantees that no player will pay more than her bid.
3 The compensation procedure
Our procedure with ex-ante payments begins by having each player contribute
the amount that they bid for their assigned bundle, yielding M dollars from
which the cost is paid. The remaining surplus M — C will be returned to the
players in the form of discounts in a way which will guarantee envy-freeness.
In each round of the compensation procedure, discounts are determined on
the basis of players’ assessments, and then assessments are revised taking dis-
count changes into account.
7 Note that, when players have linear preferences over divisible objects, the utilitarian
assignment would only divide an object if the value added by its inclusion in a player’s
bundle is the same for two or more players. In this case we may just as well assume that
the object is fully assigned to just one player.