A Value for Games Defined on Graphs

Néstor Bravo

Departamento de Matemáticas, Universidad de Guanajuato, Guanajuato, Mexico.

DOI: 10.4236/am.2024.155020                

Abstract

Given a graph $g=\left(V,A\right)$, we define a space of subgraphs M with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal coalitions) that are of interest for the game. Additionally, a partition of the game is defined in terms of the gain of each block, and subsequently, a solution to the game is defined based on distributing to each player (node and edge) present in each block a payment proportional to their contribution to the coalition.

Keywords

Graph Theory, Values for Graphs, Cooperation Games, Potential Function

1. Introduction

Cooperative game theory and graph theory are closely related areas, as both study relationships among independent agents (players-nodes). There are many ways to approach game theory via graph theory. The goal of this article is to introduce a new idea about the concept of coalition defined on graphs.

In the 1950s, Shapley [1] introduced the well-known Shapley value, one of the most famous tools in the study of cooperative n-person games. Later, Myerson [2] used ideas from graph theory to provide a communication structure to the coalitions under study. Myerson’s idea is to define a restricted game that assigns to each coalition the sum of the payments achievable by the connected components of the coalition. Two players are related if and only if both want to collaborate in t game. Owen [3] studied ways to define payoff values for situations like the one described by Myerson.

In previous works, graphs were considered where players are the nodes of the graph. Later, the idea has been extended to games where edges also participate in the game. Alarcón et al. [4] extend Myerson’s ideas to these types of situations. Games defined on networks are a very active part of game theory research; Caulier [5] provides a good compilation of known results and applications.

With the vision proposed by Myerson-Alarcón, a game defined on the nodes of the graph is considered, and then it is extended to the graph itself. What we aim to do now is to directly define a game on the components of the graph. We want to define a function that takes cooperative sub-structures and assigns their gain. One of the first problems encountered when trying to define a game in this context is the number of subgraphs that need to be studied. A solution to this problem is, instead of working with all possible subgraphs, to work with irreducible blocks of subgraphs and with classes of these. We thus define a partition of our graph of interest and generate coalitions from unions of these blocks. This way, we obtain a significant reduction in the number of coalitions that need to be studied.

In Section 2 of the article, we detail the process of partitioning graphs into blocks. In Section 3, we develop the theory of games defined on graphs, obtain a quasi-linear decomposition of the game in terms of the blocks, and then define a Shapley-type value for games of this style. The last section is dedicated to an application example that illustrates the advantages of working through this method.

2. Graphs

2.1. Definitions

Suppose we have n independent players. A natural way to model the situation of interest is by using graphs. In this section, we will first present the elementary definitions of graph theory, establish the notation, and introduce the concept of graph partition and domains of unique decomposition.

Definition 2.1 (Graph) Given a set $N=\left\{1,\cdots ,n\right\}$ , a graph with nodes in $V\subseteq N$ is a pair $g=\left(V,A\right)$ , where A is a set containing pairs $\left\{i,j\right\}$ such that

$\left\{i,j\right\}\in A,i,j\in V,i\ne j\text{.}$

The nodes N can be interpreted as the set of players, and A as the connections along with their intermediaries. Given $V\subseteq N$ , we define $g^V=\left(V,A_V\right)$ , where

$A_V=\left\{\left\{i,j\right\}:i,j\in V,i\ne j\right\}\text{.}$

That is, $g^V$ is the graph where all nodes in V are connected. Furthermore, $g^N$ is the graph where all players decide to cooperate with each other. Now, we would like to consider the set of all possible graphs with nodes in the player set N.

Definition 2.2. Given a set of nodes N, we define

$G_N=\left\{g=\left(V,A\right):V\subseteq N,\left\{i,j\right\}\in A\Rightarrow i,j\in V,i\ne j\right\}\text{.}$

This is the set of all possible graphs that have nodes in N. Given a specific graph $g=\left(V,A\right)\in G_N$ , we define

$S_g=\left\{g^{\prime }=\left(V^{\prime },A^{\prime }\right):V^{\prime }\subseteq V,A^{\prime }\subseteq A\right\},$

where $S_g$ denotes the set of subgraphs contained in g. It is clear that $S_{g^N}=G_N$ , as $g^N$ is the complete graph, and every graph with nodes in N is contained in it.

Up to this point, we have defined the notion of a Cooperation Structure among the players. We will refer to each graph $g\in G_N$ as a coalition of players in N. We acknowledge that the intermediaries on the edges are also players; however, they act differently from the rest of the players. Their actions depend on the participation of players in N. In other words, the edge $\left\{i,j\right\}\in A$ can only participate in the game (and, therefore, in the gain) if players $i,j$ decide to collaborate.

Remark 2.1. In practice, attempting to work with all possible subgraphs of a given graph proves to be very complicated. For instance, the number of subgraphs in $G_N$ where $\left|N\right|=n$ is given by

$\left|G_N\right|=\underset{k=0}{\overset{n}{{\displaystyle \sum }}}\left(\begin{array}{l}n\hfill \\ k\hfill \end{array}\right)2^{\left(\begin{array}{l}k\hfill \\ 2\hfill \end{array}\right)}\text{.}$

On the other hand, many of these graphs may not provide relevant information for our purposes. One of the goals of this conceptualization is to construct graphs in a more efficient manner and to focus on graphs that are of interest.

2.2. Graph Decomposition

Given a fixed graph $g=\left(V,A\right)$ , determined by the cooperation structure, with $V=\left\{1,\cdots ,n\right\}$ and $A\subseteq \left\{\left\{i,j\right\}:i,j\in N\right\}$ . From now on, we will consider g as the maximal graph with respect to the cooperation arrangement among players. We have defined an operation between the subgraphs of g, the union, which allows us to give an algebraic structure to the space of graphs. Formally, let $S_g$ be the set of graphs of g, that is

$S_g=\left\{h:h\subseteq g\right\}\text{.}$

We define the union of graphs as

$\cup :S_g\times S_g\to S_g,$

where if $h_1=\left(V_1,A_1\right),h_2=\left(V_2,A_2\right)\in S_g$ , then

$h_1\cup h_2=\left(V_1\cup V_2,A_1\cup A_2\right)\text{.}$

We have that $\left(S_g,\cup \right)$ has the structure of an abelian semigroup (the union is associative and commutative). Furthermore, if we consider the empty subgraph $\varnothing$ , then $\left(S_g,\cup \right)$ is a monoid.

Under what conditions is it possible that, given a certain subset of subgraphs $\mathcal{B}=\left\{h_1,\cdots ,h_k\right\}$ , we can uniquely decompose every graph $l\in M\subseteq S_g$ in terms of the elements of $\mathcal{B}$ ?

The above is, given a subset $M\subseteq S_g$ that is closed under unions, we would like to obtain a subset of subgraphs $\mathcal{B}$ such that for every $l\in M$ , there exists a unique subset $S\subseteq \mathcal{B}$ such that

$l={\displaystyle \underset{h\in S}{\cup }h}\text{.}$

The above construction allows us to have a notion of decomposition of our graphs of interest in terms of certain minimal irreducible elements. In this context, we will think of $\mathcal{B}$ as the minimal coalitions of players that interest us and M as the coalitions of interest (we will call them measurable coalitions).

Definition 2.3 (Generating Sets) Let $M\subseteq S_g$ be a subset of measurable graphs. We will say that $\mathcal{B}$ generates M if for every $l\in M$ , there exists a subset $S\subseteq \mathcal{B}$ such that

$l={\displaystyle \underset{h\in S}{\cup }h}\text{.}$

We will say that $\mathcal{B}$ generates M uniquely if for every $l\in M$ , the subset $S\subseteq \mathcal{B}$ that generates l is unique. We call the elements of S the decomposition of l. We call the pair $\left(M,\mathcal{B}\right)$ domain of unique decomposition. Given $\mathcal{B}=\left\{h_1,\cdots ,h_k\right\}$ set of graphs, we define the set generated by $\mathcal{B}$ as

$\mathcal{B}=\left\{{\displaystyle \underset{h\in S}{\cup }h}:S\subseteq \mathcal{B}\right\}\text{.}$

Example 2.1 (Edge Domain) Let $M_0\subseteq S_g$ be the subset of graphs without isolated vertices (a vertex is isolated if there is no edge connecting it to another vertex). Let $\mathcal{A}$ be the set of edges in g, that is,

$\mathcal{A}=\left\{a\subseteq g:a=\left(\left\{i,j\right\},\left\{\left\{i,j\right\}\right\}\right)\right\}\text{.}$

The elements of $\mathcal{A}$ are subgraphs that contain only two nodes and the edge that connects them. We have that every element $l\in M$ can be written as the union of the edges that compose it, i.e.,

$l={\displaystyle \underset{a\subseteq l}{\cup }a}\text{.}$

The decomposition is unique because if $S,S^{\prime }\subseteq \mathcal{A}$ are two distinct decompositions of l, without loss of generality, if $a\in S$ but $a\notin S^{\prime }$ , then

$l={\displaystyle \underset{a\in S}{\cup }a}\ne {\displaystyle \underset{a\in S^{\prime }}{\cup }a}=l\text{.}$

Then $\left(M_0,\mathcal{A}\right)$ is a domain of unique decomposition.

The purpose of the above construction is to provide a broader view of the concept of a game. We want to restrict our games to sets of coalitions that are of interest (measurable), which form a subset M. Moreover, this allows us to discuss on the existence of minimal coalitions that decompose our measurable coalitions and do so uniquely.

Remark 2.2. If $\left(M,\mathcal{B}\right)$ is a domain of unique decomposition, then M corresponds bijectively to $2^{\mathcal{B}}$ , where the element $\mathcal{A}\in 2^{\mathcal{B}}$ is associated with $l={\displaystyle {\cup }_{b\in \mathcal{A}}b}$ . In this way, we can work with subsets of subgraphs instead of considering all subgraphs as such (there are a total of $2^{\left|\mathcal{B}\right|}$ ). This represents a computational advantage regarding the number of subgraphs presented in remark 2.1.

3. Games Defined on Graphs

3.1. Game Defined on a Unique Decomposition Domain

Formally, given a domain of unique decomposition $\left(M,\mathcal{B}\right)$ , an $\left(M,\mathcal{B}\right)$ -characteristic function game will be any function

$v:M\to ℝ,$

where $v\left(l\right)$ is interpreted as the gain obtained by the subgraph $l\in M$ .

Example 3.1 (Unanimity Games) An elementary example is what we will henceforth refer to as unanimity functions (or games). Let $l\in M$ , and define the unanimity game as

$u_l\left(h\right)=\{\begin{array}{ll}1\hfill & \text{if}l\subseteq h,\hfill \\ 0\hfill & \text{otherwise}\text{.}\hfill \end{array}$

Let ${\mathcal{J}}^{M,\mathcal{B}}$ be the set of $\left(M,\mathcal{B}\right)$ -characteristic function games. We have that ${\mathcal{J}}^{M,\mathcal{B}}$ is an $ℝ$ -vector space with pointwise addition and scalar multiplication of functions. Moreover, ${\dim }_{ℝ}{\mathcal{J}}^{M,\mathcal{B}}=\left|M\right|$ . It can also be shown that the set of unanimity games $\left\{u_h:h\in M\right\}$ forms a basis for ${\mathcal{J}}^{M,\mathcal{B}}$ . Thus, every game $v\in {\mathcal{J}}^{M,\mathcal{B}}$ can be uniquely expressed as

$v\equiv {\displaystyle \underset{h\in M}{\sum }{\alpha }_h{u}_h},$

for certain coefficients ${\alpha }_h\in ℝ$ with $h\in M$ . We then have the relationship

$v\left(l\right)={\displaystyle \underset{h\subseteq l}{\sum }{\alpha }_h}\text{.}$

We can think of the scalars $\left\{{\alpha }_h\right\}$ as the contribution of h to the gain of a certain graph l. This shows that the gain of l is the sum of the contributions of all sub-coalitions that compose it.

As each element $l\in M$ is uniquely decomposed in terms of the elements $\mathcal{B}$ , it is reasonable to think that the gain must be distributed in some way among the components of l. In other words, there must be a partition $\left\{{\Gamma }_b\left(l\right):b\in \mathcal{B},b\subseteq l\right\}$ such that

$v\left(l\right)={\displaystyle \underset{b\in \mathcal{B},b\subseteq l}{\sum }{\Gamma }_b}\left(l\right),$

where we understand ${\Gamma }_b\left(l\right)$ as the part that will be distributed to b from the gain of l. Once we know the corresponding amount that will be distributed to $b\in \mathcal{B}$ for each subgraph l, we can define the function ${\Gamma }_b:M\to ℝ$ such that ${\Gamma }_b\left(l\right)$ will be this quantity. We will assume that ${\Gamma }_b\left(l\right)=0$ if $b\cancel{\subseteq }l$ . From now on, we denote

$M^b:=\left\{l\in M:b\subseteq l\right\}\text{.}$

Definition 3.1 (Partition) Let $v:M\to ℝ$ be an $\left(M,\mathcal{B}\right)$ -characteristic function game. We will say that a partition of v is a collection $\left\{{\Gamma }_b:M\to ℝ:b\in \mathcal{B}\right\}$ such that:

1. $supp{\Gamma }_b=\left\{l\in M:{\Gamma }_b\left(l\right)\ne 0\right\}\subseteq M^b$ .

2. For all $l\in M$ ,

$v\left(l\right)={\displaystyle \underset{b\in \mathcal{B}}{\sum }{\Gamma }_b}\left(l\right)={\displaystyle \underset{b\subseteq l}{\sum }{\Gamma }_b}\left(l\right).$

If $\left\{{\Gamma }_b:M\to ℝ:b\in \mathcal{B}\right\}$ is a partition of $v:M\to ℝ$ , we write

$v\equiv {\displaystyle \underset{b\in \mathcal{B}}{\sum }{\Gamma }_b{\omega }_b}.$

Before justifying the notation for partitions, we may go through an example.

Example 3.2. Consider the graph $g=\left(\left\{1,2,3,4\right\},\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{3,4\right\}\right\}\right)$ , as shown in Figure 1. Consider the edge domain $\left(M_0,\mathcal{A}\right)$ as in Example 2.1, i.e., $M_0$ consists of all subgraphs of g without isolated points, and $\mathcal{A}$ consists of subgraphs representing a single edge. We have that

$\mathcal{A}=\left\{a_{1,2},a_{1,3},a_{3,4}\right\},$

where $a_{i,j}=\left(\left\{i,j\right\},\left\{\left\{i,j\right\}\right\}\right)$ . Since $M_0$ is generated by unions in $\mathcal{A}$ , we can think of the elements of $M_0$ as subsets of $\mathcal{A}$ (subsets containing their respective edges). As we mentioned in Remark 2.2, there is a correspondence between $M_0$ and $2^{\mathcal{A}}$ , and we will refer to an element $l\in M_0$ as well as the subset $S=\left\{a_{i,j}\subseteq l\right\}$ interchangeably. Let v be the game defined by

$\begin{array}{cc}l& v\left(l\right)\\ \varnothing & 0\\ \left\{a_{1,2}\right\}& 1\\ \left\{a_{1,3}\right\}& 1\\ \left\{a_{3,4}\right\}& 2\\ \left\{a_{1,2},a_{1,3}\right\}& 4\\ \left\{a_{1,2},a_{3,4}\right\}& 5\\ \left\{a_{1,3},a_{3,4}\right\}& 5\\ \mathcal{A}& 12\end{array}$

The coefficients of its linear decomposition into unanimity games are

$\begin{array}{cc}l& {\alpha }_l\\ \varnothing & 0\\ \left\{a_{1,2}\right\}& 1\\ \left\{a_{1,3}\right\}& 1\\ \left\{a_{3,4}\right\}& 2\\ \left\{a_{1,2},a_{1,3}\right\}& 2\\ \left\{a_{1,2},a_{3,4}\right\}& 3\\ \left\{a_{1,3},a_{3,4}\right\}& 5\\ \mathcal{A}& 1\end{array}$

Later, we will discuss the calculation of ${\alpha }_l$ in the general case, as it is possible to

Figure 1. $g=\left(\left\{1,2,3,4\right\},\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{3,4\right\}\right\}\right)$ .

obtain a recursive formula for these coefficients.

A possible partition for the game v (which we will discuss in detail later) will be the collection of functions $\left\{{\Gamma }_{1,2},{\Gamma }_{1,3},{\Gamma }_{3,4}\right\}$ such that

$\begin{array}{lllll}l\hfill & \left\{a_{1,2}\right\}\hfill & \left\{a_{1,2},a_{1,3}\right\}\hfill & \left\{a_{1,2},a_{3,4}\right\}\hfill & \mathcal{A}\hfill \\ {\Gamma }_{1,2}\hfill & 1\hfill & 2\hfill & 2\hfill & 10/3\hfill \end{array}$

$\begin{array}{lllll}l\hfill & \left\{a_{1,3}\right\}\hfill & \left\{a_{1,3},a_{1,2}\right\}\hfill & \left\{a_{1,3},a_{3,4}\right\}\hfill & \mathcal{A}\hfill \\ {\Gamma }_{1,3}\hfill & 1\hfill & 2\hfill & 5/2\hfill & 23/6\hfill \end{array}$

$\begin{array}{lllll}l\hfill & \left\{a_{3,4}\right\}\hfill & \left\{a_{3,4},a_{1,2}\right\}\hfill & \left\{a_{3,4},a_{1,3}\right\}\hfill & \mathcal{A}\hfill \\ {\Gamma }_{3,4}\hfill & 2\hfill & 3\hfill & 7/2\hfill & 29/6\hfill \end{array}$

Additionally, ${\Gamma }_{i,j}=0$ outside the given tables.

The justification for our choice of notation for partitions of the $\left(M,\mathcal{B}\right)$ -game $v:M\to ℝ$ is that, for any $l\in M$ , we have

$v\left(l\right)={\displaystyle \underset{b\in \mathcal{B},b\subseteq l}{\sum }{\Gamma }_b}\left(l\right),$ (1)

where we think of v being divided (in a non-linear way) into the sum of certain unanimity games

${\omega }_b\left(l\right)=\{\begin{array}{ll}1\hfill & b\subseteq l\hfill \\ 0\hfill & \text{otherwise}\text{.}\hfill \end{array}$

Thus, (1) is equivalent to writing

$v\left(l\right)={\displaystyle \underset{b\in \mathcal{B},b\subseteq l}{\sum }{\text{Γ}}_b\left(l\right){\omega }_b\left(l\right)}={\displaystyle \underset{b\in \mathcal{B}}{\sum }{\text{Γ}}_b}\left(l\right){\omega }_b\left(l\right)\text{.}$

The advantage of working with this decomposition is that we obtain information regarding the final distribution of gains in the coalition. Our goal now is to characterize a particular partition, which will satisfy a certain equilibrium property and be well-defined for every $\left(M,\mathcal{B}\right)$ -game $v:M\to ℝ$ .

Definition 3.2 (Balanced Profit) Given an $\left(M,\mathcal{B}\right)$ -game $v:M\to ℝ$ , we will say that a partition $\left\{{\Gamma }_b:b\in \mathcal{B}\right\}$ of v has Balanced Profit if, for any $b_1,b_2\in \mathcal{B}$ and $l\in M$ such that $b_1,b_2\subset M$ , the following holds:

${\Gamma }_{b_1}\left(l\right)-{\Gamma }_{b_1}\left(l\backslash b_2\right)={\Gamma }_{b_2}\left(l\right)-{\Gamma }_{b_2}\left(l\backslash b_1\right).$ (2)

The above condition can be interpreted as follows: the difference ${\Gamma }_{b_1}\left(l\right)-{\Gamma }_{b_1}\left(l\backslash b_2\right)$ represents the gain of b₁ obtained through collaboration with b₂. Similarly, for ${\Gamma }_{b_2}\left(l\right)-{\Gamma }_{b_2}\left(l\backslash b_1\right)$ . By demanding that these gains to be equal, it indicates that the collaboration of both agents is equally beneficial for both parties. We will prove that for every $\left(M,\mathcal{B}\right)$ -game, there exists a unique partition $\left\{{\Gamma }_b\right\}$ that satisfies Balanced Profit. For this, we have the following Lemma:

Lemma 3.1. Let $P_n\in {ℝ}^{\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)+1\times n}$ be the matrix defined as follows: 1) The first row of $P_n$ is a row vector with n entries, all equal to 1. 2) Enumerate all possible pairs $\left\{i,j\right\}$ with $1\le 1,j\le n$ in the set $\left\{c_i:1\le i\le \left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)\right\}$ . For each of these $\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)$ elements, define the (k + 1)-th row of $P_n$ as the row vector $v_k$ , where the i-th entry is 1 and the j-th entry is −1. Then, the rank of $P_n$ is exactly n. Therefore, given the linear system $P_{n}x=v$ , where $x\in {ℝ}^n$ and $v\in {ℝ}^{\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)+1}$ , if there is a solution to the system, it is unique.

Proof. See appendix 6.1. ∎

With the previous lemma, we have the following theorem:

Theorem 3.1. For every $\left(M,\mathcal{B}\right)$ -game $v:M\to ℝ$ , there exists a unique partition $\left\{{\Gamma }_b:M\to ℝ:b\in \mathcal{B}\right\}$ of v that satisfies Balanced Profit, and it is given by:

${\Gamma }_b\left(l\right)=\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)},$ (3)

where $A\left(h\right)$ is the number of elements $b\in \mathcal{B}$ that make up h, and $\left\{{\alpha }_h\right\}$ are the coefficients of the linear expansion in terms of unanimity games of v.

Proof. Uniqueness. Suppose for a moment that such a partition exists. That is, $\left\{{\Gamma }_b:b\in B\right\}$ verifies (2) for any $b_1,b_2\in \mathcal{B}$ and any $l\in M$ that contains $b_1,b_2$ . We will proceed by induction. In particular, we have that

${\Gamma }_{b_1}\left(b_1\cup b_2\right)-{\Gamma }_{b_1}\left(b_1\right)={\Gamma }_{b_3}\left(b_1\cup b_2\right)-{\Gamma }_{b_2}\left(b_2\right),$

however, ${\Gamma }_b\left(b\right)=v\left(b\right)$ for every $b_1$ (a property of being a partition). Therefore,

$\begin{array}{l}{\text{Γ}}_{b_1}\left(b_1\cup b_2\right)-v\left(b_1\right)={\text{Γ}}_{b_1}\left(b_1\cup b_2\right)-v\left(b_2\right)\\ \iff {\Gamma }_{b_1}\left(b_1\cup b_2\right)-{\Gamma }_{b_2}\left(b_1\cup b_2\right)=v\left(b_1\right)-v\left(b_2\right).\end{array}$ (4)

Moreover, by being a partition, we have the equation

${\Gamma }_{b_1}\left(b_1\cup b_2\right)+{\Gamma }_{b_2}\left(b_1\cup b_2\right)=v\left(b_1\cup b_2\right).$ (5)

Combining (4) and (5), we obtain the linear system

$\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{c}{\Gamma }_{b_1}\left(b_1\cup b_2\right)\\ {\Gamma }_{b_2}\left(b_1\cup b_2\right)\end{array}\right)=\left(\begin{array}{c}v\left(b_1\cup b_2\right)\\ v\left(b_1\right)-v\left(b_2\right)\end{array}\right).$

Then, the solution is given by

$\begin{array}{l}{\Gamma }_{b_1}\left(b_1\cup b_2\right)=v\left(b_1\cup b_2\right)+v\left(b_1\right)-v\left(b_2\right),\\ {\Gamma }_{b_2}\left(b_1\cup b_2\right)=v\left(b_1\cup b_2\right)-v\left(b_1\right)+v\left(b_2\right),\end{array}$

which are known values. Therefore, if $A\left(l\right)=2$ , we can determine ${\Gamma }_b\left(l\right)$ for $b\subset l$ . Suppose that, for some $k\ge 2$ , for every $l^{\prime }\in M$ with $A\left(l^{\prime }\right)=k$ , we know the value of ${\Gamma }_b\left(l^{\prime }\right)$ for $b\subset l^{\prime }$ . Let $l\in M$ such that $A\left(l\right)=k+1$ . Suppose that $l={\displaystyle {\cup }_{i=1}^{k+1}{b}_i}$ . Due to the property of Balanced Profit for any pair $i,j$ , it holds that

${\Gamma }_{b_i}\left(l\right)-{\Gamma }_{b_i}\left(l\backslash b_j\right)={\Gamma }_{b_i}\left(l\right)-{\Gamma }_{b_j}\left(l\backslash b_i\right)\Leftarrow {\Gamma }_{b_i}\left(l\right)-{\Gamma }_{b_i}\left(l\right)={\Gamma }_{b_i}\left(l\backslash b_j\right)-{\Gamma }_{b_j}\left(l\backslash b_i\right).$

However, $A\left(l\backslash b_i\right)=k=A\left(l\backslash b_j\right)$ , so ${\Gamma }_{b_i}\left(l\backslash b_j\right)-{\Gamma }_{b_j}\left(l\backslash b_i\right)=:d^{ij}$ is a known value. For each pair $i,j$ , we obtained the equation

${\Gamma }_{b_i}\left(l\right)-{\Gamma }_{b_i}\left(l\right)=d^{ij},$ (6)

which means we have $\left(\begin{array}{c}k+1\\ 2\end{array}\right)$ distinct equations. Also, by being a partition, we have the equation

${\displaystyle \underset{i=1}{\overset{k+1}{\sum }}{\Gamma }_{b_i}\left(l\right)}=v\left(l\right).$

We have a linear system with $\left(\begin{array}{c}k+1\\ 2\end{array}\right)+1$ equations in k variables, which, expressed in matrix form, gives

$P_{k+1}\Gamma =d,$ (7)

where $\Gamma =\left({\Gamma }_{b_1}\left(l\right),\mathrm{..}\cdots ,{\Gamma }_{b_{k+1}}\left(l\right)\right)$ , $d=\left(v\left(l\right),d_0\right)$ , $d_0$ is the vector of $d^{ij}$ arranged according to the obtained equations, and $P_{k+1}$ is as in Lemma 3.1. Then, the solution to (7) is unique and depends solely on known and uniquely determined values. As the above is true for every $l\in M$ with $A\left(l\right)=k+1$ , we conclude by induction that the values of ${\Gamma }_b\left(l\right)$ are uniquely determined for every $l\in M$ .

Existence. The collection of functions defined in (3) is a partition that satisfies Balanced Profit. For every $l\in M$ with $l={\displaystyle {\cup }_{b\in \mathcal{C}}b}$ where $\mathcal{C}\subseteq \mathcal{B}$ , it holds that

$\underset{b\in \mathcal{C}}{{\displaystyle \sum }}{\text{Γ}}_b\left(l\right)=\underset{b\in \mathcal{C}}{{\displaystyle \sum }}\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)}=\underset{b\in \mathcal{C}}{{\displaystyle \sum }}A\left(h\right)\frac{{\alpha }_h}{A\left(h\right)}=\underset{b\in \mathcal{C}}{{\displaystyle \sum }}\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)}=\underset{b\in \mathcal{C}}{{\displaystyle \sum }}{\alpha }_h=v\left(l\right)\text{.}$

The equality above is due to a counting result (the term ${\alpha }_h/A\left(h\right)$ appears as many times as there are elements $b\subset h$ , i.e., $A\left(h\right)$ times). Moreover, if $b_1,b_2\in \mathcal{B}$ and $b_1,b_2\subset l$ , it holds that

${\text{Γ}}_{b_1}\left(l\right)-{\text{Γ}}_{b_1}\left(l\backslash b_2\right)=\underset{b_1\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)}-\underset{b_1\subseteq h\subseteq l\backslash b_2}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)}=\underset{b_1,b_2\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)},$

similarly

${\Gamma }_{b_2}\left(l\right)-{\Gamma }_{b_2}\left(l\backslash b_1\right)=\underset{b_2,b_1\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h}{A\left(h\right)},$

so

${\Gamma }_{b_1}\left(l\right)-{\Gamma }_{b_1}\left(l\backslash b_2\right)={\Gamma }_{b_2}\left(l\right)-{\Gamma }_{b_2}\left(l\backslash b_1\right),$

verifying Balanced Profit. This concludes the proof. ∎

In Example 3.2, we already presented the calculation of the partition from the above theorem.

Remark 3.1. The advantage of employing this formulation of graph-defined games is that it allows for the simplification of cooperative structure. Thus, we can work on a game defined over classes of blocks of the graph, instead of dealing with restriction on a game as the Myerson way.

As we will see later, our conception of graph-defined games enables us to generalize a Shapley-like value in a conceptually natural manner.

Remark 3.2. A potential disadvantage is the inability to consider that some nodes prefer to play alone. In other words, we cannot consider isolated nodes as blocks in $\mathcal{B}$ because this would imply that we cannot uniquely express a graph $h\in M$ . However, this allows us to analyze collective cooperative behavior beyond the individualism of players.

Remark 3.3. Regarding the calculation of coefficients ${\alpha }_h$ : recalling that g is our fixed ambient graph, with our domain $M,\mathcal{B}$ . Suppose $\left|\mathcal{B}\right|=A\left(g\right)=m$ , where $A\left(g\right)$ is taken as in the statement of Theorem 3.1. Then,

$v\left(g\right)=\underset{h\in M}{{\displaystyle \sum }}{\alpha }_h={\alpha }_g+\underset{h\in M,A\left(h\right)\le m-1}{{\displaystyle \sum }}{\alpha }_h$

$\iff {\alpha }_g=\underset{h\in M}{{\displaystyle \sum }}{\alpha }_h=-v\left(g\right)+\underset{h\in M,A\left(h\right)\le m-1}{{\displaystyle \sum }}{\alpha }_h\text{.}$

Thus, ${\alpha }_g$ depends solely on $v\left(g\right)$ and ${\alpha }_h$ for $h\in M$ with $A\left(h\right)\le m-1$ . These coefficients are obtained recursively since ${\alpha }_b=v\left(b\right)$ for all $b\in \mathcal{B}$ , and every $h\in M$ is the union of these b's.

3.2. The Value for Games Defined on Graphs

Now, we need to construct the payoff vector that will provide us with the final distribution of gains among the players. However, before proceeding, we have another important property that verifies the partition given by (1):

Lemma 3.2 (Linearity) Let $\left(M,\mathcal{B}\right)$ be a domain of unique decomposition, where $\mathcal{B}=\left\{b_1,\cdots ,b_k\right\}$ . We define the operator $P:{\mathcal{J}}^{M,\mathcal{B}}\to {\left({\mathcal{J}}^{M,\mathcal{B}}\right)}^k$ as

$v\mapsto \left({\Gamma }_{b_1}^v,\cdots ,{\Gamma }_{b_k}^v\right).$

Then, P is a injective linear operator, and $\left\{{\Gamma }_b^v\right\}$ is the partition given by Theorem 3.1 for the game v.

Proof. It is clear since the coefficients $\left\{{\alpha }_h^v\right\}$ of the linear expansion in terms of unanimity games depend linearly on the game v. That is, ${\alpha }_h^{v+w}={\alpha }_h^v+{\alpha }_h^w$ for any $v,w\in {\mathcal{J}}^{M,\mathcal{B}}$ . ∎

Let us recall that the elements of M are subgraphs representing (interest) coalitions of a certain set of players (nodes) N, connected through the participation of intermediaries (edges) that enable the formation of links. We think of the elements of the generating set $\mathcal{B}$ as the minimal collaboration structures that can occur.

For instance, if we consider the edge domain $\left(M_0,\mathcal{A}\right)$ , as in Example 2.1, the $\left(M_0,\mathcal{A}\right)$ -games are those in which we impose the condition that a player cannot participate alone in the game (cannot be an isolated point). In other words, a player can participate if and only if there exists another player and an intermediary connecting them, meaning that the player has to be part of an edge.

During the game development, the gain is determined solely by the presence or absence of the element $b\in \mathcal{B}$ in the formation of a coalition, without considering the specific players themselves. Now, our focus is on finding a distribution of gains among nodes and intermediaries.

For this purpose, assume that the element $b\in \mathcal{B}$ is a subgraph of the form $b=\left(V_b,A_b\right)$ , meaning it is composed of players in $V_b=\left\{n_1,\cdots ,n_k\right\}\subseteq V=\left\{1,\cdots ,n\right\}$ and intermediaries in $A_b=\left\{i_1,\cdots ,i_r\right\}\subseteq A=\left\{a_1,\cdots ,a_s\right\}$ . From now on, we will refer to the elements of $V_b\cup A_b$ as partners in b, always distinguishing between partners of the node class ( $V_b$ ) and partners of the edge class ( $A_b$ ).

Let’s assume that the partners in b agree on a distribution of the gain obtained by b in the $\left(M,\mathcal{B}\right)$ -game $v\in {\mathcal{J}}^{M,\mathcal{B}}$ for coalition l. In other words, they define functions

${\gamma }_{\alpha }^b:M^b\to \left[0,1\right],$

where $M^b$ is defined as in (3.1), such that

$\underset{\alpha \in V_b\cup A_b}{{\displaystyle \sum }}{\gamma }_{\alpha }^b\left(l\right)=1,\forall l\in M\text{.}$ (8)

These functions represent the fraction of utilities that each partner in $b\in \mathcal{B}$ will receive for playing the game v and participating in coalition l. These functions can either be agreed upon by the partners and the game context or defined in a fair manner. We will discuss possible definitions of these functions later on. Note that we can extend the functions ${\gamma }_{\alpha }^b$ to M, defining ${\gamma }_{\alpha }^b\left(l\right)=0$ for all $l\in M\backslash M^b$ .

Consider, for each $l\in M$ , the vector

$\varphi \left(b,l\right)={\left({\gamma }_{\alpha }^b\left(l\right){\delta }_{V_b\cup A_b}\left(\alpha \right)\right)}_{\alpha \in V\cup A}\in {ℝ}^{V\cup A},$

where ${\delta }_{V_b\cup A_b}$ is the indicator function of the set $V_b\cup A_b$ , and thus, $\varphi \left(b\right)$ is a vector such that in its entry corresponding to player $j\in V$ , it takes the value ${\gamma }_j^b$ if $j\in V_b$ and zero otherwise. Similarly, in the entry corresponding to edge $a\in A$ , it takes the value ${\gamma }_a^b$ if $a\in A_b$ and zero otherwise. The previous vector contains all players and intermediaries present in the game and indicates whether they belong to b.

By Theorem 3.1, every game $v\in {\mathcal{J}}^{M,\mathcal{B}}$ can be expressed in terms of the partition given by (1), such that

$v\equiv \underset{b\in B}{{\displaystyle \sum }}{\text{Γ}}_b{\omega }_b\text{.}$

We define the operator $\phi :{\mathcal{J}}^{M,\mathcal{B}}\times M\to {ℝ}^{V\cup A}$ as

$\phi \left(v,l\right)=\underset{b\in \mathcal{B}}{{\displaystyle \sum }}{\text{Γ}}_b\left(l\right)\varphi \left(b,l\right)\text{.}$

Proposition 3.1. The operator $\phi :{\mathcal{J}}^{M,\mathcal{B}}\times M\to {ℝ}^{V\cup A}$ is linear with respect to the first entry. Moreover, if ${\phi }_j\left(v,l\right)$ and ${\phi }_a\left(v,l\right)$ are the j-th entry with $j\in V$ and a-th entry with $a\in A$ of $\phi \left(v,l\right)$ respectively, then

$\underset{j\in V}{{\displaystyle \sum }}{\phi }_j\left(v,l\right)+\underset{a\in A}{{\displaystyle \sum }}{\phi }_a\left(v,l\right)=v\left(l\right)\text{.}$ (9)

Proof. Equation (9) follows from our construction. It remains to verify linearity. To see this, we note that the coefficients ${\alpha }_h$ in the linear expansion in terms of unanimity games are linear with respect to addition. That is, if $v={\displaystyle {\sum }_{h\in M}{\alpha }_h^v{u}_h}$ and $w={\displaystyle {\sum }_{h\in M}{\alpha }_h^w{u}_h}$ , then

$v+w=\underset{h\in M}{{\displaystyle \sum }}\left({\alpha }_h^v+{\alpha }_h^w\right)u_h\iff {\alpha }_h^{v+w}={\alpha }_h^v+{\alpha }_h^w\text{.}$

So, for every $b\in \mathcal{B}$ , it holds that

${\text{Γ}}_b^{v+w}\left(l\right)=\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h^{v+w}}{A\left(h\right)}=\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h^v}{A\left(h\right)}+\underset{b\subseteq h\subseteq l}{{\displaystyle \sum }}\frac{{\alpha }_h^w}{A\left(h\right)}={\text{Γ}}_b^v\left(l\right)+{\text{Γ}}_b^w\left(l\right)\text{.}$

And the linearity holds. ∎

The operator φ provides us with an assignment rule for the profits of nodes and edges for each value of l, as it indicates how much of the total gain should be assigned to each player and intermediary.

Remark 3.4. We can think of $\varphi$ as an operator that sends functions $v\in {\mathcal{J}}^{M,\mathcal{B}}$ to functions $M\to {ℝ}^{V\cup A}$ .

The essence of this definition is that we obtain an operator that behaves in a quasi-linear way with respect to the partition decomposition. It is not a linear decomposition, as the coefficients in the expansion are functions $M\to ℝ$ . That is, we have constructed a quasi-linear decomposition of the game v, and then we define an operator that preserves the quasi-linear structure in the sense that

$\phi \left(v(\cdot )\right)=\phi \left(\underset{b\in \mathcal{B}}{{\displaystyle \sum }}{\text{Γ}}_b(\cdot ){\omega }_b(\cdot )\right)=\underset{b\in \mathcal{B}}{{\displaystyle \sum }}{\text{Γ}}_b(\cdot )\phi \left({\omega }_b(\cdot )\right),$

where we have defined the image of our base $\phi \left({\omega }_b(\cdot )\right)=\varphi \left(b,\cdot \right)$ . Thus, $\phi$ is an operator that preserves scalar functions.

Remark 3.5. Given an $\alpha \in V\cup A$ , we can look at the α-th entry of the vector $\phi \left(v,l\right)$ , and we can see that it is given by

${\phi }_{\alpha }\left(v,l\right)=\underset{b\in \mathcal{B}}{{\displaystyle \sum }}{\text{Γ}}_b\left(l\right){\gamma }_{\alpha }^b{\left(l\right)}_{V_b\cup A_b}\left(\alpha \right)=\underset{\alpha \in b\in \mathcal{B}}{{\displaystyle \sum }}{\text{Γ}}_b\left(l\right){\gamma }_{\alpha }^b\left(l\right)\text{.}$

The above expression means that, by participating in the coalition l, the player α will receive a payment of ${\text{Γ}}_b\left(l\right){\gamma }_{\alpha }^b\left(l\right)$ for each of the blocks b in which they participate.

4. Example: Productive Chains

4.1. Problem Statement

Let us examine a scenario pertaining to the production process of a specific commodity. The fabrication necessitates particular raw materials, subsequently subject to manufacturing processes for enhanced manageability. Subsequently, a manufacturing facility undertakes the production of the designated product, culminating in its distribution to a final vendor. This comprehensive progression, commencing with the extraction of raw materials and concluding with the ultimate sale of the product, is denoted as the production chain. From the initial production phase to the treatment processes, assembly, and final product sale, we shall denote these junctures as distinct phases. Intervening between each phase is an intermediary tasked with orchestrating the transition, exemplified by a logistics enterprise overseeing the transportation of goods.

To exemplify this process, consider the instance of enjoying a morning cup of coffee. The prerequisite steps involve a farmer cultivating and harvesting the beans, transporting them to a processor for requisite treatment, conveying the processed beans to a packaging facility, and ultimately disbursing the product.

It is imperative that the progression unfolds in a specific sequence: raw material extraction, processing, assembly, and sale. Consequently, a prototype delineating the sequential order of this process becomes indispensable. The entire chain can be graphically represented, wherein each process stage constitutes a node. Nodes are interconnected if they represent consecutive stages in the overall process. Thus, for the aforementioned coffee production process, the resultant model would manifest as in Figure 2.

Remark 4.1. The processes under consideration for our study will be production processes, involving the transformation of an entity A into a product B. Consequently, it is imperative that the process stages do not exhibit cyclic behavior. The entire process must culminate in a sales (distribution) stage.

Due to our economic system, there will be several distinct companies responsible for carrying out the same stage of the process, naturally engaging in competition. Each of the companies assigned to different stages decides to collaborate with one another to complete the entire process. If we anticipate deriving profit from this process, it becomes essential to have at least one company for each stage. In the absence of any one of these companies, the chain is disrupted, and consequently, no profit can be realized. We can conceptualize these situations, where different companies are responsible for various tasks, as scenarios of competition.

Each of the companies involved in the chain represents a node. If two companies decide to collaborate to form the chain, we connect them with an edge (possibly requiring an intermediary to establish this connection). We group each of the companies based on the stage of the process they undertake.

Returning to the coffee example: let’s assume there are 3 farmers cultivating coffee, 3 companies producing coffee beans, 3 packaging companies, and all of them sell their products to the same store. A possible graphical representation of this scenario is as in Figure 3.

4.2. Mathematical Formulation

Definition 4.1. We will say that a graph g contains cycles if there exists a sequence of vertices $v_1,\cdots ,v_k$ such that $v_i$ is connected to $v_{i+1}$ for $1\le i\le k-1$ ,

Figure 2. Example of a productive chain.

Figure 3. Example of a competitive situation for coffee production.

and $v_k$ is connected to $v_1$ . We will say that the connected graph g is a tree if it does not contain cycles.

Let G be the graph representing a production chain. We have imposed that G does not contain cycles (stages that form a loop). On the other hand, in any process, there is a stage of public sale, and every stage of the process leads to its sale. Thus, there exists a node d in G representing this stage. Furthermore, for every node, there exists a path connecting it to d. From the above, we conclude that G is a tree.

Definition 4.2 (Competition Scenario) A competition scenario will be a graph $g=\left(V,A\right)$ associated with the production chain $G=\left(V^{\prime },A^{\prime }\right)$ if and only if

1. There exists a partition $P=\left\{V_s\subseteq V:s\in V^{\prime }\right\}$ of the node set V.

2. Given two nodes $v_1,v_2\in V$ , $v_1$ will be connected to $v_2$ if and only if $v_1\in V_{e_1}$ , $v_2\in V_{e_2}$ , and $e_1$ is connected to $e_2$ .

Now, we want to study the situation where different companies (nodes) collaborate to complete the production process and obtain profit. We need a notion of a complete chain with respect to the process defined in G; that is, a union of companies capable of completing the entire production process.

Definition 4.3 (Subchain, complete subchain) Let $g=\left(V,A\right)$ be a competition scenario associated with the production chain $G=\left(V^{\prime },A^{\prime }\right)$ . A subchain $\mathfrak{c}$ in g is a connected subgraph of g. This implies that $\mathfrak{c}$ is a tree.

A subchain $\mathfrak{c}$ will be complete if there exists at least one subgraph ${\mathfrak{c}}^{\prime }\subseteq \mathfrak{c}$ with ${\mathfrak{c}}^{\prime }=\left({V^{\prime }}_{\mathfrak{c}},{E^{\prime }}_{\mathfrak{c}}\right)$ such that ${\mathfrak{c}}^{\prime }$ is isomorphic (as graphs) to G, and moreover, if a node i in ${\mathfrak{c}}^{\prime }$ corresponds to node s in G, then $i\in V_s$ . We denote by $\mathcal{C}$ the set of complete subchains in g.

In other words, a subchain is complete if and only if it contains a subgraph that corresponds one-to-one with the production process, and each node corresponds to a specific stage. Now, we can model the generation of profit in a competition scenario through a function (game) that takes the various possible alliances of companies and associates with them the profit obtained by such collaboration.

Definition 4.4 (Production Game) Let $g=\left(V,A\right)$ be a competition scenario associated with the production chain $G=\left(V^{\prime },A^{\prime }\right)$ . Take $M_0$ as the edge domain (as in Example 2.1) associated with g, and let $\mathcal{A}$ be the set of edges. We will say that a game $v\in {\mathcal{J}}^{M_0,\mathcal{A}}$ is a production game if and only if $v\left(l\right)=0$ for all $l\notin \mathcal{C}$ .

Hereinafter, $g=\left(V,A\right)$ will be a competition scenario associated with the production chain $G=\left(V^{\prime },A^{\prime }\right)$ with $\left(M_0,\mathcal{A}\right)$ as the edge domain regarding g as in Example 2.1. Let $v\in {\mathcal{J}}^{M_0,\mathcal{A}}$ be a fixed but arbitrary game. This game admits a decomposition into unanimity games

$v\equiv \underset{h\in M_0}{{\displaystyle \sum }}{\alpha }_h{u}_h\text{.}$

Since G is itself a graph, we can consider its own edge domain ${M^{\prime }}_0,{\mathcal{A}}^{\prime }$ . Let $m=\left|{\mathcal{A}}^{\prime }\right|$ be the number of edges in G. Since G is connected and has m edges, there are $m+1$ nodes (stages of the process). In this section, if $h\in M_0$ , we will reuse the notation $A\left(h\right)$ to denote the number of elements $a\in \mathcal{A}$ composing h.

Proposition 4.1. Suppose G has edges. If $l\in M_0$ is a subgraph such that $A\left(l\right)<m$ , then

${\alpha }_l=0.$

Proof. Any graph $l\in M_0$ such that $A\left(l\right)\le m$ cannot be isomorphic to G. Isomorphisms of graphs preserve relationships between nodes (edges).

If $m=1$ , any non-empty subgraph will be complete, as g is a competition scenario, so any edge-type subgraph is a subchain. There is nothing to prove in this case.

Suppose then that $m\ge 2$ . For any edge $a\in \mathcal{A}$ , we have

$v\left(a\right)=\underset{h\in M_0}{{\displaystyle \sum }}{\alpha }_h{u}_h\left(a\right)={\alpha }_a,$

Since $A\left(a\right)\le m$ , we have $v\left(a\right)=0={\alpha }_a$ . Suppose that for $l\in M_0$ with $A\left(l\right)=k$ such that $1\le k<m$ , ${\alpha }_l=0$ . If $l^{\prime }\in M_0$ with $A\left(l^{\prime }\right)=k+1$ and $k+1<m$ , then

${\alpha }_{l^{\prime }}=-v\left(l^{\prime }\right)+\underset{h\in M_0,A\left(h\right)\le k}{{\displaystyle \sum }}{\alpha }_h=-v\left(l^{\prime }\right),$

However, since $l^{\prime }$ is not a complete chain, $v\left(l^{\prime }\right)=0={\alpha }_{l^{\prime }}$ . ∎

Corolario 4.1. If $l\in M_0$ is not a complete subchain, then ${\alpha }_l=0$ .

Proof. Let m be the number of edges in G. If $l\in M_0\mathcal{C}$ , with $A\left(l\right)<m$ , then ${\alpha }_l=0$ by the previous proposition. If $A\left(l\right)=m$ but $l\notin \mathcal{C}$ , then any subgraph $h\subset l$ is not a complete subchain, and $A\left(h\right)<m$ , so ${\alpha }_h=0$ . Then

${\alpha }_l=-v\left(l\right)+\underset{h\in M_0}{{\displaystyle \sum }}{\alpha }_h=-v\left(l\right)=0.$

Inductively, it is proven that if $l\notin \mathcal{C}$ , any subgraph $h\subset l$ with $A\left(h\right)<A\left(l\right)$ satisfies ${\alpha }_h=0$ , so ${\alpha }_l=-v\left(l\right)=0$ . ∎

The above results indicate that for the study of production games, it suffices to examine coalitions in $\mathcal{C}$ . In this particular case, it significantly reduces the number of coalitions that need to be studied for the calculation of the payoff value.

5. Conclusions

Summarizing, we have defined a new view on the coalitional structure in the graphs. We defined the concept of single decomposition domain, which contemplates the concept of minimum measurable coalitions. That is, we eliminate non-relevant information and work directly on a space with algebraic structure. Moreover, because of this, we can prove some results such as the existence of a value for the set defined on edges.

This new vision has the combinatorial advantage that it allows us to reduce the objects with which we have to work, which at a computational level can be useful. Furthermore, as we saw above, in specific cases, it allows us to elegantly model an industrial problem. For future work, this area can be directed towards the search for new game values that fit specific contexts, also in the generalization and construction of cooperation structures with more general objects.

Acknowledgements

I thank the Centro de Investigación en Matemáticas (CIMAT) and the University of Guanajuato (UG) for the support through the undergraduate scholarship. Also, I especially thank Francisco Sánchez Sánchez, PhD., researcher at CIMAT, and my mentor in Game Theory, for his advice and review of ideas for this work.

Appendix

A1. Proof of the Lemma

Lemma 5.1. Let $P_n\in {ℝ}^{\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)+1\times n}$ be the matrix defined as follows:

1. The first row of $P_n$ is a row vector with n entries of 1.

2. Enumerate all possible pairs $\left\{i,j\right\}$ with $1\le 1,j\le n$ in the set $\left\{c_i:1\le i\le \left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)\right\}$ . For each of these $\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)$ elements, define the (k + 1)-th row of $P_n$ as the row vector $v_k$ where the i-th entry is 1, and the j-th entry is −1.

Then, the rank of $P_n$ is exactly equal to n. Therefore, given the linear system $P_{n}x=v$ , with $x\in {ℝ}^n$ and $v\in {ℝ}^{\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)+1}$ , if there exists a solution to the system, it will be unique.

Proof. We proceed by induction. For the case $n=2$ , the matrix $P_n\in {ℝ}^{2\times 2}$ is

$\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),$

which has rank 2. Suppose the above holds for some $k\ge 2$ . Then, the matrix $P_n$ is of full rank and has the form

$P_n=\left(\begin{array}{c}{1}_n\\ E_n\end{array}\right),1_n=\left(1\cdots 1\right)\in {ℝ}^n$

and $E_n$ is a matrix whose rows are given by point 2. The matrix $P_{n+1}$ is constructed as follows

$P_{n+1}=\left(\begin{array}{cc}{1}_n& 1\\ E_n& 0_n\\ I{d}_n& -1_n\end{array}\right),-1_n={\left(-1\cdots -1\right)}^t,0_n={\left(0\cdots 0\right)}^t\in {ℝ}^n\text{.}$

Now, since $\text{dimImg}\left(P_n\right)=n$ , we have

$P_n=\left(\begin{array}{c}{1}_n\\ E_n\end{array}\right)$

has n linearly independent column vectors. Let $V=\left\{v\in {ℝ}^{n+1}:v=\left(v_1,\cdots ,v_{n+1}\right),v_{n+1}=0\right\}$ , then for $v\in V$

$P_{n+1}v=\left(\begin{array}{c}{1}_n\\ E_n\\ I{d}_n\end{array}\right)\left(\begin{array}{c}{v}_1\\ ⋮\\ v_{n-1}\end{array}\right)+\left(\begin{array}{c}1\\ 0_n\\ I{d}_n\end{array}\right)0=\left(\begin{array}{c}{P}_n\tilde{v}\\ \tilde{v}\end{array}\right),$

where $\tilde{v}=\left(v_1,\cdots ,v_n\right)\in {ℝ}^n$ for all $v\in V$ . Furthermore, since $P_n$ is injective, the mapping $V\to {ℝ}^n$ that sends

$v\mapsto \left(\begin{array}{c}{P}_{n}v\\ v\end{array}\right)=P_{n+1}v,$

is also injective. Additionally, $\dim V=n$ , so $n\le \text{dimran}{P}_{n+1}\le n+1$ . Finally, the vector ${\left(10-1_n\right)}^{\text{T}}$ is linearly independent of the column vectors in the matrix

$\left(\begin{array}{c}{1}_n\\ E_n\\ I{d}_n\end{array}\right)\text{.}$

Otherwise, it would imply that there exists a coefficient vector $v\in {ℝ}^n$ such that

$\left(\begin{array}{c}{1}_n\\ E_n\\ I{d}_n\end{array}\right)v=\left(\begin{array}{c}1\\ 0_n\\ -1_n\end{array}\right),$

in particular

$1_{n}v=1E_{n}v=0I{d}_{n}v=-1_n\text{.}$

From the last equation, it necessarily follows that $v=-1_n$ , but this vector does not satisfy the other conditions. Thus, $\dim P_{n+1}=n+1$ . This completes the proof. ∎

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Shapley, L.S. (1953) A Value for n-Person Games. In: Kuhn, H.W. and Tucker, A.W., Eds., Contributions to the Theory of Games II, Princeton University Press, Princeton, 307-317. https://doi.org/10.1515/9781400881970-018
[2]	Myerson, R.B. (1977) Graphs and Cooperation in Games. Mathematics of Operations Research, 2, 225-229. http://www.jstor.org/stable/3689511
[3]	Owen, G. (1986) Values of Graph-Restricted Games. Society for Industrial and Applied Mathematics, 7, 210-221. https://doi.org/10.1137/0607025
[4]	Caulier, J.-F., Skoda, A. and Tanimura, E. (2017) Allocation Rules for Networks Inspired by Cooperative Game-Theory. Revue d’économie Politique, 127, 517-558. https://doi.org/10.3917/redp.274.0517
[5]	Alarcón, A.C., Gallardo, J.M. and Jiménez-Losada, A. (2022) A Value for Graph-Restricted Games with Middlemen on Edges. Mathematics, 10, 1856. https://www.mdpi.com/2227-7390/10/11/1856 https://doi.org/10.3390/math10111856