Cutoff stability under distributional constraints with an application to summer internship matching

DOI10.1007/S10107-022-01917-1MaRDI QIDQ6120933zbMATH OpenOpenAlexFDO

Authors Haris Aziz, Anton Baychkov, Péter Biró

Publication date 21 February 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2102.02931

zbMATH Keywords

cutoff scoresdistributional constraintsmixed integer programmingNP-hardnessstable matching

Mathematics Subject Classification ID

Mixed integer programming (90C11) Matching models (91B68)

Abstract: We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restricted model with disjoint regional quotas. Our first result is that checking its existence is NP-hard. We then show that a cutoff stable matching exists not just for the summer internship problem but also for the general matching model with arbitrary heredity constraints. We present an algorithm to compute a cutoff stable matching and show that it runs in polynomial time in our special case of summer internship model. However, we also show that finding a maximum size cutoff stable matching is NP-hard, but we provide a Mixed Integer Linear Program formulation for this optimisation problem.

Recommendations

• Stability concepts in matching under distributional constraints
• Stable matching with proportionality constraints
• Stable solutions on matching models with quota restriction
• The college admissions problem with lower and common quotas
• Classified stable matching

Cites work

• A tale of two mechanisms: Student placement
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Choice function-based two-sided markets: stability, lattice property, path independence and algorithms
• College Admissions and the Stability of Marriage
• College admissions with stable score-limits
• Controlled school choice with soft bounds and overlapping types
• Decreasing minimization on M-convex sets: background and structures
• Deferred acceptance algorithms: history, theory, practice, and open questions
• Hard variants of stable marriage.
• Impossibility of weakly stable and strategy-proof mechanism
• Improved approximation results for the stable marriage problem
• Improving matching under hard distributional constraints
• Integer programming methods for special college admissions problems
• Mathematical models for stable matching problems with ties and incomplete lists
• Network flows. Theory, algorithms, and applications.
• Stability and strategy-proofness for matching with constraints: A necessary and sufficient condition
• Stability concepts in matching under distributional constraints
• Strategyproof matching with regional minimum and maximum quotas
• The college admissions problem with lower and common quotas
• The stable admissions polytope
• Two algorithms for the student-project allocation problem
• Weighted matching markets with budget constraints

This page was built for publication: Cutoff stability under distributional constraints with an application to summer internship matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120933)