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

David Ryzák, Tomáš Kroupa · 2026

Read A Tractable Class of Cooperative Games Defined by Directed Networks: Unanimity Decomposition and Shapley Value by David Ryzák, Tomáš Kroupa (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18157.txt.

Introduction

David Ryzák's 2026 paper defines a tractable class of cooperative games built from weighted directed networks. Each coalition value mixes an internal term from the induced subgraph with an external term from minimal incoming edges outside the coalition. The game admits a clean unanimity decomposition, which yields fast exact formulas for the Shapley and Banzhaf values, computable in polynomial time. The class also shows a nonempty core and total balance, giving a rare case where stability-based and fairness-based allocations part ways.

Catalog record

CREATORDavid Ryzák, Tomáš Kroupa
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31415
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18157

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Tractable Class of Cooperative Games Defined by Directed Networks: Unanimity Decomposition and Shapley Value David Ryzák, Tomáš Kroupa 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. Keywords: cooperative game theory; graph games; directed networks; Shapley value; core 1 Introduction We introduce a cooperative game induced by a weighted directed graph. The underlying network represents local evaluations between agents, which need not be symmetric. The coalitional worth combines two components: an internal term capturing interactions within coalition, and a non-additive external term determined by minimal incoming evaluations from outside the coalition. The internal component alone is, in fact, an induced subgraph game whose Shapley value coincides with symmetric weighted degree centrality. In contrast, the external component acts as a bottleneck operator and, taken in isolation, neglects inner-coalitional interactions. Their sum produces a game that reflects both internal interaction and external exposure. We analyze the resulting game through classical solution concepts. In particular, we derive explicit polynomial-time formulas for the Shapley and Banzhaf values, establish a unanimity decomposition of the game, and study properties including core characterization and total balancedness. To justify the construction, it is important to observe that neither component alone yields a sufficiently rich class of games. The internal term defines an induced subgraph game whose Möbius transform contains only pairwise contributions. In particular, no higher-order coalition effects arise and the associated Shapley value reduces to symmetric weighted degree centrality. The external component takes the worth of a coalition based on edges from players outside the coalition, thus capturing exposure to external assessments rather than internal cooperation. Considered alone, this term assigns value independently of interactions among coalition members. Its combination with the internal interaction term generates nontrivial marginal effects while preserving an unanimity decomposition. A key structural property of the game is that its Möbius transform can be expressed in simple terms. The external component induces a chain of unanimity games whose supports form an inclusion chain determined by the ordering of incoming neighbors. This chain structure allows a tractable computation of classical solution concepts, e.g., Shapley and Banzhaf values. Our main theoretical contributions are as follows. First, we derive the Möbius transform of the game and obtain polynomial-time formulas for the Shapley and Banzhaf values. Second, we characterize the marginal impact of individual local evaluations on these value operators as a function of a player’s position in the network. Finally, we establish the structural properties of the game, including a characterization of the core and total balancedness. In the following paragraph we briefly discuss related work. Related work Mathematically, our work is closely connected to studies on the complexity of cooperative games and games induced by a weighted graphs. The computational complexity of cooperative games is a crucial topic, since the cooperative game naturally has an exponential size in the number of players. Thus, a tractable computation of solution concepts is important. Chalkiadakis and Wooldridge in [ 7 ] comment on Shapley value being \sharp P in the context of weighted voting games, i.e., on a restricted class of games. The results of Deng and Papadmitriou in [ 8 ] shows that solution concepts such as the Shapley value can be computed in polynomial time in some cases, for instance, a weighted undirected graph. The work of Chalkiadakis, Elkind and Wooldridge [ 6 ] serves as a basic reference material on computational challenges in cooperative games, studying both computational complexity and the closely related topic of succinct game representation. Another succinct representations of cooperative games except of graph induced games are also MC-nets studied already by Ieong and Shoham [ 10 ] . The graph based games are studied generally from several perspectives and we aim to comment on few of them. One of the first works of graphs studied via cooperative games is work [ 11 ] with Myerson value as a flagship solution concept. Survey of Borm et al. [ 3 ] studied several types of cooperative games induced by graphs in areas of operations research. Since our solution concepts are based on local graph relationships the topic is loosely connected to the degree centrality measures. The survey of Tarkowski et al. [ 13 ] summarize degree centrality approaches. More recently, Rusinowska and Van den Brink [ 4 , 5 ] study degree centrality from an axiomatic perspective in the context of graphs and digraphs. The remainder of the paper is organized as follows. We briefly discuss related work in the following paragraph. In Section 2 , we introduce the trust game, establish its basic properties and derive the unanimity decomposition. In Sections 3 and 4 we provide closed-form expressions for the Shapley and Banzhaf values and interpretation of their marginal effects in terms of the underlying weigthed graph and its local structure. Section 5 investigates stability properties of the game, showing that the core is a singleton and establishing that the game is totally balanced. Finally, Section 6 concludes. 2 Trust Game We start with the definition of the game which we also call trust game as in Bandhana et al. [ 1 ] Definition 2.1 (Trust Game) . Let G=(N,E) be a weighted directed graph, where each edge (i,j)\in E is assigned a weight a_{ij}\in[0,1] . Let (N,v) be a trust game given by v(S)=\underbrace{\sum_{\begin{subarray}{c}i\in S,j\in S\\ (i,j)\in E\end{subarray}}a_{ij}}_{\text{internal}}+\underbrace{\sum_{i\in S^{*}}\min_{j\notin S:(j,i)\in E}a_{ji}}_{\text{external}},\ \text{for each}\ S\subseteq N where S^{*}=\{i\in S: there exists j\notin S such that (j,i)\in E\} . Bandhana et al. [ 1 ] established some elementary properties of this game. • Trust game is superadditive , i.e. for all disjoint coalitions S,T\subseteq N , v(S\cup T)\;\geq\;v(S)+v(T). • Trust game is monotone , i.e. for all coalitions S,T\subseteq N with S\subseteq T , v(S)\;\leq\;v(T). • There exists at least one allocation in the core of the trust game. Next, we introduce the notation for the trust game, which we will use repeatedly in what follows. For every player i\in N , we denote by \displaystyle N^{-}(i)=\{\,i_{1},i_{2},\dots,i_{m_{i}}\,\} the set of players that have an incoming edges to i (the in-neighbours of i ) and we have indexed them in nondecreasing order, i.e., a_{i_{1}i}\leq a_{i_{2}i}\leq\ldots\leq a_{i_{m_{i}}i} . For the notational convenience and to stress the ranking among in-neigbours we use the following notation b_{i}(t):=a_{i_{t}i} , thus \displaystyle b_{i}(1)\leq b_{i}(2)\leq\dots\leq b_{i}(m_{i}). We set b_{i}(0):=0 for convenience. Let us now make more precise definition of the external game with respect to possibility of no in-neighbors for a given player i in coalition S . Definition 2.2 (External game of the player i ) . We denote by w_{i}(S) the external game of player i which is defined as follows: \displaystyle w_{i}(S):=\min_{j\notin S:(j,i)\in E}a_{ji}=\begin{cases}\displaystyle\min_{i_{t}\notin S}b_{i}(t),&\text{if }i\in S,\\[6.0pt]

Read the complete text