[UTMD-072] Tandem concavity with application to matching problems (by Satoru Fujishige, Koji Yokote)

Satoru Fujishige, Koji Yokote

As a generalization of ordinal concavity we introduce a new notion of discrete concavity called tandem concavity defined for a function over the subsets of a finite set E endowed with an ordered partition (E1,E2) of E. Every function expressed as a lexicographic composition of two ordinally concave functions satisfies tandem concavity. We apply tandem concavity to the rationalization of choice rules in stable matching problems. Moreover, we show that tandem concavity rationalizes a wider class of choice rules in matching markets than ordinal concavity.