Skip to content

ALGORITHM.md

Latest commit

 

History

History
81 lines (58 loc) · 2.96 KB

ALGORITHM.md

File metadata and controls

81 lines (58 loc) · 2.96 KB

Algorithm Details

Gale-Shapley (Deferred Acceptance) Algorithm

This document describes the mathematical foundations of the matching algorithm used in this project.

Problem Formulation

Let:

  • C = {c₁, c₂, …, cₙ} be a set of n candidates (job seekers / students)
  • P = {p₁, p₂, …, pₙ} be a set of n positions (training courses / employers)
  • S(cᵢ) = the skill set of candidate cᵢ
  • R(pⱼ) = the required skill set of position pⱼ

Preference Scoring

The preference score of candidate cᵢ for position pⱼ is:

σ(cᵢ, pⱼ) = |S(cᵢ) ∩ R(pⱼ)|

Candidates rank positions (and positions rank candidates) in descending order of σ.

Stability Definition

A matching M is stable if there is no blocking pair (cᵢ, pⱼ) ∉ M such that:

  • cᵢ prefers pⱼ over their current match in M, and
  • pⱼ prefers cᵢ over their current match in M

Algorithm (Candidate-Optimal)

Input:  preference lists for all candidates and all positions
Output: a stable matching M

1. Initialise all candidates and positions as free.
2. While ∃ free candidate cᵢ who has not yet proposed to all positions:
   a. Let pⱼ = highest-ranked position in cᵢ's list to whom cᵢ has not yet proposed.
   b. cᵢ proposes to pⱼ.
   c. If pⱼ is free:
        (cᵢ, pⱼ) become tentatively matched.
      Else if pⱼ prefers cᵢ over its current partner cₖ:
        (cᵢ, pⱼ) become tentatively matched.
        cₖ becomes free again.
      Else:
        pⱼ rejects cᵢ; cᵢ remains free.
3. Return M.

Complexity

Aspect Value
Time O(n²)
Space O(n²) for preference lists
Rounds At most n² proposals

Properties of the Output

  1. Existence: A stable matching always exists (Gale & Shapley, 1962).
  2. Candidate-optimality: Every candidate is matched to the best possible partner in any stable matching.
  3. Position-pessimality: Conversely, every position receives the worst stable partner.
  4. Uniqueness of optimal: The candidate-optimal stable matching is unique.

Happiness Index

To quantify the quality of a matching M, we define the Happiness Index:

H(M) = Σ  [ rank_C(cᵢ, M(cᵢ)) + rank_P(M(cᵢ), cᵢ) ]
       cᵢ∈C

where rank_C(c, p) is the 0-indexed rank of position p in candidate c's preference list (and vice versa). Lower values of H(M) indicate a better overall matching.

References

  • Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1), 9–15.
  • Roth, A. E. (2008). Deferred acceptance algorithms: history, theory, practice, and open questions. International Journal of Game Theory, 36(3), 537–569.
  • Martinez-Gil, J., & Freudenthaler, B. (2019). Optimal Selection of Training Courses for Unemployed People based on Stable Marriage Model. iiWAS 2019, 260–266. https://doi.org/10.1145/3366030.3366063