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



Bidding for envy-freeness

745


(double arrow). Have all players return any compensations they have re-
ceived, and repeat Step 2 to restart the compensation procedure.

4. If there are envious players, perform a round of compensations: identify
those players whose maximum envy is directed towards a non-envious
player. Compensate them by their maximum envy difference, thus making
them non-envious. Then recalculate the assessment matrix (but only after
all the compensations have been made in this round), and repeat Step 2.

5. Have each player pay an equal share of the total compensations and the
total cost C.

We provide an example of the modified compensation procedure in the Ap-
pendix.

It is important to note that the procedure as formulated above cycles to a
utilitarian assignment and establishes envy-freeness only for n exogenously
given bundles. In particular, when each bundle contains only a single object,
the final assignment will be utilitarian. In our more general framework,
though, an assignment does not require the same number of objects as players.
Consequently, an assignment is non-utilitarian not only when the n bundles of
the assignment are allocated ine‰ciently, but also if the m objects are bundled
ine‰ciently. Since cyclical trades under the compensation procedure involve
complete bundles of objects, players may thus still wish to trade individual
objects when the procedure is finished, even though they will not want to trade
complete bundles. However, this type of envy will be di‰cult to identify under
the compensation procedure, because the discounts that players receive apply
only to their complete bundles; they cannot be broken down into partial dis-
counts and associated with individual objects. The compensation procedure
thus establishes envy-freeness for the highest aggregate utility that any player
can identify. In order to obtain an e‰cient bundling of objects, players may
still have to resort to computational support in order to improve their best
initial guess.

7 Conclusions

Our objective in this paper was to formally develop a practical procedure for
multilateral problems of fair-division. Our procedural approach eliminates
envy in a ‘‘natural’’ way: it first identifies the players who are non-envious (we
showed that there will always be at least one if the assignment of bundles
is e‰cient), and then it compensates those players whose maximum envy is
directed towards non-envious players. By first beginning with an e‰cient as-
signment, we formulated the procedure for establishing envy-freeness using
intuitive, plausible, and manageably simple steps. We then showed that the
procedure is also capable of guiding parties to an e‰cient assignment when
the bundles are fixed. Moreover, the outcome of the compensation procedure
is the same no matter which e‰cient assignment is eventually reached.

In our analysis, we placed no bound on the level of individual compensa-



More intriguing information

1. Learning-by-Exporting? Firm-Level Evidence for UK Manufacturing and Services Sectors
2. The name is absent
3. Should Local Public Employment Services be Merged with the Local Social Benefit Administrations?
4. The name is absent
5. Linkages between research, scholarship and teaching in universities in China
6. American trade policy towards Sub Saharan Africa –- a meta analysis of AGOA
7. The mental map of Dutch entrepreneurs. Changes in the subjective rating of locations in the Netherlands, 1983-1993-2003
8. IMPROVING THE UNIVERSITY'S PERFORMANCE IN PUBLIC POLICY EDUCATION
9. Une Gestion des ressources humaines à l'interface des organisations : vers une GRH territoriale ?
10. THE CO-EVOLUTION OF MATTER AND CONSCIOUSNESS1
11. Healthy state, worried workers: North Carolina in the world economy
12. Uncertain Productivity Growth and the Choice between FDI and Export
13. Comparative study of hatching rates of African catfish (Clarias gariepinus Burchell 1822) eggs on different substrates
14. The Importance of Global Shocks for National Policymakers: Rising Challenges for Central Banks
15. Institutions, Social Norms, and Bargaining Power: An Analysis of Individual Leisure Time in Couple Households
16. Implementation of the Ordinal Shapley Value for a three-agent economy
17. The name is absent
18. How we might be able to understand the brain
19. The Interest Rate-Exchange Rate Link in the Mexican Float
20. The Impact of EU Accession in Romania: An Analysis of Regional Development Policy Effects by a Multiregional I-O Model