  We study the complexity of finding a Walrasian equilibrium in markets where
the agents have $k$-demand valuations. These valuations are an extension of
unit-demand valuations where a bundle's value is the maximum of its
$k$-subsets' values. For unit-demand agents, where the existence of a Walrasian
equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$,
we show that it is NP-hard to decide if a Walrasian equilibrium exists even if
the valuations are fractionally subadditive (XOS), while for $k=3$ the hardness
carries over to budget-additive valuations. In addition, we give a
polynomial-time algorithm for markets with 2-demand single-minded valuations,
or unit-demand valuations.
