We introduce the classified stable matching problem, a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both institutes and applicants have preferences over the other side. An institute classifies the applicants based on their research areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which no group of participants has reason to deviate. Moreover, the matching should respect the upper lower bounds of the classes. In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of order types.'' We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching. In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matching polytope and prove that it is integral. This integrality allows us to find various optimal stable matchings using Ellipsoid algorithm. A further ramification of our result is the description of the stable matching polytope for the many-to-many (unclassified) stable matching problem. This answers an open question posed by Sethuraman, Teo and Qian.
Stable matching problems have drawn the intensive attention of researchers in various disciplines in the past decades since the seminal paper of Gale and Shapley @cite_13 . For a summary, see @cite_22 @cite_9 @cite_5 . Vande Vate @cite_3 initiated the study of stable matching using mathematical programming approach; further developments using this approach can be found in @cite_12 @cite_23 @cite_10 @cite_7 @cite_6 @cite_17 @cite_8 .
@cite_22 @cite_7 @cite_8 @cite_10 @cite_9 @cite_3 @cite_6 @cite_23 @cite_5 @cite_13 @cite_12 @cite_17
1978696336 2066306418 2168987865 2004854811 2033701176 2093966655 2017008045 1563534733 2091887239 2104688227 2059209074 1507630703 2053079891 2019340823 2547342773 2145015113 2055193025 1557896792 178770064 1977846486
We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope. Abstract A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable matching can be found in O ∗ ( m ) time by a polynomial number of processors, where m is the total length of preference lists of individuals. Vande Vate 1989 described the polytope whose extreme points are the stable core matchings in the Marriage Problem. Rothblum 1989 simplified and extended this result. This paper explores a corresponding linear program, its dual and consequences of the fact that the dual solutions have an unusually direct relation to the primal solutions. This close relationship allows us to provide simple proofs both of Vande Vate and Rothblum's results and of other important results about the core of marriage markets. These proofs help explain the structure shared by the marriage problem without sidepayments and the assignment game with sidepayments. The paper further explores "fractional" matchings, which may be interpreted as lotteries over possible matches or as time-sharing arrangements. We show that those fractional matchings in the Stable Marriage Polytope form a lattice with respect to a partial ordering that involves stochastic dominance. Thus, all expected utility functions corresponding to the same ordinal preferences will agree on the relevant comparisons. Finally, we provide linear programming proofs of slightly stronger versions of known incentive compatibility results. We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+e)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching. It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem. We show that the replica symmetric solution of the matching problem (bipartite or not) with independent random distances is stable. We compute the fluctuations and get the O(1 N) corrections to the length of the optimal matching in a generic sample On montre que la solution symetrique dans les repliques du probleme d'appariement (bipartite ou pas) dans lequel les distances sont des variables aleatoires est stable. On calcule les fluctuations et on obtient les conections d'ordre 1 N pour la longueur de l'appariement optimal dans un echantillon generique The original work of Gale and Shapley on an assignment method using the stable marriage criterion has been extended to find all the stable marriage assignments. The algorithm derived for finding all the stable marriage assignments is proved to satisfy all the conditions of the problem. Algorithm 411 applies to this paper. In an instance of the stable marriage problem with ties and incomplete preference lists, stable matchings can have different sizes. It is APX-hard to compute a maximum cardinality stable matching, but there have recently been proposed polynomial-time approximation algorithms, with constant performance guarantees for both the general version of this problem, and for several special cases. Our contribution is to describe a @math -approximation algorithm for the general version of this problem, improving upon the recent @math -approximation algorithm of Kiraly. Interest in such algorithms arises because of the problem's application to centralized matching schemes, the best known of which involve the assignment of graduating medical students to hospitals in various countries. This book probes the stable marriage problem and its variants as a rich source of problems and ideas that illustrate both the design and analysis of efficient algorithms. It covers the most recent structural and algorithmic work on stable matching problems, simplifies and unifies many earlier proofs, strengthens several earlier results, and presents new results and more efficient algorithms.The authors develop the structure of the set of stable matchings in the stable marriage problem in a more general and algebraic context than has been done previously; they discuss the problem's structure in terms of rings of sets, which allows many of the most useful features to be seen as features of a more general set of problems. The relationship between the structure of the stable marriage problem and the more general stable roommates problem is demonstrated, revealing many commonalities.The results the authors obtain provide an algorithmic response to the practical, and political, problems created by the asymmetry inherent in the Gale Shapley solutions, leading to alternative methods and better compromises than are provided by the Gale Shapley method. And, in contrast to Donald Knuth's earlier work which primarily focused on the application of mathematics to the analysis of algorithms, this book illustrates the productive and almost inseparable relationship between mathematical insight and the design of efficient algorithms.Dan Gusfield is Associate Professor of Computer Science at the University of California, Davis. Robert W. Irving is Senior Lecturer in Computing Science at the University of Glasgow. The Stable Marriage Problem is included in the Foundations of Computing Series, edited by Michael Garey and Albert Meyer. In this paper, we propose a new approach, parallel iterative improvement (PII), to solving the stable matching problem. This approach treats the stable matching problem as an optimization problem with all possible matchings forming its solution space. Since a stable matching always exists for any stable matching problem instance, finding a stable matching is equivalent to finding a matching with the minimum number (which is always zero) of unstable pairs. A particular PII algorithm is presented to show the effectiveness of this approach by constructing a new matching from an existing matching and using techniques such as randomization and greedy selection to speedup the convergence process. Simulation results show that the PII algorithm has better average performance compared with the classical stable matching algorithms and converges in n iterations with high probability. The proposed algorithm is also useful for some real-time applications with stringent time constraint. The Stable Marriage Problem and its many variants have been widely studied in the literature (Gusfield and Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, 1989; Roth and Sotomayor, Two-sided matching: a study in game-theoretic modeling and analysis, Econometric Society Monographs, vol. 18, Cambridge University Press, Cambridge, 1990; Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997), partly because of the inherent appeal of the problem, partly because of the elegance of the associated structures and algorithms, and partly because of important practical applications, such as the National Resident Matching Program (Roth, J. Political Economy 92(6) (1984) 991) and similar large-scale matching schemes. Here, we present the first comprehensive study of variants of the problem in which the preference lists of the participants are not necessarily complete and not necessarily totally ordered. We show that, under surprisingly restrictive assumptions, a number of these variants are hard, and hard to approximate. The key observation is that, in contrast to the case where preference lists are complete or strictly ordered (or both), a given problem instance may admit stable matchings of different sizes. In this setting, examples of problems that are hard are: finding a stable matching of maximum or minimum size, determining whether a given pair is stableeven if the indifference takes the form of ties on one side only, the ties are at the tails of lists, there is at most one tie per list, and each tie is of length 2; and finding, or approximating, both an egalitarian' and a minimum regret' stable matching. However, we give a 2-approximation algorithm for the problems of finding a stable matching of maximum or minimum size. We also discuss the significant implications of our results for practical matching schemes. An instance of the classical Stable Roommates problem (sr) need not admit a stable matching. This motivates the problem of finding a matching that is “as stable as possible”, i.e. admits the fewest number of blocking pairs. In this paper we prove that, given an sr instance with n agents, in which all preference lists are complete, the problem of finding a matching with the fewest number of blocking pairs is NP-hard and not approximable within @math , for any e>0, unless P=NP. If the preference lists contain ties, we improve this result to n1−e. Also, we show that, given an integer K and an sr instance I in which all preference lists are complete, the problem of deciding whether I admits a matching with exactly K blocking pairs is NP-complete. By contrast, if K is constant, we give a polynomial-time algorithm that finds a matching with at most (or exactly) K blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blocking pairs over all matchings in terms of some properties of a stable partition, given an sr instance I. We analyze the Gale-Shapley matching problem within the context of Rawlsian justice. Defining a fair matching algorithm by a set of 4 axioms (Gender Indifference, Peer Indifference, Maximin Optimality, and Stability), we show that not all preference profiles admit a fair matching algorithm, the reason being that even this set of minimal axioms is too strong in a sense. Because of conflict between Stability and Maximin Optimality, even the algorithm which generates the mutual agreement match, paradoxically, has no chance to be fair. We give a 3 2 -approximation algorithm for finding stable matchings that runs in O(m) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but runs in O(n3 2m) time, where n denotes the number of people andm is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stable many-to-many matchings. In an instance G = (A union B, E) of the stable marriage problem with strict and possibly incomplete preference lists, a matching M is popular if there is no matching M0 where the vertices that prefer M' to M outnumber those that prefer M to M'. All stable matchings are popular and there is a simple linear time algorithm to compute a maximum-size popular matching. More generally, what we seek is a min-cost popular matching where we assume there is a cost function c : E -> Q. However there is no polynomial time algorithm currently known for solving this problem. Here we consider the following generalization of a popular matching called a popular half-integral matching: this is a fractional matching x = (M_1 + M_2) 2, where M1 and M2 are the 0-1 edge incidence vectors of matchings in G, such that x satisfies popularity constraints. We show that every popular half-integral matching is equivalent to a stable matching in a larger graph G^*. This allows us to solve the min-cost popular half-integral matching problem in polynomial time. We study two-sided matching markets with couples and show that for a natural preference domain for couples, the domain of weakly responsive preferences, stable outcomes can always be reached by means of decentralized decision making. Starting from an arbitrary matching, we construct a path of matchings obtained from satisfying' blocking coalitions that yields a stable matching. Hence, we establish a generalization of Roth and Vande Vate's (1990) result on path convergence to stability for decentralized singles markets. Furthermore, we show that when stable matchings exist, but preferences are not weakly responsive, for some initial matchings there may not exist any path obtained from satisfying' blocking coalitions that yields a stable matching. We investigate the complexity of approximately counting stable matchings in the k-attribute model, where the preference lists are determined by dot products of ''preference vectors'' with ''attribute vectors'', or by Euclidean distances between ''preference points ''and ''attribute points''. Irving and Leather (1986) [14] proved that counting the number of stable matchings in the general case is #P-complete. Counting the number of stable matchings is reducible to counting the number of downsets in a (related) partial order [14] and is interreducible, in an approximation-preserving sense, to a class of problems that includes counting the number of independent sets in a bipartite graph (#BIS) ( (2004) [6]). It is conjectured that no FPRAS exists for this class of problems. We show this approximation-preserving interreducibility remains even in the restricted k-attribute setting when k>=3 (dot products) or k>=2 (Euclidean distances). Finally, we show it is easy to count the number of stable matchings in the 1-attribute dot-product setting. We study strategic issues in the Gale-Shapley stable marriage model. In the first part of the paper, we derive the optimal cheating strategy and show that it is not always possible for a woman to recover her women-optimal stable partner from the men-optimal stable matching mechanism when she can only cheat by permuting her preferences. In fact, we show, using simulation, that the chances that a woman can benefit from cheating are slim. In the second part of the paper, we consider a two-sided matching market found in Singapore. We study the matching mechanism used by the Ministry of Education (MOE) in the placement of primary six students in secondary schools, and discuss why the current method has limited success in accommodating the preferences of the students, and the specific needs of the schools (in terms of the “mix” of admitted students). Using insights from the first part of the paper, we show that stable matching mechanisms are more appropriate in this matching market and explain why the strategic behavior of the students need not be a major concern. (Stable Marriage; Strategic Issues; Gale-Shapley Algorithm; Student Posting Exercise) We present the first complete algorithm for the SMTI problem, the stable marriage problem with ties and incomplete lists. We do this in the form of a constraint programming encoding of the problem. With this we are able to carry out the first empirical study of the complete solution of SMTI instances. In the stable marriage problem (SM) [5] we have n men and n women. Each man ranks the women, giving himself a preference list. Similarly each woman ranks the men, giving herself a preference list. The problem is then to marry men and women such that they are stable i.e. such that there is no incentive for individuals to divorce and elope. This problem is polynomial time solvable. However, when preference lists contain ties and are incomplete (SMTI) the problem of determining if there is a stable matching of size n is then NP-complete, as is the optimisation problem of finding the largest or smallest stable matching [6, 10]. In this paper we present constraint programming solutions for the SMTI decision and optimisation problems, a problem generator for random instances of SMTI, and an empirical study of this problem. The theory of linear inequalities and linear programming was recently applied to study the stable marriage problem which until then has been studied by mostly combinatorial methods. Here we extend the approach to the general stable matching problem in which the structure of matchable pairs need not be bipartite. New issues arise in the analysis and we combine linear algebra and graph theory to explore them.