  Single minded agents have strict preferences, in which a bundle is acceptable
only if it meets a certain demand. Such preferences arise naturally in
scenarios such as allocating computational resources among users, where the
goal is to fairly serve as many requests as possible. In this paper we study
the fair division problem for such agents, which is harder to handle due to
discontinuity and complementarities of the preferences.
  Our solution concept---the competitive allocation from equal incomes
(CAEI)---is inspired from market equilibria and implements fair outcomes
through a pricing mechanism. We study the existence and computation of CAEI for
multiple divisible goods, cake cutting, and multiple discrete goods. For the
first two scenarios we show that existence of CAEI solutions is guaranteed,
while for the third we give a succinct characterization of instances that admit
this solution; then we give an efficient algorithm to find one in all three
cases. Maximizing social welfare turns out to be NP-hard in general, however we
obtain efficient algorithms for (i) divisible and discrete goods when the
number of different \emph{types} of players is a constant, (ii) cake cutting
with contiguous demands, for which we establish an interesting connection with
interval scheduling, and (iii) cake cutting with a constant number of players
with arbitrary demands.
  Our solution is useful more generally, when the players have a target set of
desired goods, and very small positive values for any bundle not containing
their target set.

Computer Science and Game Theory