Finding maxmin allocations in cooperative and competitive fair division

We define a subgradient algorithm to compute the maxmin value of a completely divisible good in both competitive and cooperative strategic contexts. The algorithm relies on the construction of upper and lower bounds for the optimal value which are based on the convexity properties of the range of utility vectors associated to all possible divisions of the good. The upper bound always converges to the optimal value. Moreover, if two additional hypotheses hold: that the preferences of the players are mutually absolutely continuous, and that there always exists relative disagreement among the players, then also the lower bound converges, and the algorithm finds an approximately optimal allocation