Because preferences naturally arise and play an important role in many real-life decisions, they are at the backbone of various fields. In particular preferences are increasingly used in almost all matching procedures-based applications. In this work we highlight the benefit of using AI insights on preferences in a large scale application, namely the French Admission Post-Baccalaureat Platform (APB). Each year APB allocates hundreds of thousands first year applicants to universities. This is done automatically by matching applicants preferences to university seats. In practice, APB can be unable to distinguish between applicants which leads to the introduction of random selection. This has created frustration in the French public since randomness, even used as a last mean does not fare well with the republican egalitarian principle. In this work, we provide a solution to this problem. We take advantage of recent AI Preferences Theory results to show how to enhance APB in order to improve expressiveness of applicants preferences and reduce their exposure to random decisions.
In Artificial Intelligence, several researchers considered the stable marriage problem. In @cite_32 , the authors introduce a local search approach which exploits properties of the problems to reduce the size of a state neighborhood. In @cite_17 , male optimality and uniqueness of stable marriages for partially ordered preferences are studied.
@cite_32 @cite_17
178770064 1481515824 1480100487 2047128428 2400632488 2739659036 2052785830 2037963188 2071503214 2000321198 2042477843 2100727443 1563534733 2736636075 2091887239 2033301836 2133312780 2059209074 2017008045 2162429744
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. In this paper, we study the concepts of male optimality and uniqueness of stable marriages for partially ordered preferences. We give an algorithm to find a stable marriage that is male optimal, and a sufficient condition on the preferences, which guarantees the uniqueness of stable marriages. The original stable marriage problem requires all men and women to submit a complete and strictly ordered preference list. This is obviously often unrealistic in practice, and several relaxations have been proposed, including the following two common ones: one is to allow an incomplete list, i.e., a man is permitted to accept only a subset of the women and vice versa. The other is to allow a preference list including ties. Fortunately, it is known that both relaxed problems can still be solved in polynomial time. In this paper, we show that the situation changes substantially if we allow both relaxations (incomplete lists and ties) at the same time: the problem not only becomes NP-hard, but also the optimal cost version has no approximation algorithm achieving the approximation ratio of N1-Ɛ, where N is the instance size, unless P=NP. The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as O(n log(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem. The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or more generally to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here we consider stable marriage problems with weighted preferences: each man (resp., woman) provides a score for each woman (resp., man). Such problems are more expressive than the classical stable marriage problems. Moreover, in some real-life situations it is more natural to express scores (to model, for example, profits or costs) rather than a qualitative preference ordering. In this context, we define new notions of stability and optimality, and we provide algorithms to find marriages which are stable and or optimal according to these notions. While expressivity greatly increases by adopting weighted preferences, we show that in most cases the desired solutions can be found by adapting existing algorithms for the classical stable marriage problem. The Balanced Stable Marriage problem is a central optimization version of the classic Stable Marriage problem. Here, the output cannot be an arbitrary stable matching, but one that balances between the dissatisfaction of the two parties, men and women. We study Balanced Stable Marriage from the viewpoint of Parameterized Complexity. Our "above guarantee parameterizations" are arguably the most natural parameterizations of the problem at hand. Indeed, our parameterizations precisely fit the scenario where there exists a stable marriage that both parties would accept, that is, where the satisfaction of each party is "close" to the best it can hope for. Furthermore, our parameterizations accurately draw the line between tractability and intractability with respect to the target value. In this paper a parallel algorithm to solve the stable marriage problem is given. The worst case performance of this algorithm is stated. A theoretical analysis shows that the probability of the occurrence of this worst case is extremely small. For instance, if there are sixteen men and sixteen women involved, then the probability that the worst case occurs is only 10−45. Possible future research is also discussed in this paper. We study the Hospitals Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a parameter. We also apply a local search approach, and examine the possibilities for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplified version of the Hospitals Residents with Couples problem modeling the case when no preferences are given. The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2 (1 p L−2) for instances in which only men have ties of length at most L. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13 7( 1.1052). We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching. Evidence is presented showing that the McVitie and Wilson algorithm to solve the stable marriage problem has a sequential component that is quite large on the average. Hence parallel implementations of the algorithm are likely to achieve only mediocre average case speedup. A corollary result is that an approximate solution with a few unstable pairings can be found much faster than an exact solution. Given an instance I of the classical Stable Marriage problem with Incomplete preference lists (smi), a maximum cardinality matching can be larger than a stable matching. In many large-scale applications of smi, we seek to match as many agents as possible. This motivates the problem of finding a maximum cardinality matching in I that admits the smallest number of blocking pairs (so is ''as stable as possible''). We show that this problem is NP-hard and not approximable within n^1^-^@e, for any @e>0, unless P=NP, where n is the number of men in I. Further, even if all preference lists are of length at most 3, we show that the problem remains NP-hard and not approximable within @d, for some @d>1. By contrast, we give a polynomial-time algorithm for the case where the preference lists of one sex are of length at most 2. We also extend these results to the cases where (i) preference lists may include ties, and (ii) we seek to minimize the number of agents involved in a blocking pair. 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. Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESM), Balanced Stable Marriage (BSM), max-Stable Marriage with Ties (max-SMT) and min-Stable Marriage with Ties (min-SMT) problems. In this paper, we analyze these problems from the viewpoint of Parameterized Complexity. We conduct the first study of these problems with respect to the parameter treewidth. First, we study the treewidth @math of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time @math , we prove that all of these algorithms are likely to be essentially optimal. Next, we study the treewidth @math of the rotation digraph. In this context, the max-SMT and min-SMT are not defined. For both SESM and BSM, we design (non-trivial) algorithms that run in time @math . Then, for both SESM and BSM, we also prove that unless SETH is false, algorithms that run in time @math do not exist for any fixed @math . We thus present a comprehensive, complete picture of the behavior of central optimization versions of Stable Marriage with respect to treewidth. 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. The stable marriage problem, i.e., the problem of assigning the members of two disjoint sets to one another is extended to the case in which individual preferences are represented by weak orderings instead of linear orderings. This leads to a more natural solution for such problems as the processing of college admissions and the optimal distribution of personnel. The paper begins with a formal definition of an assignments function and introduces conditions on it, among them stability. It is shown how the Gale and Shapley algorithm for finding stable assignments can be extended to the more general case considered here. It is shown that if there is an assignment which is preferred by a majority to all other assignments, then this assignment is necessarily stable. Moreover, in a situation where all preference orders are linear orders, all stable assignments are majority assignments. We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants ?,?? such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of ?,?? (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes. 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. 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. The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications ranging from matching resident doctors to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale-Shapley algorithm, which runs in polynomial time. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale-Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale-Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.