## 6 W-Manipulation
### W-Manipulation for Link-Additive Stability  
Every procedure for link-additive stability is strictly w-manipulable. **Theorem 6**: _Every procedure that returns a link-additive stable matching is 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, say \(P\): \(\{m_{1}:w_{2}^{[6]}>w_{1}^{[4]},m_{2}:w_{2}^{[5]}>w_{1}^{[4]},w_{1}:m_{1}^{[4] }>m_{2}^{[3]},w_{2}:m_{1}^{[3]}>m_{2}^{[2]}\}\). \(P\) has a unique link-additive stable matching, which is \(M_{1}=\{(m_{1},w_{2}),(m_{2},w_{1})\}\). Assume that \(w_{1}\) mis-reports her preferences as follows: \(w_{1}:m_{1}^{[5000]}>m_{2}^{[2]}\). Then, in the new problem, which we call \(P^{\prime}\), there is only one stable matching, which is \(M_{2}=\{(m_{1},w_{1}),(m_{2},w_{2})\}\), and \(M_{2}\) is better than \(M_{1}\) for \(w_{1}\) in \(P\). Since there is only one stable matching in both \(P\) and \(P^{\prime}\), every procedure that returns a link-additive stable matching will return \(M_{2}\) in \(P\) and \(M_{1}\) in \(P^{\prime}\), and thus, it is strictly w-manipulable. \(\Box\)  
The example in the proof of the above theorem shows a very intuitive and dangerous manipulation scheme: the manipulator sets a very high weight (higher than twice the highest of the other weights in the profile) for its top choice. In this way, it will surely be matched to its top choice, no matter the procedure used or the preferences of the other agents over the alternatives that are not their top choices. This form of manipulation can be avoided by forcing the same weight for all top choices of all agents. This restriction, however, does not prevent all forms of w-manipulation. **Theorem 7**: _If we restrict to profiles with the same weight for all top choices, every procedure that returns a link-additive stable matching is w-manipulable, and there is at least one procedure that is strictly w-manipulable._  
**Proof:** Let \(\{w_{1},w_{2},w_{3}\}\) and \(\{m_{1},m_{2},m_{3}\}\) be, respectively, the set of women and men. Consider the following instance of an SMW, \(P\): \(\{m_{1}:w_{3}^{[7]}>w_{2}^{[6]}>w_{1}^{[5]},m_{2}:w_{3}^{[7]}>w_{2}^{[6]}>w_{1 }^{[5]},m_{3}:w_{3}^{[7]}>w_{2}^{[6]}>w_{1}^{[5]},w_{1}:m_{3}^{[7]}>m_{1}^{[5] }>m_{2}^{[4]},w_{2}:m_{3}^{[7]}>m_{1}^{[5]}>m_{2}^{[4]},w_{3}:m_{3}^{[7]}>m_{1}^ {[6]}>m_{2}^{[5]}\}\). \(P\) has an unique link-additive stable matching, which is \(M_{1}=\{(m_{1},w_{2}),(m_{2},w_{1}),\ (m_{3},w_{3})\}\). Assume that \(w_{1}\) mis-reports her preferences as follows: \(w_{1}:m_{3}^{[7]}>m_{1}^{[6]}>m_{2}^{[4]}\). Then, in the new problem, that we call \(P^{\prime}\), there are only two link-additive stable matchings,_i.e._, \(M_{1}\) and \(M_{2}=\{(m_{1},w_{1}),(m_{2},w_{2}),(m_{3},w_{3})\}\), where \(M_{2}\) is better than \(M_{1}\) for \(w_{1}\). Thus, every procedure is w-manipulable. If we consider the procedure that returns matching \(M_{2}\) in \(P^{\prime}\), this pair of profiles shows that this procedure is strictly w-manipulable. \(\Box\)  
Notice that, if we consider profiles where all top choices have the same weight and all differences (of weights of adjacent items in the preference lists) are exactly one, then weights are fixed and are thus irrelevant. Furthermore, obviously, w-manipulation cannot occur, since agents cannot modify the weights. We may wonder whether, by restricting to profiles that are close to this extreme case, we may avoid w-manipulation. Unfortunately, this is not so. In fact, we can consider just profiles with the same weight for all top choices and where at most one difference is two, while all the others are one, for every agent. This holds for the example in the proof of Theorem 7. This shows that even this strong restriction is not enough to avoid w-manipulation.