Designing matching mechanisms under constraints: An approach from discrete convex analysis

Fuhito Kojima, Akihisa Tamura, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)


We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.

Original languageEnglish
Pages (from-to)803-833
Number of pages31
JournalJournal of Economic Theory
Publication statusPublished - 2018 Jul


  • Deferred acceptance
  • Discrete convex analysis
  • Market design
  • Matching with constraints
  • Matching with contracts
  • Two-sided matching

ASJC Scopus subject areas

  • Economics and Econometrics


Dive into the research topics of 'Designing matching mechanisms under constraints: An approach from discrete convex analysis'. Together they form a unique fingerprint.

Cite this