## 6 W-Manipulation
### W-Manipulation for \(\alpha\)-Stability
**Definition 11** (\(\alpha\)-**w-manipulable**): _A procedure that returns an \(\alpha\)-stable matching is \(\alpha\)-w-manipulable if it is w-manipulable for all \(\alpha\) and it is strictly w-manipulable for at least one \(\alpha\)._  
**Theorem 4**: _There is a procedure that returns an \(\alpha\)-stable matching that is \(\alpha\)-w-manipulable._  
**Proof:** Let \(\{w_{1},w_{2}\}\) and \(\{m_{1},m_{2}\}\) be, respectively, the set of women and men. Consider the following instance of an SMW, \(P\): \(\{m_{1}:w_{1}^{[3]}>w_{2}^{[2]}\); \(m_{2}:w_{2}^{[3]}>w_{1}^{[2]}\); \(w_{1}:m_{2}^{[3]}>m_{1}^{[2]}\); \(w_{2}:m_{1}^{[3]}>m_{2}^{[2]}\}\). For every \(\alpha\), \(P\) has two \(\alpha\)-stable matchings: \(M_{1}=\{(m_{1},w_{1}),\,(m_{2},w_{2})\}\) and \(M_{2}=\{(m_{1},w_{2}),\,(m_{2},w_{1})\}\). When \(\alpha=1\), \(M_{2}\) is strictly better than \(M_{1}\) for \(w_{1}\) in \(P\), while when \(\alpha>1\), \(M_{2}\) is equally preferred to \(M_{1}\) for \(w_{1}\) in \(P\). Assume that \(w_{1}\) mis-reports her preferences as follows: \(w_{1}:m_{2}^{[3]}>m_{1}^{[1]}\). Let us denote with \(P^{\prime}\) the problem obtained from \(P\) by using this mis-reported preference for \(w_{1}\). When \(\alpha\in\{1,2\}\), \(M_{2}\) is strictly better than \(M_{1}\) for \(w_{1}\) in \(P^{\prime}\), while when \(\alpha>2\), \(M_{2}\) is equally preferred to \(M_{1}\) for \(w_{1}\) in \(P^{\prime}\). Let us consider a procedure, which we call mGS, which works as the Gale-Shapley algorithm over all the profiles except on \(P\) and \(P^{\prime}\), where it works as follows: if a matching is strictly better than another matching in terms of \(\alpha\) for \(w_{1}\), then it returns the best one, while if a matching is equally preferred to another matching in terms of \(\alpha\) for \(w_{1}\), then it returns the worst one for \(w_{1}\) w.r.t. the strict preference ordering induced by the weights. Therefore, when \(\alpha=1\), mGS returns \(M_{2}\) in both \(P\) and \(P^{\prime}\); when \(\alpha=2\), mGS returns \(M_{1}\) in \(P\) and \(M_{2}\) in \(P^{\prime}\), while when \(\alpha>2\), mGS returns \(M_{1}\) in both \(P\) and \(P^{\prime}\). Therefore, if \(w_{1}\) lies, for every \(\alpha\), he obtains a partner that is better than or equal to the one obtained by telling the truth, and there is a value, \(\alpha\) (i.e., \(\alpha\)=2), where he obtains a partner that is better than the one obtained by telling the truth. Therefore, the mGS procedure is \(\alpha\)-w-manipulable. \(\Box\)  
As in the case when \(\alpha\) is known, we may consider restricting to profiles with at most one tie per agent. However, the example in the above proof satisfies this restriction, so it shows that \(\alpha\)-w-manipulability is possible also with such a severe restriction. It is also possible to give a stronger result that is based on the following notion of manipulation. **Definition 12** (\(\alpha\)-**strictly-w-manipulable**): _A procedure that returns an \(\alpha\)-stable matching is \(\alpha\)-strictly-w-manipulable if it is strictly w-manipulable for all \(\alpha\)._  
**Theorem 5**: _There is a procedure that returns an \(\alpha\)-stable matching that is \(\alpha\)-strictly-w-manipulable._  
**Proof:** Let \(\{w_{1},w_{2}\}\) and \(\{m_{1},m_{2}\}\) be, respectively, the set of women and men. Consider the following instance of an SMW, \(P\): \(\{m_{1}:w_{1}^{[3]}>w_{2}^{[2]},m_{2}:w_{2}^{[3]}>w_{1}^{[2]},w_{1}:m_{2}^{[3]}> m_{1}^{[2]},w_{2}:m_{1}^{[3]}>m_{2}^{[2]}\}\). For every \(\alpha\), \(P\) has two \(\alpha\)-stable matchings: \(M_{1}=\{(m_{1},w_{1}),(m_{2},w_{2})\}\) and \(M_{2}=\{(m_{1},w_{2}),(m_{2},w_{1})\}\). Assume that \(w_{1}\) mis-reports her preferences as follows: \(w_{1}:m_{2}^{[3]}>m_{1}^{[1]}\). Let us denote with \(P^{\prime}\) the problem obtained from \(P\) by using this mis-reported preference for \(w_{1}\).