[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). 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. We show that tandem concavity rationalizes a wider class of choice rules than ordinal concavity.