Talk:Gale–Shapley algorithm

GA Review

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

This review is transcluded from Talk:Gale–Shapley algorithm/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Femke (talk · contribs) 20:27, 13 January 2024 (UTC)

I remember reviewing an article from you a couple years back where I gave a single suggestion for improvement. I think this article again shows how science communication is done. I've read the article twice, and have only four comments:

• Optional: the gif is not as clear as could be. I think it's better to have the preferences on top, have the solution highlighted in the same way for proposers/acceptors, and to use a larger font size for the text top right.
• "If an applicant X and an employer Y could form an unstable pair, Y would have made an offer to their preferred match X, before making another offer to their actual match. But X would have accepted this offer and kept it in preference to the offer they ended up with. Therefore, no such pair is possible.[9]" - this is difficult to understand. It's a confusing that we start by contemplating an unstable pair (X is not the preferred match), and then call some other preferred match X too. Could you reword?
• optional: The method is complicated by side constraints that make the problem it solves not exactly the stable matching problem.-- the word side reads off to me. Is extra constraints better wording?
• "A stable matching instance can have multiple stable matchings." I read this initially as " a stable matching solution can have multiple solutions". Can we have a different word for instance? Such as problem? Or problem instance?

Will do a spot check later. —Femke 🐦 (talk) 20:27, 13 January 2024 (UTC)

I spot checked 6 statements using 3 sources. No problems found. —Femke 🐦 (talk) 20:42, 13 January 2024 (UTC)

Re the animation: Unfortunately I'm not really set up to create or modify animated gifs.

Re "side constraints": changed "side" to "additional".

Re "It's a confusing that we start by contemplating an unstable pair (X is not the preferred match), and then call some other preferred match X too." (in the matches are stable part of the correctness argument): no, it really is the same X both times. But I rewrote this to avoid the appearance of proof by contradiction: now we show that each pair is not unstable, rather than assuming an unstable pair and showing that its existence contradicts the outcome of the algorithm. I hope this is less confusing.

Re "A stable matching instance": "instance" is the correct technical word here for a specific input to a general computational problem, but I suppose that being technical and using jargon is not really the point. Reworded to "There may be many stable matchings for the same system of preferences."

—David Eppstein (talk) 02:32, 14 January 2024 (UTC)

Brilliant, thanks. The new wording for the unstable matching is clearer, but the first sentence is still a bit confusing. The following sounds better to my ears: There cannot be an applicant X and employer Y who prefer each other over their final match. The "unmatched pair" makes it sound like we're in the middle of the algorithm where they haven't been matched yet. —Femke 🐦 (talk) 10:02, 14 January 2024 (UTC)

Reworded. —David Eppstein (talk) 18:23, 14 January 2024 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by DirtyHarry991 talk 00:42, 25 January 2024 (UTC)

(

• Comment or view
• Article history

)

• ... that descriptions of the Gale–Shapley algorithm in terms of marriage proposals have been criticized as both sexist and unrealistic? Source: Wagner, [1]
  • ALT1: ... that the Gale–Shapley algorithm was used to assign medical students to residencies long before its publication by Gale and Shapley? Source: Roth, [2]
  • Reviewed: Template:Did you know nominations/Carol Mutch and Template:Did you know nominations/Susan Berget (double QPQ for heavy backlog)

Improved to Good Article status by David Eppstein (talk). Self-nominated at 21:24, 14 January 2024 (UTC). Post-promotion hook changes for this nom will be logged at Template talk:Did you know nominations/Gale–Shapley algorithm; consider watching this nomination, if it is successful, until the hook appears on the Main Page.

• Good article status checks out. Both hooks are verified and may be promoted.
  I personally prefer the main hook — it is more interesting and more clickable. --Moscow Connection (talk) 01:10, 15 January 2024 (UTC)