Monday, March 31, 2008

Theorem on zero tolerance and behavior control

We formally state and prove the fact about zero-tolerance and progressive penalties described in a prior entry.

Definitions. A utility function is any real function. A penalty is a real non-decreasing function p(x) such that p(x) = 0 if xxlegal, for some fixed xlegal value. The penalty is said to be zero-tolerance if it has the form p0 + r(x) for x < xlegal, with p0 > 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 xmax > xlegal and p(x) = p0 + r(x) a zero-tolerance penalty such that u(xlegal) − εw(x) = u(x) − p(x) for x > xlegal and some ε > 0. There is then a progressive penalty p'(x) such that u(xlegal) > u(x) − p'(x) and p'(x) ≤ p(x) for x > xlegal.

Proof. Choose some continuous strictly increasing function d(x) on [xlegal, xmax] with d(xlegal) = 0, d(x) ≤ ε in all its domain (for instance, d(x) = ε(xxlegal)/(xmaxxlegal) ) and define p'(x) on [xlegal, xmax] as

p'(x) = u(x) − u(xlegal) + d(x),

which is clearly non-decreasing given the unimodality of u(x). Then, for any x in (xlegal, xmax] we have:

u(x) − p'(x) = u(xlegal) − d(x) < u(xlegal),

and also:

p'(x) = u(x) − u(xlegal) + d(x) ≤ u(x) − u(xlegal) + ε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 > xmax as p'(x) = p'(xmax). 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(xlegal) > w(x) = u(x) − p(x) for x > xlegal; the figure shows a counterexample:

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

No comments :

Post a Comment