Maximizing Nash Social Welfare under Two-Sided Preferences
Authors: Pallavi Jain, Rohit Vaish
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our work deviates from this trend and studies NSW maximization for two-sided preferences, wherein a set of workers and firms, each having a cardinal valuation function, are matched with each other. We provide a systematic study of the computational complexity of maximizing NSW for many-to-one matchings under two-sided preferences. Our main negative result is that maximizing NSW is NP-hard even in a highly restricted setting... In search of positive results, we develop approximation algorithms as well as parameterized algorithms... We also provide algorithms for restricted domains... |
| Researcher Affiliation | Academia | 1Indian Institute of Technology Jodhpur, India 2Indian Institute of Technology Delhi, India |
| Pseudocode | No | The paper describes algorithms (e.g., dynamic programming, polynomial multiplication, greedy algorithm) in text but does not include any structured pseudocode blocks or clearly labeled algorithm listings. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not use or reference any datasets, and therefore no training, validation, or test splits are applicable or provided. |
| Hardware Specification | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not involve empirical experiments requiring specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not mention any specific software dependencies with version numbers for reproducing experiments. |
| Experiment Setup | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not describe any empirical experimental setup details such as hyperparameters or system configurations. |