liveBook · Manning

Preference list

As explained in Algorithms Every Programmer Should Know

A preference list records a participant’s possible matches in ranked order.

A preference list ranks possible matches from most to least preferred. In matching, one side can propose in list order while the other uses its own list to compare offers. section 2.4 section 2.1.2

The lists guide both sides of a match:

  • Proposers approach potential matches in preference order. section 2.1.2
  • Receivers use their ranking to choose between a new offer and a current match. section 2.1.2

A one-pass match

University X ranks Alice first and proposes to her. Alice’s list is [X, Y, Z], so she accepts the only offer; Y and Z likewise propose to their first choices, completing the match in one pass. section 2.1.1

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 how a ranked list helps resolve a conflict: X compares Bob and Carol, keeps its preferred candidate, and rejects the other. section 2.1.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines ranked order and traces how lists guide proposals, rejections, and rematching through examples.
Examples
Traces first-choice university proposals and a conflict resolved by comparing Bob and Carol.
What you can do after
Apply it via Gale–Shapley to order proposals and compare candidates during matching.
How it connects
Connects ranked preferences to the Gale–Shapley algorithm, stable matching, and deferred acceptance.

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.