In this paper, we consider two-sided, many-to-one matching problems where agents in one side of the market (hospitals) impose some distributional constraints (e.g., a minimum quota for each hospital). We show that when the preference of the hospitals is represented as an M-natural-concave function, the following desirable properties hold: (i) the time complexity of the generalized GS mechanism is O(|X|^3), where |X| is the number of possible contracts, (ii) the generalized Gale & Shapley (GS) mechanism is strategyproof, (iii) the obtained matching is stable, and (iv) the obtained matching is optimal for the agents in the other side (doctors) within all stable matchings.Furthermore, we clarify sufficient conditions where the preference becomes an M-natural-concave function. These sufficient conditions are general enough so that they can cover most of existing works on strategyproof mechanisms that can handle distributional constraints in many-to-one matching problems. These conditions provide a recipe for non-experts in matching theory or discrete convex analysis to develop desirable mechanisms in such settings.
展开▼
机译：在本文中，我们考虑了双向，多对一的匹配问题，即市场一侧（医院）的代理商施加了一些分配限制（例如，每家医院的最低配额）。我们表明，当医院的偏好表示为M-自然凹函数时，具有以下理想属性：（i）广义GS机制的时间复杂度为O（| X | ^ 3），其中| X |是可能的合同数量，（ii）广义Gale＆Shapley（GS）机制具有策略证明力，（iii）所获得的匹配是稳定的，并且（iv）所获得的匹配对于另一方的代理人（医生）是最佳的在所有稳定匹配中。此外，我们阐明了优先条件变为M-自然凹函数的充分条件。这些足够的条件是足够通用的，因此它们可以涵盖大多数关于策略验证机制的工作，这些机制可以处理多对一匹配问题中的分布约束。这些条件为匹配理论或离散凸分析的非专业人士提供了开发此类环境中所需机制的方法。
展开▼
