Exploring the Gale-Shapley Algorithm
By Ethan Williams, Enock Nyakundi and Muhiim Ali
Project Overview
What Is The Stable Matching Problem?
In the stable matching problem, several participants rank their preferences over other participants. The goal is to find a matching of participants that is stable: one where no pair of participants would rather be with each other than their assigned match.
A
B
X
Y
C
Z
Stable Matching Variants
We picked: Participants divided into proposers and receivers.
We picked: Participants can only be matched with at most one other participant.
We picked: Participants are allowed to leave others unranked.
We picked: Participants must be ranked in order.
Applications For the Version We Picked
Quick Runthrough
A
B
X
Y
X
Y
A
B
A
B
X
Y
Square’s Preferences
(Receiver)
Offers
Triangle’s Preferences
(Proposer)
A
B
X
Minimal Description Of Gale-Shapley
Most descriptions of the Gale-Shapley algorithm are implementation-focused.
Contain extra data structures that serve as redundant indexes into other data structures. These help with runtime performance.
However, to model the algorithm in Forge, we put significant effort into identifying a minimal description of the Gale-Shapley algorithm.
Our Only Data Structure: offer
The state of the algorithm in our model is represented by one data structure, offer. It is a set of pairs of proposers and receivers. A proposer-receiver pair (px -> rx) in offer means that px is proposing to rx in that round; or that px already has a tentative match to rx. The pair (px -> rx) is considered a tentative match if rx accepts the proposal: if px is the only proposer matched with rx and rx ranks px.
By lumping together tentative matches and active proposals, we are able to unify the two kinds of rejections in Gale-Shapley: receivers leaving proposers for a more favorable match, and proposers proposing to receivers where the receiver does not rank the proposer.
Initial State
The initial state of offer has every proposer paired with their favorite receiver.
Multiple proposers may be paired with the same receiver.
A
B
X
Y
State Transition
Receivers pick their favorite proposer among the offers they receive in a particular round. Rejected proposers advance their offers to their next most favorite receiver.
A
B
X
Y
Termination Condition
We have a non-standard termination condition: the receivers reject everyone that they need to. In other words, each receiver has exactly one entry in offer, and the corresponding proposer is one that they rank.
A
B
X
Y
True Preferences and False Preferences
We are interested in seeing how reporting dishonest preferences impacts the execution of the algorithm.
To this end, we support multiple sets of preferences for the participants. We can run multiple instances of the algorithm in parallel, and observe how this influences the resulting matches.
Attacking Gale-Shapley Matchings
Why Would Participants Lie?
Can a participant get a better outcome from lying?
Explain How To Read The Visualizer
Lies
Truth
Does Lying Benefit Receivers?
A receiver can misrepresent their true preferences and get a better outcome.
Here, R0 lies by misranking P0 so that they can avoid matching with them over their preferred P1.
truth
lies
Receiver-Receiver Collusion
A receiver can also misrepresent their preferences to help another receiver.
Here, R0 lies so that R2 can match with their first choice: P1.
Does Lying Benefit Proposers?
We wanted to see if lying can benefit proposers. We verified that a proposer that misrepresents their individual preferences never benefits.
Proposer-Proposer Collusion
However, proposer can misrepresent their true preferences to benefit a different proposer (who doesn’t have to lie).
Here, P1 lies that they don’t like R1 so that P0 can match with R1.
Lies
Truth
Proposer-Receiver Collusion Benefits
Proposer
Proposer-receiver collusion is possible in that if a proposer and a receiver coordinate to misrepresent their preferences, they cannot both benefit, but the proposer can.
Here, R0 lies that they like R0 so that P0 can match with them.
Proposer-Receiver Collusion Benefits Receiver
Proposer-receiver collusion is possible in that if a proposer and a receiver coordinate to misrepresent their preferences, they cannot both benefit, but the receiver can.
Here, P0 lies that they like R1 so that R0 can match with their true preference, P2.
What Does This Mean?
These properties were previously well known, but we verified them using Forge and without any domain-specific mathematical techniques.
New non-intuitive scenarios can be quickly generated.
More complex conditions, such as regret conditioned on known preferences, can be encoded and tested.
What Did We Verify
Takeaways
Solutions To These Vulnerabilities: Receivers
Effort to prevent misrepresentations by receivers are absolutely required.
These measures may include discovering the true preferences from means other than asking receivers to self-report them.
Dating app: determine preferences based on the user’s indicated interests
Matching clients and servers: Use data gathered from the network to match preferences instead of input from the end user
Solutions To These Vulnerabilities: Proposers
Effort is required for ensuring that proposers do not collude. This may include only using the Gale-Shapley algorithm in places where there are no strong outside motivations.
Since at best, colluding between proposers leaves one proposer worse off, it could also be advisable to only admit proposers who are strongly motivated to get the best match outcome.
Social Considerations
The Gale-Shapley algorithm is always run with the goal of automatically assigning matches on participants.
It suffers from the vulnerabilities that we discussed: lying, asymmetry.
There are military applications (Operations Research) for the algorithm that result in death.
Further Exploration
Regret
Encoding known information for a specific matching (like physical keys)
Stakeholders
Depends on the application, but in general
In the mentor matching application, this could additionally include
Live Demo