What exactly is a "successor" in the Extended Gale-Shapley algorithm?

Question

Background

In the main Gale-Shapley algorithm, a Stable Matching (if one exists) within the conventional Stable Marriage Problem is achieved as follows:

INITIALIZE M to be an empty matching 
WHILE (some man m is free)
    w <- first woman on m's list to whom m has not yet proposed 
IF (w is unmatched)
    Add m-w to matching M 
ELSE IF (w prefers m to current partner m')
    Replace m' - w with m - w in matching M 
ELSE //w is already matched

In the Extended Gale-Shapley algorithm, a weakly stable matching from the Stable Marriage Problem with Indifference is achieved as follows:

INITIALIZE M to be an empty matching
WHILE (some man m is free)
    w <- first woman on m’s list
    Add m-w to matching M
    IF(some man m' is engaged to w)
        Remove m'- w from M
    FOR EACH successor m’' of m on w’s list
        Remove m'' - w from M
end

The first difference I notice is that adding a pair to Matching M is automatic, and removal happens after that fact, rather then an active check to see if w is matched in the original algorithm. However, I have trouble understanding what a "successor" is in this context. What exactly is a successor in the case of ties, and how does the algorithm know how many w's or m's are part of a tie? This confusion is what lead me to ask:

Question

What exactly is a "successor" in the context of the Extended Gale Shapley algorithm?

Answer 1

As we learn from reading the paper, Wikipedia doesn't really know what's going on here.

The actual way to find weakly stable matchings is this:

1. Break all ties arbitrarily.
2. Use the Gale-Shapley algorithm.

The result is a matching that's stable with respect to the tiebroken preferences; this means that it must be weakly stable even without the tiebreaks. (A counterexample to weak stability is a man $m$ and woman $w$ that strictly prefer each other to their partners, and this strict preference is unaffected by breaking ties.)

---

The extended Gale-Shapley algorithm in the Wikipedia article is quoted directly from Irving's paper. It is still meant for solving the stable matching problem in the case with no ties, so $m'$ is a successor of $m$ on $w$'s list if $w$ prefers $m$ to $m'$, with no discussion of what happens if preferences are tied.

In fact, in all cases, Gale-Shapley and extended Gale-Shapley output exactly the same result; extended Gale-Shapley just does different book-keeping to get there. It deletes edges where Gale-Shapley just keeps track of which women a man has already proposed to, but ordinary Gale-Shapley would never want to use those edges. This may save a few checks down the line, but both algorithms are $O(n^2)$ in any case, so it doesn't save too many.

The extended Gale-Shapley algorithm exists to simplify the exposition in Irving's paper. Irving's other algorithms (the ones quoted in the rest of the Wikipedia article) are refinements of it: they also proceed by deleting edges. Those algorithms are meant to deal with ties, and are careful to only talk about "strict successors". If there are in fact no ties, those algorithms will end up taking the same actions as extended Gale-Shapley (and deleting the same edges).