Saturday, June 3, 2023

The critical role of Kelso & Crawford in the development of the stable matching literature

 In the physics literature there has long been an interest in economics (econophysics) that takes many forms. Here's a review of stable matching, which identifies Kelso and Crawford as a critical step in the evolution of the matching literature following Gale and Shapley.

Danilov, V.I. Review of the Theory of Stable Matchings and Contract Systems. Computational Mathematics and Mathematical Physics. 63, 466–490 (2023).

"The real development was started by the work of Kelso and Crawford [123], who considered the more general problem of hiring workers (many-to-one). Their problem statement differed from the college admission problem in that the behavior of firms was more flexible than simply setting a quota in [81]. When hiring workers, the firm dealt with a “crowd” of candidates and chose the group of workers it needed from among this crowd. The description of the behavior of such a firm was no longer given by a simple ranking of candidates, but by a choice function. Below, we consider such functions in more detail. An important merit of Kelso and Crawford was that they found the “correct” condition on the choice function, which generalized the Gale–Shapley “linear” choice and which had previously appeared in economics as a substitutability condition. (Later it turned out that such a condition had already been introduced in the choice theory [152] under the name path independence.) Using this condition, Kelso and Crawford [123] showed that the Gale–Shapley algorithm works and gives a stable distribution of workers among firms. In [88], the notion of substitutability was used in the case of indivisible goods and led to a series of papers on this topic (see [79, 51, 65, 103]). Two years later, Roth [158] showed that the same substitutability condition also works well in a many-to-many situation, when firms could hire many workers and workers could work in several firms, see [62]. The results of this direction were summed up in the monograph [160]."

No comments: