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
More intriguing information
1. TOMOGRAPHIC IMAGE RECONSTRUCTION OF FAN-BEAM PROJECTIONS WITH EQUIDISTANT DETECTORS USING PARTIALLY CONNECTED NEURAL NETWORKS2. Tobacco and Alcohol: Complements or Substitutes? - A Statistical Guinea Pig Approach
3. Integration, Regional Specialization and Growth Differentials in EU Acceding Countries: Evidence from Hungary
4. The Economics of Uncovered Interest Parity Condition for Emerging Markets: A Survey
5. The value-added of primary schools: what is it really measuring?
6. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.
7. Conflict and Uncertainty: A Dynamic Approach
8. The name is absent
9. Auctions in an outcome-based payment scheme to reward ecological services in agriculture – Conception, implementation and results
10. Personal Income Tax Elasticity in Turkey: 1975-2005