Algo Hr Matching

Gale-Shapley Stable Matching

Overview

Gale-Shapley (deferred acceptance) finds a stable matching between two equally-sized sets where no unmatched pair prefers each other over their current match. Runs in O(n²) worst case. Proposer-optimal: the proposing side gets their best stable partner.

When to Use

Trigger conditions:

• Matching candidates to job positions based on mutual preferences
• Assigning students to schools or residents to hospitals
• Any two-sided matching where stability (no blocking pairs) is required

When NOT to use:

• For one-sided assignment (use Hungarian algorithm)
• When preferences are based on scores, not rankings (use optimization)

Algorithm

IRON LAW: The Proposing Side Gets Their BEST Stable Partner
Gale-Shapley is proposer-optimal and reviewer-pessimal. If employers
propose, they get their best stable match; candidates get their worst.
The CHOICE of who proposes determines which stable matching is found.

Phase 1: Input Validation

Collect: preference rankings from both sides. Each participant ranks all members of the other side. Gate: Complete preference lists, equal-sized groups (or handle unequal with dummy entries).

Phase 2: Core Algorithm

1. All proposers are "free" (unmatched) 2. While any proposer is free and hasn't proposed to everyone:

• Free proposer proposes to their highest-ranked unproposed-to reviewer
• Reviewer accepts if unmatched, or replaces current match if new proposer is preferred
• Replaced proposer becomes free again

3. Terminate when all proposers are matched

Phase 3: Verification

Check stability: for every unmatched pair (a,b), verify that at least one of them prefers their current match over the other. No blocking pairs = stable. Gate: Zero blocking pairs found.

Phase 4: Output

Return matching with stability confirmation.

Output Format

{
  "matching": [{"proposer": "Candidate_A", "reviewer": "Company_X", "proposer_rank": 1, "reviewer_rank": 2}],
  "metadata": {"pairs": 10, "rounds": 23, "blocking_pairs": 0, "proposer_side": "candidates"}
}

Examples

Sample I/O

Input: 3 candidates, 3 companies, each with full preference rankings Expected: Stable matching with zero blocking pairs. Candidate-proposing gives candidate-optimal result.

Edge Cases

Gotchas

• Proposer advantage: If candidates propose, they get better matches than if companies propose. This is a design choice with equity implications.
• Incomplete preferences: If participants don't rank everyone, unmatched results are possible. Handle with acceptable-partner thresholds.
• Many-to-one: Hospital-resident matching uses the many-to-one variant (each hospital has multiple slots). Use the Roth-Peranson extension.
• Strategic manipulation: The reviewing side CAN benefit from misreporting preferences (truncating lists). The proposing side cannot — truthful reporting is dominant strategy for proposers.
• Preference elicitation: Getting honest, complete rankings is hard in practice. People satisfice rather than fully rank all options.

References

• For many-to-one matching (hospital-resident), see references/many-to-one.md
• For strategic behavior analysis, see references/strategic-manipulation.md

直接建立檔案：

# Example: 新創公司秋招 — 5 名候選人 × 5 個職缺穩定配對

## Scenario

FinStack（金融科技新創）今年秋招開放 5 個職缺：前端工程師（FE）、後端工程師（BE）、資料工程師（DE）、產品經理（PM）、資安工程師（SEC）。人資 Kelly 收到 5 名最終候選人：Alice、Bob、Carol、Dave、Eve。

雙方都已完成互相評分，Kelly 希望產出一份「穩定配對」名單，確保不會在 offer 發出後出現「候選人更想去另一個職缺，而那個職缺也更想要那名候選人」的局面（blocking pair），導致 offer 被拒或內部競爭。

Kelly 決定讓**公司職缺為 proposer 端**（由公司主動出 offer），因為 FinStack 品牌較弱，讓公司優先鎖定首選人選可降低 offer 被拒率。

### 偏好排名

**公司職缺偏好（由高到低）：**

| 職缺 | 第 1 | 第 2 | 第 3 | 第 4 | 第 5 |
|------|------|------|------|------|------|
| FE   | Carol | Alice | Eve  | Bob  | Dave |
| BE   | Alice | Dave  | Bob  | Eve  | Carol |
| DE   | Eve  | Carol | Dave | Alice | Bob |
| PM   | Bob  | Alice | Carol | Dave | Eve |
| SEC  | Dave | Eve   | Alice | Bob  | Carol |

**候選人偏好（由高到低）：**

| 候選人 | 第 1 | 第 2 | 第 3 | 第 4 | 第 5 |
|--------|------|------|------|------|------|
| Alice  | BE   | PM   | FE   | SEC  | DE  |
| Bob    | PM   | BE   | DE   | FE   | SEC |
| Carol  | FE   | DE   | PM   | BE   | SEC |
| Dave   | SEC  | BE   | DE   | PM   | FE  |
| Eve    | DE   | SEC  | FE   | PM   | BE  |

---

## Analysis

### Phase 1：輸入驗證

- 雙方各 5 個，等量 ✓
- 每方對另一方完整排名（5 選 5）✓
- 無重複、無缺漏 ✓
- **Proposer 端：公司職缺**（FE、BE、DE、PM、SEC）

Gate 通過，進入核心演算法。

---

### Phase 2：Gale-Shapley 執行追蹤

> 符號：`X → Y` = X 向 Y 提出，`Y ✓ X` = Y 接受，`Y ✗ X` = Y 拒絕

**Round 1：所有職缺向各自第 1 志願提出**

| 職缺 | 提出給 | 候選人反應 |
|------|--------|-----------|
| FE   | Carol  | Carol 暫時接受（首個 offer） |
| BE   | Alice  | Alice 暫時接受（首個 offer） |
| DE   | Eve    | Eve 暫時接受（首個 offer） |
| PM   | Bob    | Bob 暫時接受（首個 offer） |
| SEC  | Dave   | Dave 暫時接受（首個 offer） |

Round 1 後：全部配對，無自由職缺。  
**→ 演算法在 Round 1 即終止。**（n=5 時最佳情況：所有第 1 志願互不衝突）

---

### Phase 3：穩定性驗證

檢查所有 10 個未配對組合是否存在 blocking pair：

| 未配對組合 | 條件 A（職缺偏好）| 條件 B（候選人偏好）| Blocking？|
|------------|-----------------|-----------------|---------|
| FE ↔ Alice | FE 排 Alice 第 2（高於 Carol 第 1？No，Carol 是第 1）| — | 否 |
| FE ↔ Bob   | FE 排 Bob 第 4（低於 Carol 第 1）| — | 否 |
| FE ↔ Dave  | FE 排 Dave 第 5（低於 Carol 第 1）| — | 否 |
| FE ↔ Eve   | FE 排 Eve 第 3（低於 Carol 第 1）| — | 否 |
| BE ↔ Bob   | BE 排 Bob 第 3（低於 Alice 第 1）| — | 否 |
| BE ↔ Carol | BE 排 Carol 第 5（低於 Alice 第 1）| — | 否 |
| BE ↔ Dave  | BE 排 Dave 第 2（高於 Alice）✓ | Dave 偏好 SEC（第 1）> BE（第 2）→ Dave 不偏好 BE 勝過 SEC | 否 |
| DE ↔ Alice | DE 排 Alice 第 4（低於 Eve 第 1）| — | 否 |
| PM ↔ Alice | PM 排 Alice 第 2（高於 Bob）✓ | Alice 偏好 BE（第 1）> PM（第 2）→ Alice 不偏好 PM 勝過 BE | 否 |
| SEC ↔ Eve  | SEC 排 Eve 第 2（高於 Dave）✓ | Eve 偏好 DE（第 1）> SEC（第 2）→ Eve 不偏好 SEC 勝過 DE | 否 |

**Blocking pairs：0**  
Gate 通過，穩定匹配確認。

---

### Phase 4：結果解讀

因公司為 proposer 端，本結果為 **公司最優穩定匹配**（company-optimal）：

- FE 拿到首選 Carol
- BE 拿到首選 Alice
- DE 拿到首選 Eve
- PM 拿到首選 Bob
- SEC 拿到首選 Dave

這對候選人而言是 **reviewer-pessimal** 的穩定匹配——若改由候選人為 proposer，結果可能對候選人更有利。Kelly 應向候選人說明配對邏輯，以維持透明度。

---

## Result

{ "matching": [ {"proposer": "FE", "reviewer": "Carol", "proposer_rank": 1, "reviewer_rank": 1}, {"proposer": "BE", "reviewer": "Alice", "proposer_rank": 1, "reviewer_rank": 1}, {"proposer": "DE", "reviewer": "Eve", "proposer_rank": 1, "reviewer_rank": 1}, {"proposer": "PM", "reviewer": "Bob", "proposer_rank": 1, "reviewer_rank": 1}, {"proposer": "SEC", "reviewer": "Dave", "proposer_rank": 1, "reviewer_rank": 1} ], "metadata": { "pairs": 5, "rounds": 1, "blocking_pairs": 0, "proposer_side": "job_positions" } }

### 給 Kelly 的行動建議

1. **同步發出 5 封 offer**：第 1 輪無衝突，可立即確認，無需分批。
2. **告知候選人配對為公司優先**：若有候選人反映「這不是我最想要的職缺」，需解釋穩定匹配邏輯，避免誤解為歧視。
3. **備案：候選人拒絕 offer**：若任一人拒絕（偏好外部公司），重新執行 Gale-Shapley，將拒絕者標記為不可用，並補入候補候選人。
4. **下次考慮候選人優先**：若 FinStack 品牌提升，改為候選人 propose，可作為吸引人才的談判籌碼（「我們讓你決定職缺」）。

Many-to-One Stable Matching

Many-to-one matching extends Gale-Shapley to handle cases where one side has capacity > 1: hospitals accept multiple residents, universities accept multiple students, companies fill multiple identical seats.

The standard one-to-one algorithm breaks here because a hospital holding q seats is not the same as q independent hospitals — accepting or rejecting a new applicant is relative to the hospital's entire current cohort.

---

Formal Definition

Participants:

• R = {r₁, r₂, ..., rₙ} — residents (proposers), each wants exactly one position
• H = {h₁, h₂, ..., hₘ} — hospitals (reviewers), each has quota qⱼ ≥ 1
• Σqⱼ ≥ n (enough total capacity; some seats may go unfilled)

Preferences:

• Each resident ranks a subset of hospitals (acceptable list)
• Each hospital ranks all residents who listed it as acceptable

Stable matching conditions (adapted):

A matching μ is stable if: 1. No resident is matched to an unacceptable hospital 2. No hospital is matched beyond quota 3. No blocking pair (r, h) exists such that:

• r prefers h over μ(r) (or is unmatched)
• h prefers r over some resident in μ(h) (or has unfilled capacity)

---

Algorithm: Hospital-Resident Deferred Acceptance

This is the resident-proposing version — residents get their best stable match, hospitals get their worst.

Input:
  residents: list of (resident_id, [hospital preferences in order])
  hospitals: list of (hospital_id, quota, [resident preferences in order])

State:
  free_residents: queue of unmatched residents
  hospital_holds: dict mapping hospital_id → set of currently held residents
  next_proposal: dict mapping resident_id → index into their preference list

Algorithm:

1. Initialize:
   free_residents = all residents
   hospital_holds[h] = {} for all h
   next_proposal[r] = 0 for all r

2. While free_residents is not empty:
   r = free_residents.dequeue()
   
   If next_proposal[r] >= len(r.preferences):
     r remains permanently unmatched (exhausted list)
     continue
   
   h = r.preferences[next_proposal[r]]
   next_proposal[r] += 1
   
   hospital_holds[h].add(r)
   
   If len(hospital_holds[h]) > h.quota:
     # Hospital is over capacity — reject worst held resident
     worst = min(hospital_holds[h], key=lambda x: h.rank(x))
     hospital_holds[h].remove(worst)
     free_residents.enqueue(worst)

3. Output:
   matching = {r: h for h in hospitals for r in hospital_holds[h]}

Key difference from one-to-one: Step 2 uses > quota check and ejects the worst current hold, not a single current match. The hospital may hold up to q residents simultaneously.

---

Worked Example

Three hospitals, five residents:

Hospitals:
  Mass General (MGH): quota=2, ranks residents: A > C > B > D > E
  Beth Israel (BID): quota=2, ranks residents: B > A > D > C > E
  Brigham (BWH): quota=1, ranks residents: C > A > E > B > D

Residents (preference lists):
  A: MGH > BID > BWH
  B: BID > MGH > BWH
  C: BWH > MGH > BID
  D: MGH > BID
  E: BID > BWH

Execution:

Round 1 — all residents propose to top choice:

• A → MGH (MGH holds: {A}, 1/2)
• B → BID (BID holds: {B}, 1/2)
• C → BWH (BWH holds: {C}, 1/1)
• D → MGH (MGH holds: {A, D}, 2/2)
• E → BID (BID holds: {B, E}, 2/2)

All hospitals within quota. No rejections.

Result: All 5 matched, 1 BWH seat filled, 0 open MGH seats.

Matching:
  A → MGH  (rank 1 for A, rank 1 for MGH among its held)
  D → MGH  (rank 1 for D, rank 4 for MGH)
  B → BID  (rank 1 for B, rank 1 for BID)
  E → BID  (rank 2 for E, rank 5 for BID)
  C → BWH  (rank 1 for C, rank 1 for BWH)

Blocking pair check:

• (E, MGH): E prefers BID over MGH → not a blocking pair from E's side
• (D, BID): D only listed MGH and BID. D prefers MGH (current) → not a blocking pair
• No blocking pairs → stable

---

More Contentious Example: Rejection Cascade

Hospitals:
  H1: quota=1, ranks: X > Y > Z
  H2: quota=1, ranks: Y > X > Z

Residents:
  X: H1 > H2
  Y: H1 > H2
  Z: H1 > H2

Round 1:

• X → H1 (H1 holds: {X})
• Y → H1 (H1 over quota: holds {X,Y}, ejects Y — H1 prefers X over Y)
• Z → H1 (H1 over quota: holds {X,Z}, ejects Z — H1 prefers X over Z)

Round 2:

• Y → H2 (H2 holds: {Y})
• Z → H2 (H2 over quota: holds {Y,Z}, ejects Z — H2 prefers Y over Z)

Z exhausts preference list → Z permanently unmatched.

Final matching: X → H1, Y → H2, Z → unmatched

This is correct and stable: Z cannot block because both H1 and H2 prefer their current match over Z.

---

Quota-Filling Edge Cases

---

Proposer-Optimality Still Holds

The IRON LAW from the parent skill applies unchanged:

• Resident-proposing → every resident gets their best stable partner
• Hospital-proposing → every hospital gets its best stable cohort (as a set)

In practice, national residency matches (NRMP in the USA) use resident-proposing because residents are the weaker bargaining side. If hospitals proposed, they would extract all the surplus.

Do not let stakeholders flip who proposes without understanding this. A hospital administrator asking to "optimize for hospital preferences" is asking for hospital-proposing GS, which gives every resident their worst stable partner.

---

Roth-Peranson Extension (Couples)

The real NRMP problem includes couples who must match to geographically co-located hospitals. This breaks the clean O(n²) guarantee and stable matching may not exist.

The Roth-Peranson algorithm handles couples by: 1. Running standard many-to-one GS 2. Inserting couple proposals as atomic units (both partners propose together) 3. If a couple causes a cascade of rejections that loop, declare instability

For most practical instances (< 5% couples), a stable matching exists and the algorithm finds it. Theoretical worst-case: no stable matching exists, but this is rare in real data.

If your problem has couples or joint constraints: flag it explicitly. The simple many-to-one algorithm above does not handle this.

---

Implementation Notes

Ranking lookup must be O(1)

The inner loop runs O(n·q) times. If h.rank(r) is a linear scan, total runtime becomes O(n²q). Pre-build a rank dict:

# Build once per hospital
hospital_rank = {
    h_id: {r_id: idx for idx, r_id in enumerate(h_prefs)}
    for h_id, h_prefs in hospital_preferences.items()
}

# O(1) lookup
def rank_of(hospital_id, resident_id):
    return hospital_rank[hospital_id].get(resident_id, float('inf'))

Residents not on a hospital's list get rank inf — they are never chosen over anyone acceptable.

Holding structure

Use a max-heap keyed by hospital's rank of each resident so ejecting the worst hold is O(log q):

import heapq

# hospital_holds[h] = min-heap of (-hospital_rank, resident_id)
# Negate rank so Python's min-heap gives us the worst (highest rank number) quickly

def add_to_hospital(h_id, r_id, holds, quota):
    rank = rank_of(h_id, r_id)
    heapq.heappush(holds[h_id], (-rank, r_id))  # negated = worst at top
    if len(holds[h_id]) > quota[h_id]:
        _, ejected = heapq.heappop(holds[h_id])  # eject highest rank (worst)
        return ejected
    return None

Stability verification (post-run)

def find_blocking_pairs(matching, resident_prefs, hospital_prefs, hospital_holds, quota):
    blocking = []
    for r, matched_h in matching.items():
        r_pref = resident_prefs[r]
        matched_h_rank = r_pref.index(matched_h) if matched_h else len(r_pref)
        
        for h in r_pref[:matched_h_rank]:  # hospitals r prefers over current
            h_held = hospital_holds[h]
            if len(h_held) < quota[h]:
                blocking.append((r, h, "hospital has capacity"))
            else:
                worst_held_rank = max(hospital_prefs[h].index(x) for x in h_held)
                r_rank_at_h = hospital_prefs[h].index(r) if r in hospital_prefs[h] else float('inf')
                if r_rank_at_h < worst_held_rank:
                    blocking.append((r, h, "hospital prefers r over worst held"))
    return blocking

Zero results from this function = confirmed stable.

---

Complexity

For n=1000 residents, m=200 hospitals, q=10: roughly 10⁷ operations — fast enough to run interactively.

Strategic Manipulation in Gale-Shapley

The Core Asymmetry

Gale-Shapley has a fundamental, proven asymmetry in strategic vulnerability:

This is not a heuristic — it is a theorem. Dubins & Freedman (1981) and Roth (1982) proved both directions.

Implication for HR systems: If candidates propose (which is typical in job markets), candidates have no incentive to game the system. But if you are an employer (reviewer), you might benefit from strategically limiting your stated acceptable-partner list.

---

Why Proposers Cannot Manipulate

The Dominance Proof (Informal)

In candidate-proposing Gale-Shapley:

1. At any round, a candidate's proposal to their next choice is triggered only after being rejected by all previous choices. 2. If a candidate misreports by skipping someone (pretending to rank them lower), they either:

• Never reach that person (because they got matched earlier — no loss), or
• Reach them later and still propose (no gain from the skip), or
• Never propose to them and end up unmatched (a loss).

3. If a candidate misreports by promoting someone (pretending they rank a "safe" match higher), they get matched to a worse-ranked true preference.

There is no rearrangement of a proposer's reported list that produces a match better than their true top achievable stable partner.

What "Proposer-Optimal" Means Concretely

If the true set of stable matchings is {M₁, M₂, M₃}, the proposing side gets M₁ (the best stable matching for them, worst for reviewers). No manipulation can get them above M₁. They can only hurt themselves by lying.

---

How Reviewers Can Manipulate: Truncation

The only proven effective strategy for reviewers is preference list truncation: a reviewer submits only a subset of their true acceptable partners, rejecting the rest outright.

Why Truncation Works

When a reviewer truncates their list, they artificially create "unmatched" proposers. This forces the algorithm to reassign those proposers elsewhere — potentially freeing up better proposers for the truncating reviewer.

Worked Example

Setup: 3 candidates (C1, C2, C3), 3 companies (E1, E2, E3). Candidates propose.

True preferences:

Algorithm with truthful reporting:

• Round 1: C1→E1 (accepted), C2→E1 (E1 prefers C1, rejects C2), C3→E2 (accepted)
• Round 2: C2→E2 (E2 prefers C2 over C3, accepts; C3 freed)
• Round 3: C3→E1 (E1 prefers C1, rejects C3)
• Round 4: C3→E3 (accepted)

Result: {C1↔E1, C2↔E2, C3↔E3}

E2 gets C2 (their 1st choice). E1 gets C1 (their 1st choice). E3 gets C3.

Now E1 truncates: E1 reports only {C1} as acceptable (drops C2 and C3).

• Round 1: C1→E1 (accepted), C2→E1 (E1 rejects — C2 not on truncated list), C3→E2 (accepted)
• Round 2: C2→E2 (E2 prefers C2 over C3, C3 freed)
• Round 3: C3→E1 (E1 rejects — C3 not on truncated list)
• Round 4: C3→E3 (accepted)

Result: {C1↔E1, C2↔E2, C3↔E3} — same outcome. Truncation had no effect here because the truthful result already gave E1 their top choice.

Now try a case where truncation changes the result:

Modify E2's preferences: E2 ranks C1 > C2 > C3 (E2 now prefers C1).

Truthful run:

• Round 1: C1→E1 (accepted), C2→E1 (rejected by E1; E1 prefers C1), C3→E2 (accepted)
• Round 2: C2→E2 (E2 prefers C2 over C3? No — E2: C1>C2>C3. C2 vs C3: C2 is preferred. Accept C2, free C3.)
• Round 3: C3→E1 (rejected), C3→E3 (accepted)

Result: {C1↔E1, C2↔E2, C3↔E3}. E2 gets C2 (rank 2).

E2 truncates to {C1, C2} — no change possible here since C3 gets pushed to E3 anyway.

Construct a case where truncation truly helps:

Truthful run (candidates propose):

• Round 1: C1→E1 (accepted), C2→E2 (accepted), C3→E1 (E1: C1>C3, rejects C3)
• Round 2: C3→E2 (E2: C1>C3>C2; C3 vs C2: C3 preferred. E2 accepts C3, frees C2.)
• Round 3: C2→E1 (E1: C1>C2; rejects C2)
• Round 4: C2→E3 (accepted)

Result: {C1↔E1, C3↔E2, C2↔E3}. E2 gets C3 (rank 2 for E2).

E2 truncates to {C1} — only accepts C1:

• Round 1: C1→E1 (accepted), C2→E2 (E2 rejects — C2 not on list), C3→E1 (E1 rejects C3)
• Round 2: C2→E1 (rejected), C3→E2 (E2 rejects — C3 not on list... wait, C1 is only acceptable)

Hmm — C3→E2: E2's truncated list is {C1}, so C3 is rejected.

• Round 2: C2→E1 (rejected), C3→E2 (rejected)
• Round 3: C2→E2 (rejected), C3→E3 (accepted)
• Round 4: C2→E3 (E3: C2 preferred over C3; wait, C3 already there. E3: C1>C2>C3. C2 vs C3: C2 wins. E3 accepts C2, frees C3.)
• Round 5: C3→E2 (still rejected), then C3 is unmatched.

Actually if E2 truncates to only C1, and C1 goes to E1, E2 ends up unmatched — worse for E2.

The lesson from these examples: Truncation only helps when it causes a chain reaction that eventually frees a preferred proposer for the truncating reviewer. This requires specific preference configurations and is not guaranteed.

---

Conditions Under Which Truncation Helps

Truncation is beneficial for reviewer R only when all of the following hold:

1. R is not getting their first choice under truthful play. 2. There exists a proposer P whom R prefers over their current truthful match. 3. P is currently matched to someone else under truthful play. 4. Rejecting lower-ranked proposers causes a chain that eventually frees P.

Formally: reviewer R benefits from truncating at threshold k (keeping only their top k choices) if doing so changes R's match from rank-j to rank-i, where i < j ≤ k.

Detection heuristic: compare the proposer-optimal stable matching against the reviewer-optimal stable matching. If they are different, reviewers in the "gap" (who got worse outcomes under proposer-optimal) have a potential incentive to manipulate.

---

Finding All Stable Matchings (The Manipulation Space)

Reviewers can only achieve outcomes within the set of stable matchings. Strategic manipulation cannot produce an unstable outcome — it can only shift which stable matching is selected.

The Lattice of Stable Matchings

All stable matchings form a distributive lattice:

• One extreme: proposer-optimal (best for proposers, worst for reviewers)
• Other extreme: reviewer-optimal (best for reviewers, worst for proposers)
• Every point in between is also a stable matching

Implication: A reviewer who successfully manipulates can move the outcome from the proposer-optimal end toward the reviewer-optimal end — but no further. They cannot achieve a match that isn't stable.

Rotation Pointers (Advanced)

The full set of stable matchings can be enumerated using the rotation pointers technique (Irving & Leather 1986). Each "rotation" is a set of proposer-reviewer pairs that can be simultaneously reassigned. Applying a subset of rotations to the proposer-optimal matching produces a different stable matching.

For HR systems with n candidates: there are at most n(n-1)/2 rotations and potentially exponentially many stable matchings, but the proposer-optimal and reviewer-optimal bounds are always computable in O(n²).

---

Practical Detection in HR Systems

Red Flags That Manipulation May Be Occurring

1. Employer submits unusually short preference lists: if market norm is ranking 10 candidates but an employer ranks only 3, they may be truncating. 2. Systematic "no-hire" outcomes for specific employers: an employer that appears to never hire might be truncating so aggressively they end up unmatched by mistake. 3. Preference list submitted very late: late submission sometimes indicates strategic waiting to observe others' lists (relevant in non-simultaneous systems).

What You Can Prove vs. Infer

---

Incentive-Compatible Alternatives

If manipulation is a concern, these variants address it:

Random Serial Dictatorship (for one-sided)

Not applicable to two-sided matching, but useful context: when one side has no preferences, random assignment is strategy-proof.

Jury/Quota Mechanisms

In school-choice systems (Abdulkadiroğlu & Sönmez 2003), allowing schools to rank students by lottery (rather than true preference) creates a one-sided structure that is strategy-proof for students.

Two-Sided Matching Without Manipulation Guarantees

No two-sided stable matching mechanism is simultaneously:

• Stable
• Strategy-proof for both sides

This is proven impossible (Roth 1982). You must choose which side gets strategy-proofness. Gale-Shapley gives it to the proposing side.

---

Decision Framework for System Designers

Is truthful reporting from BOTH sides required?
│
├── YES → Two-sided mechanism cannot achieve this. Consider:
│         - One-sided mechanism (one side has no strategic role)
│         - Scoring-based assignment (no stated preferences)
│         - Repeated game with reputation effects
│
└── NO → Choose who proposes based on equity/optimality goals:
          │
          ├── Favor candidates → Candidates propose
          │   (Candidates get proposer-optimal match, strategy-proof for candidates)
          │
          └── Favor employers → Employers propose
              (Employers get proposer-optimal match, strategy-proof for employers)

Recommendation for job markets: Candidate-proposing is standard (NRMP, law clerk matching) because: 1. Candidates are the less powerful party and benefit from the guarantee. 2. Employers have repeated interactions and reputation constraints that partially substitute for formal strategy-proofness.

---

Summary Table

The safe default for any participant who does not know the full preference landscape: report truthfully. Only reviewers with near-complete information about others' preferences can reliably benefit from manipulation — and even then only in specific configurations.