Topkis question

I have a question about Topkis. In order to apply Topkis, do we have to have maximizaton problem or minimization is fine, too?

Our statement of Topkis has been for maximization of a supermodular function. You can write other (more general) forms that involve minimization and/or submodularity/decreasing differences. However, I always find it easiest to just work with the basic statement of the theorem, and map your problem into “Topkis form.”

Let’s say, my original problem is Min f(x,t) wrt x and i want to figure out whether my optimizer is increasing in x or not. Can I directly find the answer by just saying f function is supermodular in (x,t) ?

Moreover is it true that if I have increasing differences in (x,t) for minimization problem, I would have increasing differences in (-x,t) for corresponding maximization problem?

Whether or not that works depends on whether x and t are single or multidimensional. To apply Topkis, you need the objective function of a maximization problem (here, for example, g(x,t) = -f(x,t) ) to be supermodular in its arguments.

Suppose x and t are single-dimensional. If f is supermodular in (x,t) as you stated, then g is supermodular in (x, -t). So by Topkis, x*(t) is nonincreasing in t.

Now suppose that x or t are multidimensional. If f is supermodular in (x,t), that means it has ID in (x_i, x_j), (t_k, t_l), and (x_i, t_k) for all i ~= j and k ~= l. You cannot generally get supermodularity of g in anything.

In general, applying Topkis to a minimization problem requires that the objective function be submodular. If it’s supermodular, you’re in luck as long as its a function of only two variables.


There are no comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: