Near-Feasible Stable Matchings with Budget Constraints
Authors: Yasushi Kawase, Atsushi Iwasaki
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper deals with two-sided matching with budget constraints where one side (firm or hospital) can make monetary transfers (offer wages) to the other (worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota: the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, a hospital instead has a fixed budget: the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence of stable matchings, we extend the matching with contracts model of Hatfield and Milgrom, so that it handles near-feasible matchings that exceed each budget of the hospitals by a certain amount. We then propose two novel mechanisms that efficiently return such a near-feasible matching that is stable with respect to the actual amount of wages allocated by each hospital. In particular, by sacrificing strategy-proofness, our second mechanism achieves the best possible bound. |
| Researcher Affiliation | Academia | Yasushi Kawase Tokyo Institute of Technology and RIKEN AIP Center, Tokyo, Japan. kawase.y.ab@m.titech.ac.jp Atsushi Iwasaki University of Electro-Communications and RIKEN AIP Center, Tokyo, Japan. iwasaki@is.uec.ac.jp |
| Pseudocode | Yes | Algorithm 1: Generalized DA; Algorithm 2:; Algorithm 3: |
| Open Source Code | No | The paper does not provide explicit statements or links to open-source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical models and algorithms; it does not use a dataset for training or evaluation. |
| Dataset Splits | No | The paper focuses on theoretical models and algorithms; it does not use data splits for validation. |
| Hardware Specification | No | The paper does not mention any hardware specifications as it is theoretical in nature and does not report on experiments requiring specific hardware. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers as it focuses on theoretical algorithms. |
| Experiment Setup | No | The paper focuses on theoretical algorithms and their properties; it does not describe an experimental setup with hyperparameters or system-level training settings. |