  When agents are acting together, they may need a simple mechanism to decide
on joint actions. One possibility is to have the agents express their
preferences in the form of a ballot and use a voting rule to decide the winning
action(s). Unfortunately, agents may try to manipulate such an election by
misreporting their preferences. Fortunately, it has been shown that it is
NP-hard to compute how to manipulate a number of different voting rules.
However, NP-hardness only bounds the worst-case complexity. Recent theoretical
results suggest that manipulation may often be easy in practice. To address
this issue, I suggest studying empirically if computational complexity is in
practice a barrier to manipulation. The basic tool used in my investigations is
the identification of computational "phase transitions". Such an approach has
been fruitful in identifying hard instances of propositional satisfiability and
other NP-hard problems. I show that phase transition behaviour gives insight
into the hardness of manipulating voting rules, increasing concern that
computational complexity is indeed any sort of barrier. Finally, I look at the
problem of computing manipulation of other, related problems like stable
marriage and tournament problems.
