liveBook · Manning

Proposal

As explained in Algorithms Every Programmer Should Know

A proposal is an offer made by a proposer to a potential matching partner during the matching procedure.

A proposal is an offer a proposer makes to a potential matching partner. The receiver compares it with their preferences and may accept or reject it. section 2.1.1

During matching, proposals can lead to:

  • Acceptance, when the receiver has no better option among the offers considered. section 2.1.1
  • Rejection, after which the proposer can approach their next preferred partner. section 2.1.2

Carol tries again

When X rejects Carol in favor of Bob, she proposes to Y, then Z. Y also rejects her, but Z 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 of student proposals and X's choice between Bob and Carol. section 2.1.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces acceptance, rejection, and rematching through examples without detailing algorithm internals.
Examples
Uses students and universities, including Carol's proposals to X, Y, and Z.
What it assumes
Assumes preference rankings for proposers and receivers, illustrating them through student-university examples.
What you can do after
Understand how an offer can be accepted or rejected as preference-based matching proceeds.
How it connects
Connects proposals to stable matching, the Gale-Shapley algorithm, and preference rankings.

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.