we-solve (beta)

Econ-139 · economics · computer science · Computational economics

Complexity of reachability in the divorce digraph

LLM status Open unverified

Statement

MM-13 |  Matching markets and allocation

Published question; corrected scope

Definitions and assumptions

Let $I$ be a complete strict stable-marriage instance with $n$ agents on each side, and let $M$ be a perfect matching. For a blocking pair $(u,w)$, a divorce operation produces \[ T_{u,w}(M)= \left(M\setminus\{(u,M(u)),(M(w),w)\}\right) \cup\{(u,w),(M(w),M(u))\}. \] Thus the blocking pair forms a couple and their displaced partners must also form a couple. Define $D_I$ to have all $n!$ perfect matchings as vertices and arcs $M\to T_{u,w}(M)$ for every blocking pair of $M$. Its sinks are exactly the stable matchings.

Formal question

Determine the computational complexity of deciding, given $(I,M_0)$, whether \[ \exists M\in\mathcal S(I)\quad\exists\text{ directed path in }D_I \text{ from }M_0\text{ to }M. \] Classify this problem for complete strict preference lists, and determine whether affirmative instances admit polynomially bounded divorce paths or efficiently checkable certificates.

Scope and status

The question concerns computational classification, not whether every starting matching reaches a stable matching. Universal reachability was already disproved by size-four examples reported in the source. Dropping the requirement that displaced partners remarry yields a different dynamic with different reachability properties. The survey leaves complete strict instances open while reporting hardness for a ties/incompleteness extension. Chen's later version establishes NP-hardness even for incomplete strict lists; that does not by itself classify the complete-list problem. Exponential state-space size gives a straightforward polynomial-space decision procedure but does not establish NP membership or polynomial solvability.

References for the source of the problem

Katarína Cechlárová, Ágnes Cseh, and David F. Manlove (2019), Selected open problems in Matching Under Preferences, Section 3.2.2, especially the decision question after the counterexamples: https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. Jiehua Chen (2019 preprint), Reaching Stable Marriage via Divorces is Hard, abstract and incomplete-preferences hardness theorem: https://arxiv.org/abs/1906.12274. This preprint was initially referenced under the title Stable matchings in divorce graphs.

Common conventions: Source mathematical conventions

Well-defined objects. All probability spaces and measurable variables are specified or inherited from a local statistical model. Expectations used as finite targets require the stated integrability. A decision rule or estimator is measurable with respect to its available information; randomized rules may use an auxiliary independent random variable. Norms without a subscript are Euclidean in finite-dimensional spaces. An optimizer is requested only when attainment is assured; otherwise the question concerns the optimal value and $\varepsilon$-optimal admissible rules for every $\varepsilon>0$.

Identification. A structural model $m\in\mathcal M$ implies an observable law $P_m^{\rm obs}$ and target $\theta(m)$. The target is point identified on $\mathcal M$ if \[ P_{m_1}^{\rm obs}=P_{m_2}^{\rm obs} \quad\Longrightarrow\quad\theta(m_1)=\theta(m_2) \qquad(m_1,m_2\in\mathcal M). \] When this fails, the sharp identified set is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M, P_m^{\rm obs}=P\}. \] Specifying an intervention or estimand does not establish identification. Positivity, exclusion, causal sufficiency, measurement restrictions, and transport assumptions are substantive local inputs, never automatic consequences of notation.

Minimax risk and nontrivial inference. For a statistical experiment with data law $P^{(n)}$, target $\theta(P)$, and nonnegative loss $\ell$, define \[ \mathcal R_n(\mathcal P,\ell) =\inf_{\widehat\theta_n}\sup_{P\in\mathcal P} \E_{P^{(n)}}\ell(\widehat\theta_n,\theta(P)). \] The infimum is over measurable estimators. A sharp rate is a sequence $r_n$ for which $0<c\leq C<\infty$, independent of $n$, satisfies $c r_n\leq\mathcal R_n\leq C r_n$ for all sufficiently large $n$. Squared-error parametric risk is of order $n^{-1}$; the corresponding root-mean-squared error is of order $n^{-1/2}$. These different conventions are distinguished locally. A uniform asymptotic confidence region $C_n$ must satisfy \[ \liminf_{n\to\infty}\inf_{P\in\mathcal P} \Pr_{P^{(n)}}\{\theta(P)\in C_n\}\geq 1-\alpha, \qquad 0<\alpha<1, \] together with an informative diameter or expected-width requirement. Coverage alone permits the vacuous whole parameter space. Testing questions similarly impose both size control and power against a declared separated alternative class.

Binary causal baseline. When an entry explicitly invokes this baseline, one observes independent copies of $O=(X,W,Y)$, with $W\in\{0,1\}$ and potential outcomes $Y(0),Y(1)$. Assume consistency $Y=Y(W)$, no interference, conditional exchangeability $(Y(0),Y(1))\perp W\mid X$, and overlap $\epsilon\leq e(X)\leq1-\epsilon$ almost surely for a fixed $0<\epsilon<1/2$, where \[ e(x)=\Pr(W=1\mid X=x),\qquad m_w(x)=\E[Y\mid W=w,X=x],\qquad \tau(x)=m_1(x)-m_0(x). \] These assumptions identify conditional mean effects almost everywhere under the covariate law. Pointwise or uniform effects require appropriate regularity and a specified support. Continuous treatment, longitudinal data, adaptive experiments, and network interference require their own assumptions in place of this baseline. Bounded outcomes, densities, and smoothness are additional assumptions only where stated.

Function classes. On $[0,1]^d$, $\mathcal H_d^s(L)$ is the isotropic Hölder ball of radius $L>0$: put $k=\lceil s\rceil-1$ and $\gamma=s-k\in(0,1]$, bound derivatives through order $k$, and require the order-$k$ derivatives to be $\gamma$-Hölder with constant at most $L$. Thus integer orders use a Lipschitz final derivative convention. The class $\operatorname{BV}_d(L)$ consists of functions $f\in L^1((0,1)^d)$ whose distributional derivative is a finite vector measure and for which $\|f\|_{L^1}+|Df|((0,1)^d)\leq L$. An $L^\infty$ bound or a particular pointwise version is imposed separately when needed. Sparse and neural-network classes require a declared dictionary or architecture and coefficient bounds.

An anisotropic Hölder class with declared block smoothness indices means coordinatewise Hölder regularity in each block, uniformly in the other blocks, with all corresponding derivative and Hölder bounds at most the stated radius. Derivative orders and the integer-order convention in each block are those just given. Mixed-derivative bounds are additional restrictions only when explicitly stated.

Decision and computational questions. Policy regret compares admissible feasible policies under the same law and constraints. In computational entries, finite data and thresholds have rational encodings; running time is measured in their total bit length. Real-valued equilibrium search uses the explicitly declared algebraic or FIXP encoding. An approximation ratio for maximization is written $\operatorname{OPT}/\operatorname{ALG}$ and for minimization as $\operatorname{ALG}/\operatorname{OPT}$, with zero optima and infeasible instances handled locally. Historical approximation bounds are not automatically current bounds.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-139-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-139

Problem ID: C78-136 Model: GPT 6 Astra Ultra Version: 1

Complexity of reachability in the divorce digraph

Status. Unresolved for general complete strict preference lists. We prove short successful divorce paths on a structural domain and an exact parameterized algorithm for mutually preferred independent blocks.

Short problem and exact dynamics

There are $n$ men and $n$ women with complete strict preferences. A perfect matching $M$ admits a blocking pair $(u,w)$ when both prefer each other to their current partners. A divorce operation replaces $(u,M(u))$ and $(M^{-1}(w),w)$ by $(u,w)$ and $(M^{-1}(w),M(u))$. Displaced partners must remarry; all states therefore remain perfect matchings. The question is whether a given initial matching reaches any stable matching under such operations, and how difficult it is to decide this for complete lists.

A mutual-top elimination order is a list of pairs $(u_1,w_1),\ldots,(u_n,w_n)$ using every agent once such that, after the preceding pairs are deleted from the preference lists, $u_j$ and $w_j$ rank each other first among remaining agents. This is an explicit recognizable restriction on preferences, not an assumption about the starting matching.

Theorem (Universal short reachability under mutual-top elimination): If an instance admits a mutual-top elimination order, it has a unique stable matching, namely the listed pairs. From every initial perfect matching there is a divorce path to it of length at most $n-1$. Given an elimination order, the path can be found with polynomially many preference comparisons.
Proof: A mutual first-choice pair must belong to every stable matching: otherwise it blocks. Delete that forced pair and repeat along the order. This proves uniqueness and identifies the only possible stable matching; the listed matching is stable because, for any unmatched pair, its earlier eliminated member ranks its assigned partner ahead of the later member.

Now process the order from the initial matching, maintaining that all earlier listed pairs are matched together and never changed again. If $(u_j,w_j)$ is already present, continue. Otherwise both its agents and their current partners are among the remaining agents. They prefer each other to those partners by the mutual-top condition, so their pair is blocking. Perform its divorce operation. The displaced partners remain in the remaining population, and all earlier pairs remain fixed. This makes the next required pair correct. At most one divorce is used per stage, and the last pair is automatic once the preceding $n-1$ are fixed. ∎

Proposition (Recognition and a common-priority special case): Repeatedly deleting any currently mutual-top pair recognizes the existence of a mutual-top elimination order in polynomial time. In particular, if all women share one strict ranking of men, every initial matching reaches the unique stable matching in at most $n-1$ divorces.
Proof: Suppose an elimination order exists and $(u,w)$ is any currently mutual-top pair. It must appear as a pair in that order: its earlier appearing member cannot be paired with someone else while its first-choice partner remains. Move this pair to the start of the order. Every other pair that was mutual-top when deleted remains mutual-top after additional agents have been removed. Thus deleting an arbitrary available pair preserves existence of an order for the residual instance. If the greedy algorithm gets stuck before deleting everyone, no such order could have existed. Scanning preference lists after each deletion is polynomial. For the common-ranking case, take the highest-ranked remaining man and his favorite remaining woman. He is her first choice among remaining men, so they are mutual-top. Repeat. The preceding theorem then applies. ∎

An exact reachability reduction for separated markets

A balanced partition consists of blocks $(P_j,R_j)$ with $|P_j|=|R_j|=n_j$. Assume every member of $P_j$ ranks every member of $R_j$ above every outsider and vice versa. The initial matching is internal if it matches each block to itself. Let $I_j$ be the restriction to block $j$, and $M_{0,j}$ the initial restricted matching.
Lemma (Product dynamics from internal states): Starting from an internal matching, all blocking pairs and all subsequent divorce operations are internal to one block. A resulting matching is stable globally if and only if all its block restrictions are stable.
Proof: At an internal matching, each agent has an inside partner and ranks every outsider below that partner. Thus a cross-block pair cannot block. An inside blocking pair displaces only inside partners, so the divorce keeps every block internal. Induction gives invariance of the internal state set. Within it, cross-block blocking is impossible and inside blocking is exactly blocking in the restricted instance. This proves the equivalence of stability. ∎
Theorem (Bounded-block exact algorithm and certificate bound): Given a balanced mutually preferred partition and an internal initial matching, a stable matching is reachable globally if and only if it is reachable from $M_{0,j}$ in every block $I_j$. If every $n_j\leq k$, reachability is decidable in time \[ O\left(\sum_j n_j!\,\operatorname{poly}(n_j)+\operatorname{poly}(n)\right) \subseteq O\left(n k!\,\operatorname{poly}(k)+\operatorname{poly}(n)\right). \] Every affirmative instance has a path of length at most $\sum_j(n_j!-1)$, with a directly checkable sequence of blocking pairs.
Proof: Every global path projects onto a legal path in each block after deleting steps in other blocks, by the lemma. Reaching a global stable matching therefore requires success in every block. Conversely, concatenate one successful local path for each block, leaving the others fixed. Each local blocking pair is still blocking globally, so this is a valid global path ending at a stable matching. For each block enumerate its $n_j!$ permutations. At a state inspect all at most $n_j^2$ man--woman pairs using precomputed ranks; each blocking pair gives one successor permutation. Breadth-first search from $M_{0,j}$ finds a stable state if and only if one is reachable. Generating and indexing a successor takes polynomial time in $n_j$, giving the running time. A shortest successful local path never repeats a vertex and therefore has at most $n_j!-1$ arcs. Concatenation yields the length bound. Verification checks preference inequalities and the prescribed partner swap at every step. ∎
The parameter guarantee is for the maximum block size of a supplied, verifiable partition; its factorial dependence is explicit. It remains useful when the total market is large but has small independent components. Requiring an internal initial matching is essential to the proof: when agents start across blocks, outsiders can be preferred to their current partners and cross-block operations may occur.

Why this does not classify the general problem

A mutual-top pair can always be fixed constructively, but in a general instance the elimination can stop on a residual market without such a pair. The short-path theorem gives no conclusion about that residual market. Likewise, a complete-list instance need not have small independent blocks. The general digraph still has $n!$ vertices. A simple-path bound of $n!-1$ permits a nondeterministic polynomial-space search by storing the current permutation and a binary step counter. Guess each blocking-pair move and accept if a stable state is reached within the bound. Deterministic polynomial space can also be seen directly. To decide whether one permutation reaches another in at most $L$ moves, enumerate all midpoint permutations and recursively test the two halves with bounds $\lfloor L/2\rfloor$ and $\lceil L/2\rceil$. At $L\le1$, test equality or a single legal move. Equality permits padding a shorter path. The recursion has depth $O(\log(n!))=O(n\log n)$; each frame stores a constant number of permutations, a midpoint enumeration counter, and a length bound, using $O(n\log n)$ bits. Enumerate stable target permutations in an outer loop. This is polynomial space, although its time need not be polynomial. Neither search supplies a polynomial-length certificate or NP membership. Our stronger path bounds rely on the stated structural restrictions.

No reduction from incomplete lists is asserted: completing lists can introduce new blocking pairs and paths. Proving that a completion gadget preserves both affirmative and negative reachability is an additional task, not a consequence of hardness for the incomplete-list model.

References and source scope

Katarína Cechlárová, Ágnes Cseh and David F. Manlove (2019), Selected open problems in Matching Under Preferences, Section 3.2.2. https://hpi.de/friedrich/docs/publications/2019/BEATCS.pdf. The primary survey was inspected for the complete-list reachability question and the restriction that displaced partners remarry.

Jiehua Chen (2019 preprint), Reaching Stable Marriage via Divorces is Hard, arXiv:1906.12274. https://arxiv.org/abs/1906.12274. The primary record's incomplete-preference hardness statement was checked; it is not cited as a classification of complete strict lists. The structural path and product arguments above are given in full without a priority claim.

Completion Estimate

20%

Go to contribution →