This paper extends the classic cake-cutting problem to a situation in which the "cake" is divided among families. Each piece of cake is owned and used simultaneously by all members of the family. A typical example of such a cake is land. We examine three ways to assess the fairness of such a division, based on the classic no-envy criterion: (a) Average envy-freeness means that for each family, the average value of its share (averaged over all family members) is weakly larger than the average value of any other share; (b) Unanimous envy-freeness means that in each family, each member values the family's share weakly more than any other share; (c) Democratic envy-freeness means that in each family, at least half the members value the family's share weakly more than any other share. We study each of these definitions from both an existential and a computational perspective.
Besides land division, family preferences are important in matching markets, too. For example, when matching doctors to hospitals, usually a husband and a wife want to be matched to the same hospital. This issue poses a substantial challenge to stable-matching mechanisms @cite_13 @cite_30 @cite_19 .
@cite_30 @cite_19 @cite_13
1557896792 2099790472 196267042 2084501762
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) Couples looking for jobs in the same labor market may cause instabilities. We deter- mine a natural preference domain, the domain of weakly responsive preferences, that guarantees stability. Under a restricted unemployment aversion condition we show that this domain is maximal for the existence of stable matchings. We illustrate how small deviations from (weak) responsiveness, that model the wish of couples to be closer together, cause instability, even when we use a weaker stability notion that excludes myopic blocking. Our remaining results deal with various properties of the set of stable matchings for "responsive couples markets," viz., optimal- ity, filled positions, and manipulation. Journal of Economic Literature Classification Numbers: C78; J41. The classical Hospitals Residents problem (HR) models the assignment of junior doctors to hospitals based on their preferences over one another. In an instance of this problem, a stable matching M is sought which ensures that no blocking pair can exist in which a resident r and hospital h can improve relative to M by becoming assigned to each other. Such a situation is undesirable as it could naturally lead to r and h forming a private arrangement outside of the matching. The original HR model assumes that preference lists are strictly ordered. However in practice, this may be an unreasonable assumption: an agent may find two or more agents equally acceptable, giving rise to ties in its preference list. We thus obtain the Hospitals Residents problem with Ties (HRT). In such an instance, stable matchings may have different sizes and MAX HRT, the problem of finding a maximum cardinality stable matching, is NP-hard. In this paper we describe an Integer Programming (IP) model for MAX HRT. We also provide some details on the implementation of the model. Finally we present results obtained from an empirical evaluation of the IP model based on real-world and randomly generated problem instances. We report on the design of the new clearinghouse adopted by the National Resident Matching Program, which annually fills approximately 20,000 jobs for new physicians in the United States. Because that market exhibits many complementarities between applicants and between positions, the theory of simple matching markets does not apply directly. However, computational experiments reveal that the theory provides a good approximation, and furthermore the set of stable matchings, and the opportunities for strategic manipulation, are surprisingly small. A new kind of core convergence' result is presented to explain this; the fact that each applicant can interview for only a small fraction of available positions is important. We also describe in detail engineering aspects of the design process.