Currently, we have several companies that are basically destroying the environment in several African countries and decimating the regional or local economies. If they were unregulated, would this behavior not increase?
This happens on typical Tragedy of the Commons scenarios, where an agent can externalize part of his costs. If property rights are respected, the owners of those properties being damaged by such companies could stop them or demand something in exchange.
The important thing is that every agent internalize all its costs.
But what happens in an unregulated market where Walmart gets together with every other retail giant and price fixes labor costs?
"Getting together" to "fix prices" doesn't work if there is freedom of entry. Doesn't matter who's getting together or what prices we're talking about, if a competitor can always enter the market proposing better prices, such cartel cannot stand for long. The wider the gap this cartel tries to create, the stronger the incentive for someone to enter the market or even some participant of the cartel to leave it. Cartels like this need the use of force (normally masked as "regulation") to stand for long*.
This is particularly strong on the labor market, since competition among employers is wide. Wallmart doesn't compete only with other retailers, but with everybody that's looking for non-skilled labor. Labor is finite, but the demand for it is virtually infinite due to the constant state of unsatisfaction of the human being (there's always something that can be done to better satisfy us).
*And even in some coercion scenarios, some interesting examples of "market solutions" may arise. I've known places where it was forbidden for some business to propose prices lower than a certain floor. Two things used to happen: some participants would propose better prices "under the table", and some would add "extras" to their services, for example a gas station that also washes your car for free if you fill your tank there.
IMO, trying to coercively set prices like that is much less effective than regulations that prevent or completely forbid the entry of new participants in a market, like the regulation that simply stopped MtGox from operating in France. These regulations are stronger "cartel keepers". The alternative to them are black markets, but for some sectors they are not really an option, particularly those sectors which strongly depend on contract enforcement, like banking. Most people are not willing to ask "the Mafia guy" to mediate their contracts...