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
Initializes a `StableMatching::Marriage` object.
Inputs:
alpha_preferences
-
A
Hash
ofArray
values specifying the preferences of the alpha group.Array
can containString
orInteger
entries. beta_preferences
-
A
Hash
ofArray
values specifying the preferences of the beta group.Array
can containString
orInteger
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
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
ofArray
values specifying the preferences of the alpha group beta_preferences
-
A
Hash
ofArray
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
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
# File lib/stable-matching/marriage.rb, line 113 def alpha_preferences @alpha_preferences ||= PreferenceTable.new(@orig_alpha_preferences) end
# File lib/stable-matching/marriage.rb, line 117 def beta_preferences @beta_preferences ||= PreferenceTable.new(@orig_beta_preferences) end
# 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
# File lib/stable-matching/marriage.rb, line 109 def validate! Validator.validate_pair!(@orig_alpha_preferences, @orig_beta_preferences) end