reported evaluations), the algorithm does provide nonintuitive solutions in some cases. This prompted an investigation
of alternative approaches, and ultimately led to the deployment of a new algorithm in April 2015, based entirely on the
results presented in (the original version of) this paper.
It is important to point out that Spliddit not only motivates our research questions, but also helps answer them.
Indeed, while Spliddit’s primary goals are making fair division methods accessible to people, and outreach, a secondary goal is the collection of an unprecedented dataset for
fair division research. 9 This real-world dataset is exciting
because, as noted by Herreiner and Puppe, 12 fair division is
hard to study in the lab: researchers can tell subjects what
their valuations are for different goods, but these values are
not ecologically realistic, in that they do not represent subjects’ actual preferences. To quote Herreiner and Puppe, 12
“the goods in the lab are not really distributed among participants, but serve as temporary substitutes for money.”
In contrast, Spliddit instances are ecologically valid, as
they are posed by real people facing real division problems.
Thus the Spliddit data enables studies at a realistic level and
scale that was not possible before. Even better, we can ask
Spliddit users to evaluate different solutions based on the
actual instances they participated in. This is exactly what we
do in this paper.
1. 2. Our results
We start, in Section 3, by constructing a general yet simple
algorithmic framework for optimization under the envy free-
ness constraint. Specifically, our algorithm maximizes the
minimum of linear functions of the utilities, subject to envy
freeness, in polynomial time. We do this by using the Second
Welfare Theorem to argue that we can employ any welfare-
maximizing assignment of players to rooms, and then solve
a linear program to compute the optimal envy free prices.a
Our main goal in Section 4 is to understand the relation
between two solution concepts: the maximin solution, 2 which
maximizes the minimum utility of any player subject to
envy freeness; and the equitable solution, which minimizes
disparity—the maximum difference in utilities—subject to
envy freeness. (Our algorithm can compute either solution
in polynomial time.) Our most significant result in this sec-
tion is proving that the maximin solution is also equitable,
but not every equitable solution is maximin.
Based on these results, we have implemented the polynomial-time algorithm of Section 3, with the maximin objective
function.b As noted above, it has been deployed on Spliddit
since April 2015.
a It is interesting to note that, even though the instances on Spliddit are
small, computational tractability does play a key role, as there are many instances and computation incurs a cost (Spliddit uses Amazon Web Services
to run all its algorithms).
b To be completely precise, the algorithm deployed on Spliddit first tries to
maximize the minimum utility, subject to envy freeness as well as an additional constraint: prices must be non-negative. If an envy-free solution with
non-negative prices does not exist [ 4], it removes the non-negative price
constraint (in which case a solution always exists). Most of our results go
through even when prices are assumed to be non-negative. In any case, real-world instances where negative prices actually help are extremely rare, so
throughout the paper prices are unconstrained.
Figure 1. Envy-free solutions, illustrated.
(a) Values, shown by colored boxes. For example, the values
of the green, blue, and red players for Room 1 are 6, 5, and
4, respectively. Note that the values of each player for the
three rooms add up to the total rent of 10.
(b) Prices, shown by gray boxes, and utilities. For example,
the price of Room 1 is 5, and the utility of the green player
for Room 1 at its price is 6 − 5 = 1.
(c) An envy-free solution. For example, the green player is
not envious because he has utility 1 for his room (Room 1),
utility − 1 for Room 2 (indicated by an “X” in the top box),
and utility 0 for Room 3.
Room 2 Room 3