Approximately Stable Matchings with General Constraints
Pith reviewed 2026-05-25 00:09 UTC · model grok-4.3
The pith
A framework adapts online packing algorithms to produce approximately stable matchings under general constraints.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors establish a framework to analyze this problem on packing problems and the framework enables us to access the wealth of online packing algorithms so that we construct approximately stable algorithms as a variant of generalized deferred acceptance algorithm. We further provide some inapproximability results.
What carries the argument
Generalized deferred acceptance algorithm adapted from online packing algorithms for packing-type constraints.
Load-bearing premise
The constraints belong to packing-type classes whose online algorithms can be directly adapted to produce bounded instability in the matching setting.
What would settle it
A concrete matching instance with knapsack or matroid intersection constraints where the adapted algorithm yields instability exceeding the bound given by the online packing guarantee.
read the original abstract
This paper focuses on two-sided matching where one side (a hospital or firm) is matched to the other side (a doctor or worker) so as to maximize a cardinal objective under general feasibility constraints. In a standard model, even though multiple doctors can be matched to a single hospital, a hospital has a responsive preference and a maximum quota. However, in practical applications, a hospital has some complicated cardinal preference and constraints. With such preferences (e.g., submodular) and constraints (e.g., knapsack or matroid intersection), stable matchings may fail to exist. This paper first determines the complexity of checking and computing stable matchings based on preference class and constraint class. Second, we establish a framework to analyze this problem on packing problems and the framework enables us to access the wealth of online packing algorithms so that we construct approximately stable algorithms as a variant of generalized deferred acceptance algorithm. We further provide some inapproximability results.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies two-sided matching in which one side (e.g., hospitals) is subject to general feasibility constraints (knapsack, matroid intersection) and cardinal preferences (submodular), under which stable matchings may fail to exist. It classifies the computational complexity of deciding and computing stable matchings according to preference and constraint classes, develops a reduction of the approximately-stable matching problem to online packing problems, and uses this reduction inside a generalized deferred-acceptance procedure to obtain approximately stable algorithms whose instability is controlled by the competitive ratio of the invoked packing algorithm; inapproximability results are also stated.
Significance. If the claimed reduction preserves approximation guarantees, the work supplies a systematic way to import the extensive literature on online packing algorithms into the design of approximately stable matchings with packing-type constraints. The complexity classification and inapproximability statements would further delineate the boundary between tractable and intractable cases.
minor comments (1)
- [Abstract] The abstract states that the framework yields approximately stable algorithms but does not name the concrete approximation ratios or instability bounds obtained; these should be stated explicitly in the introduction or theorem statements.
Simulated Author's Rebuttal
We thank the referee for their summary of the manuscript and for noting its potential significance in connecting stable matching to online packing algorithms, conditional on the reduction preserving guarantees. We address this point below. No explicit major comments appear under the 'MAJOR COMMENTS' heading.
read point-by-point responses
-
Referee: If the claimed reduction preserves approximation guarantees, the work supplies a systematic way to import the extensive literature on online packing algorithms into the design of approximately stable matchings with packing-type constraints. The complexity classification and inapproximability statements would further delineate the boundary between tractable and intractable cases.
Authors: We confirm that the reduction preserves approximation guarantees: Theorem 4.2 establishes that if the invoked online packing algorithm has competitive ratio α, then the output matching is α-approximately stable (with respect to the given submodular objective and packing constraints). The proof proceeds by showing that any blocking pair or coalition in the final matching would imply a violation of the packing algorithm's competitive ratio, which is a contradiction. This is formalized via a direct reduction in Section 4 that maps the approximately-stable matching instance to an online packing instance while preserving the objective value up to the competitive ratio. The complexity classification (Theorems 3.1–3.4) and inapproximability results (Theorems 5.1–5.3) are obtained by reductions from known hard problems in submodular optimization and matroid intersection, and they apply to both exact stability and constant-factor approximations. revision: no
Circularity Check
Minor self-citation not load-bearing; derivation imports external results
full rationale
The paper reduces approximately stable matchings under packing constraints (knapsack, matroid intersection) to online packing problems, then adapts existing online algorithms inside a generalized deferred-acceptance procedure. No step equates a prediction to its own fitted input, renames a known result as new unification, or relies on a self-citation chain whose cited result is itself unverified or defined in terms of the target claim. External online packing competitive ratios supply the stability bounds, satisfying the independence criteria. A possible minor self-citation on the generalized DA variant exists but is not load-bearing for the central claims.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Two-sided matching model with one-sided general feasibility constraints and cardinal preferences
- domain assumption Submodular preferences and packing constraints (knapsack, matroid intersection) admit online algorithms with known competitive ratios
Reference graph
Works this paper leans on
-
[1]
A. Abdulkadiro˘ glu and T. S¨ onmez. School choice: A mech anism design approach. American Economic Review, 93(3):729–747, 2003
work page 2003
-
[2]
A. Abizada. Stability and incentives for college admiss ions with budget constraints. Theoretical Economics, 11(2):735–756, 2016. 14
work page 2016
-
[3]
E. M. Arkin, S. W. Bae, A. Efrat, K. Okamoto, J. S. Mitchell , and V. Polishchuk. Geometric stable roommates. Information Processing Letters , 109(4):219–224, 2009
work page 2009
-
[4]
B. V. Ashwinkumar. Buyback problem - approximate matroi d intersection with cancellation costs. In Proceedings of ICALP, pages 379–390, 2011
work page 2011
- [5]
-
[6]
A. Chakrabarti and S. Kale. Submodular maximization mee ts streaming: Matchings, matroids, and more. Mathematical Programming, 154(1–2):225–247, 2015
work page 2015
-
[7]
T.-H. H. Chan, S. H.-C. Jiang, Z. G. Tang, and X. Wu. Online submodular maximization problem with vector packing constraint. In Proceedings of ESA, volume 87, pages 24:1–24:14, 2017
work page 2017
-
[8]
B. C. Dean, M. X. Goemans, and N. Immorlica. The unsplitta ble stable marriage problem. In Proceedings of IFIP TCS , pages 65–75, 2006
work page 2006
-
[9]
D. Delacr´ etaz, S. D. Kominers, and A. Teytelboym. Refug ee resettlement. Working paper, 2016
work page 2016
-
[10]
J. Edmonds. Submodular functions, matroids, and certa in polyhedra. In Combinatorial Struc- tures and Their Applications , pages 69–87. Gordon and Breach, New York, 1970
work page 1970
-
[11]
A. M. Frieze. Complexity of a 3-dimensional assignment problem. European Journal of Oper- ational Research, 13(2):161–164, 1983
work page 1983
- [12]
-
[13]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York, 1979
work page 1979
-
[14]
I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim. Effective a ffirmative action in school choice. Theoretical Economics, 8(2):325–363, 2013
work page 2013
- [15]
-
[16]
J. W. Hatfield and P. R. Milgrom. Matching with contracts . American Economic Review , 95(4):913–935, 2005
work page 2005
-
[17]
K. Iwama and S. Taketomi. Removable online knapsack pro blems. In Proceedings of ICALP, pages 293–305, 2002
work page 2002
-
[18]
T. A. Jenkyns. The efficacy of the “greedy” algorithm. In Proceedings of SEICCGTC , pages 341–350, 1976
work page 1976
-
[19]
Y. Kamada and F. Kojima. Efficient matching under distrib utional constraints: Theory and applications. American Economic Review , 105(1):67–99, 2015. 15
work page 2015
-
[20]
Y. Kawase and A. Iwasaki. Near-feasible stable matchin gs with budget constraints. In Pro- ceedings of IJCAI , pages 242–248, 2017
work page 2017
-
[21]
Y. Kawase and A. Iwasaki. Approximately stable matchin gs with budget constraints. In Proceedings of AAAI, pages 242–248, 2018
work page 2018
- [22]
-
[23]
B. Korte and D. Hausmann. An analysis of the greedy heuri stic for independence systems. Algorithmic aspects of combinatorics , 2:65–74, 1978
work page 1978
- [24]
-
[25]
D. F. Manlove. Algorithmics of Matching Under Preferences . World Scientific Publishing Company, 2013
work page 2013
-
[26]
A. McLoughlin. The complexity of computing the coverin g radius of a code. IEEE Transactions on Information Theory , 30(6):800–804, 1984
work page 1984
- [27]
-
[28]
J. G. Oxley. Matroid Theory. Oxford University Press, 1992
work page 1992
-
[29]
A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching: A Study in Game-theoretic Mod- eling and Analysis (Econometric Society Monographs) . Cambridge University Press, 1990. 16 A Proof of Nonexistence of Stable Matchings In this section, we formally prove that there exist no stable matchings in the markets described in Examples 1 and 2. Proposition 1. The...
work page 1990
-
[30]
28 < (1 + √ 17)/ 4). Suppose that µ is a 1 . 28-stable matching. Case 1: (d4, h 1) ∈ µ (h1). In this case, µ (h2) = {d3} since otherwise {d3} is a 1 . 28-blocking coalition for h2. Thus, µ (h1) is {d4},{d1, d 4}, or {d2, d 4}. Hence, uh1(µ (h1))≤ 7 + √ 17 and {d1, d 2} is a 1 . 28-blocking coalition for h1 by uh1({d1, d 2}) = 6 + 2 √ 17 = (7 + √ 17)(1 + √...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.