liveBook · Manning

Proposer

As explained in Algorithms Every Programmer Should Know

A proposer is a participant role that initiates matching proposals in a deferred-acceptance procedure.

A proposer is the participant who initiates offers in a deferred-acceptance procedure. The role can belong to either side of a matching, such as students or universities; it is not tied to one kind of participant. section 2.0 section 2.1.1

A proposer’s role in the matching:

  • Offers go to the proposer’s next preferred participant. section 2.1.2
  • A receiver may keep its preferred offer so far and reject the others. section 2.1.2
  • A rejected proposer tries another preference; held matches can change as better offers arrive. section 2.1.2

Carol’s proposals

When students propose, Carol is rejected by X and then Y, which each prefer another student. She proposes to Z next, and Z accepts her. 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.

The figure shows a first-round conflict: Bob and Carol propose to X, which keeps its preferred option and rejects Carol. section 2.1.2

Choosing which side proposes matters: the proposer side has the advantage among stable outcomes. In online dating, for example, the person who initiates a like or message acts as proposer. section 2.1.3 section 2.2.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces proposals through acceptance, rejection, and rematching, then notes proposer advantage.
Examples
Uses universities proposing to students, students proposing to universities, and users initiating dating-app contact.
What it assumes
Assumes two groups with ranked preferences and introduces their proposing and receiving roles through matching examples.
What you can do after
Understand how proposal order assigns initiative and affects which side receives its preferred stable outcome.
How it connects
Connects proposers with deferred acceptance, stable matching, receivers, and preference lists.

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.