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 envy-freeness in this framework.
Keywords
- Agent-based and Multi-agent Systems: Computational Social Choice
- Agent-based and Multi-agent Systems: Algorithmic Game Theory
- Agent-based and Multi-agent Systems: Noncooperative Games
- Agent-based and Multi-agent Systems: Resource Allocation
