Definitions. A utility function is any real function. A penalty is a real non-decreasing function p(x) such that p(x) = 0 if x ≤ x_{legal}, for some fixed x_{legal} value. The penalty is said to be zero-tolerance if it has the form p_{0} + r(x) for x < x_{legal}, with p_{0} > 0 and r(x) non-decreasing. On the other hand, p(x) is progressive if it is continuous.

Theorem. Let u(x) be a continuous unimodal utility function with maximum at x_{max} > x_{legal} and p(x) = p_{0} + r(x) a zero-tolerance penalty such that u(x_{legal}) − ε ≥ w(x) = u(x) − p(x) for x > x_{legal} and some ε > 0. There is then a progressive penalty p'(x) such that u(x_{legal}) > u(x) − p'(x) and p'(x) ≤ p(x) for x > x_{legal}.

Proof. Choose some continuous strictly increasing function d(x) on [x_{legal}, x_{max}] with d(x_{legal}) = 0, d(x) ≤ ε in all its domain (for instance, d(x) = ε(x − x_{legal})/(x_{max} − x_{legal}) ) and define p'(x) on [x_{legal}, x_{max}] as

p'(x) = u(x) − u(x_{legal}) + d(x),

which is clearly non-decreasing given the unimodality of u(x). Then, for any x in (x_{legal}, x_{max}] we have:

u(x) − p'(x) = u(x_{legal}) − d(x) < u(x_{legal}),

and also:

p'(x) = u(x) − u(x_{legal}) + d(x) ≤ u(x) − u(x_{legal}) + ε ≤ p(x),

where the last inequality follows directly from the theorem hypothesis on p(x). To complete our definition of p'(x), extend it for x > x_{max} as p'(x) = p'(x_{max}). p'(x) is then clearly a progressive penalty and verifies all the conditions of the theorem.

It is not possible to relax the theorem hypothesis to merely requiring that u(x_{legal}) > w(x) = u(x) − p(x) for x > x_{legal}; the figure shows a counterexample:

The zero-tolerance penalty function p(x) tends to u(x_{max}) − u(x_{legal}) when x tends to x_{max} from the left, even though p(x_{max}) > u(x_{max}) − u(x_{legal}). So, for any continuous p'(x) ≤ p(x) we will have p'(x_{max}) ≤ u(x_{max}) − u(x_{legal}), making p'(x) an inefficient penalty for u(x). Anyway, this limit case has no real-life significance.