pith. sign in

arxiv: 2605.18157 · v1 · pith:GZT2Q5OFnew · submitted 2026-05-18 · 💻 cs.GT · econ.TH

A Tractable Class of Cooperative Games Defined by Directed Networks: Unanimity Decomposition and Shapley Value

David Ryz\'ak , Tom\'a\v{s} Kroupa This is my paper

Pith reviewed 2026-05-19 23:51 UTC · model grok-4.3

classification 💻 cs.GT econ.TH
keywords cooperative gamesdirected networksunanimity gamesShapley valueBanzhaf valuecoretotal balancednessnetwork games
0
0 comments X

The pith

Directed network games decompose into unanimity games, giving closed-form Shapley values and a nonempty core.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines cooperative games on weighted directed graphs by combining the value of the induced subgraph inside any coalition with an external term based on the minimal incoming edges reaching that coalition from outside. This specific definition produces a game that can be expressed exactly as a linear combination of unanimity games. The unanimity representation immediately supplies explicit, polynomial-time formulas for both the Shapley value and the Banzhaf value. The same structure also proves that every game in the class has a nonempty core and remains totally balanced on every subset of players.

Core claim

The coalitional value, formed by an internal interaction term given by the induced subgraph game plus an external component based on minimal incoming edges from outside the coalition, admits a convenient representation in terms of unanimity games. This representation yields closed-form polynomial-time formulas for the Shapley and Banzhaf values. The resulting games are further shown to have a nonempty core and to be totally balanced.

What carries the argument

The coalitional value that adds an internal subgraph interaction term to an external term based on the minimal number of incoming edges from outside the coalition.

Load-bearing premise

The coalitional value must combine the internal induced-subgraph term with an external term drawn from minimal incoming edges.

What would settle it

A concrete weighted directed graph on which the Shapley value computed by the unanimity formula differs from the value obtained by direct definition, or on which the core is empty.

Figures

Figures reproduced from arXiv: 2605.18157 by David Ryz\'ak, Tom\'a\v{s} Kroupa.

Figure 1
Figure 1. Figure 1: Graph example for marginal effects. aij ϕi 0 1 ak1j = 0.2 ak2j = 0.5 ak3j = 0.8 P0 P1 P2 P3 P4 P5 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Marginal effects on the Shapley value for player [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Marginal effects on the Shapley value for player [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Marginal effects on the Shapley value for player [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
read the original abstract

We introduce a class of cooperative games induced by weighted directed graphs. Specifically, the coalitional value combines an internal interaction term given by the induced subgraph game with an external component based on minimal incoming edges from outside the coalition. The resulting game has a convenient representation in terms of unanimity games. This representation enables closed-form polynomial-time formulas for the Shapley and Banzhaf values. We further establish that the game has a nonempty core and is totally balanced. The class of such games therefore provides an analytically and computationally tractable example of structured network- induced cooperative games in which stability-based allocations and fairness-based solution concepts do not coincide.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper defines a class of cooperative games on weighted directed graphs where the coalitional value v(S) is the sum of an internal term given by the induced subgraph game on S and an external term based on the minimal incoming edge weights from V∖S. It establishes a representation of v as a linear combination of unanimity games, derives closed-form polynomial-time expressions for the Shapley and Banzhaf values, and proves that the core is nonempty and the game is totally balanced. The class is positioned as a tractable example of network-induced games in which core allocations and the Shapley value generally differ.

Significance. If the central claims hold, the work supplies an analytically and computationally tractable family of structured cooperative games with explicit unanimity decompositions, efficient solution-concept formulas, and a separation between stability and fairness concepts. The decomposition and closed-form results, if verified, constitute a concrete advance for network games.

major comments (1)
  1. [§3.2] §3.2, Definition 2 and the subsequent unanimity decomposition: the external term relies on a minimization over incoming edge weights. The manuscript asserts that the resulting v admits an exact finite linear combination of unanimity games, but the explicit construction that converts the min operation into such a combination (without introducing extra parameters or restricting the weight domain) is not fully detailed in the provided derivation steps. This step is load-bearing for both the closed-form Shapley/Banzhaf claims and the total-balancedness proof.
minor comments (2)
  1. [§2] Notation for the external component (e.g., the precise definition of the minimal incoming weight function) should be introduced with an equation number and used consistently in later sections.
  2. [§4] The running example in §4 would benefit from an explicit table listing v(S) for all coalitions together with the corresponding unanimity coefficients to allow direct verification of the decomposition.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive evaluation of its significance. The single major comment identifies a point where the derivation of the unanimity decomposition can be strengthened for clarity. We address it below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3.2] §3.2, Definition 2 and the subsequent unanimity decomposition: the external term relies on a minimization over incoming edge weights. The manuscript asserts that the resulting v admits an exact finite linear combination of unanimity games, but the explicit construction that converts the min operation into such a combination (without introducing extra parameters or restricting the weight domain) is not fully detailed in the provided derivation steps. This step is load-bearing for both the closed-form Shapley/Banzhaf claims and the total-balancedness proof.

    Authors: We appreciate the referee’s identification of this load-bearing step. The external term is defined via the minimum incoming edge weight from V∖S. Our construction proceeds by sorting the distinct positive edge weights incident to each vertex and expressing the min operator as a telescoping difference of threshold indicators; each such indicator corresponds to a unanimity game on the set of coalitions that include the relevant vertex and at least one incoming neighbor above the threshold. This yields an exact finite linear combination whose coefficients are determined solely by the ordered weights and the graph structure, without auxiliary parameters or restrictions on the weight domain. While the manuscript sketches this argument, we agree that the intermediate algebraic steps converting the min into the explicit coefficients are compressed. In the revision we will expand §3.2 with a self-contained lemma that states the precise coefficients for both the internal and external components, followed by a short verification that the representation is exact for arbitrary positive weights. The expanded derivation will be used directly in the proofs of the closed-form Shapley and Banzhaf values and of total balancedness, thereby addressing the referee’s concern. revision: yes

Circularity Check

0 steps flagged

Derivation proceeds from explicit new definition without reduction to inputs

full rationale

The paper introduces an explicit definition of the coalitional value v(S) as the sum of an internal induced-subgraph term and an external term based on minimal incoming edges from V/S. From this definition it derives an explicit linear combination of unanimity games, closed-form Shapley/Banzhaf formulas, and total balancedness. Every cooperative game admits a unanimity decomposition by the standard Möbius inversion formula; the paper simply computes the coefficients for this particular structured class. No step reduces a claimed result to a fitted parameter, self-citation, or definitional tautology. The construction is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the authors' chosen definition of the coalitional value function and on standard background facts from cooperative game theory and graph theory.

axioms (1)
  • standard math Standard definitions and properties of cooperative games, induced subgraphs, and minimal incoming edges hold.
    Invoked implicitly when defining the game value and when claiming the unanimity representation and core properties.

pith-pipeline@v0.9.0 · 5641 in / 1208 out tokens · 38040 ms · 2026-05-19T23:51:07.708986+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    Trust in Shapley: A Cooperative Quest for Global Trust in P2P Network

    Arti Bandhana, Tomáš Kroupa, and Sebastián García. Trust in Shapley: A Cooperative Quest for Global Trust in P2P Network. InProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’24, pages 132–140, Richland, SC, May

    work page

  2. [2]

    International Foundation for Autonomous Agents and Multiagent Systems

    work page

  3. [3]

    Bondareva

    Olga N. Bondareva. Some applications of linear programming methods to the theory of cooperative games.Problemy Kybernetiki, 10:119–139, 1963. 13

    work page 1963

  4. [4]

    Operations research games: A survey.TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 9:139–199, February 2001

    Peter Borm, Herbert Hamers, and Ruud Hendrickx. Operations research games: A survey.TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 9:139–199, February 2001

    work page 2001

  5. [5]

    The degree measure as utility function over positions in graphs and digraphs.European Journal of Operational Research, 299(3):1033–1044, 2022

    René van den Brink and Agnieszka Rusinowska. The degree measure as utility function over positions in graphs and digraphs.European Journal of Operational Research, 299(3):1033–1044, 2022

    work page 2022

  6. [6]

    Degree centrality, von Neumann–Morgenstern expected utility and externalities in networks.European Journal of Operational Research, 319(2):669–677, 2024

    René van den Brink and Agnieszka Rusinowska. Degree centrality, von Neumann–Morgenstern expected utility and externalities in networks.European Journal of Operational Research, 319(2):669–677, 2024

    work page 2024

  7. [7]

    Computational Aspects of Cooperative Game Theory

    Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational Aspects of Cooperative Game Theory. InSynthesis Lectures on Artificial Intelligence and Machine Learning, volume 5. October 2011

    work page 2011

  8. [8]

    Weighted Voting Games

    Georgios Chalkiadakis and Michael Wooldridge. Weighted Voting Games. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D.Editors Procaccia, editors,Handbook of Computational Social Choice, pages 377–396. Cambridge University Press, 2016

    work page 2016

  9. [9]

    Papadimitriou

    Xiaotie Deng and Christos H. Papadimitriou. On the Complexity of Cooperative Solution Concepts.Mathematics of Operations Research, 19(2):257–266, May 1994

    work page 1994

  10. [10]

    Cambridge University Press, 127 edition, 2009

    Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap.Aggregation functions. Cambridge University Press, 127 edition, 2009

    work page 2009

  11. [11]

    Marginal contribution nets: a compact representation scheme for coalitional games

    Samuel Ieong and Yoav Shoham. Marginal contribution nets: a compact representation scheme for coalitional games. InProceedings of the 6th ACM conference on Electronic commerce, pages 193–202, Vancouver BC Canada, June 2005. ACM

    work page 2005

  12. [12]

    Roger B. Myerson. Graphs and Cooperation in Games.Mathematics of Operations Research, 2(3):225–229, 1977. _eprint: https://doi.org/10.1287/moor.2.3.225

    work page doi:10.1287/moor.2.3.225 1977

  13. [13]

    Lloyd S. Shapley. On balanced sets and cores.Naval Research Logistics Quarterly, 14(4):453–460, 1967

    work page 1967

  14. [14]

    Game-theoretic Network Centrality: A Review

    Mateusz K. Tarkowski, Tomasz P. Michalak, Talal Rahwan, and Michael Wooldridge. Game- theoretic Network Centrality: A Review, 2017. _eprint: 1801.00218. 14

    work page internal anchor Pith review Pith/arXiv arXiv 2017