  The Deferred Acceptance Algorithm (DAA) is the most widely accepted and used
algorithm to match students, workers, or residents to colleges, firms or
hospitals respectively. In this paper, we consider for the first time, the
complexity of manipulating DAA by agents such as colleges that have capacity
more than one. For such agents, truncation is not an exhaustive strategy. We
present efficient algorithms to compute a manipulation for the colleges when
the colleges are proposing or being proposed to. We then conduct detailed
experiments on the frequency of manipulable instances in order to get better
insight into strategic aspects of two-sided matching markets. Our results bear
somewhat negative news: assuming that agents have information other agents'
preference, they not only often have an incentive to misreport but there exist
efficient algorithms to find such a misreport.
