What does Supermodular Chaining of Stock Assets conclude, in numbers, about “The Best Chaining Set: Choosing Under Caps on Working Hours and Contact Frequency”?
Answer: Chapter 4 selects the best chaining set under caps on hours and contact: on supermodular problems the greedy method's worst case reaches only 0.2188 of the optimum, pair-aware selection lifts it to 0.5358, and any sensitivity to contact makes the best number of chains finite.
Scope of the numbers: In the illustrative model, twelve of the fifteen pairs of six assets are complements and three are substitutes, and with all six switched on the monthly value is 23,104 against a stand-alone sum of 13,668. Parameters are illustrative and correspond to no real business, customer, creator or sale; all calculations are generated by the book's programs.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.2188, 0.5358
| bound 1 - 1/e = 0.6321 | |||
| (a) coverage, submodular | |||
| method | worst ratio | mean ratio | share optimal |
| greedy | 0.9241 | 0.9937 | 0.750 |
| greedy+swap | 0.9378 | 0.9981 | 0.895 |
| pair-aware | 0.9241 | 0.9937 | 0.750 |
| (b) paired bonus, supermodular | |||
| method | worst ratio | mean ratio | share optimal |
| greedy | 0.2188 | 0.5195 | 0.000 |
| greedy+swap | 0.2188 | 0.8555 | 0.595 |
| pair-aware | 0.5358 | 0.9744 | 0.780 |
Show the full program
# Chapter 4. p42: greedy works for substitutes, can fail for complements.
# Pick k = 4 of 12 assets. Two families of random instances (seeded):
# (a) submodular: weighted coverage of 40 audience segments; each asset
# covers each segment with probability 0.15. Greedy is guaranteed at
# least 1 - 1/e of the optimum (Nemhauser, Wolsey and Fisher 1978).
# (b) supermodular: small stand-alone values a_i in [0, 1], plus a bonus
# b in [4, 8] for each of 5 random pairs that only pays when both
# members are chosen; 2 decoy assets with stand-alone value 2.5.
# Methods: plain greedy, greedy then single swaps, pair-aware greedy
# (also scores adding two assets at once). Ratios are to the exhaustive
# optimum over all C(12, 4) = 495 sets.
import itertools
import math
import random
K, NI = 4, 12
def greedy(f, k):
s = []
while len(s) < k:
s.append(max((x for x in range(NI) if x not in s),
key=lambda x: (f(s + [x]), -x)))
return s
def swaps(f, s):
s = list(s)
better = True
while better:
better = False
for i in range(len(s)):
for x in range(NI):
if x in s:
continue
t = s[:i] + [x] + s[i + 1:]
if f(t) > f(s) + 1e-12:
s, better = t, True
return s
def pair_greedy(f, k):
s = []
while len(s) < k:
opts = [[x] for x in range(NI) if x not in s]
if k - len(s) >= 2:
opts += [[x, y] for x, y in itertools.combinations(range(NI), 2)
if x not in s and y not in s]
s += max(opts, key=lambda o: ((f(s + o) - f(s)) / len(o), -o[0]))
return s
def run(make, rng, reps=200):
rows = {"greedy": [], "greedy+swap": [], "pair-aware": []}
for _ in range(reps):
f = make(rng)
opt = max(f(list(c)) for c in itertools.combinations(range(NI), K))
g = greedy(f, K)
for name, s in (("greedy", g), ("greedy+swap", swaps(f, g)),
("pair-aware", pair_greedy(f, K))):
rows[name].append(f(s) / opt)
return rows
def coverage(rng):
w = [rng.uniform(0.5, 1.5) for _ in range(40)]
cov = [[j for j in range(40) if rng.random() < 0.15] for _ in range(NI)]
def f(s):
hit = set()
for x in s:
hit.update(cov[x])
return math.fsum(w[j] for j in sorted(hit))
return f
def pairs(rng):
a = [rng.uniform(0.0, 1.0) for _ in range(NI)]
a[10] = a[11] = 2.5
allp = list(itertools.combinations(range(10), 2))
bonus = {p: rng.uniform(4.0, 8.0) for p in rng.sample(allp, 5)}
def f(s):
ss = set(s)
terms = [a[x] for x in s]
terms += [b for (x, y), b in sorted(bonus.items())
if x in ss and y in ss]
return math.fsum(terms)
return f
if __name__ == "__main__":
print("bound 1 - 1/e = {:.4f}".format(1 - 1 / math.e))
for title, make, rng in (("(a) coverage, submodular", coverage,
random.Random(37504)),
("(b) paired bonus, supermodular", pairs,
random.Random(37505))):
rows = run(make, rng)
print(title)
print(" method worst ratio mean ratio share optimal")
for name in ("greedy", "greedy+swap", "pair-aware"):
r = rows[name]
hit = len([x for x in r if x > 1 - 1e-9])
print(" {:<12} {:>12.4f} {:>11.4f} {:>14.3f}".format(
name, min(r), math.fsum(r) / len(r), hit / len(r)))Single source and citation
Fan, Y. (2026). Supermodular Weapon-Arsenals, Adjacent-Possible Recombination Graphs and Cross-Asset Cashflow Chaining (Version 1.0.0), Chapter 4: The Best Chaining Set: Choosing Under Caps on Working Hours and Contact Frequency. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-375 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026375,
author = {Fan, Yafu},
title = {Supermodular Weapon-Arsenals, Adjacent-Possible Recombination Graphs and Cross-Asset Cashflow Chaining},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Matrix of Pairwise Gains: Cross-Differences Separate Complements, Independents and Substitutes
- Chapter 2 · Supermodular Functions on a Lattice: Topkis's Monotone Comparative Statics and the Single-Practice Pilot Trap
- Chapter 3 · A Graph of the Adjacent Possible: One-Step Combinations and the Trade-off of Unfamiliarity
- Chapter 5 · Chaining Cash Flow: the Bottleneck of a Cross-Asset Funnel, Quantiles for the Doubling Slogan and Single-Level Commission
- Chapter 6 · Testing Complementarity: the 2×2 Factorial Test, Standard Errors and Sample Size
- Chapter 7 · Classical Sources: Regular and Unusual Forces in the Sunzi, Aristotle on Wholes and Adam Smith on the Extent of the Market
- Chapter 8 · Field Tools and Checker Specifications: the Monthly Chaining Ledger, a Pre-Registered Test and Refutation Conditions