Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Weighted Matching Markets with Budget Constraints
Authors: Anisse Ismaili, Naoto Hamada, Yuzhe Zhang, Takamasa Suzuki, Makoto Yokoo
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate markets with a set of students on one side and a set of colleges on the other... We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is co NP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is ΣP 2 -complete: NPNP-complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Thus, we consider a restricted market called a typed weighted market... We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets. This paper examined two-sided matchings with budget constraints and showed several computational hardness results for problems related to coalitional stability. Then, we designed a strategy-proof mechanism, which is pairwise stable and Pareto efficient among the pairwise stable outcomes. |
| Researcher Affiliation | Academia | Anisse Ismaili EMAIL RIKEN Center for Advanced Intelligence Project Naoto Hamada EMAIL Graduate School of Information Science and Electrical Engineering, Kyushu University Yuzhe Zhang EMAIL Bernoulli Institute, University of Groningen Takamasa Suzuki EMAIL Gifu Shotoku Gakuen University Makoto Yokoo EMAIL Graduate School of Information Science and Electrical Engineering, Kyushu University |
| Pseudocode | Yes | Definition 15 (Deferred Acceptance mechanism (DA)). 1. Re . 2. Y Ch ˆS(X ˆS \ Re), Z Ch C(Y ). 3. If Y = Z, then return Y , otherwise: Re Re (Y \ Z), go to Step 2. Mechanism 1 (Sequential Deferred Acceptance) Let Y and i 1. Round i : 1. Let ˆS {s S | τ(s) = θi}, i.e., the set of all type θi students, and run the DA. 2. Let Y i be the obtained matching. Y Y Y i. 3. If i = k then return Y , otherwise: c C, bc bc P x Y ic x W ; i i + 1; Go to Round i. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on mechanism design and computational complexity; it does not present empirical experiments that use datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets, thus no dataset splits are discussed. |
| Hardware Specification | No | The paper is theoretical and does not involve experiments that would require specific hardware. |
| Software Dependencies | No | The paper is theoretical and does not involve experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup or hyperparameters. |