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



Bidding for envy-freeness

737


for all i; j. Summing the above equation over all j, one obtains that for all i,

Xdj - di) a M - Xbi(Bj).                                 (5)

Choose any player i who was not compensated throughout the entire proce-
dure (there must be at least one, by Theorem 1). Since
di ¼ 0, and since the
sum of the bids of any player is
C or greater, we must have that

X dj a M - C;

which shows that the sum of the compensations does not exceed the sur-
plus.                                                                     
r

5 Dividing the remaining surplus

According to Theorem 4, after the compensation procedure has established
envy-freeness, the remaining surplus
S is given by

S ¼ M - C - X dj b 0.

jAI

With S0, there is surplus left to distribute among the players. The distri-
bution schemes that are of interest here are those that maintain envy-freeness.
There is a convex and compact set of envy-free discounts to choose from.11
We consider two alternative methods for implementing a unique solution.

Equal distribution of the surplus or ‘‘ex-post equal payments’’

With an envy-free assessment matrix at the end of the compensation proce-
dure, no envy will be created if all entries in the matrix are increased by the
same amount. This is easily achieved through an equal distribution of the
remaining surplus among all players. Denoting players’ final discounts under
this equal distribution scheme by
die , this gives

die ¼ di +1 S.                                                               (6)

in

The equal distribution of the remaining surplus was demonstrated in our exam-
ple in Sect. 3. Despite the simplicity of this distribution scheme, some parties
may dislike the procedural asymmetry because they pay different amounts for
their bundles but receive identical shares of the remaining surplus.

Therefore, consider the following modification of the compensation pro-
cedure: parties are assigned bundles, but they
do not pay in advance. Instead,
a (hypothetical) mediator finances the compensation procedure and charges
the group afterwards for total compensations and the cost
C. The mediator

11 The set of envy-free prices is given by a convex polyhedron characterized by n2
inequalities that can be derived from the envy-free assessment matrix.



More intriguing information

1. Regional differentiation in the Russian federation: A cluster-based typification
2. The name is absent
3. The name is absent
4. Weather Forecasting for Weather Derivatives
5. The name is absent
6. On the estimation of hospital cost: the approach
7. Effects of a Sport Education Intervention on Students’ Motivational Responses in Physical Education
8. Impact of Ethanol Production on U.S. and Regional Gasoline Prices and On the Profitability of U.S. Oil Refinery Industry
9. Spectral calibration of exponential Lévy Models [1]
10. The name is absent
11. Does Market Concentration Promote or Reduce New Product Introductions? Evidence from US Food Industry
12. New urban settlements in Belarus: some trends and changes
13. QUEST II. A Multi-Country Business Cycle and Growth Model
14. FUTURE TRADE RESEARCH AREAS THAT MATTER TO DEVELOPING COUNTRY POLICYMAKERS
15. Inflation and Inflation Uncertainty in the Euro Area
16. The name is absent
17. Fiscal Rules, Fiscal Institutions, and Fiscal Performance
18. Learning and Endogenous Business Cycles in a Standard Growth Model
19. Alzheimer’s Disease and Herpes Simplex Encephalitis
20. Searching Threshold Inflation for India