## 6 W-Manipulation
### W-Manipulation for \(\alpha\)-Stability  
We first assume that the agents know the value of \(\alpha\). We show that, when using weights, agents can manipulate by just modifying the weights. **Theorem 3**: _Let \(\alpha\) be any natural number \(>\)1. Every procedure that returns an \(\alpha\)-stable matching is w-manipulable, and there is at least one procedure that 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_{1}^{[x+\alpha]}>w_{2}^{[x]}\)
* \(m_{2}:w_{1}^{[x+\alpha]}>w_{2}^{[x]}\)
* \(w_{1}:m_{1}^{[x+\alpha]}>m_{2}^{[x+1]}\)
* \(w_{2}:m_{1}^{[x+\alpha]}>m_{2}^{[x]}\)  
where \(x\) is any value greater than zero. \(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_{1}^{[x+\alpha]}>m_{2}^{[x]}\),_i.e._, assume that she changes the weight given to \(m_{2}\) from \(x+1\) to \(x\). Let us denote with \(P^{\prime}\) the resulting problem. \(P^{\prime}\) has a unique \(\alpha\)-stable matching, that is, \(M_{1}\), which is the best \(\alpha\)-stable matching for \(w_{1}\) in \(P\). Therefore, it is possible for \(w_{1}\) to change her weights to get a better or equal result than the one obtained by telling the truth. Furthermore, since \(P^{\prime}\) has a unique \(\alpha\)-stable matching, every procedure that returns an \(\alpha\)-stable matching returns such a matching. Thus, every procedure is w-manipulable. Moreover, if we take the procedure that returns \(M_{2}\) in the first profile, this example shows that this procedure is strictly w-manipulable. \(\Box\)  
Let us now see whether there is any syntactical restriction over the profiles that can prevent this additional form of manipulation. First, we may notice that this manipulation is only related to the fact that some distances between adjacent weights are made larger or smaller. This, depending on the chosen \(\alpha\), may imply that some elements are considered in a tie or ordered in \(\alpha(P)\). Thus, a manipulator may introduce a tie that was not in its real preference ordering or may eliminate a tie from this ordering. Based on this consideration, we can consider restricting our attention to profiles where ties are not allowed. However, this would simply mean eliminating the weights, since, in this case, the \(\alpha\)-stable matchings would coincide with the stable matchings of the SM obtained by just forgetting the weights. We can thus consider what happens if we allow at most one tie (that is, a difference less than \(\alpha\)) in each preference ordering. Even this strong restriction does not avoid w-manipulation, since the example in the proof of Theorem 3 respects this restriction. A weaker restriction would be to allow at most one tie in the whole profile, but this would mean requiring coordination between the agents or knowing who is the manipulator. Furthermore, again, the same example obeys this restriction. Summarizing, if agents know the value of \(\alpha\), there is no way to prevent w-manipulation! Some hope remains for when \(\alpha\) is not known by the agents. Assume that this is the case, but agents know that \(\alpha\) is bounded by a certain value, say \(\alpha_{max}\). Unfortunately, again, the example in the proof of Theorem 3 (where we replace every \(\alpha\) with \(\alpha_{max}\)) holds. Thus, every procedure is still w-manipulable, and some are also strictly w-manipulable. Furthermore, restricting to at most one tie per agent will not avoid w-manipulation, since, again, the same example holds. The most promising case is when agents have no information about \(\alpha\). In this case, we need to define what it means for a procedure to be manipulable.