Dataset Information

"Almost-stable" matchings in the Hospitals / Residents problem with Couples.

ABSTRACT: The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

SUBMITTER: Manlove DF

PROVIDER: S-EPMC7115081 | biostudies-literature | 2017

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

"Almost-stable" matchings in the Hospitals / Residents problem with Couples.

Manlove David F DF McBride Iain I Trimble James J

Constraints : an international journal 20160811 1

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even ...[more]

PMID: 32269496

Similar Datasets

Project description:The influence of the health-related behavior of one spouse on that of the other is an important research question with public policy reprecussions. Yet, we are unaware of any previous study, which considered endogeneity problems between couples. Moreover, only a few studies considered ethnic origin differences among couples. Based on the 2016 wave of the Israeli longitudinal survey, we observe the cross-sectional correlation between the married couples' BMI, age, and accumulated wealth. The BMI (= [Formula: see text]) is a conventional measure of obesity, where BMI≥25 is considered overweight. Using a 3SLS methodology (in an effort to correct the endogeneity problem associated with BMI couples), the analysis tests the mutual obesity hypothesis among married couples. This hypothesis states that the BMI of the male influences that of a female and vice versa. Results indicate that on the one hand, a one-percent BMI increase among Arab Israeli males is associated with a projected 0.969 percent BMI increase among Arab Israeli females (p = 0.017); and in the case that an Arab Israeli male suffers from overweight, the projected probability of his Arab Israeli female counterpart to suffer from overweight as well rises (p = 0.050). On the other hand, one cannot reject the null hypothesis that projected BMI of the Arab Israeli male is unaffected by that of his Arab Israeli female counterpart (p = 0.907 and p = 0.853). As for the Jewish Israeli population, in the case that the 3SLS methodology is employed, so that the endogeneity problem among couples is considered, a one-percent BMI increase among Jewish Israeli females is associated with a projected 0.639 percent BMI increase among Jewish Israeli males (p = 0.091). Unlike Arab Israeli couples, no support is found to indicate the influence in the other direction, namely, the BMI of the male influences that of the female spouse. Research findings may thus be of relevance to public health and policy planners. Two limitations of this research lie in: 1) the self-reported BMI (which might be different from the measured BMI); and 2) missing confounders, such as regional dummies, which are not available in the dataset.

Project description:Objective was to examine the temporal variation of HIV sero-discordancy in select representative countries (Kenya, Lesotho, Mali, Niger, Tanzania, and Zimbabwe) in sub-Saharan Africa at different HIV epidemic scales. A sero-discordant couple is defined as a stable couple (SC) in which one partner is HIV-positive while the other is HIV-negative.A deterministic compartmental mathematical model was constructed to describe HIV transmission dynamics. The model was pair-based, that is explicitly modeling formation of SCs and infection dynamics in both SCs and in single individuals. The model accommodated for different forms of infection statuses in SCs. Using population-based nationally-representative epidemiologic and demographic input data, historical (1980-2014) and future (2015-2030) trends of sero-discordancy and other demographic and epidemiologic indicators were projected throughout HIV epidemic phases.As the epidemics emerged, about 90% of SCs affected by HIV were sero-discordant. This proportion declined to 45%-88% at epidemic peak and stabilized as the epidemics started their natural decline. The largest reductions in sero-discordancy were in high HIV-prevalence countries. As the epidemics further declined with antiretroviral therapy (ART) scale-up, the proportion of sero-discordant couples among HIV-affected couples was projected to increase to 70%-92% by 2030. The proportion of sero-discordant couples among all SCs increased as the epidemics emerged and evolved, then peaked at 2%-20% as the epidemics peaked, and then declined as the epidemics declined to reach 0.3%-16% by 2030.Sero-discordancy patterns varied with the evolution of the epidemics, and were affected by both epidemic phase and scale. The largest variations were found in high HIV-prevalence countries. The fraction of stable couples that are sero-discordant, as opposed to being sero-concordant positive, was projected to increase with ART scale-up and further HIV incidence decline over the coming two decades. These findings inform strategic planning and resource allocation for interventions among sero-discordant couples.

Dataset Information

"Almost-stable" matchings in the Hospitals / Residents problem with Couples.

Publications

"Almost-stable" matchings in the Hospitals / Residents problem with Couples.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets