Common stable matching with two changed agents on each side → 2-SAT search Complexity open
Unsolved
Why this question matters
Moderate: a successful structured encoding would settle the first unresolved case after one-sided preference changes and could support robust market design when a few participants revise rankings. It would not classify arbitrary numbers of changed agents.
Gangam and coauthors explicitly say they do not know the complexity of nonempty intersection at (2,2), although they expect a polynomial algorithm. Their (0,n) and (1,n) algorithms and general jointly-stable hardness have different hypotheses.
The reduction to construct
The input gives the same n workers and n firms with two complete strict preference profiles A and B; at most two workers and at most two firms change their lists between profiles. An output is a perfect matching stable in both profiles, or NO-SOLUTION exactly when none exists.
The input is an explicit 2-CNF formula. A valid output is a satisfying truth assignment, or NO-SOLUTION exactly when the formula is unsatisfiable.
Construct deterministic polynomial-time F and G so that F encodes each two-sided-change instance as 2-CNF and G recovers a common stable matching from every satisfying assignment, with NO-SOLUTION preserved. This would yield a polynomial algorithm for the exact (2,2) case without assuming the common matchings form a sublattice.
High: the paper's (1,n) lattice and linear-program algorithms fail at (2,2), where the common stable matchings need not be a sublattice. A route is to encode only rotations affected by the four changed lists and enforce pairwise compatibility, but proving that all residual conflicts reduce to 2-CNF is untested.
What a complete answer must include
Specify the Boolean variables, clauses and recovery, prove soundness and completeness for every valid target output, and bound both maps in bits and time. Later tests should compare recovered matchings with independently checked blocking pairs and infeasible small markets.
References
Literature checked 2026-09-26. Checked the 2023 arXiv full text, Introduction, Theorems 11-14 and the (2,2) counterexample; searched 2026-09-26 for 'common stable matching (2,2)', 'stable under both two workers two firms', and 'jointly stable nearby preferences 2026'. No matching resolution surfaced in indexed results. The 2-SAT route is a proposed stronger constructive target, not a theorem from the paper. Gates 1-4 pass within this coverage; Gate 5 holds until the affected-rotation encoding is established; Gate 6 was not assessed.