Approximately Stable Matchings With Budget Constraints
Authors: Yasushi Kawase, Atsushi Iwasaki
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We then propose two novel mechanisms that efficiently return a stable matching that exactly satisfies the budget constraints. Specifically, by sacrificing strategy-proofness, our first mechanism achieves the best possible bound. We also explore a special case on which a simple mechanism is strategy-proof for doctors, while maintaining the best possible bound of the general case. The contribution of this paper is twofold: First, we modify the generalized DA algorithm and devise a new property, which we call α-approximation... Second, we propose two novel mechanisms that efficiently return a stable matching that exactly satisfies the budget constraints. Specifically, by sacrificing strategy-proofness, the best possible bound is achieved. |
| 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:; Algorithm 4:; Algorithm 5: |
| Open Source Code | No | The paper provides a link to its full version on arXiv (http://arxiv.org/abs/1711.07359), but this is a link to the paper itself, not to open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets for training, validation, or testing. It includes an example trace, but not a dataset for public use. |
| Dataset Splits | No | The paper is theoretical and does not report on empirical experiments or specify any dataset splits for validation. |
| Hardware Specification | No | The paper is purely theoretical and does not report on any experiments that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper focuses on theoretical algorithms and proofs; it does not provide specific software dependencies or version numbers needed for replication. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and their properties, but it does not report on empirical experiments, therefore no experimental setup details like hyperparameters or training configurations are provided. |