Frankl–Wilson Dividend Games: Compact Support and Tractable Shapley, Core, and Least-Core Computation

Cooperative games with transferable utility are a standard framework for modeling collaboration, fair division, cost sharing, and coalition formation. Computing central solution concepts such as the Shapley value, the core, the least core, and the nucleolus is often computationally difficult because a general game contains exponentially many coalitions. Recent work on extremal dividend structures, such as sunflower-dividend games, shows that restricting the Harsanyi dividend support to a structured set family can restore substantial algorithmic tractability. This paper introduces Frankl–Wilson dividend games, also called L-intersecting dividend games, a class of cooperative games in which the nonzero non-singleton Harsanyi dividends are supported on a structured intersection family. We distinguish two precise cases. In the uniform ordinary case, the dividend support is an r-uniform L-intersecting family: every two distinct dividend coalitions have an intersection size belonging to a fixed set L. In the modular Frankl–Wilson case, the dividend support satisfies prescribed intersection congruences modulo a prime p, together with the admissibility condition that coalition sizes avoid the allowed intersection residues modulo p. The algorithmic tools used in this paper are classical: the Shapley value is computed from Harsanyi dividends, and coalition-excess separation for non-negative dividends is performed via the standard maximum-weight closure construction. The paper does not propose a new Shapley algorithm, a new maximum-flow algorithm, or a new linear-programming method. Its main contribution is structural: it identifies Frankl–Wilson admissible dividend supports as a cooperative-game condition under which these classical procedures receive a polynomially compact input and therefore become polynomial-time algorithms in the number of players when the intersection complexity is fixed. We prove several results. First, for a modular Frankl–Wilson dividend game with residue set Aand s=∣A∣, the non-singleton dividend support has size at most Σsi=0 (ni), which is polynomial in n for fixed s. In the uniform ordinary case with ∣L∣ =s, the support size is at most (ns). Second, when the dividend support is explicitly given, the Shapley value is computable in time polynomial in n, the support size, and the input bit length. Third, for non-negative dividends, core and least-core separation can be performed through a maximum-weight closure construction whose graph size is polynomial in the dividend support. Hence, for fixed intersection complexity s, the least core is polynomial-time computable under explicit support. Fourth, we state a conditional nucleolus result. If the fixed constraints in the lexicographic scheme have a polynomial-size explicit representation and a polynomial-time constrained K-best closure oracle is available, then the nucleolus is polynomial-time computable. Without these additional assumptions, nucleolus computation for general Frankl–Wilson dividend games remains open. Fifth, if a game’s Harsanyi dividends can be approximated in dividend mass by an L-intersecting or Frankl–Wilson-admissible subfamily, then its Shapley value can be approximated with additive error bounded by the omitted dividend mass. We also show that total dividend approximation error gives explicit approximate least-core and approximate-core stability bounds. Frankl–Wilson dividend games are closely related to several extremal dividend structures. Sunflower active coalitions with common kernel size κform a κ-intersecting family; when the active coalitions are uniform, they fit the Type I case, and under additional modular admissibility conditions they may also fit Type II. Pairwise disjoint dividend coalitions correspond to L=0. Finite-geometric designs, block designs, and modular intersection families provide natural examples. The paper therefore extends the research program of using extremal set theory to create cooperative-game classes with exact or certified approximate tractability.