FEBRUARY 2018 | VOL. 61 | NO. 2 | COMMUNICATIONS OF THE ACM 99
average satisfaction level reported for the arbitrary EF solution and maximin solution when relating to each player’s
individual outcome (left chart), and others’ outcomes (right
chart). In all cases, the maximin solution is rated significantly higher than the envy-free solution for both questions,
passing a Wilcoxon signed-rank test with p < 0.04.
Why did players overwhelmingly prefer the prices from the
maximin solution over the arbitrary EF solution? Given the
high importance attributed to social disparity when reasoning
about fair division, 12 we hypothesized that the price vectors of
the maximin solution exhibited significantly lower disparity
than the price vectors of the EF solution. This was supported
by many of the textual comments relating to social disparity.
Figure 5 shows the cumulative distribution of disparity across
all instances that were included in the user study. The x axis
indicates the disparity as percentage of the total rent. As shown
by the figure, the disparity associated with the maximin solution is indeed significantly lower. In fact, in many instances
the disparity is zero under the maximin solution (this is guaranteed to be true when n = 2, as we show in the original version
of the paper). We believe that this large difference in disparity
played a key role in subjects’ preference for the maximin solution, trumping the relatively small improvement in utilities.
address; users can opt to send out URLs to other users, which is
what the vast majority of users choose to do. We only contacted
users who supplied their email address—a relatively small subset of the users who were involved in rent division instances.
All participants were given a $10 compensation that did
not depend on their responses. In total, the invitation email
was sent to 344 Spliddit users, of which 46 users (13%) chose
to participate. The study was approved by the Institutional
Review Board (IRB) of Carnegie Mellon University.
The study followed a within-subject design, by which each
of the subjects was shown, in random order, an arbitrary EF
solution (as discussed in Section 5) and the maximin solution, applied to their original problem instance.
Importantly, we wished to preserve the privacy of players regarding their evaluations over the different rooms.
Therefore, each player who participated in the study was
shown a slightly modified version of their own rent division
problem. Information that was already known to each subject was identical to the original Spliddit instance, including
the total rent, the number of rooms, their names, the subject’s own values for the different rooms, and the allocation
of the rooms to the players. Information that was perturbed
to preserve the privacy of the other players included their
names, which were changed to “Alice”, “Bob” or “Claire”,
depending on whether there were 2, 3, or 4 players; and the
other players’ valuations, which were randomly increased
or decreased by a value of up to 15% under the constraint
that the total rent is unchanged, and that player valuations
are still valid (non-negative and sum to the total rent).
The subjects were shown the two solutions—maximin
and arbitrary EF—for the instance presented to them. Both
solutions include the same room allocation, but possibly
differ in the prices paid by the players. The two solution outcomes were shown in sequence, and in random order.
The subjects were asked to rate two different aspects of
each of the two solutions on a scale from 1 to 5, with 1 being
least satisfied and 5 being most satisfied. The two aspects
are the subject’s individual allocation, and the allocations of
the other players. The two questions were phrased as follows
(using an example with n = 3):
1. Individual: This question relates to your own allocation. In other words, we would like you to pay attention
only to your own benefit. How happy are you with getting the room called 〈RoomName〉 for 〈price〉?
2. Others: This question relates to the allocation for
everyone else. How fair do you rate the allocation for
Bob and Claire?
In both questions, players were able to write an argument or
justification for their rating. To cancel order effects, the two
questions were presented in random order.
6. 2. Results
We hypothesized that players would rate their own allocation under the maximin solution significantly higher than
under the EF solution, and similarly for the allocation of
the other participants. Figure 4 shows the results of the
user study. For each number of players ( 2, 3, 4) we show the
Figure 4. Results of the user study.
2 3 4 All
3. 28 3. 19
Number of players
2 3 4 All
2. 71 2. 82
4 3. 92
Number of players