Graphical One-Sided Markets
Authors: Sagar Massand, Sunil Simon
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 2stable 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. |
| Researcher Affiliation | Academia | Sagar Massand and Sunil Simon Department of CSE, IIT Kanpur, Kanpur, India {smassand, simon}@cse.iitk.ac.in |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., a link to a repository or an explicit statement of code release) for open-source code related to its methodology. |
| Open Datasets | No | The paper is a theoretical work focusing on model properties and complexity. It does not utilize or describe any datasets for training or empirical evaluation, thus no public availability information for a dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with data. Therefore, it does not describe dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper does not describe any specific hardware used to run experiments, as it is a theoretical work. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers for replication or running experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and complexity analysis. It does not include details about an experimental setup, such as hyperparameters or system-level training settings. |