The Blocking Lemma and strategy-proofness in many-to-many matchings

• Published in: Games and economic behavior 2017-03, Vol.102, p.44-55
• Main Authors: Jiao, Zhenhua, Tian, Guoqiang
• Format: Article
• Language: English
• Subjects: Blocking Lemma; Deferred acceptance algorithm; Many-to-many matching; Max–min preferences; Strategy-proofness
• ISSN: 0899-8256; 1090-2473
• DOI: 10.1016/j.geb.2016.10.015

•This paper considers the incentive compatibility in many-to-many two-sided matching problems.•We propose the extended max–min preference criterion and the quota-saturability condition.•We show that the Blocking Lemma holds for many-to-many matchings under the above two conditions.•This result extends the Blocking Lemma for one-to-one matching and for many-to-one matching to many-to-many matching problem.•It is then shown that the deferred acceptance mechanism is strategy-proof for agents on the proposing side under the above two conditions. This paper considers the incentive compatibility in many-to-many two-sided matching problems. We first show that the Blocking Lemma holds for many-to-many matchings under the extended max–min preference criterion and quota-saturability condition. This result extends the Blocking Lemma for one-to-one matching and for many-to-one matching to many-to-many matching problem. It is then shown that the deferred acceptance mechanism is strategy-proof for agents on the proposing side under the extended max–min preference criterion and quota-saturability condition. Neither the Blocking Lemma nor the incentive compatibility can be guaranteed if the preference condition is weaker than the extended max–min criterion.