Jump to ContentJump to Main Navigation
An Introduction to Auction Theory$

Flavio M. Menezes and Paulo K. Monteiro

Print publication date: 2004

Print ISBN-13: 9780199275984

Published to Oxford Scholarship Online: April 2005

DOI: 10.1093/019927598X.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 26 February 2017

(p.165) Appendix D Convexity

(p.165) Appendix D Convexity

Source:
An Introduction to Auction Theory
Publisher:
Oxford University Press

In this section, we consider a few results on convex functions that are used in Chapter 6. We begin with the convex hull.

Definition 28 The convex hull of a function f(·) is the greatest convex function that is pointwise smaller than f. That is, if f:[0,1] → ℝ then g:[0,1] → ℝ is the convex hull of f if:

  1. 1. g is convex;

  2. 2. gf, that is g(x) ≤ f(x), for all x ∈ [0,1];

  3. 3. if h is a convex function and h ≤ f then h ≤ g.

The convex hull of a function exists and has an explicit expression (see Rockafellar: 36). We do not consider here the more general case.

Proposition 11 If h:[0,1] → ℝ is continuous then the function g defined below is the convex hull of h:

(D.1)
g ( q ) = min { l = 1 n λ l h ( r l ) ; λ l , r l [ 0 , 1 ] , l n λ l = 1 l n λ l r l = q }

Proof: The minimum is attained since h is continuous. It is immediate that g(q) ≤ h(q) for every q. Now if fh is a convex function then for any convex combination q = l = 1 n λ l r l we have that

f ( q ) = f ( l = 1 n λ l r l ) l λ l f ( r l ) l λ l h ( r l ) .
(p.166) Hence f(q) ≤ g(q). It remains to prove that g is convex. Suppose λ ∈ (0,1) and q 1,q 2 ∈ [0,1]. Then there exists ωl,rl,ω′l,r′l such that
q 1 = l = 1 n w l r l ; w l 0 , r l [ 0 , 1 ] l = 1 n w l = 1 ; q 2 = l = 1 n w l r l ; w l 0 , r l [ 0 , 1 ] l = 1 n w l = 1 ; g ( q 1 ) = l = 1 n w l g ( r l ) , g ( q 2 ) = l = 1 n w l h ( r l ) .
We have that
λ g ( q 1 ) + ( 1 λ ) g ( q 2 ) = λ l = 1 n w l h ( r l ) + ( 1 λ ) l = 1 n w l h ( r l ) = l = 1 n λ w l h ( r l ) + l = 1 n ( 1 λ ) w l h ( r l ) = i = 1 2 n θ i h ( s i ) ; θ i = { λ w i if i n ( 1 λ ) w l if i = l + n , l n
and
s i = { r i if i n r l if i = l + n , l n .
Thus,
g ( λ q 1 + ( 1 λ ) q 2 ) i = 1 2 n θ i h ( s i ) = λ g ( q 1 ) + ( 1 λ ) g ( q 2 ) .

Lemma 14 If g(x) < f(x) then g′(y) = g′(x) in a neighborhood of x.

Proof: Suppose g(x) < f(x). There are λl ≥ 0, ∑lλl = 1,xl ∈ [0,1], x = ∑lλl xl such that g(x) = ∑lλl f(xl). Since

g ( x ) l λ l g ( x l ) l λ l f ( x l ) = g ( x ) ,
we conclude that g(xl) = f(xl) for every l. We first show that there is a θ ∈ [0,1] such that g(x) = θf(ak) + (1 − θ)f(al) and θak + (1 − θ)al = x. To see this (p.167) note that if λ* is a solution of
min l = 1 n λ l b l ,
λ l > 0 , l = 1 n λ l < 1 , l = 1 n λ l a l = x
then for some μ real
b l = μ a l , 1 l n
and in this case ∑lλl bl = μx for every λ and therefore for some λ with λl = 0 as well. Now consider the problem
min l = 1 n λ l b l ,
λ l 0 , l = 1 n λ l = 1 , l = 1 n λ l a l = x
and consider the solution λ* with the greatest number of zero coefficients λ*l. From the previous case we see that n = 2. Define α = ak and β = al, we may write
g ( θ α + ( 1 θ ) β ) = θ f ( α ) + ( 1 θ ) f ( β ) , θ α + ( 1 θ ) β = x .
Without loss of generality α < x < β. Now consider y,y′ such that α < y < x < y′ < β. There are a,b ∈ (0,1) such that aα + (1 − a)x = y and bx + (1 − b)β = y′. Namely a = (xy)/(x − α) and b = (β − y′)/(β − x). Then
g ( y ) a g ( α ) + ( 1 a ) g ( x ) , g ( y ) b g ( x ) + ( 1 b ) g ( β ) .
Moreover, r : = y x y y ( 0 , 1 ) is such that ry + (1 − r)y′ = x. Then
(D.2)
g ( x ) r g ( y ) + ( 1 r ) g ( y ) r a g ( α ) + ( r ( 1 a ) + ( 1 r ) b ) g ( x ) + ( 1 r ) ( 1 b ) g ( β ) ,
and thus,
g ( x ) r a r a + ( 1 r ) ( 1 b ) f ( α ) + ( 1 r ) ( 1 b ) r a + ( 1 r ) ( 1 b ) f ( β ) = β + x β + α f ( α ) + x α β + α f ( β ) = θ f ( α ) + ( 1 θ ) f ( β ) = g ( x ) .
Thus the inequalities in (D.2) are equalities and this ends the proof. □

(p.168) We now consider the one-sided derivative of a convex function.

Proposition 12 If g:[0,1) → ℝ is convex then for every x ∈ [0,1) there exists

(D.3)
g + ( x ) = lim r 0 g ( x + r ) g ( x ) r .
Moreover, the function x → g+(x) is increasing.

Proof: First note that if a < b and c < d,ac,bd then

g ( b ) g ( a ) b a g ( d ) g ( c ) d c .
To see this consider first a = c. That is a = c < bd. Then if r = (db)/(da) we have that
g ( b ) = g ( r a + ( 1 r ) d ) d b d a g ( a ) + b a d a g ( d ) .
The case b = d is analogous. Thus we have that
g ( b ) g ( a ) b a g ( d ) g ( a ) d a , a < b < d .
Therefore, the ratio (g(b) − g(a))/(ba) decreases with b > a for every a. The same is therefore true of (g(d) − g(c))/(dc). We see from (D.3) that (g(d) − g(c))/(dc) has a lower bound (namely (g(b) − g(a))/(ba)). Therefore there exists
g + ( c ) = lim d c g ( d ) g ( d ) d c .
We see also from (D.3) that g+(a) ≤ g+(c) whenever a < c.