  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 envy-freeness in this framework.
