Let us now discuss a third optimization objective, the
money-Rawlsian solution, which is mentioned by Alkan
et al., 2 and implemented in polynomial time by Aragones. 3
The latter author describes the following procedure for finding EF solutions. Begin by finding a welfare-maximizing
assignment of rooms (again, assume without loss of generality that room i goes to player i); next, find a vector of
non-negative values such that and
is minimized. That is, each player i pays a value of . Next,
increase the prices of all players by a quantity α such that
nα − Q = 1, that is the vector (α, . . ., α) − q is a valid price vector.
While the money-Rawlsian solution is interesting, it may
be “maximally unfair” in terms of disparity, as the following
Example 4. 3. We analyze the following rent division instance:
The welfare-maximizing assignment allocates room i to
player i, and q = (0, . . ., 0). A uniform increase in rent will
ensue, resulting in the price vector (1/2, 1/2) and the utility
vector (1/2, 0). Crucially, the money-Rawlsian price vector
maximizes disparity among all EF solutions. Note that the
maximin price vector is (3/4, 1/4), which, of course, minimizes disparity.
To conclude, so far we know that the maximin solution,
the equitable solution, and the money-Rawlsian solution
can be computed in polynomial time. Moreover, Theorem
4. 1 shows that the maximin solution, which by definition
maximizes the minimum utility, also minimizes disparity
(among all EF solutions)—so it is a refinement of the equitable solution. In stark contrast, the money-Rawlsian solution may maximize disparity (among all EF solutions). We
therefore view the maximin solution as the clear choice, and
focus on analyzing its effectiveness hereinafter.
5. ON THE IMPORTANCE OF BEING EQUITABLE
Our goal in this section is to understand how much better
the maximin solution is, in terms of the maximin and disparity objectives, compared to suboptimal solutions on average. The original version of the paper includes a theoretical
analysis in a formal probabilistic model. Here we focus on
empirical results, which demonstrate the practical benefit
of the maximin solution with respect to real-world instances
that were submitted by Spliddit users.
In our experiments, we compare the maximin solution
to an arbitrary EF solution, which is obtained by solving a
feasibility linear program without an optimization objective. (We note that similar empirical results are obtained
when comparing the maximin solution to the algorithm of
Abdulkadiroğlu et al. 1) The comparison is in terms of both
of our main objectives, D and U (which are simultaneously
optimized by the maximin solution). We expected that D
would be significantly lower, and U significantly higher, in the
maximin solution compared to an arbitrary EF solution.
We focus our analysis on 1,358 rent division instances
involving 3,682 players, which were submitted on Spliddit
this quantity. An outcome (σ*, p*) is called equitable if it
minimizes D over EF(V), that is,
Herreiner and Puppe12 demonstrate via experiments with
human subjects that equitability is of great importance in deter-
mining whether an allocation is perceived to be fair by people.
Alternatively, instead of minimizing social disparity, one
might be interested in maximizing the utility of the worst
off player. More formally, given an EF solution (σ, p), we let
U(σ, p) = mini∈N ui(σ, p); if
then we say that (σ*, p*) is a maximin solution.
Alkan et al. 2 argue that the maximin solution—which
they call the value-Rawlsian solution—is compelling on philosophical grounds. Mathematically, they demonstrate that
the maximin solution is associated with a unique vector of
utilities, making this solution even more appealing.
The fact that equitable and maximin allocations are
constrained to be EF again allows us to employ the Second
Welfare Theorem (Theorem 3. 3) to great effect. Indeed, if
(σ*, p*) is equitable (resp., maximin), and σ¢ is a welfare-maximizing assignment, then (σ¢, p*) is equitable (resp.,
maximin). Therefore, hereinafter we assume without loss
of generality that the identity assignment σ(i) = i is welfare
maximizing, and simply use D(p) or U(p) to refer to these
measures under the identity assignment. In particular, we
can talk about equitable or maximin vectors of prices with
respect to the identity assignment.
At first glance, the equitability and maximin criteria seem
equally appealing. Which one leads to fairer solutions? The
next theorem shows that we do not have to choose—the
maximin solution is equitable.
Theorem 4. 1. If p is a maximin vector of prices, then it is also
By contrast, an equitable solution may not be maximin,
as the following example shows.
Example 4. 2. This example is particularly appealing, as it is
a real-world instance submitted by Spliddit users.
Note that the total rent is $2935. The optimal room
assignment gives room i to player i; the maximin rent division is , with a utility vector of
, , . We have
, and by Theorem 4. 1 any solution
that has the same disparity is equitable. However, the price
vector is an EF rent division resulting in , , , and
as well, that is, it is equitable, but the
minimum utility is (much) smaller than that under p*.