Markets, like governments, are very much social constructs. The market is a set of behaviors that is structured by rules, and many of the most important rules have been developed and enforced by government. Without these rules, our prized free-market economy would be a stunted and feeble version of what we see today. - Douglas J. Amy, Capitalism Requires Government
This is a common argument, one used by minarchist luminary Ayn Rand among others.
The main problem with this argument is that is assumes without proof that only a monopoly State can provide defense services. The argument makes true statements about the need for rectificatory force for enforcing property norms, but falsely (and covertly) makes the mistaken assumption that only compulsory government can possibly provide these functions.
Some formulations of this argument, such as Ayn Rand's version, acknowledges the possibility of a free market in defense services, but then falsely assumes that this would automatically lead to violent battles between "warlords." As David Friedman pointed out, "This is the wrong answer." Instead, private defense agencies (PDAs) would have a strong incentive to negotiate and use arbitration. This is obvious, when we notice that is precisely what States - in an anarchic relationship with each other - so often do. Not all States go to war with their neighbors! Since PDAs cannot shove the costs of war onto hapless citizen-serfs like States do, PDAs have a much stronger incentive to seek arbitration. Furthermore, such violence is costly, and PDAs that refuse to submit to arbitration will have higher costs than firms which do.
Note that defense services do not have a large economy of scale. Smaller more local defense services (including police departments today) tend to be more efficient than the large ones. PDAs enforcing local norms have no incentive (unlike statist monopoly police) to enforce their customers' contracted norms in "foreign" areas or enclaves. Thus, in a stateless society, polycentric law will prevail. As for property norms, property panarchy will prevail - anarcho-capitalists in their enclaves, geoists in theirs, mutualists in theirs, and anarcho-socialists in theirs. Let a thousand flowers bloom!
Here is a video with David Friedman explaining how it would work:
Also see:
Defense Services on a Free Market by Murray Rothbard.