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



732


C.-J. Haake et al.

Proof. We check:

∑⅜t(i) = ]Γ(bi(Bπ(0)- bπ(i)(Bπ(0)+ dπ(0)

¼ ∑>‰)-M + £ dia ∑di;

which follows from the definition of M, the maximum sum of bids. The in-
equality is clearly an equality when p is the diagonal assignment.          
r

We keep track of ‘‘chains’’ of envy with the following notation. We write
i ! j if j is the player that i envies the most (if there are several,pick one ar-
bitrarily). In this case
aii <aij and aij is the largest entry in row i. The single
arrows thus only indicate maximum envy relations. We use a double arrow
i ) j if i envies no one but feels tied with jand this tie was the result of an
earlier compensation. Thus
aii =aij, and these are the largest entries in row i.
Note that double arrows only keep track of
created ties, and are not used for
ties occurring ‘‘by coincidence’’ (e.g., where
aii =aij but this was not the result
of a previous compensation). In the sequel when we refer to ‘‘arrow’’ we shall
mean either a single or double arrow unless explicitly specified.

We form a directed graph G in which the vertices represent players and the
edges are given by the arrow relations between players.9 (We shall speak of
‘‘players’’ and ‘‘vertices’’ interchangeably in all that follows.) Throughout the
procedure, the directed graph
G will change. Keeping track of how G evolves
is the key to showing that the procedure terminates.

Lemma 2. At any step in the procedure, the directed graph G contains no cycles.

Proof. If there were a cycle of single arrows, say i1 ! i2 ! ■ ■ ■ ! ik ! i1, then
ai1i1 ai1i2

ai2i2 ai2i3                                                                                         (2)

.
.

aikik <aik i1 ;

and by adding these relations one would find that

ai1i1 + ai2i2 + ■■■ + aikik ai1i2 + ai2i3 + ■■■ + aiki1 ;                               (3)

which augmented by the other diagonal terms would contradict Lemma 1.

A nearly identical argument can be used for cycles in which some (but
not all) of the arrows are double; some of the envy inequalities in (2) would
become equalities, but the inequality (3) would remain strict as long as there
were a single arrow in the cycle.

The only other possibility is a cycle consisting entirely of double arrows.
But this cannot arise, because double arrows only originate from single arrows

9 It is important to note that our directed graph G is simpler than the graphs con-
structed by Aragones (1995) and Klijn (2000), since our procedure only keeps track of
maximum envy.



More intriguing information

1. The name is absent
2. Agricultural Policy as a Social Engineering Tool
3. The Impact of Hosting a Major Sport Event on the South African Economy
4. Großhandel: Steigende Umsätze und schwungvolle Investitionsdynamik
5. SOME ISSUES IN LAND TENURE, OWNERSHIP AND CONTROL IN DISPERSED VS. CONCENTRATED AGRICULTURE
6. The name is absent
7. Revisiting The Bell Curve Debate Regarding the Effects of Cognitive Ability on Wages
8. The name is absent
9. The name is absent
10. The name is absent
11. Valuing Farm Financial Information
12. Empirically Analyzing the Impacts of U.S. Export Credit Programs on U.S. Agricultural Export Competitiveness
13. The name is absent
14. THE ANDEAN PRICE BAND SYSTEM: EFFECTS ON PRICES, PROTECTION AND PRODUCER WELFARE
15. Notes on an Endogenous Growth Model with two Capital Stocks II: The Stochastic Case
16. ALTERNATIVE TRADE POLICIES
17. The name is absent
18. The name is absent
19. The name is absent
20. Moi individuel et moi cosmique Dans la pensee de Romain Rolland