for all i ∈ [n], with strict inequality for at least one i ∈ [n]. To
see this, note that σ is welfare-maximizing by Theorem 3. 2,
and the sum of prices is 1 under both p and p¢.
We are now ready to present our polynomial-time algorithm for maximizing the minimum of linear functions
f1, . . ., ft of the utilities, subject to EF; it is given as Algorithm 1.
1. Let be a welfare-maximizing
2. Compute a price vector p by solving the linear program
The algorithm starts by computing a welfare-maximizing
assignment σ of players to rooms; this can be done in polynomial time, as this task reduces to the maximum weight
bipartite matching problem, with players on one side of the
graph, rooms on the other, and a weight vij on each edge (i, j).
It then solves (in polynomial time) a linear program, with
variables p1, . . ., pn, which computes optimal envy-free prices
with respect to σ. The first constraint sets (in an optimal solution) the objective R to the minimum of the linear functions
fq(⋅). Envy-freeness is enforced by the second constraint, and
the third constraint guarantees that the prices sum to 1.
However, it may not be immediately clear why starting
from an arbitrary welfare-maximizing assignment allows us
to compute the optimal solution subject to envy freeness.
In a nutshell, the reason is the second Welfare Theorem: If
(σ¢, p) is an optimal EF solution, and σ is an arbitrary welfare-maximizing assignment, then (σ, p) is EF (so p is a feasible solution to the linear program) and induces the same
utilities as (σ¢, p), that is, it achieves the same objective
4. RELATIONS BETWEEN THE FAIREST SOLUTIONS
Algorithm 1 allows us to maximize the minimum of linear
functions of the utilities, subject to EF, in polynomial time.
With the potential computational barrier out of the way,
we would like to understand which optimization objective
to use. Specifically, we focus on two natural optimization
objectives, and evaluate their properties.
We refer to the first objective as equitability. Let EF(V) be
the set of all EF solutions for V. Given a solution (σ, p) ∈ EF(V),
we define D(σ, p) as the difference between the utilities of
the happiest player and the worst off player under the solution
(σ, p), that is,
In more general terms, the function D measures the social
disparity under the solution (σ, p); we would like to minimize
can be done in polynomial time, when the objective func-
tion is the minimum of linear functions of the utilities.
Theorem 3. 1. Let f1, . . ., ft: Rn → R be linear functions, where
t is polynomial in n. Given a rent division instance V, a solution
(σ, p) that maximizes the minimum of fq(u1(σ, p), ..., un(σ, p))
over all q ∈ [t] subject to envy freeness can be computed in
Natural examples of objective functions of the form spec-
ified in the theorem are maximizing the minimum utility,
and minimizing the maximum difference in utilities; we dis-
cuss these objectives in detail in Section 4. The former objec-
tive can be directly captured by setting t = n, and fi(u1(σ, p),
. . ., un(σ, p) ) = ui(σ, p) for all i ∈ [n]. The latter criterion is also
captured by setting t = n2 and,
so maximizing the minimum of these linear functions is equivalent to minimizing the maximum difference in utilities.
Our polynomial-time algorithm relies on a connection
between envy-free rent division and the concept of Walrasian
equilibrium. To understand this connection, imagine a
more general setting where a set of buyers [n] are interested
in purchasing bundles of goods G; here, each buyer i has a
valuation function vi: 2G → R, assigning a value vi(S) to every
bundle of goods. A Walrasian equilibrium is an allocation A
= (A1, . . ., An) of the goods to buyers (where Ai ⊆ G is the bundle
given to buyer i), coupled with a price vector p that assigns
a price to each good, such that each player receives the best
bundle of goods that she can buy for the price p; formally:
. ( 2)
We say that an allocation A is welfare-maximizing if it maximizes . The following properties of Walrasian
equilibria are well known; see, for example, the book of
Mas-Colell et al. 16 (Chapter 16).
Theorem 3. 2 (1st Welfare Theorem). If (A, p) is a Walrasian
equilibrium, then A is a welfare-maximizing allocation.
Theorem 3. 3 (2nd Welfare Theorem). If (A, p) is a
Walrasian equilibrium, and A¢ is a welfare-maximizing
allocation, then (A¢, p) is a Walrasian equilibrium as well.
Furthermore, vi (Ai) – p(Ai) = vi(A¢ i ) – p(A¢ i ) for all i ∈ [n].
Now, an EF solution in the rent division setting is a
Walrasian equilibrium in the setting where the goods are the
rooms, and the valuation function of each player for a subset
S ⊆ [n] of rooms is given by vi(S) = maxj∈S vij (these are unit
demand valuations)—it is easily seen that Equation ( 1) coincides with Equation ( 2) in this case. This means that we can
apply the welfare theorems to EF allocations. For example,
we can immediately deduce a simple result of Svensson19:
any EF solution (σ, p) is Pareto efficient, in the sense that
there is no other solution (σ¢, p¢) such that ui(σ¢, p¢) ≥ ui(σ, p)