Figure 6: Partition of the square whose vertices coincide with the diagonal.
We can repeat this argument k times until getting a rectangle whose length is
not bigger than α. Once again we apply assumption A1 and Lemma 8.1 to show
that submodularity holds for this rectangle as well and we can conclude that,
F(x, z) - F(z, z) ≥ F (x, x) - F (x, z) .
Hence submodularity is satisfied for any square with vertices coinciding with
the diagonal. ■
The following Lemma establishes that the analysis of submodularity of any
rectangle formed by four points of the domain [0, c]2 can be reduced to the
analysis of submodularity for points placed in such a way that they form a
square with vertices coinciding with the diagonal.
Lemma 8.3 If A1 and A2 hold, then F and G are submodular on [0, c]2 .
Proof. (Lemma 8.3) Due to the kink along the diagonal, one cannot invoke
Topkis’s simple cross-partial test (Topkis’s Characterization Theorem in the
Appendix) to verify submodularity of F and G. Instead, we use definition of
submodularity for any configuration of four points in the domain, constituting
a rectangle. If the rectangle is completely contained in either ∆U or ∆L ,the
submodularity condition follows from A1. Every other situation can be reduced
by adding subrectangles, each of which lying fully in either ∆U or ∆L ,tothe
36