740
C.-J. Haake et al.
players’ maximum possible discounts under envy-freeness differ. The asym-
metry becomes apparent if the remaining surplus is used to maximize the dis-
count ofa specific player i,while raising the discounts of the other players just
enough to maintain envy-freeness. If this is done with each of the n players,
one obtains n extreme discount distributions, each favoring a specific player.
The average discount method takes the average of these n extreme surplus
distributions, yielding a unique outcome, generally in the interior of the envy-
free set.13
Focusing on a specific player i A I, we denote by diji Player i’s own maxi-
mum discount and the minimum corresponding discounts of all other players
j A I by djji. At the start,all players’ discounts are as given by the compensa-
tion procedure, i.e., djji :¼ dj, j A I.14 The extreme discounts djji are then
updated according to the following four-step algorithm.
The average discount method
(i) Begin by placing Player i in the set D of players whose discounts are to
be increased. Formally: D :¼ fig.
(ii) Add to the set D all the players who are not in D but feel tied with some
player in D. Note that these are the players who would become envious if
the discounts of the players in D were increased. Continue looking for
additional players to be included in D until only those players are left
(outside of D) who value the discounted bundle of every player in D
less than their own. Formally: D+ :¼ D w fh a InD j ahj ¼ αhh; j a Dg. If
D+ 0 D, then D :¼ D+, and repeat Step (ii).
(iii) If the set D contains all the players of I, then distribute the remaining
surplus equally among the players. Otherwise, determine how far the dis-
counts of the players in D can be raised without creating envy for any
player who is not in D. The discounts of the players in D can then be
increased up to this maximum amount as long as there is enough sur-
plus left. Update the discounts of the players in D, recalculate the corre-
sponding columns of the assessment matrix, and recalculate the remain-
ing surplus. Formally: if D ¼ I, then increase the discounts of all players
by d+ :=jD; else determine d+ :¼ min(mmAai∖d{α⅛⅛ - α⅛j; j a Dg;ɪ.
Update: dj∣i∙ := d∣i∙ + d+; aj := aj + d+, Ej a D; S := M — C — Pj-Ai dj∣i∙.
(iv) If there is no surplus left (which happens ifd+ ¼ S=jDj), quit. Otherwise,
if some surplus remains, we need to update D by returning to Step (ii).
(The updated discounts from the last step will have created players, not
in D, who feel tied with players belonging to D.) Formally: if S ¼ 0, quit.
If S > 0, return to Step (ii).
13 More generally, one could also maximize the discounts of every subset of players,
thus tracing out all the corners of the polyhedron of envy-free prices, and then take the
midpoint of all outcomes.
14 We use ‘‘:=’’ as an assignment operator to update variables in the following way:
the value of the term on the right-hand side is assigned to the variable on the left-hand
side.