Optimization and Equilibrium Seminar “Satisficing Matching: the One-to-One Case”

Abstract: We bring the notion of “satisficing” behavior to matching theory and develop the resulting solution concept, which is weaker than stability. Satisficing behavior is an alternative to maximizing behavior where, instead of always going for the best alternative, “satisficers” settle on choices that are “good enough”. We say that a matching is satisficing if every agent is matched to an achievable partner. (An agent is achievable to another if they are matched in some stable matching.)

We show that satisficing matchings have the following properties: (i) they are Pareto efficient; (ii) all women (men) weakly prefer the woman-optimal (man-optimal) stable matching to any satisficing matching; (iii) for any two distinct satisficing matchings, there exist two pairs, each formed under one of the two matchings, such that the agents in each pair have opposite preferences over the two matchings; (iv) if agents are asked to vote between a stable matching and a satisficing matching, the two matchings tie; and (v) truthtelling is a rationalizable strategy for satisficing mechanisms.

We also argue that our definition is falsifiable upon the observation of all satisficing matchings, and discuss how existing algorithms can be used for the computation of the set of satisficing matchings. Finally, using as operator an extension, via the join, of the least upper bound of the common order of one gender, we show that the set of satisficing matchings forms a semigroup one of whose ideals is the set of stable matchings.

Speaker: Andrés Carvajal (Departamento de Ingeniería Industrial, Universidad de Chile)