Bidding for Envy-Freeness: A Procedural Approach to n-Player Fair Division Problems

Bidding for envy-freeness

B =∣(B1, ... ; Bn)j Bi J K ; Bi X Bj ¼ q;

6 B_i ¼ K ; (+addl. restr: on B_i ) >.
iAI

An assignment B A B thus groups the m objects of K into n separate bundles
Bi without dividing them; if there are fewer objects than players, B will nec-
essarily also include empty bundles.

The set of assignments B may be further restricted by specific requirements
for the individual bundles. In the simplest case, the additional restriction may
just be an exogenously given bundling of objects. For an endogenous bundl-
ing of objects, one could specify that all players receive the same number of
objects (jBij ¼ m=n), or that each player receives a minimum number of
objects (jB_i j b m, where m a m=n). Or, in a different context, assume that
the objects are distinct territories in a geographical region. One may then
wish to have the territories in each bundle be connected in some specific form,
e.g., lying within a single sub-region. Generally, the set of assignments B can
include any restriction on the objects of K that is player-anonymous; in par-
ticular,there are no restrictions of the form ‘‘Player i must (or must not) receive
object k.’’ Indeed, with an exogenously imposed restriction of this type, no
procedure can guarantee envy-freeness. However, if the players themselves
wish to give a particular player special attention, they can express this directly
via their preferences over the objects.

We view the assignment of the m objects to the n players as a joint venture,
for which there is a total cost C (measured in the common unit of account)
that must also be divided among the players. Denoting by c_i the contribution
that is to be paid by the player receiving bundle Bi, this implies ^P_iA_I ci ¼ C.

Assumption 2. Players have linear preferences over values measured in the com-
mon unit of account.

Under Assumptions 1 and 2, we can characterize players’ preferences
through quasi-linear utility functions u_i : 2K x R ! R, with

U (Bj ; Cj )¼ bi (Bj )- Cj ;   i; j A I :

In order to implement an e‰cient outcome, our fair-division procedure is
based on an assignment that maximizes the (unweighted) sum of players’ util-
ities. We characterize such a utilitarian assignment B a B by

The utilitarian assignment B yields the maximum sum of players’ bids,

<<   <   2   3   4   5   6   7   8   >   >>