RUS  ENG
Full version
JOURNALS // Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki // Archive

Zh. Vychisl. Mat. Mat. Fiz., 2023 Volume 63, Number 3, Pages 491–516 (Mi zvmmf11530)

This article is cited in 3 papers

Computer science

Review of the theory of stable matchings and contract systems

V. I. Danilov

Central Economics and Mathematics Institute, Russian Academy of Sciences, 117418, Moscow, Russia

Abstract: A review of works devoted to the theory of stable matchings or, more generally, of stable networks of contracts is given. A set (network) of contracts is called stable if no coalition has an available contract that gives all coalition members strictly more than the proposed set. In a special case, this concept was introduced in 1962 by Gale and Shapley and has since gone a long way in its development both theoretically (theorems, structures, and algorithms) and in the field of applications in economics, physics, biology, and mathematics.

Key words: stable matching, stable roommate, networks of contracts, phenomenon of rural hospitals, lattice, manipulation, Scarf’s lemma, hypergraph, perfect graph, choice function.

UDC: 519.865

Received: 22.06.2022
Revised: 10.07.2022
Accepted: 17.11.2022

DOI: 10.31857/S0044466923030067


 English version:
Computational Mathematics and Mathematical Physics, 2023, 63:3, 466–490

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2026