class StableMatching::Marriage

Provides a solution to the Stable Marriage problem by implementing the Gale-Shapley algorithm

Takes as input the preferences of two groups - alpha and beta - and produces a mathematically optimal matching/pairing between the two groups.

Example Input:

alpha_preferences = {
  "A" => ["M", "N", "L"],
  "B" => ["N", "M", "L"],
  "C" => ["M", "L", "N"],
}

beta_preferences = {
  "L" => ["B", "C", "A"],
  "M" => ["B", "A", "C"],
  "N" => ["A", "C", "B"],
}

Example Output:

{"A"=>"M", "B"=>"N", "C"=>"L", "L"=>"C", "M"=>"A", "N"=>"B"}

Public Class Methods

new(alpha_preferences, beta_preferences, opts = {}) click to toggle source

Initializes a `StableMatching::Marriage` object.

Inputs:

alpha_preferences

A Hash of Array values specifying the preferences of the alpha group. Array can contain String or Integer entries.

beta_preferences

A Hash of Array values specifying the preferences of the beta group. Array can contain String or Integer entries.

opts[:logger]

Logger instance to use for logging

Output:

StableMatching::Marriage instance

# File lib/stable-matching/marriage.rb, line 77
def initialize(alpha_preferences, beta_preferences, opts = {})
  @orig_alpha_preferences = alpha_preferences
  @orig_beta_preferences = beta_preferences

  @alpha_preferences, @beta_preferences =
    PreferenceTable.initialize_pair(alpha_preferences, beta_preferences)

  set_logger(opts)
end
solve!(alpha_preferences, beta_preferences) click to toggle source

Runs the algorithm with the specified inputs.

This is a class level shortcut to initialize a new StableMatching::Marriage instance and calls solve! on it.

Inputs:

alpha_preferences

A Hash of Array values specifying the preferences of the alpha group

beta_preferences

A Hash of Array values specifying the preferences of the beta group

Output: A Hash mapping alpha members to beta and beta members to alpha members.

# File lib/stable-matching/marriage.rb, line 56
def self.solve!(alpha_preferences, beta_preferences)
  new(alpha_preferences, beta_preferences).solve!
end

Public Instance Methods

solve!() click to toggle source

Runs the algorithm on the alpha and beta preference sets. Also validates the preference sets and raises an error if invalid.

Output:

A Hash mapping alpha members to beta and beta members to alpha members.

Raises:

StableMatching::InvalidPreferences

When alpha or beta preference groups are of invalid format

# File lib/stable-matching/marriage.rb, line 98
def solve!
  validate!

  @logger.info("Running Phase I")
  PhaseIRunner.new(alpha_preferences, beta_preferences, logger: @logger).run

  build_solution
end

Private Instance Methods

alpha_preferences() click to toggle source
# File lib/stable-matching/marriage.rb, line 113
def alpha_preferences
  @alpha_preferences ||= PreferenceTable.new(@orig_alpha_preferences)
end
beta_preferences() click to toggle source
# File lib/stable-matching/marriage.rb, line 117
def beta_preferences
  @beta_preferences ||= PreferenceTable.new(@orig_beta_preferences)
end
build_solution() click to toggle source
# File lib/stable-matching/marriage.rb, line 121
def build_solution
  solution = {}

  @alpha_preferences.members.each do |partner|
    solution[partner.name] = partner.current_acceptor.name
  end

  @beta_preferences.members.each do |partner|
    solution[partner.name] = partner.current_proposer.name
  end

  solution
end
validate!() click to toggle source
# File lib/stable-matching/marriage.rb, line 109
def validate!
  Validator.validate_pair!(@orig_alpha_preferences, @orig_beta_preferences)
end