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
2047128428 1481515824
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 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. We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope. 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. 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. We study the behavior of random walks along the edges of the stable marriage lattice for various restricted families of allowable preference sets. In the "k-attribute model," each man is valued in each of k attributes, and each woman's ranking of the men is determined by a linear function, representing her relative ranking of those attributes; men's rankings of the women are determined similarly. We show that sampling with a random walk on the marriage lattice can take exponential time, even when k = 2. Moreover, we show that the marriage lattices arising in the k-attribute model are more restrictive than in the general setting; previously such a restriction had only been shown for the sets of preference lists. The second model we consider is the "k-range model," where each person lies in a position in [i, i + k - 1], for some i, on every preference list of the opposite sex. When k = 1 there is a unique stable marriage. When k = 2 there already can be an exponential number of stable marriages, but we show that a random walk on the stable marriage lattice always converges quickly to equilibrium. However, when k ≥ 5, there are preference sets such that the random walk on the lattice will require exponential time to converge. Lastly, we show that in the extreme case where each gender's rankings of the other are restricted to one of just a constant k possible preference lists, there are still instances for which the Markov chain mixes exponentially slowly, even when k = 4. This oversimplification of the general model helps elucidate why Markov chains based on spouse-swapping are not good approaches to sampling, even in specialized scenarios. 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. The stable marriage problem is that of matching n men and n women, each of whom has ranked the members of the opposite sex in order of preference, so that no unmatched couple both prefer each other to their partners under the matching. At least one stable matching exists for every stable marriage instance, and efficient algorithms for finding such a matching are well known. The stable roommates problem involves a single set of even cardinality n, each member of which ranks all the others in order of preference. A stable matching is now a partition of this single set into n2 pairs so that no two unmatched members both prefer each other to their partners under the matching. In this case, there are problem instances for which no stable matching exists. However, the present paper describes an O(n2) algorithm that will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching. 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 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. 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. 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. 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 consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. 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) 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 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. 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 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.