Structural Complexities of Matching Mechanisms

We study various novel complexity measures for two-sided matching mechanisms, applied to the two canonical strategyproof matching mechanisms, Deferred Acceptance (DA) and Top Trading Cycles (TTC). Our metrics are designed to capture the complexity of various structural (rather than computational) concerns, in particular ones of recent interest within economics. We consider a unified, flexible approach to formalizing our questions: Define a protocol or data structure performing some task, and bound the number of bits that it requires. Our main results apply this approach to four questions of general interest; for mechanisms matching applicants to institutions, our questions are:

(1) How can one applicant affect the outcome matching?

(2) How can one applicant affect another applicant's set of options?

(3) How can the outcome matching be represented / communicated? (4) How can the outcome matching be verified?

Holistically, our results show that TTC is more complex than DA, formalizing previous intuitions that DA has a simpler structure than TTC. For question (2), our result gives a new combinatorial characterization of which institutions are removed from each applicant's set of options when a new applicant is added in DA; this characterization may be of independent interest. For question (3), our result gives new tight lower bounds proving that the relationship between the matching and the priorities is more complex in TTC than in DA. We nonetheless showcase that this higher complexity of TTC is nuanced: By constructing new tight lowerbound instances and new verification protocols, we prove that DA and TTC are comparable in complexity under questions (1) and ( 4). This more precisely delineates the ways in which TTC is more complex than DA, and emphasizes that diverse considerations must factor into gauging the complexity of matching mechanisms.