{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:28:01Z","timestamp":1778498881081,"version":"3.51.4"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>We study the problem of allocating indivisible objects to a set of\nrational agents where each agent's final utility depends on the\nintrinsic valuation of the allocated item as well as the allocation\nwithin the agent's local neighbourhood. We specify agents' local\nneighbourhood in terms of a weighted graph. This extends the model of\none-sided markets to incorporate neighbourhood externalities. We\nconsider the solution concept of stability and show that, unlike in the\ncase of one-sided markets, stable allocations may not always\nexist. When the underlying local neighbourhood graph is symmetric, a\n2-stable allocation is guaranteed to exist and any decentralised\nmechanism where pairs of rational players agree to exchange objects\nterminates in such an allocation. We show that computing a 2-stable\nallocation is PLS-complete and further identify subclasses which are\ntractable. In the case of asymmetric neighbourhood structures, we show\nthat it is NP-complete to check if a 2-stable allocation exists. We then\nidentify structural restrictions where stable allocations always exist\nand can be computed efficiently. Finally, we study the notion of envy-freeness in this framework.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/70","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"492-498","source":"Crossref","is-referenced-by-count":7,"title":["Graphical One-Sided Markets"],"prefix":"10.24963","author":[{"given":"Sagar","family":"Massand","sequence":"first","affiliation":[{"name":"Department of CSE, IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunil","family":"Simon","sequence":"additional","affiliation":[{"name":"Department of CSE, IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","theme":"Artificial Intelligence","location":"Macao, China","acronym":"IJCAI-2019","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2019,8,10]]},"end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:34Z","timestamp":1564285594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/70"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/70","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}