Graphical One-Sided Markets
Graphical One-Sided Markets
Sagar Massand, Sunil Simon
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 492-498.
https://doi.org/10.24963/ijcai.2019/70
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