Abstract
We study the problem of allocating indivisible objects to a set of rational agents where each agent’s
final utility depends on the intrinsic valuation of the
allocated item as well as the allocation within the
agent’s local neighbourhood. We specify agents’
local neighbourhood in terms of a weighted graph.
This extends the model of one-sided markets to
incorporate neighbourhood externalities. We consider the solution concept of stability and show that,
unlike in the case of one-sided markets, stable allocations may not always exist. When the underlying local neighbourhood graph is symmetric, a 2-
stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational players agree to exchange objects terminates in such an
allocation. We show that computing a 2-stable allocation is PLS-complete and further identify subclasses which are tractable. In the case of asymmetric neighbourhood structures, we show that it is
NP-complete to check if a 2-stable allocation exists. We then identify structural restrictions where
stable allocations always exist and can be computed
efficiently. Finally, we study the notion of envyfreeness in this framework