liveBook · Manning

Rejection

As explained in Algorithms Every Programmer Should Know

A rejection is a receiver's refusal of a proposal because another available proposal is preferred or the receiver has no capacity to accept it.

In Gale–Shapley matching, a receiver rejects a proposal when they prefer another candidate. The rejected proposer remains unmatched and can try their next preferred receiver. section 2.1.2

Carol tries her next choice

Carol proposes to X, but X prefers Bob and rejects her. She then proposes to Y, which prefers Alice and rejects her too. Carol proposes to Z, which accepts. section 2.1.2

Figure 2.3 Round 1 where students are proposers. Alice, Bob, and Carol propose to their first choices from the list. A conflict is seen between Bob and Carol, where both students opt for university X. X prefers Bob over Carol and rejects Carol.

See the first-round conflict: X prefers Bob over Carol and rejects Carol's proposal. section 2.1.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces rejection and rematching through three rounds, then checks whether the resulting matching is stable.
Examples
Uses Carol's proposals to X, Y, and Z, with X and Y rejecting her before Z accepts.
What it assumes
Assumes preference rankings are available and introduces proposer and receiver roles through a worked matching.
What you can do after
Understand how a rejected proposer continues through preferences and how rejection contributes to a stable matching.
How it connects
Connects Gale–Shapley matching with preference lists, proposers, receivers, and stable matching.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.