The Gale-Shapley Algorithm for stable matching is not dominant strategy truthful for women (i.e. the women have incentive to lie to get a preferred partner), when the men propose.
I have been trying to think of an example where this statement holds, but have only managed to figure out one where if two women cooperate they get better matches.
Could I get an example (or a hint of how to think up of one myself) where a single woman lies and is able to benefit by doing so?
Best Answer
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...
Does that work? Sure! So let's turn this into a list of preferences for everyone:
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.)