Popular and Dominant Matchings with Uncertain and Multimodal Preferences
Authors: Gergely Csáji
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the Popular Matching (PM) problem in multiple models, where the preferences of the agents in the instance may change or may be unknown or uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preference lists, a Multilayer model, where there are layers of preference profiles, and a Robust popularity model, where any agent may move some other agents up or down some places in his preference list. We study both one-sided (only one class of the agents have preferences) and two-sided bipartite markets. In the one-sided model, we show that all our problems can be solved in polynomial time by utilizing the structure of popular matchings. We also obtain nice structural results. With two-sided preferences, we show that all three above models lead to NP-hard questions for popular matchings. By using the connection between dominant matchings and stable matchings, we show that in the robust and uncertainty models, a certainly dominant matching in all possible preference profiles can be found in polynomial time, whereas in the multilayer model, the problem remains NP-hard for dominant matchings too. We also answer an open question about d-robust stable matchings. |
| Researcher Affiliation | Academia | Gergely Cs aji1,2 1 HUN-REN KRTK KTI 2 ELTE E otv os Lor and University csaji.gergely@krtk.hun-ren.hu |
| Pseudocode | No | The paper describes algorithms and solutions, such as using the Hungarian-algorithm, Egerváry's algorithm, or Linear Programming, but it does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing access to any source code for its methods or implementations. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or evaluation. Its contributions are in algorithm design and complexity analysis. |
| Dataset Splits | No | The paper is theoretical and does not involve data splits for training, validation, or testing, as it does not conduct experiments on datasets. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments; therefore, no specific hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe computational experiments. It refers to established algorithms (e.g., Hungarian-algorithm, Egerváry's algorithm), but it does not list any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe an experimental setup with hyperparameters, training configurations, or other system-level settings. |