Yonsei University
Chae-Yeon Xon
Yonsei University, School of Economics
Home/Resources/Geometry, Dynamics, and Operators for Economic Models/III-15
Sets, Optimization, and Sequential Information · Chapter III-15

Set Functions, Mobius Inversion, and Modularity

When outcomes depend on bundles of inputs or options, a set function records the value of every feasible subset. Mobius inversion isolates interaction terms and minimal enabling combinations. Modularity is a strong restriction: it makes reference-set increments portable across bundles, while monotonicity alone permits complements and substitutes.

Conceptual map

  1. III-15.01Boolean lattices
  2. III-15.02Minimal enabling sets
  3. III-15.03Mobius inversion
  4. III-15.04Representability
  5. III-15.05Modularity

1. Packages form a Boolean lattice

When an outcome depends on which inputs are jointly available, its domain is the set of subsets. Möbius coefficients separate singleton contributions, interactions, and higher-order overlap.

Let \(N=\{1,\ldots,n\}\) be a finite input set and \(W:2^{N}\to \mathbb{R}\) a set value. The Boolean lattice orders packages by inclusion. The marginal value of input \(i\) at reference package \(S\) is \(\Delta _{i}W(S)=W(S\cup {i})-W(S)\).

Definition 1 · Minimal enabling sets

For a monotone binary feasibility rule \(F\), a package \(A\) is minimally enabling when \(F(A)=1\) and \(F(B)=0\) for every strict subset \(B\subsetneq A\). The collection of minimal enabling sets is an antichain.

If feasibility requires either input 3 alone or the pair {1,2}, the minimal enabling antichain consists of {3} and {1,2}. Packages containing both paths create overlap that an additive input count does not record.

2. Möbius inversion

Define the Möbius coefficient of \(A\subseteq N\) by

\[m(A)=\sum _{B\subseteq A}(-1)^{|A\setminus B|}W(B).\](1)
Proposition 1 · Reconstruction

For every package \(S\),

\[W(S)=\sum _{A\subseteq S}m(A).\](2)

Proof. Substitute (1) into the right side of (2) and collect the coefficient on \(W(B)\). It equals \(\sum _{A: B\subseteq A\subseteq S}(-1)^{|A\setminus B|}=(1-1)^{|S\setminus B|}\). This coefficient is one for \(B=S\) and zero otherwise. ∎

3. A three-input value surface

Set \(W(\varnothing)=0\) and assign

\[W_{1}=2, W_{2}=1, W_{3}=\frac{3}{2}; \quad W_{12}=4, W_{13}=3, W_{23}=3, W_{123}=5.\](3)

The singleton Möbius coefficients are 2, 1, and 3/2. The pair coefficients are \(m_{12}=1\), \(m_{13}=-1/2\), and \(m_{23}=1/2\). The third-order coefficient is \(-1/2\). Summing all coefficients gives 5, which reconstructs \(W_{123}\).

Failure case · Monotonicity used as a sign restriction

Every inclusion in (3) weakly raises value, so \(W\) is monotone. Two Möbius coefficients are negative. Monotonicity restricts first differences; it does not force all interaction coefficients to be nonnegative.

4. Reference-independent marginal values

Proposition 2 · Equivalent forms of modularity

The following are equivalent: (i) \(\Delta _{i}W(S)\) is independent of \(S\); (ii) \(W(A)+W(B)=W(A\cup B)+W(A\cap B)\); (iii) every Möbius coefficient with \(\lvert A\rvert \ge2\) is zero; (iv)

\[W(S)=W(\varnothing )+\sum _{i\in S}[W(\{i\})-W(\varnothing )].\](4)

Proof sketch. Reference-independent increments telescope to (4). The representation implies the lattice equality in (ii). Applying (1) to (4) makes every coefficient of order at least two vanish. Finally, (2) with only constant and singleton coefficients gives (4). ∎

5. Implementation, exercises, and sources

Index subsets by bit masks, enumerate submasks to compute (1), and reconstruct every set value with (2). Report the largest reconstruction residual and group coefficients by order. For estimated set values, attach uncertainty to contrasts before assigning complementarity or substitutability labels.

Download the volume verification script →

Exercises

  1. Reproduce every coefficient in the three-input example and verify all eight reconstructions.
  2. Compute the Möbius coefficients of the binary enabling rule with minimal paths {3} and {1,2}.
  3. Prove the implication from the lattice identity in Proposition 2 to reference-independent marginal increments.
Partial solutions

1. Compute singletons first, then pair contrasts, then subtract every lower-order term from \(W_{123}\). Reconstruction follows by summing coefficients indexed by subsets of each package. 2. The enabling rule is \(F(S)=1\{3\in S\ \text{or}\ \{1,2\}\subseteq S\}\)}. Its nonzero coefficients are \(m_{3}=1\), \(m_{12}=1\), and \(m_{123}=-1\), where the final term removes double counting.

  1. Gian-Carlo Rota (1964), “On the Foundations of Combinatorial Theory I: Theory of Möbius Functions,” Zeitschrift für Wahrscheinlichkeitstheorie 2, 340–368.Incidence-algebra inversion.
  2. Donald M. Topkis, Supermodularity and Complementarity, Chapters 2–3.Lattice differences and economic complementarity.
  3. Lloyd S. Shapley (1953), “A Value for n-Person Games.”Allocation from set values.

6. Audit checkpoint

Declare the ground set, value normalization, minimal enabling antichain, full set table, transform convention, reconstruction residual, monotonicity contrasts, and modularity restrictions.

7. Scope boundary

The chapter covers finite Boolean lattices, enabling antichains, Möbius inversion, and modularity. Matroid theory and extremal combinatorics lie outside scope.

Prerequisites