Is it really that hard though? On the top of my mind I can come up with several success stories of solving tragedy of the commons type of problems. For example:

Global regulation around CFCs made the ozone hole shrink

The don't mess with texas anti littering campaign and similar outreach programs worldwide reduced littering

In general taxing negative externalities seems to have an effect