It is true that both parties in the transaction must be better off if they agreed to the deal. Nonetheless, the standard argument for unfettered voluntary exchange does not apply because there are externalities. That is, when one person sells his vote to another, that transaction may affect unrelated third parties through the electoral process.However, there are serious flaws in this approach. His colleague Michael Sandow points out one obvious point that if a person were merely persuaded to change his vote, instead of being paid to do so, it would still have the same negative effects on the third party. So by Dr. Mankiw's explanation, we would be forced to prohibit political persuasion as well as outright vote-buying.
There is another, larger problem which gets to the heart of reasonable critiques of free trade in general. That is, many types of trade create negative externalities for others. To cite an obvious example, if I buy an automobile and gasoline, I affect the air quality for the people around me who do not necessarily benefit from my having an automobile. More crucially, perhaps, engaging in international trade has effects for the geopolitical situation. China's rise in power, which is causing a great deal of heartburn for national-security types in Washington, has been enabled directly by the world's trade. To base the legitimacy of a voluntary exchange on whether it creates negative externalities would be to undermine the free market in its entirety.
That being the case, can one argue for free trade in a case where it creates negative externalities? Free-market advocates would say that in a true free market, any negative externalities would be mitigated through voluntary exchange, leaving everyone or nearly everyone in a far superior position than if there had been no trade in the first place. And to be sure, it is hard to imagine any alternative to free trade that has not created far more misery than free trade would have. (For example, in our rush to get away from oil, we have poured vast amounts of money into ethanol-based fuels which have had the perverse effect of encouraging clear-cutting in Indonesia and elsewhere, and have driven up food prices for the world's poor.)
But the problem of negative externalities remains an issue. In the absence of an omniscient despot, the best course would probably be for budding entrepreneurs to seek out such externalities and devise ways to mitigate them for a profit, and thus remove the perceived need for coercion. But we cannot pretend that such externalities do not exist in the first place.