A Note on the Equivalence Between Substitutability and M ♮ -convexity

TL;DRAbstract

The property of “substitutability ” plays a key role in guaranteeing the existence of a stable solution in the stable marriage problem and its generalizations. On the other hand, the concept of M♮-convexity, introduced by Murota–Shioura (1999) for functions defined over the integer lattice, enjoys a number of nice properties that are expected of “discrete convexity ” and provides with a natural model of utility functions. In this note, we show that M♮-convexity is characterized by two variants of substitutability.

Chat with Paper

AI Agents for this Paper