We study how the relative cost efficiency of three market-based instruments—emission taxes, tradable permits and output taxes—is influenced by the combination of accounting for incomplete compliance and pre-existing labor taxes. First, accounting for violations makes the policy instruments less effective so that environmental damages have to be larger to justify a policy. Secondly, including fines in a second-best setting provides a new means of collecting government revenues and of lessening existing tax distortions. We show that the relative position of grandfathered tradable permits vis-à-vis emission taxes improves considerably when incomplete compliance is incorporated in a second-best setting. A simple AGE model illustrates the results.