Well, handling property damages in court is deterring "tragedy of the commons" by making putting the commons-over-user at financial risk.
> ... more subtle things like information asymmetries and cognitive overload.
You pay someone to give you information. We do this now: our taxes fund the EPA and they give us information.
> You can't just ignore the parts of economics that don't fit into your ideology.
I'm not a libertarian. To the best of my understanding, there are some things that really should be done by the private sector and not by the government (airport security, for example). There are also things that really should be done by the government and not by the private sector (the trend of privatizing prisons disturbs me).
You asked a question, though: how would a libertarian society's environment be protected. I offered up an option.