5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! That's a very clear example, with a great definition as to how it works. And creatively described :) $\endgroup$
    – monadoboi
    May 11 '18 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.