They are permissible in a free market the same way NDAs are: one freely trades an opportunity to exercise a right at some future time for a guarantee of payment today.
In reality, in the vast majority of cases, the employers have much more leverage, and therefore non-competes aren't used as a negotiating tool for both parties, they're used by employers to stifle competition for labor and therefore stifle salaries.