Topkis's Theorem

Topkis’ Theorem for Set-Valued Decisions and Supermodular Functions

🌐 Introduction

Topkis’ theorem is one of the cornerstones of monotone comparative statics — it tells us that under certain “complementarity” conditions, optimal choices move monotonically with parameters.

⚙️ Setting

Let $X$ be a finite ground set. The decision variable is a subset $S \subseteq X$, and we consider the lattice $(2^X, \subseteq)$ with:

• Join operation: $S \vee T = S \cup T$
• Meet operation: $S \wedge T = S \cap T$

Let the parameter $t$ vary in a subset $T \subseteq \mathbb{R}$.

We study the optimization problem:

$$\max_{S \subseteq X} f(S, t)$$

where $f: 2^X \times T \to \mathbb{R}$ is our objective function.

🧩 Assumptions

1. Supermodularity in $S$

For each fixed $t$, $f(\cdot, t)$ is supermodular on $2^X$.
That is, for all $A, B \subseteq X$:

$$f(A, t) + f(B, t) \le f(A \cup B, t) + f(A \cap B, t).$$

Equivalently, this inequality can be rewritten as

$$f(B, t) - f(A \cap B, t) \le f(A \cup B, t) - f(A, t).$$

Let $\Delta = B \setminus (A \cap B) = (A \cup B) \setminus A$.
Since $C = A \cap B \subset A$, the inequality above can also be expressed as

$$f(C\cup \Delta, t) - f(C, t) \le f(A\cup \Delta, t) - f(A, t).$$

This reformulation highlights the complementarity among elements of the set $S$:
the incremental benefit of adding a common “increment” $\Delta$ is larger when it is added to a bigger base set. In other words, the marginal gain from adding elements increases as the set grows.

---

2. Increasing Differences between $S$ and $t$

For all $A \subseteq A' \subseteq X$ and $t\le t'$:

$$[f(A', t') - f(A', t)] \ge [f(A, t') - f(A, t)].$$

This condition means that the marginal gain with respect to the parameter is nondecreasing as the set grows. In other words, larger sets benefit more (or suffer less) from an increase in $t$.

We can express this idea in an equivalent, dual form — stating that the marginal gain with respect to the set is also nondecreasing as parameter increases:

$$[f(A', t') - f(A, t')] \ge [f(A', t) - f(A, t)].$$

Equivalently, $f$ is supermodular on the product lattice $2^X \times T$:

$$f(A', t) + f(A, t') \le f(A', t') + f(A, t),$$

or, using lattice notation,

$$f(A', t) + f(A, t') \le f\big((A', t) \vee (A, t')\big) + f\big((A', t) \wedge (A, t')\big).$$

This property captures complementarity between the decision variable $S$ and the parameter $t$— an increase in $t$ raises the attractiveness of choosing larger sets.

🧠 Theorem (Topkis’ Monotonicity Theorem – Set Version)

Let

$$\mathcal{M}(t) = \arg\max_{S \subseteq X} f(S, t)$$

be the set of optimal choices at parameter $t$.

Then for any $t \le t'$:

1. If $A \in \mathcal{M}(t)$ and $B \in \mathcal{M}(t')$, then

   $$A \cap B \in \mathcal{M}(t) \quad \text{and} \quad A \cup B \in \mathcal{M}(t').$$

2. Consequently, if we define the minimal and maximal optimal sets:

   $$\underline{M}(t) = \bigcap_{S \in \mathcal{M}(t)} S, \quad \overline{M}(t) = \bigcup_{S \in \mathcal{M}(t)} S,$$

   then both are monotone nondecreasing in $t$:

   $$\underline{M}(t) \subseteq \underline{M}(t'), \quad \overline{M}(t) \subseteq \overline{M}(t').$$

🧾 Proof Sketch

We’ll outline the standard Topkis argument, adapted for set-valued choices.

Step 1: A Key Inequality

Under supermodularity and increasing differences, we can show that for all $A, B \subseteq X$ and $t' \ge t$:

$$\tag{★} f(A, t) + f(B, t') \le f(A \cup B, t') + f(A \cap B, t).$$

Why?

• By increasing differences:

  $$f(B, t') - f(B, t) \le f(A \cup B, t') - f(A \cup B, t).$$

• Rearranging gives

  $$f(B, t') \le f(A \cup B, t') - f(A \cup B, t) + f(B, t).$$

• Adding $f(A, t)$ to both sides and using supermodularity of $f(\cdot, t)$:

  $$f(A, t) + f(B, t) \le f(A \cup B, t) + f(A \cap B, t),$$

  which yields (★).

Step 2: Apply Optimality

Let $A \in \mathcal{M}(t)$ and $B \in \mathcal{M}(t')$.
From (★):

$$f(A, t) + f(B, t') \le f(A \cup B, t') + f(A \cap B, t).$$

Because $A$ and $B$ are optimal:

$$f(A, t) \ge f(A \cap B, t), \quad f(B, t') \ge f(A \cup B, t').$$

Combining these with (★), we get equality:

$$f(A, t) = f(A \cap B, t), \quad f(B, t') = f(A \cup B, t').$$

Thus $A \cap B \in \mathcal{M}(t)$ and $A \cup B \in \mathcal{M}(t')$.

Step 3: Monotonicity of Extreme Optima (check)

Because the family $\mathcal{M}(t)$ is closed under intersections and unions, the smallest and largest elements exist:

$$\underline{M}(t) = \bigcap_{S \in \mathcal{M}(t)} S, \quad \overline{M}(t) = \bigcup_{S \in \mathcal{M}(t)} S.$$

Applying Step 2 to the pair $(\underline{M}(t), \overline{M}(t'))$ yields:

$$\underline{M}(t) \subseteq \underline{M}(t'), \quad \overline{M}(t) \subseteq \overline{M}(t').$$

Hence both extreme optimal sets increase monotonically with $t$.

💡 Intuition

Supermodularity expresses complementarity within the set $S$ — adding an element becomes more valuable when others are already present.

Increasing differences express complementarity between $S$ and the parameter $t$ — when $t$ rises (for example, a “market size” or “budget”), the incentive to choose a larger set increases.

Together, these ensure that optimal sets expand as $t$ increases — a clean monotonicity result without solving the optimization explicitly.

📚 Further Reading

• Topkis, D. M. (1978). Minimizing a submodular function on a lattice. Operations Research, 26(2):305–321.
• Topkis, D. M. (1998). Supermodularity and Complementarity. Princeton University Press.
• Milgrom, P., & Shannon, C. (1994). Monotone comparative statics. Econometrica, 62(1):157–180.