Re: What kind of math problem is this?
- To: mathgroup@smc.vnet.net
- Subject: [mg12209] Re: [mg12130] What kind of math problem is this?
- From: Daniel Lichtblau <danl@wolfram.com>
- Date: Fri, 1 May 1998 03:08:57 -0400
- References: <199804270546.BAA09492@smc.vnet.net.>
Seth Chandler wrote:
> [Edited slightly for readability. DL]
> I know this is a little off topic, but I am hoping there are enough
> mathematicians with tolerance on this list that I can get some help
> for a problem relevant to the game theoretic analysis of legal rules.
>
> Also, my apologies for the one-dimensional Mathematica notation here.
> Until newgroups better understands Mathematica notebooks or until
> MathML, this is the best I can do.
>
> Suppose I have two functions f[x,y] and g[x,y]. Both map two real
> numbers onto a real number. Suppose that f[x,y]+g[x,y] is uniquely
> maximized at some point { x*,y*}. What relationships and qualities
> must f and g have such that there exists a transfer function t[x,y] so
> that f[x,y]-t[x,y] is maximized with respect to x at x* for all values
> of y and so that g[x,y]+t[x,y] is maximized with respect to y at y*
> for all values of x.
>
> By way of example:
>
> Define functions f and g as follows:
>
> In[82]:= f[x_,y_]=y-(x-2)^2;
>
> In[83]:= g[x_,y_]=x-(y-3)^2;
>
> We can determine (somewhat sloppily) the maximum of these functions as
> follows:
>
> In[6]:= Solve[{D[f[x,y]+g[x,y],x]==0,
> D[f[x,y]+g[x,y],y]==0}, {x,y}] // InputForm
> Out[6]=//InputForm= {{x -> 5/2, y -> 7/2}}
>
> There exists a function t[x_,y_]=y-x such that my requirements are met
>
> In[84]:= t[x_,y_]=y-x;
>
> In[19]:= Solve[D[f[x,y]-t[x,y],x]==0,x] // InputForm
> Out[19]=//InputForm= {{x -> 5/2}}
>
> In[20]:= Solve[D[g[x,y]+t[x,y],y]==0,y] // InputForm
> Out[20]=//InputForm= {{y -> 7/2}}
>
> On the other hand for f1 and g1 I don't believe a function t exists.
>
> In[85]:= f1[x_,y_]= x y - y ^2 -(x-2)^2;
>
> In[86]:= g1[x_,y_]=2 x y - x^2 - (y-3)^2;
>
> In[62]:= Solve[{D[f1[x,y]+g1[x,y],x]==0,D[f1[x,y]+g1[x,y],y]==0},
> {x,y}] // InputForm
> Out[62]=//InputForm= {{x -> 34/7, y -> 36/7}}
>
> Here is a function t1 that makes part of the requirements come true
>
> In[87]:= t1[x_,y_]=x y - 40 x /7;
>
> In[70]:= Solve[D[f1[x,y]-t1[x,y],x]==0,x] // InputForm
> Out[70]=//InputForm= {{x -> 34/7}}
>
> But not the other part. (the optimal y value ends up depending on x)
>
> In[68]:= Solve[D[g1[x,y]+t1[x,y],y]==0,y] // InputForm
> Out[68]=//InputForm= {{y -> (3*(2 + x))/2}}
>
> My problem is, I can't even figure out what kind of a problem this is.
> Could someone out there help? If they wanted to use Mathematica to
> illuminate the problem, that would be fabulous.
If we assume the functions f, g, and t all have power series
representations then we can find t as below. Actually this assumption
is stronger than what we need, and I will indicate how to weaken it
later. For notational ease we will assume the extreme point is the
origin. This may always be achieved by translation of coordinates. In
your examples, just replace x by new_x-2 and y by new_y-3 (but don't
use the underscores in Mathematica).
So we write (in notation that is not quite Mathematica but should be
comprehensible)
f = Sum[j,k>=0][a[j,k]*x^j*y^k]
g = Sum[j,k>=0][b[j,k]*x^j*y^k]
t = Sum[j,k>=0][c[j,k]*x^j*y^k]
where the a's, b's, and c's are coefficients. In your first example
(after translation to make the origin the extreme point) we have
y+3-x^2, hence a[0,0]=3, a[0,1]=1, a[2,0]=-1, and all other a's are
zero. Now we look at the conditions on t[x,y]. We must have
(i) D[t,x] == D[f,x] at points of the form {0,y} (ii) D[t,y] == -D[g,y]
at points of the form {x,0}
Differentiating term-wise and evaluating appropriately we get
Sum[k>=0][c[1,k]*y^k] == Sum[k>=0][a[1,k]*y^k] for all k
and similarly
Sum[k>=0][c[j,1]*y^k] == Sum[k>=0][-b[j,1]*y^k] for all j
Since the first holds for all values of x we may equate coefficients to
see that c[1,k] == a[1,k] for all k, and similarly c[j,1] == -a[j,1]
for all j. Other coefficients in t are arbitrary subject to having the
sum converge. In the first example the particular choice of t was
obtained by setting them all to zero.
It is important to notice that there is a compatibility condition on f
and g imposed by taking j=k=1:
a[1,1] == -b[1,1]
This is true for the first example (where both are zero) and false for
the second, when (even after translation) we have a[1,1]=1 and
b[1,1]=2. Hence no function t may be constructed to fit the
requirements (at least under the assumption that all functions are
real-analytic, that is, can be represented as power series).
Actually we can water down the assumptions and still get essentially the
same result. If we assume the functions are a few times differentiable
in each variable then we can represent them as Taylor polynomials
(truncations of power series) plus error terms that are smaller than
the polynomial terms as {x,y}->0 (that is, the ration goes to zero). In
assuming a few derivatives exist we are (i) assuming the functions are
"smooth" at the origin (that is, no cusps, let alone discontinuities)
and again (ii) we have again forced the bi-linear term compatibility
condition. I suspect the primary interest is in functions f and g that
can be explicitly represented as power series (or perhaps polynomials,
a stronger restriction) so this last paragraph may be overkill.
I think we can further extend to allow f and g to have cusps at the
extreme point (e.g. having something like 1-Sqrt[Abs[x*y]] for the sum
f+g) provided there is a smooth representation in a punctured
neighborhood of the origin (a neighborhood excluding the origin
itself). One again gets the same sort of conditions because of Taylor
polynomial identities satisfied in a punctured neighborhood of the line
segments through the origin.
If you make no assumption about t[x,y] beyond continuity, not much can
be done. Picture a non-smooth pair of "mountain ridges" for the surface
defined by t[x,y], such that along one axis they go up very fast (so as
to give f+t a max along that axis when approaching it from the
perpendicular direction), and falling off sharply to give a min along
the opposite axis. I think such t will always work if we only assume f
and g are continuous, hence there is no compatibility condition to be
obtained.
Daniel Lichtblau
Wolfram Research