Say you're a woman named Xena, and we are cooking up a scenario in which you'd want to lie in Gale-Shapley.
To do that, we first have to give you a choice. So let's say you are the first choice of both Albus and Brian, who begin the algorithm by proposing to you.
If one of them is your favorite, then you just win automatically. To avoid that, let's imagine that your heart belongs to a third man named Conan. Unfortunately, he didn't propose to you; his top choice was that hussy, Yvonne.
Now, between Albus and Brian, you prefer Albus. Why might you provisionally accept Brian's proposal, anyway? (This would be the dishonest step of Gale-Shapley.)
Well, maybe it's like this...
- if you accept Albus's proposal, Brian proposes to Zoe next, and Zoe (not having any other suitors) says yes. The game ends, and everyone marries whoever they're dating at the moment.
- if you accept Brian's proposal, Albus proposes to Yvonne, and she dumps Conan, giving you a chance with him.
Does that work? Sure! So let's turn this into a list of preferences for everyone:
- Albus: Xena > Yvonne > Zoe
- Brian: Xena > Zoe > Yvonne
- Conan: Yvonne > Xena > Zoe
- Xena: Conan > Albus > Brian
- Yvonne: Albus > Conan (it doesn't matter where Brian fits in)
- Zoe: (Zoe's preferences won't affect anything at all)
This is a case where Gale-Shapley goes better for Xena if she lies and acts as though her preferences are Conan > Brian > Albus, instead. (Assuming that everyone else is honest.)