Fractional Matchings under Preferences: Stability and Optimality
Authors: Jiehua Chen, Sanjukta Roy, Manuel Sorge
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We complete the complexity classification of both optimization problems for both ordinal stability and cardinal stability, distinguishing between the marriage (bipartite) and roommates (non-bipartite) cases and the presence or absence of ties in the preferences. In particular, we prove a surprising result that finding a cardinally stable fractional matching with maximum social welfare is NP-hard even for the marriage case without ties. |
| Researcher Affiliation | Academia | Jiehua Chen , Sanjukta Roy and Manuel Sorge TU Wien, Austria {jiehua.chen, sanjukta.roy, manuel.sorge}@tuwien.ac.at |
| Pseudocode | Yes | Algorithm 1: Compute an OSM for (G, sat). ... Algorithm 2: Irving s phase-1 algo. on input (G, sat) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | This is a theoretical paper focusing on complexity and structural properties of algorithms, and does not involve the use of empirical datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical validation on datasets with training, validation, and test splits. |
| Hardware Specification | No | This is a theoretical paper and does not describe any experimental setup requiring specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not specify software dependencies with version numbers, as it does not involve empirical implementations. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training configurations. |