# A Myerson Value for Multi-choice Games with a Communication Network

David Lowing, Satoshi Nakada, Serge Bertrand Nlend Oum, Philippe Solal

<figure><img src="image_1.png" /></figure>

## To cite this version:

David Lowing, Satoshi Nakada, Serge Bertrand Nlend Oum, Philippe Solal. A Myerson Value for Multi-choice Games with a Communication Network. 2025. hal-05354219

HAL Id: hal-05354219

https://hal.science/hal-05354219v1

Preprint submitted on 7 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Myerson Value for Multi-choice Games with a
Communication Network

David Lowing * Satoshi Nakada† Serge Bertrand Nlend Oum ‡ Philippe Solal‡

November 7, 2025

Abstract

This paper studies cooperative games where agents have multiple participation levels, and are embed-
ded in a communication network. We introduce a solution concept that generalizes the Myerson value.
It is constructed through a restriction operator that captures the interaction between the network structure
and agents’ participation levels, and the way this interaction constrains feasible coalitions. The solution
is axiomatically characterized and shown to satisfy a stability property. To demonstrate its applicability,
we extend the classical sequencing problem to a setting where agents can exert effort to reduce processing
times. Our solution then determines how the resulting cost savings are distributed when agents exert
maximal effort and tasks are ordered in a cost-minimizing sequence.

**Keywords:** Multi-choice games; Communication networks; Axiomatic characterization; Stability; Sequencing problems

JEL codes: C71; C44

<footnote>*Ecole Normale Supérieure de Rennes, CNRS UMR 6211 CREM, Bruz, France</footnote>

<footnote>†School of Management, Department of Business Economics, Tokyo University of Science, 1-11-2, Fujimi, Chiyodaku, Tokyo, 102-0071, Japan</footnote>

<footnote>‡Université de Saint-Etienne, CNRS UMR 5824 GATE Lyon Saint-Etienne, France</footnote>
# 1 Introduction

Cooperative situations in which a group of agents can generate collective utility through collaboration are naturally modeled as cooperative games with transferable utility (TU-games). In their classical form, TU-games assume that each agent faces a binary choice: either to join a coalition or to remain outside it. While this abstraction has been fundamental for the development of cooperative game theory, it often falls short in capturing the richness of real-world interactions, where participation can be gradual and constrained by social, organizational, or technological structures.

To address these limitations, two extensions of the classical framework have been proposed. The first generalization, due to Hsiao and Raghavan (1992), allows each agent to select among multiple levels of participation, giving rise to **multi-choice cooperative games**. This model captures settings in which agents can contribute at varying intensities—ranging from non-participation to full involvement. Extensions of classical solution concepts such as the Shapley value (Shapley, 1953) to this richer environment have been developed in, among others, van den Nouweland (1993), Klijn et al. (1999), Peters and Zank (2005), Grabisch and Lange (2007), Lowing and Techer (2022a), and Béal et al. (2025).

The second line of generalization enriches the agent set with a **structure** that restricts cooperation possibilities. In the standard TU-game, any subset of agents can cooperate freely; yet, in practice, collaboration is often limited by communication networks, organizational hierarchies, or institutional partitions. Structured TU-games formalize such constraints by embedding the agent set in a communication network, hierarchy, or partition. For instance, hierarchical constraints have been modeled as directed graphs in which cooperation requires authorization from superiors (Gilles et al., 1992; van den Brink and Gilles, 1996; van den Brink, 1997, 2017). Partition-based structures, introduced by Aumann and Dreze (1974) and Owen (1977), restrict cooperation to predefined unions of agents. Communication networks, first introduced by Myerson (1977), capture situations where agents can cooperate only if they are connected through a path of cooperating agents within the same coalition.

Although both extensions have been extensively studied in isolation, their intersection has received relatively limited attention. Existing contributions include Béal et al. (2012), who extend the Average Tree solution of Herings et al. (2008) to multi-choice games with a communication network; Albizuri (2009), who generalize the Owen value to multi-choice games with a priori unions; and Lowing and Techer (2022b), Lowing (2023), who develop extensions of the Shapley value for games with priority (see Béal et al., 2022) and permission structures. Building on this literature, this paper focuses on **multi-choice cooperative games with communication networks**.
Integrating participation levels and communication structures raises fundamental conceptual questions. As noted by Lowing (2023), the interaction between these two dimensions is not straightforward: when exactly can two connected agents cooperate?<fnref n="1" /> One possibility is that any positive level of participation enables communication and cooperation. This interpretation is adopted in Béal et al. (2012). Another interpretation is that communication capacity increases with participation intensity, allowing agents to collaborate over a wider range as their participation level rises. In this paper, we adopt a simple **interpretation**: connected agents can cooperate through the network only if all of them participate at their maximal level.<fnref n="2" /> This interpretation aligns with practical scenarios, as we will demonstrate through a concrete application.

Under this interpretation, we introduce a **new solution concept** for multi-choice games with a communication network, which unifies and extends the multi-choice Shapley value of Klijn et al. (1999) and the Myerson value of Myerson (1977). The proposed solution is constructed through a restriction operator that maps each coalition to a collection of feasible coalitions. A coalition is deemed feasible if it consists solely of agents who are both maximally participating and mutually connected within the network. Observe that a coalition consisting of only one active player is always feasible.

We establish two main results. First, we provide an **axiomatic characterization** of the solution on the full domain of multi-choice games with a communication network (Section 4), relying on recognized principles from the cooperative game literature. Second, we show that the solution satisfies a **stability property**: removing a link in the network weakly reduces the payoffs of the agents connected by that link (Section 5). This result holds for superadditive multi-choice games with a communication network, representing environments where cooperation is always beneficial.

To illustrate the relevance of our framework and our approach, we consider **sequencing problems**. In a single-machine environment, agents form a queue to process tasks, where each task has a fixed processing time and each unit of waiting time incurs a cost per agent. Two key questions arise: determining the queue that minimizes total waiting costs, and allocating the resulting savings among agents. Smith (1953) show that the optimal order arranges agents in descending order of urgency indices, defined as the ratio of waiting cost to processing time. Curiel et al. (1989) extend this setting to cooperative sequencing games, where coalitions can reorder their members provided that no agent overtakes a non-member. Each such game can be represented as a cooperative game with a line-graph communication network, and a corresponding solution specifies how to allocate the resulting cost savings among agents.

We extend this model by allowing agents to **shorten their processing times through effort**—such as

<footnote n="1">¹This remark concerns multi-choice games with a permission structure, but the reasoning applies similarly in our setting.</footnote>

<footnote n="2">²Alternative interpretations are discussed in the Conclusion as directions for future research.</footnote>
learning or training—which we interpret as their level of participation. This transforms the sequencing environment into a multi-choice game with a line-graph communication network. Applying our proposed solution yields a new allocation of cost savings that accounts for agents’ waiting costs, processing times, and capacities for efficiency improvements through efforts. The interpretation underlying our solution naturally applies to the sequencing problem: a planner reorders agents only after they have exerted maximal effort, ensuring that no potential gains from further individual improvement are lost. Otherwise, reordering prematurely could lead to future adjustments and inefficiencies resulting from an initially suboptimal configuration.

The remainder of the paper is organized as follows. Section 2 reviews the necessary concepts and definitions for multi-choice games and communication networks. Section 3 introduces the model of multi-choice games with a communication network and discusses the implications of our interpretation for the interaction between participation levels and network communication. In Section 4, we present our solution and provide an axiomatic characterization. Section 5 establishes the stability result, while Section 6 illustrates the framework through its application to sequencing problems. Finally, Section 7 concludes.

# 2 Preliminaries

We denote by $|A|$ the number of elements in any finite set $A \subset \mathbb{N}$. Consider any $A \subset \mathbb{N}$ and any $s \in \mathbb{R}^{|A|}$.
For each non-empty subset $B \subseteq A$, we denote by $(s^{-B}, j) \in \mathbb{R}^{|A|}$ the vector such that $(s^{-B}, j)_i = j$ for each $i \in B$ and $(s^{-B}, j)_i = s_i$ otherwise. If $B = \{i\}, i \in A$, then we will make an abuse of notation and use $(s^{-i}, j)$ instead of $(s^{-\{i\}}, j)$. We also define the vector $s^B = (s^{-A\setminus B}, 0)$ such that $(s^B)_i = s_i$ if $i \in B$ and $(s^B)_i = 0$ otherwise. If $B = \{i\}, i \in A$, then we will use $s^i$ instead of $s^{\{i\}}$.

We denote by $e^B \in \mathbb{R}^{|A|}$ the vector such that $e_i^B = 1$ if $i \in B$ and $e_i^B = 0$ otherwise. If $B = \{i\}, i \in A$, then we will use $e^i$ instead of $e^{\{i\}}$. Observe that, for each $s \in \mathbb{R}^{|A|}$, $s^i = s_i e^i$. For any two $s, t \in \mathbb{R}^{|A|}$, we use the notation $s \ge t$ when $s_i \ge t_i$ for each $i \in A$, and $s > t$ when $s \ge t$ and $s \ne t$. The symbol $||s||$ stands for the Manhattan norm $\sum_{i \in N} s_i$.

## 2.1 Multi-choice games

Throughout the paper, we fix a finite set of agents $N = \{1, \dots, n\}$. Each agent $i \in N$ has a finite set of pairwise distinct and linearly ordered participation levels $\{0, \dots, m_i\}$, where $m_i$ is the maximal participation level of $i$. The vector $m = (m_1, \dots, m_n)$ plays the role of the grand coalition, whereas $\mathbf{0} = (0, \dots, 0)$ plays the role of the empty coalition. All vectors $\mathbf{0} \le s \le m$ are called (multi-choice) coalitions. For any two
$s, t \le m$, if $t \le s$, then $t$ is called a sub-coalition of $s$.

An **MC-game** is a couple $(m, v)$ where $v: \prod_{i \in N}\{0, \dots, m_i\} \to \mathbb{R}$ is a characteristic function, such that $v(0) = 0$, that specifies a real worth $v(s)$ to each coalition $s \le m$. Throughout the paper, we also fix $m \in \mathbb{N}^N$ so that, when no confusion arise, an MC-game is denoted by $v$. The class of MC-games with grand coalition $m$ is denoted by $\mathcal{V}^m$.

For any two MC-games $v, w \in \mathcal{V}^m$ and for any $c \in \mathbb{R}$, the MC-game $v + cw$ is such that, for each $s \le m$, $(v + cw)(s) = v(s) + cw(s)$. An MC-game $v \in \mathcal{V}^m$ is a null game if $v(s) = 0$ for each $s \le m$. When $m = (1, \dots, 1)$ an MC-game is just a cooperative game with transferable utility (TU-game for short).

Consider any $t \le m$. The minimal participation game $u_t$ is an MC-game in which each agent $i \in N$ is required to be active at least at his level $t_i$ to allow a coalition to generate a non-zero worth. Formally, those are defined, for each $t \le m$, as

$$ \forall s \le m, \quad u_t(s) = \begin{cases} 1 & \text{if } s \ge t, \\ 0 & \text{otherwise.} \end{cases} $$

For each MC-game $v \in \mathcal{V}^m$, the characteristic function $v$ admits a unique linear decomposition in terms of minimal participation games (Hsiao and Raghavan (1992)):

$$ v = \sum_{t \le m} \Delta_v(t) u_t, \quad (1) $$

where $\Delta_v(t)$ is called the (multi-choice) **Harsanyi dividend** of coalition $t$. This dividend represents the economic surplus generated by the coalition. Formally, they are defined recursively as

$$ \forall t \le m, \quad \Delta_v(t) = v(t) - \sum_{s<t} \Delta_v(s), $$

$$ \text{and} \quad \Delta_v(0, \dots, 0) = 0. $$

## 2.2 Communication networks

A (communication) network on $N$ is an undirected graph $(N, G)$, or $G$ for short, where $G = \{\{i, j\} : i, j \in N, i \ne j\}$ and $\{i, j\}$ represents a communication link between agents $i, j \in N$. We write $ij$ for a pair $\{i, j\}$ for convenience. In particular, $G^N$ denotes the complete network on $N$. Let $G^N = \{G : G \subseteq G^N\}$ be the set of all networks on $N$.

For any $G \in \mathcal{G}^N$, let $G_{-ij} = G \setminus \{ij\}$ be the network that remains after removing an existing link $ij$ in the network $G$. For $E \in 2^N$ and $G \in \mathcal{G}^N$, $G|_E = \{ij \in G : i, j \in E\}$ is the restricted network, or the subgraph of $G$ on $E$.
The direct neighbors of an agent $i \in N$ in $G$ is denoted by $N_i(G) = \{j \in N : \{i, j\} \in G\}$. Given a network $G \in \mathcal{G}^N$, a sequence of agents $i_1, \dots, i_h$ ($h \ge 2$) is a path from $i_1$ to $i_h$ in $G$ if $i_{t+1} \in N_i(G)$ for each $t = 1, \dots, h-1$. Coalition $E \in 2^N$ is connected in a network $G \in \mathcal{G}^N$ if there is a path from $i$ to $j$ for any two $i, j \in E$, or if $E$ is a singleton coalition, i.e., if it contains only one agent.

A coalition $E \in 2^N$ is a component of $G \in \mathcal{G}^N$ if $E$ is connected in $G$ and if $E \cup \{i\}$ is not connected in $G$ for any $i \notin E$. For each $E \in 2^N$, we denote by $E/G$ the partition of $E$ with respect to the components of $G|_E$.

# 3 Multi-choice games and communication networks

In this section, we first introduce the model of multi-choice games with a communication network and formally define the feasibility conditions for coalitions (sub-section 3.1). Next, we demonstrate that any non-feasible coalition can be uniquely decomposed into a collection of feasible sub-coalitions (sub-section 3.2). Finally, we apply these concepts and results to construct a network-restricted formulation of multi-choice games (sub-section 3.3).

## 3.1 Model and feasible coalitions

An MC-game with a communication network is couple $(v, G)$. The class of such games is denoted by $\mathcal{V}^m \times \mathcal{G}^N$. The set of active agents in some $s \le m$ is defined as $A(s) = \{i \in N : s_i > 0\}$. The set of maximally active agents in some $s \le m$ is defined as $M(s) = \{i \in N : s_i = m_i\}$.

In this paper, we assume that **agents are unable to communicate with other unless they have reached their maximal level** of participation. As a result, in any coalition $s \le m$, only those agents included in $M(s)$—the set of maximally participating agents—can potentially engage in communication, provided they are effectively connected, with other agents. To formalize this idea, we define a set of feasible coalitions comprising two distinct categories of counterfactual:

* **Singleton coalitions**, where only one agent is active. These represent situations in which a single agent participates independently, which is always considered feasible.

* **Maximally connected coalitions**, where all active agents are participating at their maximal levels, and are connected.

**Definition 1.** The set $\mathcal{F}(G)$ of **feasible coalitions** is defined as

$$ \mathcal{F}(G) = \{ke^i < m^i : i \in N \text{ and } k < m_i\} \cup \{m^E : E \subseteq N \text{ and } E \text{ is connected in } G\}. $$
The left hand side of the definition of the set of feasible coalitions corresponds to singleton coalitions, whereas the right hand side corresponds to maximally connected ones. Observe that singleton coalitions do not contain scenarios where the active agent is participating at its maximal level. This convention is for practical reasons since these scenarios are included in the second category.

It is clear that any coalition with at least two active and connected agents cannot be feasible if one of these agents is not participating at its maximal level. Similarly, if all active agents are maximally active, but are not connected in the graph, then the coalition is not feasible. Observe that $0 < m^i$, for each $i \in N$, is allowed, which makes the empty coalition a feasible coalition.

## 3.2 Decomposition into feasible sub-coalitions

Even if a coalition is not feasible, it can be decomposed into feasible sub-coalitions. The decomposition of a coalition is a collection of coalitions that sums to the original coalition. We propose a (minimal) decomposition of any coalition as a collection of feasible coalitions. This collection can be divided in two categories, just like the set of feasible coalitions.

Consider any coalition $s \le m$. The decomposition begins by identifying the active, but not maximally active, agents in $s$. For each such agent $i$, the singleton coalition $s^i$ is part of the decomposition. Next, we consider the set of maximally active agents in $s$ who are also connected in $G$. We are identifying the components of $M(s)$ induced by the restricted graph $G_{|M(s)}$. For each $E$ of these components, the coalition $m^E$ is part of the decomposition (note that $E$ can be a singleton).

**Definition 2.** For each $0 < s \le m$, its minimal decomposition into feasible coalitions is defined as

$$ \mathcal{D}_G(s) = \{s^i : i \in N \text{ and } 0 < s_i < m_i\} \cup \{m^E : E \in M(s)/G\}, $$

$$ \text{and verifies } s = \sum_{t \in \mathcal{D}_G(s)} t = \sum_{\substack{i \in N \\ 0 < s_i < m_i}} s^i + \sum_{E \in \mathcal{M}(s)/G} m^E. $$

The term *minimal* refers to the fact that other decompositions of coalitions into feasible coalitions are possible, but the decomposition we propose is the one using the minimal amount of feasible vectors to be defined. For instance, one could take any $E \in M(s)/G$, $|E| \ge 2$, and decompose $m^E$ as $\{m^i : i \in E\}$. In that case $(\mathcal{D}_G(s) \setminus \{m^E\}) \cup \{m^i : i \in E\}$ is still a decomposition of $s$ into feasible coalitions since each $m^i$, $i \in E$, is feasible by definition. However, this alternative decomposition uses a strictly larger number of coalitions to decompose $s$, and thus we do not qualify it as “minimal”. In fact, it can be shown that any other decompositions into feasible coalitions comprises of sub-coalitions of the elements of our minimal
decomposition. To avoid heavy formalism, we omit defining such alternative decompositions and focus on the minimal one.

Since $\mathcal{D}_G(s)$ is the minimal decomposition of a coalition $s$, there should not be any other decomposition that comprises of less feasible coalitions. A direct consequence of this observation is that any sub-coalition that is not a sub-coalition of any elements of the minimal decomposition of $s$ should not be feasible. Otherwise, this would contradict the definition of $\mathcal{D}_G(s)$. The following lemma expresses this idea.

**Lemma 1.** For any two $s, t \le m$ such that $t \le s$, if $t \not\le t'$ for every $t' \in \mathcal{D}_G(s)$, then $t \notin \mathcal{F}(G)$.

**Proof.** Consider any $s, t \le m$ such that $t \le s$, and such that $t \not\le t'$ for every $t' \in \mathcal{D}_G(s)$. Then one of the two scenarios holds:

(a) $0 < t_i \le s_i$ and $0 < t_j \le s_j$ for some $i, j \in N$ such that $s_i < m_i$ and/or $s_j < m_j$.

(b) $0 < t_i \le s_i$ and $0 < t_j \le s_j$ for some $i, j \in N$ such that $s_i = m_i$ and $s_j = m_j$, and $ij \notin G$.

In any case, it holds that $t \notin \mathcal{F}(G)$. Indeed, in (a), there exists a $i \in N$ such that $t_i < m_i$. Since, there exists a $j \in N$ such that $t_j > 0$, it follows that $t$ does not fall in any of the feasible categories of $\mathcal{F}(G)$. In (b), if $t_i = s_i$ and $t_j = s_j$, then $t$ is only feasible if $ij \in G$, which is not the case. Otherwise, the same argument than for (a) applies. $\square$

## 3.3 Restricted multi-choice game

Following the approach of Myerson, we define a restricted game using the concept of minimal decomposition. In this game, the value assigned to any coalition is the sum of the values of the sub-coalitions in its minimal decomposition. The interpretation is as follows: in a multi-choice setting, agents who do not participate at their maximal level are treated as isolated—they cannot cooperate with others. Only those who are maximally active and mutually connected can form cooperating groups. Thus, the notion of connected components introduced in Myerson applies exclusively to maximally participating agents, while non-maximally active agents remain singletons. As a result, the worth of any coalition is given by the sum of the values of singleton sub-coalitions and maximally connected sub-coalitions.

**Definition 3.** For each game $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ define the associated restricted game $v^G$ as

$$ \forall s \le m, \quad v^G(s) = \sum_{t \in \mathcal{D}_G(s)} v(t). $$
The next lemma provides an expression of the restricted game using Harsanyi dividends. It shows that only the dividends of feasible coalitions are relevant to defined the restricted game. Essentially, the lemma (and its proof) show that dividends of non feasible coalitions have a zero value in the restricted game.

**Lemma 2.** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, $v^G = \sum_{s \in \mathcal{F}(G) \setminus \{0\}} \Delta_{v^G}(s)u_s$.

**Proof.** Consider any $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$. To demonstrate this lemma, let us show that, for each $s \notin \mathcal{F}(G)$, it holds that $\Delta_{v^G}(s) = 0$. We proceed by induction on $||s||$. If $||s|| = 1$, then $s$ is always feasible and, by definition of $v^G$, $\Delta_{v^G}(s) = v^G(s) = v(s)$. If $||s|| = 2$ and $s$ is non feasible, then $s = s^i + s^j$ for some $i, j \in N$. Observe that $||s^i|| = 1$ and $||s^j|| = 1$, and thus $s^i$ and $s^j$ are feasible. Therefore, by the case $||s|| = 1$, it holds that $\Delta_{v^G}(s^i) = v(s^i)$ and $\Delta_{v^G}(s^j) = v(s^j)$. Finally, by definition of the dividends and of the restricted game $v^G$, we obtain

$$ \begin{aligned} \Delta_{v^G}(s) &= v^G(s) - \Delta_{v^G}(s^i) - \Delta_{v^G}(s^j) \\ &= v(s^i) + v(s^j) - v(s^i) - v(s^j) \\ &= 0. \end{aligned} $$

Assume that there exists a $W < ||m||$ such that, for each $s \le m$, where $||s|| \le W$ and $s \notin \mathcal{F}(G)$, it holds that $\Delta_{v^G}(s) = 0$. Let us show that for each $s \le m$ such that $||s|| = W + 1$ and $s \notin \mathcal{F}(G)$, it holds that $\Delta_{v^G}(s) = 0$.

$$ \begin{aligned} \Delta_{v^G}(s) &= v^G(s) - \sum_{t<s} \Delta_{v^G}(t) \\ &= \sum_{u \in \mathcal{D}_G(s)} v(u) - \sum_{t<s} \Delta_{v^G}(t) \\ &= \sum_{u \in \mathcal{D}_G(s)} \sum_{t \le u} \Delta_{v^G}(t) - \sum_{t<s} \Delta_{v^G}(t) \\ &= - \sum_{\substack{t<s \\ t \notin u, \forall u \in \mathcal{D}_G(s)}} \Delta_{v^G}(t). \end{aligned} $$

By Lemma 1 and the induction hypothesis, it holds that $\Delta_{v^G}(t) = 0$ for each $t < s$ such that $t \notin u$ for any $u \in \mathcal{D}_G(s)$. Consequently, we have shown that $\Delta_{v^G}(s) = 0$. This concludes the induction step and the proof of the lemma. $\square$

A direct consequence of Lemma 2 is that, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, the Harsanyi dividends of the restricted game $v^G$ can be expressed as

$$ \Delta_{v^G}(t) = \begin{cases} v(t) - \sum_{s<t} \Delta_{v^G}(s) & \text{if } t \in \mathcal{F}(G), \\ 0 & \text{otherwise.} \end{cases} $$
# 4 Characterization of a multi-choice Myerson value

This section begins with the definition of our value for multi-choice games with a communication network (sub-section 4.1). Then, we discuss new and classical axioms for multi-choice games, and provide an axiomatic characterization of our value (sub-section 4.2).

## 4.1 The My$^{KSZ}$ value

A agent-participation level pair, or simply a pair, $(i, k)$ represents an agent $i \in N$ and one of his (strictly positive) participation levels $0 < k \le m_i$. We use $M^+ = \cup_{i \in N} (\{i\} \times \{1, \dots, m_i\})$ to denote the set of all agent-participation level pairs. A payoff vector $x \in \mathbb{R}^{|M^+|}$ assigns a payoff $x_{ik} \in \mathbb{R}$ to each (positive) participation level $k$ of each agent $i$, or equivalently, to each pair $(i, k) \in M^+$. The real $x_{ik}$ captures the (incremental) payoff assigned to agent $i$ for an increase in participation from level $k-1$ to level $k$. A value on $\mathcal{V}^m \times \mathcal{G}^N$ is a map $f$ that assigns a unique payoff vector $f(v, G) \in \mathbb{R}^{|M^+|}$ to each $v \in \mathcal{V}^m$.

In this paper, we focus on values for MC-games that are inspired from the Shapley value (Shapley, 1953) for transferable utility games. It appears that there exists several ones. In this section, we only discuss the value introduced by Klijn et al. (1999), which we refer to as the Klijn-Slikker-Zarzuelo (KSZ) value.<fnref n="3" /> To that end, we must introduce the B-support of coalitions. For each $s \le m$, the B-support of $s$ is denoted by $B(s)$ and is defined as

$$B(s) = \{(i, k) \in M^+ : k \le s_i\}.$$

This support gathers all the pairs whose participation level can be considered as relevant to form $s$. The KSZ value is the unique value that divides the dividend of each coalition equally among the pairs in the B-support of the coalition. The value is defined, for each $v \in \mathcal{V}^m$, as

$$\forall (i, k) \in M^+, \quad KSZ_{ik}(v) = \sum_{\substack{s \le m \\ B(s) \ni (i, k)}} \frac{\Delta_v(s)}{|B(s)|}.$$

Klijn et al. (1999) provide an equivalent expression of KSZ in terms of average marginal contributions of the pairs $(i, k) \in M^+$. Define the bijection $\sigma : M^+ \to \{1, \dots, ||m||\}$ that assigns a unique position $\sigma(i, k) \in \{1, \dots, ||m||\}$ to each pair in $M^+$, and denote by $M^{+, \sigma(i, k)} \subseteq M^+$ the subset of pairs with a position less than or equal to $\sigma(i, k)$ in $\sigma$. Next, define the map $g$ that assigns to each every subset $T$ of

<footnote n="3">³The value was introduced in a broader context by Derks and Peters (1993), but Klijn et al. (1999) proposed the first formal representation of the value.</footnote>
$M^+$ the maximal coalition $g(T) \in \prod_{i \in N} \{0, \dots, m_i\}$ satisfying the following condition: for each $i \in N$, if $g_i(T) = k > 0$, then all pairs $(i, 1), \dots, (i, k)$ belong to $T$. Formally,

$$g_i(T) = \begin{cases} \max\{k \le m_i : (i, 1), \dots, (i, k) \in T\} & \text{if } (i, 1) \in T, \\ 0 & \text{otherwise.} \end{cases}$$

From this, the marginal contribution of the pair $(i, k) \in M^+$ in $v$ with respect to $\sigma$ is given by

$$v(g(M^{+, \sigma, \sigma(i,k)})) - v(g(M^{+, \sigma, \sigma(i,k)-1})),$$

with the convention $M^{+, \sigma, 0} = \emptyset$. An equivalent expression of the value $KSZ_{ik}(v)$ is given by the average of the marginal contributions of the pair $(i, k) \in M^+$ over all possible bijections $\sigma$.

$$\forall (i, k) \in M^+, \quad KSZ_{ik}(v) = \sum_{\sigma} \frac{1}{||m||!} \left( v(g(M^{+, \sigma, \sigma(i,k)})) - v(g(M^{+, \sigma, \sigma(i,k)-1})) \right). \quad (2)$$

According to this expression, $KSZ$ can be interpreted as the Shapley value (Shapley (1953)) of the TU-game $(M^+, w_{v,g})$ where $w_{v,g}(T) = v(g(T))$ for each coalition of pairs $T \subseteq M^+$.

We have the material to define a value for MC-games enriched with a communication network. We denote this value by $My^{KSZ}$ as a reference to the Myerson value and the $KSZ$ value from which it is built upon. It is computed, for each MC-games enriched with a communication network, as the $KSZ$ value of the corresponding restricted game. Using Lemma 2, we propose an expression of the value in terms of Harsanyi dividends.

**Definition 4.** The $My^{KSZ}$ value is defined, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, as

$$\forall (i, k) \in M^+, \quad My_{ik}^{KSZ}(v, G) = KSZ_{ik}(v^G).$$

**Lemma 3.** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, it holds that

$$\forall (i, k) \in M^+, \quad My_{ik}^{KSZ}(v, G) = \sum_{\substack{s \in \mathcal{F}(G) \\ B(s) \ni (i, k)}} \frac{\Delta_{v^G(s)}}{|B(s)|}.$$

**Proof.** The proof is direct from Definition 4 and Lemma 2. $\square$

We provide an example to demonstrate how the $My^{KSZ}$ value is applied.

**Example 1.** Let $N = \{1, 2, 3\}$ and $m_i = 2$ for any $i \in N$. Suppose that $G = \{12, 23\}$. Then, by definition,

$$\mathcal{F}(G) = \{ke^i : i \in N \text{ and } k = 0, 1\} \cup \{(2, 0, 0), (0, 2, 0), (0, 0, 2), (2, 2, 0), (0, 2, 2), (2, 2, 2)\}.$$
We consider the $My^{KSZ}$ value for $v = u_{(1,0,1)}$. By Lemma 2, it holds that $v^G = u_{(2,2,2)}$. Therefore, we have $My_{ik}^{KSZ}(v, G) = 1/6$ for any $(i, k) \in M^+$. Note that $KSZ_{ik}(v) = 1/2$ for $(i, k) = (1, 1), (3, 1)$, and $0$ otherwise.

In this example, agents 1 and 3 must both participate at least at level 1 to generate any worth. However, they can cooperate only if two conditions are met: both must reach their maximal level of participation, and agent 2 must also participate at its maximal level to connect them within the network. Hence, $v^G = u_{(2,2,2)}$. This explains why all pairs receive the same payoff: worth can be generated only by the grand coalition.

## 4.2 Axiomatic study

Next, we present an axiomatic characterization of the $My^{KSZ}$ value based on four axioms. The first, Component Efficiency, states that for any component of $G$, the sum of the cumulative payoffs across all agent levels within the component must equal its worth. This axiom is conceptually aligned with the original Component Efficiency axiom for values of transferable utility games with a communication structure.

The underlying rationale is that, since no communication occurs between members of different components, the worth generated within each component should be distributed entirely among its members, with no transfers to or from other components.

**Component Efficiency (CE).** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$,

$$ \forall E \in N/G, \quad \sum_{i \in E} \sum_{k \le m_i} f_{ik}(v, G) = v(m^E). $$

The second axiom, Level Network Fairness, examines the effects of deleting a link in the communication network. The axiom states that for any two pairs, each consisting of one agent from either side of the deleted link, the payoff variation resulting from the deletion should be the same, independently on the level considered. This axiom is conceptually aligned with the Network Fairness axiom for values of transferable utility games with a communication structure.

The underlying rationale is that the joint production attributable to the two agents connected by the link was equally distributed across their respective participation levels. Consequently, deleting the link leads to a payoff loss for these levels. Notably, in cumulative terms, the agent with the higher maximal participation level will experience a greater overall impact.

**Level Network Fairness (LNF).** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, and each $ij \in G$,

$$ \forall k \le m_i, \forall l \le m_j, \quad f_{ik}(v, G) - f_{ik}(v, G_{-ij}) = f_{jl}(v, G) - f_{jl}(v, G_{-ij}). $$
The third axiom, Restricted Null Pair, states that if an agent is unproductive from a certain level, and has no neighbors in the graph, then they should receive a zero payoff for that level. To formalize the axiom, we define the notion of unproductive and null pairs. A pair $(i, j) \in M^+$ is unproductive in some $v \in \mathcal{V}^m$ if $v(s^{-i}, j) = v(s)$ for each $s \le m$ such that $s_i = j - 1$. A pair $(i, j) \in M^+$ is null in some $v \in \mathcal{V}^m$ if each pair $(i, j')$, such that $j \le j' \le m_i$, is an unproductive pair. A null pair represents a participation level from which an agent stops contributing to the game.

The Restricted Null Pair axiom builds on the Null Pair axiom introduced by Klijn et al. (1999) to characterize the KSZ value. The original Null Pair axiom states that each null pair should receive a zero payoff. We adopt the same outcome, but under the additional condition that the agent in question is unconnected to the rest of the agent set. The intuition is that even if an agent becomes unproductive beyond a certain participation level, they may still be essential to the network by enabling communication between other agents. In other words, some worth cannot be generated without their full participation in cooperative activities. Consequently, the agent may receive a positive payoff for their otherwise unproductive levels. Therefore, we must consider an additional condition of un-connectedness to prescribe null payoffs to null pairs.

**Restricted Null Pair (RNP).** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, and each $(i, k) \in M^+$, if $(i, k)$ is a null pair and $N_i(G) = \emptyset$, then $f_{ik}(v, G) = 0$.

The last axiom, Intra-Fairness, advocates that if an agent stops being productive from a certain level, then all levels below should be equally impacted in terms of payoffs. The axiom is conceptually close to the Equal Loss axiom introduced by Klijn et al. (1999) to characterize the KSZ value. However, Equal Loss examines counterfactual scenarios in which some agent reduces their maximal participation level. Instead, Intra-Fairness examines what happens if some agent nullifies one of its participation level. In addition, the axiom requires that the agent has no neighbors in the network.

To properly define the axiom, we introduce a notation. For each $v \in \mathcal{V}^m$ and each $(i, k) \in M^+$, define the game $v_{-(i,k)}$, for each $s \le m$, as $v_{-(i,k)}(s) = v(s^{-i}, k-1)$ if $s_i \ge k$, and $v_{-(i,k)}(s) = v(s)$ otherwise. In $v_{-(i,k)}(s)$, the pair $(i, k)$ has been nullified. In other words, agent $i$ is no longer productive starting from its level $k$.

**Intra-Fairness (IF).** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, each $i \in N$ such that $N_i(G) = \emptyset$, and each $k \le m_i$, $\forall k', k'' \le k$, $f_{ik'}(v, G) - f_{ik'}(v_{-(i,k)}, G) = f_{ik''}(v, G) - f_{ik''}(v_{-(i,k)}, G)$.

**Theorem 1.** A value for MC-games with a communication network $f$ satisfies Component Efficiency (CE), Level Network Fairness (LNF), Restricted Null Pair (RNP), and Intra-Fairness (IF) if and only if $f = My^{KSZ}$.
**Proof. Existence:** We show that $My^{KSZ}$ satisfies all the axioms invoked in Theorem 1.

**Component Efficiency (CE):** Take any $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, and any $E \in N/G$. Let us show that

$$ \sum_{i \in E} \sum_{k \le m_i} My_{ik}^{KSZ}(v, G) = v(m^E). $$

First, we show that $My^{KSZ}$ satisfies (CE) in $(v', G)$ where $v'$ is derived from $v$ by nullifying the agents outside the component $E$, i.e., $(i, 1)$ is null in $v'$ for each $i \in N \setminus E$.

Observe that $v'(s) = v(s^E)$ for each $s \le m$, and that $v'(t) = 0$ for each $t \le m$ such that $A(t) \cap E = \emptyset$. By Definition 3, it follows that

$$ \forall s \le m, \quad v'^G(s) = \sum_{\substack{t \in \mathcal{D}_G(s) \\ A(t) \subseteq E}} v'(t). $$

Observe that $v'^G(s^{-i}, k) = v'^G(s^{-i}, k - 1)$ for each $s \le m$, each $i \in N \setminus E$, and each $1 \le k \le m_i$. That is the pair $(i, 1)$ is null in $v'^G$, for each $i \in N \setminus E$.

Klijn et al. (1999) proved that KSZ satisfies the Null Pair axiom (null pairs should receive a zero payoff) and Efficiency (the sum of the payoffs should be equal to the worth of the grand coalition $m$). By Definition 4, we obtain

$$ \sum_{i \in E} \sum_{k \le m_i} My_{ik}^{KSZ}(v', G) = \sum_{i \in E} \sum_{k \le m_i} KSZ_{ik}(v'^G) = v'^G(m). $$

Since $v'(t) = 0$ for each $t \le m$, $A(t) \cap E = \emptyset$, by Definition 3, it follows that $v'^G(m) = v'(m^E)$. Therefore, we obtain $v'^G(m) = v(m^E)$.

It remains to show that, for each $i \in E$ and each $1 \le k \le m_i$, $My_{ik}^{KSZ}(v, G) = My_{ik}^{KSZ}(v', G)$. By Lemma 3, it suffices to show that $\Delta_{v,G}(s) = \Delta_{v',G}(s)$, for each $s \in \mathcal{F}(G)$, $B(s) \ni (i, k)$.

Take any $s \in \mathcal{F}(G)$, $B(s) \ni (i, k)$. By Definition 1, it holds that $s \le m^E$, since $k > 0$. Therefore, $v'(s) = v(s)$. In addition, each $t < s$ satisfies $t \le m^E$. Thus, for each $t < s$, $v'(t) = v(t)$. This shows that we have $\Delta_{v,G}(s) = \Delta_{v',G}(s)$. Therefore, $My^{KSZ}$ satisfies (CE).

**Restricted Null Pair (RNP):** Take any $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ and any $(i, k) \in M^+$ such that $N_i(G) = \emptyset$. Assume that $(i, k)$ is a null pair in $v$. Let us show that $My_{ik}^{KSZ}(v, G) = 0$.

By Lemma 3, it suffices to show that $\Delta_{v,G}(s) = 0$ for each $s \in \mathcal{F}(G)$ such that $B(s) \ni (i, k)$. First, we show that the pair $(i, k)$ is null in $v^G$. Take any $k \le k' \le m_i$ and any $s = (s^{-i}, k') \le m$. By Definition 3, $v^G(s) = v^G(s^{-i}, k' - 1)$ since $N_i(G) = \emptyset$ and the pair $(i, k)$ is null in $v$. Thus, it holds that $(i, k)$ is a null pair in $v^G$.

Now, take any $s \in \mathcal{F}(G)$ such that $B(s) \ni (i, k)$. By Definition 1, $s$ is a singleton since $N_i(G) = \emptyset$ and $k > 0$. In addition, we have $s_i \ge k$ since $(i, k) \in B(s)$. By Proposition 7 in Lowing and Yokoo (2025), it
follows that $\Delta_{vG}(s) = 0$ holds, since the pair $(i, k)$ is null in $v^G$. This shows that $My^{KSZ}$ satisfies (RNP).

**Level Network Fairness (LNF):** Take any $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, any $ij \in G$, any $k \le m_i$, and any $l \le m_j$. Let us show that

$$ My_{ik}^{KSZ}(v, G) - My_{ik}^{KSZ}(v, G_{-ij}) = My_{jl}^{KSZ}(v, G) - My_{jl}^{KSZ}(v, G_{-ij}). $$

Take any $s \in \mathcal{F}(G)$, $B(s) \ni (i, k)$. One of the following cases holds: $s \in \mathcal{F}(G_{-ij})$ and $j \notin A(s)$, $s \in \mathcal{F}(G_{-ij})$ and $j \in A(s)$, or $s \in \mathcal{F}(G) \setminus \mathcal{F}(G_{-ij})$.

Take any $s \in \mathcal{F}(G_{-ij})$ such that $j \notin A(s)$, and any $t \le s$. It holds that $\mathcal{D}_G(t) = \mathcal{D}_{G_{-ij}}(t)$. By Definition 3, it follows that $v^G(t) = v^{G_{-ij}}(t)$. Thus, we have that $\Delta_{vG}(s) = \Delta_{v^{G_{-ij}}}(s)$ for each $s \in \mathcal{F}(G_{-ij})$ such that $B(s) \ni (i, k)$ and $j \notin A(s)$. Therefore,

$$ My_{ik}^{KSZ}(v, G) - My_{ik}^{KSZ}(v, G_{-ij}) = \sum_{\substack{s \in \mathcal{F}(G_{-ij}) \\ j \in A(s) \\ B(s) \ni (i, k)}} \frac{(\Delta_{v^G}(s) - \Delta_{v^{G_{-ij}}}(s))}{|B(s)|} + \sum_{\substack{s \in \mathcal{F}(G) \setminus \mathcal{F}(G_{-ij}) \\ B(s) \ni (i, k)}} \frac{\Delta_{v^G}(s)}{|B(s)|}. \quad (3) $$

By Definition 1, for each $s \in \mathcal{F}(G_{-ij})$ such that $j \in A(s)$ and $B(s) \ni (i, k)$, we have $s_i = m_i$ and $s_j = m_j$, since $k > 0$. In addition, for each $s \in \mathcal{F}(G) \setminus \mathcal{F}(G_{-ij})$, we have $s_i = m_i$ and $s_j = m_j$. Thus, $B(s) \ni (i, k)$ in any case, and (3) becomes

$$ My_{ik}^{KSZ}(v, G) - My_{ik}^{KSZ}(v, G_{-ij}) = \sum_{\substack{s_i=m_i \\ s_j=m_j}} \frac{(\Delta_{v^G}(s) - \Delta_{v^{G_{-ij}}}(s))}{|B(s)|} + \sum_{\substack{s \neq \mathbf{0} \\ s \in \mathcal{F}(G) \setminus \mathcal{F}(G_{-ij})}} \frac{\Delta_{v^G}(s)}{|B(s)|}. $$

The same reasoning and result applies to $(j, l)$. Therefore, we obtain the desired result. This shows that $My^{KSZ}$ satisfies (LNF).

**Intra-Fairness (IF):** Take any $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, any $i \in N$ such that $N_i(G) = \emptyset$, and any $k', k'' \le k \le m_i$. Let us show that

$$ My_{ik'}^{KSZ}(v, G) - My_{ik'}^{KSZ}(v_{-(i,k)}, G) = My_{ik''}^{KSZ}(v, G) - My_{ik''}^{KSZ}(v_{-(i,k)}, G). $$

Take any $s \in \mathcal{F}(G)$ such that $B(s) \ni (i, k')$. One of the following cases holds: either $B(s) \ni (i, k)$ or $B(s) \niiid (i, k)$. By Definition 1, it holds that $s$ is a singleton, since $N_i(G) = \emptyset$. Therefore, $s = s_i e_i$, $s_i \ge k'$, where $s_i \ge k$ if $B(s) \ni (i, k)$, and $s_i < k$ otherwise.

Assume that $B(s) \ni (i, k)$. Observe that the pair $(i, k)$ is null in $v_{-(i,k)}$. We have shown in case (RNP) that this implies that $\Delta_{v^G_{-(i,k)}}(s) = 0$, for $B(s) \ni (i, k)$.
Now, consider the case where $B(s) \ni (i, k')$ and $B(s) \nmid (i, k)$. Take any $t \le s$. We have $v_{-(i,k)}(t) = v(t)$, since $t_i \le s_i < k$. Also, $t$ is a singleton since $s$ is a singleton. By Definition 3, it follows that $v^G(t) = v^G_{-(i,k)}(t)$, and thus, $\Delta_{v^G}(s) = \Delta_{v^G_{-(i,k)}}(s)$. It follows that we have

$$ 
\begin{aligned}
My_{ik'}^{KSZ}(v, G) - My_{ik'}^{KSZ}(v_{-(i,k)}, G) &= \sum_{\substack{s \in \mathcal{F}(G) \\ B(s) \ni (i,k) \\ B(s) \ni (i,k')}} \frac{\Delta_{v^G}(s)}{|B(s)|} \\
&= \sum_{\substack{s \in \mathcal{F}(G) \\ B(s) \ni (i,k)}} \frac{\Delta_{v^G}(s)}{|B(s)|}.
\end{aligned}
$$

The second equality follows from the fact that $k \ge k'$. The same reasoning and result applies to $(i, k'')$. Therefore, we obtain the desired result. This shows that $My^{KSZ}$ satisfies (IF).

**Uniqueness:** We demonstrate that if a value satisfies (CE), (LNF), (RNP), and (IF), then it is unique. Denote by $f$ such a value. Let us show that $f(v, G)$ is uniquely determined for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$. We proceed by induction on the number of links in $G$, which we denote by $l(G)$.

**Initialization:** Assume that there is no link in the communication network, i.e., $l(G) = 0$ and $N_i(G) = 0$ for each $i \in N$. Let us show that, in that case, $f(v, G)$ is uniquely determined. To that end, we proceed by induction on the number of non-null participation levels. Consider any $i \in N$.

**Initialization:** Consider the game $(v_{-(i,1)}, G)$. In this game, $(i, 1)$ is a null pair, and thus, all pairs $(i, k)$, $k \le m_i$, are null pairs. By (RNP), $f_{ik}(v_{-(i,1)}, G) = 0$ for each $k \le m_i$. Next, consider the game $(v_{-(i,2)}, G)$. In this game, $(i, 2), \dots, (i, m_i)$ are null pairs, and thus, by (RNP), $f_{ik}(v_{-(i,2)}, G) = 0$ for each $2 \le k \le m_i$. By (CE), we also have that $f_{i1}(v_{-(i,2)}, G) = v_{-(i,2)}(m^i)$. We can conclude that $f_{ik}(v_{-(i,2)}, G)$ is uniquely determined for each $k \le m_i$.

**Hypothesis:** Next, assume that there exists a $2 \le k' < m_i$ such that $f_{ik}(v_{-(i,k')}, G)$ is uniquely determined for each $k \le m_i$.

**Induction:** In the case where $k' < m_i$, let us show that $f_{ik}(v_{-(i,k'+1)}, G)$ is uniquely determined for each $k \le m_i$. By (RNP), $f_{ik}(v_{-(i,k'+1)}, G) = 0$ for each $k \ge k' + 1$. Combining this observation with (CE), we obtain that

$$ \sum_{k \le k'} f_{ik}(v_{-(i,k'+1)}, G) = v_{-(i,k'+1)}(m^i) \quad (4) $$
Then, by (IF),

$$ \forall k < k', \quad f_{ik}(v_{-(i,k'+1)}, G) - f_{ik'}(v_{-(i,k'+1)}, G) = f_{ik}(v_{-(i,k')}, G) - f_{ik'}(v_{-(i,k')}, G). \quad (5) $$

By the induction hypothesis, the right hand side of each equation depicted by (5) is uniquely determined. Combining the equations in (5) with (4), one obtains $k'$ linearly independent equations with $k'$ unknowns. These equations form a solvable system of equations with a unique solution. Therefore, $f_{ik}(v_{-(i,k'+1)}, G)$ is uniquely determined for each $k \le m_i$.

Finally, let us show that if $k' = m_i$, then $f_{ik}(v, G)$ is uniquely determined for each $k \le m_i$. By (IF),

$$ \forall k < m_i, \quad f_{ik}(v, G) - f_{im_i}(v, G) = f_{ik}(v_{-(i,m_i)}, G) - f_{im_i}(v_{-(i,m_i)}, G). \quad (6) $$

By the induction hypothesis, the right hand side of each equation depicted by (6) is uniquely determined. Combining (6) with (CE), one obtains $m_i$ linearly independent equations with $m_i$ unknowns. These equations form a solvable system of equations with a unique solution. Therefore, $f_{ik}(v, G)$ is uniquely determined for each $k \le m_i$. This concludes the induction.

We have shown that, for each $i \in N$, $f_{ik}(v, G)$ is uniquely determined for each $k \le m_i$ when $l(G) = 0$.

**Hypothesis:** Assume that there exists an integer $W < \frac{n(n-1)}{2}$ such that if $l(G) = W$, then $f(v, G)$ is uniquely determined.

**Induction:** Let us show that $f(v, G)$ is uniquely determined when $l(G) = W + 1$. Consider any component $E \in N/G$. Assume that $|E| = 1$, i.e., $E = \{i\}$ for some $i \in N$. Then, we can show that, for each $k \le m_i$, $f_{ik}(v, G)$ is uniquely determined by using the same arguments than in the initialization step. Assume that $|E| \ge 2$. For each $i \in E$, we can generate, by (LNF), the following equations

$$ \forall k \le m_i, \forall l \le m_j, \quad f_{ik}(v, G) - f_{jl}(v, G) = f_{ik}(v, G_{-ij}) - f_{jl}(v, G_{-ij}), \quad (7) $$

where $j \in N_i(G)$ is an arbitrary agent linked to $i$. By the hypothesis, the right hand side of (7) is uniquely determined. From (7) and (CE), it is possible to derive $(\sum_{k \in E} m_k)$ linearly independent equations with as many variables. For clarity, and without loss of generality, let us label agents in $E$ as $i_1, \dots, i_e$, so that agent
$i_1$ is the neighbor of agent $i_2$, which in turn is the neighbor of agent $i_3$, and so on.

$$f_{i_1 1}(v, G) - f_{i_2 1}(v, G) = f_{i_1 1}(v, G_{-i_1 i_2}) - f_{i_2 1}(v, G_{-i_1 i_2})$$

$$f_{i_1 2}(v, G) - f_{i_2 1}(v, G) = f_{i_1 2}(v, G_{-i_1 i_2}) - f_{i_2 1}(v, G_{-i_1 i_2})$$

$\vdots$

$$f_{i_1 m_{i_1}}(v, G) - f_{i_2 1}(v, G) = f_{i_1 m_{i_1}}(v, G_{-i_1 i_2}) - f_{i_2 1}(v, G_{-i_1 i_2})$$

$$f_{i_2 1}(v, G) - f_{i_3 1}(v, G) = f_{i_2 1}(v, G_{-i_2 i_3}) - f_{i_3 1}(v, G_{-i_2 i_3})$$

$\vdots$

$$f_{i_2 m_{i_2}}(v, G) - f_{i_3 1}(v, G) = f_{i_2 m_{i_2}}(v, G_{-i_2 i_3}) - f_{i_3 1}(v, G_{-i_2 i_3})$$

$\vdots$

$$f_{i_{e-1} m_{i_{e-1}}}(v, G) - f_{i_e 1}(v, G) = f_{i_{e-1} m_{i_{e-1}}}(v, G_{-i_{e-1} i_e}) - f_{i_e 1}(v, G_{-i_{e-1} i_e})$$

$$f_{i_e 2}(v, G) - f_{i_{e-1} 1}(v, G) = f_{i_e 2}(v, G_{-i_{e-1} i_e}) - f_{i_{e-1} 1}(v, G_{-i_{e-1} i_e})$$

$$f_{i_e 3}(v, G) - f_{i_{e-1} 1}(v, G) = f_{i_e 3}(v, G_{-i_{e-1} i_e}) - f_{i_{e-1} 1}(v, G_{-i_{e-1} i_e})$$

$\vdots$

$$f_{i_e m_{i_e}}(v, G) - f_{i_{e-1} 1}(v, G) = f_{i_e m_{i_e}}(v, G_{-i_{e-1} i_e}) - f_{i_{e-1} 1}(v, G_{-i_{e-1} i_e})$$

$$\sum_{i \in E} \sum_{k \le m_i} f_{ik}(v, G) = v(m^E).$$

The system is constructed as follows. First, we relate the payoffs of all levels of agent $i_1$ to the payoff of the first level of agent $i_2$. Next, we relate the payoffs of all levels of agent $i_2$ to the payoff of the first level of agent $i_3$, and so on, continuing this process up to agent $i_{e-1}$. Agent $i_e$ is treated differently: the payoffs of its levels 2 through $m_e$ are related to the payoff of the first level of agent $i_{e-1}$.

The resulting set of equations, together with the final equation (CE), defines a system of $(\sum_{k \in E} m_k)$ linearly independent equations with $(\sum_{k \in E} m_k)$ unknowns, resulting in a unique solution. It follows that the full system of linear equations obtained by (LNF) and (CE) admits at most one solution. Thus, $f(v, G)$ is uniquely determined when $l(G) = W + 1$. This ends the induction step.

By the existence part, $My^{KSZ}$ satisfies all the axioms of the statement of the theorem. We conclude that $f = My^{KSZ}$. This ends the proof of the theorem.

□
The axioms invoked in the statement of Theorem 1 are logically independent as shown by the following counter-examples.

* The null value defined, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ and each $(i, k) \in M^+$, as $f_{ik}(v, G) = 0$, satisfies all the axioms aside from Component Efficiency (CE).

* Define $\Gamma(i) = \{ke^i : k \le m_i\}$ for each $i \in N$. The value $f$ defined, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ and each $(i, k) \in M^+$, as

$$ \forall (i, k) \in M^+, \quad f_{ik}(v, G) = \sum_{s \in \Gamma(i)} \frac{\Delta_{vG}(s)}{|B(s)|} + \sum_{\substack{s \in \mathcal{F}(G) \\ B(s) \ni (i, k) \\ s \notin \Gamma(i)}} \frac{\Delta_{vG}(s)}{|A(s)|}, $$

satisfies all the axioms aside from Level Network Fairness (LNF).

* The value $f$ defined, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ and each $(i, k) \in M^+$, as

$$ \forall E \in N/G, \forall i \in E, \forall k \le m_i, \quad f_{ik}(v, G) = \frac{v(m^E)}{\sum_{j \in E} m_j} $$

satisfies all the axioms aside from Restricted Null Pair (RNP).

* The value $f$ defined, for each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$ and each $(i, k) \in M^+$, as

$$ \forall (i, k) \in M^+, \quad f_{ik}(v, G) = \sum_{s \in \Gamma(i)} \frac{\Delta_{vG}(s)}{|A(s)|} + \sum_{\substack{s \in \mathcal{F}(G) \\ B(s) \ni (i, k) \\ s \notin \Gamma(i)}} \frac{\Delta_{vG}(s)}{|B(s)|}, $$

satisfies all the axioms aside from Intra-Fairness (IF).

# 5 Stability of the MyKSZ value

A value is said to be stable on a given domain of MC-games with a communication network if, for every game in this class, the removal of any link never results in a strict increase in the payoffs of the agents connected by that link. Equivalently, the establishment of a communication link between two agents is always mutually beneficial. Stability for a value has been introduced by Myerson (1977) for situations where the maximal participation level of each agent is 1, i.e., for standard transferable utility games. We generalize this requirement to fit the framework of MC-games.

**Stability (S).** For each $(v, G) \in \mathcal{V}^m \times \mathcal{G}^N$, each communication link $\{i, j\} \in G$,

$$ \forall (i, k), (j, k') \in M^+, \quad f_{ik}(v, G) \ge f_{ik}(v, G_{-ij}) \quad \text{and} \quad f_{jk'}(v, G) \ge f_{jk'}(v, G_{-ij}). $$
To state the following result, we define a property for characteristic functions, which indicates that two disjoint coalitions always have an interest in merging.

**Definition 5.** A characteristic function $v \in \mathcal{V}^N$ is **superadditive** if for any two coalitions $s$ and $s'$ such that $A(s) \cap A(s') = \emptyset$,

$$v(s + s') \geq v(s) + v(s').$$

**Theorem 2.** The multi-choice Myerson value $My^{KSZ}$ satisfies Stability (S) on the domain of MC-games with a communication network where the characteristic function of the MC-games is superadditive.

**Proof.** Pick any MC-game with a communication network $(v, G)$ as hypothesized. Consider any nonempty coalition $s$. By definition of $\mathcal{D}_G(s)$, the subsets of agents that define $\mathcal{D}_G(s)$, that is the singletons and the connected sets $E \subseteq N$ of $G$, form a partition of $N$. In addition, for each communication link $\{i, j\}$ of $G$, that partition of $N$ associated with $\mathcal{D}_{G-ij}(s)$ is finer or equivalent to that associated with $\mathcal{D}_G(s)$. Therefore, using superadditivity of $v$,

$$v^G(s) = \sum_{t \in \mathcal{D}_G(s)} v(t) \geq \sum_{t' \in \mathcal{D}_{G-ij}(s)} v(t') = v^{G-ij}(s),$$

so that the MC-game $v^G - v^{G-ij}$ is non-negative. In particular if $i \notin A(s)$ and $0 \leq k' < k \leq m_i$,

$$(v^G - v^{G-ij})(s + k e^i) - (v^G - v^{G-ij})(s + k' e^i) \geq 0. \quad (8)$$

Inequality (8) is a consequence of the following cases.

**Case 1:** $0 \leq k' < k < m_i$. In this case,

$$(v^G - v^{G-ij})(s + k e^i) - (v^G - v^{G-ij})(s + k' e^i) = 0.$$

To see this, remark that the partition of $N$ associated with $\mathcal{D}_G(s+ke^i)$ coincides with the one associated with $\mathcal{D}_{G-ij}(s+ke^i)$, since $k < m_i$. In particular, $ke^i$ belongs to $\mathcal{D}_G(s+ke^i)$ and $\mathcal{D}_{G-ij}(s+ke^i)$. The same remark applies to $k' e^i$ with respect to the profile $s + k' e^i$. Using the definition of a restricted game, we obtain

$$(v^G - v^{G-ij})(s + k e^i) = (v^G - v^{G-ij})(s + k' e^i) = 0.$$

**Case 2:** $k = m_i$. Two sub-cases arise.

(a) All the neighbors (if any) of agent $i$ in $G$ do not participate at their maximal level so that the partition of $N$ associated with $\mathcal{D}_G(s + m^i)$ coincides with the one associated with $\mathcal{D}_{G-ij}(s + m^i)$ and
the same remains true for $\mathcal{D}_G(s + k'e^i)$ and $\mathcal{D}_{G-ij}(s + k'e^i)$. Similar to the case $0 \le k' < k < m_i$, (8) follows from the fact that

$$ (v^G - v^{G-ij})(s + m^i) = (v^G - v^{G-ij})(s + k'e^i) = 0, $$

by definition of the restricted games $v^G$ and $v^{G-ij}$.

(b) Agent $j$ chooses $m_j$. If the removal of the link $\{i, j\}$ does not disconnect the component of $G$ to which $i$ and $j$ belong, then $\mathcal{D}_G(s + m^i) = \mathcal{D}_{G-ij}(s + m^i)$ and $\mathcal{D}_G(s + k'e^i) = \mathcal{D}_{G-ij}(s + k'e^i)$. In that case, (8) follows from the same reasoning as above.

Next, if the removal of the link $\{i, j\}$ disconnects the component of $G$ to which $i$ and $j$ belong, the partition of $N$ associated with $\mathcal{D}_{G-ij}(s + m^i)$ is finer than the one associated with $\mathcal{D}_G(s + m^i)$. In this case, (8) follows from the superadditivity of $v$, which implies that

$$ (v^G - v^{G-ij})(s + m^i) \ge 0 = (v^G - v^{G-ij})(s + k'e^i). $$

Next, the payoff obtained by the pair $(i, k) \in M^+$ under $My^{KSZ}$ is given by

$$ My_{ik}^{KSZ}(v, G) = KSZ_{ik}(v^G) \quad \text{and} \quad My_{ik}^{KSZ}(v, G - ij) = KSZ_{ik}(v^{G-ij}). $$

KSZ is a linear value on $\mathcal{V}^m$ (see Klijn et al., 1999) so that

$$ My_{ik}^{KSZ}(v, G) - My_{ik}^{KSZ}(v, G - ij) = KSZ_{ik}(v^G - v^{G-ij}). $$

Using expression (2) of $KSZ_{ik}$ in terms of expected marginal contributions and (8), one obtains

$$ (v^G - v^{G-ij})(g(M^{+,\sigma,\sigma(i,k)})) - (v^G - v^{G-ij})(g(M^{+,\sigma,\sigma(i,k)-1})) \ge 0, $$

therefore

$$ KSZ_{ik}(v^G - v^{G-ij}) \ge 0, \quad \text{or equivalently} \quad My_{ik}^{KSZ}(v, G) \ge My_{ik}^{KSZ}(v, G - ij) $$

as asserted. The same reasoning applies to agent $j$. This concludes the proof of Theorem 2. □

# 6 Application to sequencing problems

In a one-machine sequencing environment, a group of agents forms a queue to perform a task on a single machine. Each task requires a fixed amount of processing time, and each unit of time spent waiting in the queue—including the time spent executing the task—imposes a disutility or cost on the agent. Agents
may have heterogeneous per-unit waiting costs, which creates the possibility of reducing the total cost by reordering the queue.

This gives rise to two central problems: determining the optimal queue that minimizes total cost, and allocating the resulting cost savings among the agents. Smith (1953) addresses the first problem by showing that the optimal queue is obtained by ordering agents according to their urgency indices in descending order, where an agent's urgency index is defined as the ratio of its unit cost to its task processing time. Curiel et al. (1989) tackle the second problem by proposing rules for sharing the cost savings. To this end, they formulate a sequencing cooperative game subject to a participation constraint: a coalition can reorganize its members within the queue provided that no member jumps over a non-member.

Each sequencing game can thus be represented as a cooperative game on a communication network. Specifically, the network is a line graph representing the initial queue, so a coalition is feasible if it forms a connected subset of the line. The characteristic function of such a sequencing game corresponds to the network-restricted characteristic function introduced by Myerson (1977) (see also van den Brink et al. (2007)).

Extensions of the Curiel et al. (1989) framework have considered features such as ready times, due dates, multiple machines, and multi-stage settings (see, for instance, Hamers et al., 1995, 1999; Borm et al., 2002; Slikker, 2006). In this paper, we propose a new extension in which agents can reduce their task processing times by exerting effort. Operating certain machines effectively requires learning, so agents may invest in training to acquire skills and routines that reduce their processing times.

Formally, let $N = \{1, \dots, n\}$ denote the set of agents forming a queue to use a machine. The **processing time** $t_i(s_i)$ for agent $i$'s task is a strictly decreasing function of the effort level $s_i \in \{1, \dots, m_i\}$, where $m_i$ corresponds to the effort level at which the agent fully masters the machine. Any lower effort level results in additional costs due to suboptimal task processing.

The **cost per unit of time** incurred by agent $i$ is constant and denoted by $c_i > 0$. Given a permutation $\rho$ of the agents in $N$ that specifies their positions in the queue, and a coalition $s$ in which all agents are active (i.e., $A(s) = N$), the cumulative processing time of agent $i$'s task and the corresponding cost are, respectively,

$$T_i(\rho, s) = \sum_{\substack{j \in N \\ \rho(j) \le \rho(i)}} t_j(s_j) \quad \text{and} \quad c_i T_i(\rho, s).$$

The **total cost** of processing the tasks in $N$ given a permutation $\rho$ and a coalition $s$ where all agents are
active is given by

$$C(\rho, s) = \sum_{i \in N} c_i T_i(\rho, s).$$

Without loss of generality, assume that the initial queue is given by $\rho^0$ with $\rho^0(i) = i$ for each $i \in N$. This queue can be represented by the line network

$$G^0 = \{\{i, i + 1\} : i \in N \setminus \{n\}\}.$$

For $i \le j$, let $[i, j] = \{i, i + 1, \dots, j\}$ denote a set of consecutive agents, with $[i, i]$ or $[i]$ representing the singleton $\{i\}$. A subset $E \subseteq N$ is connected in $G^0$ if either $E$ is empty or there exists a pair of agents $\{i, j\} \subseteq N$ such that $E = [i, j]$.

A nonempty coalition $s$ can generate **cost savings**, or additional costs, only if $s \in \mathcal{F}(G^0)$; that is, either $s = ke^i$ for some $k \in \{1, \dots, m_i\}$, or $s = m^{[i,j]}$ for some consecutive subset $[i, j]$ with $i \ne j$. In other words, a feasible coalition is either a singleton agent with the opportunity to reduce their task processing time (when $k < m_i$), or a group of consecutive agents in the line network who fully participate.

In the first case, the singleton agent has not yet acquired the skills necessary to fully master the machine. This limitation generates additional costs, making any change in queue position suboptimal. Only agents with sufficient skills can rearrange their positions to reduce the total cost. In the latter case, members of the consecutive group may exchange positions within the line network to minimize total cost. Thus, the participation constraint—requiring that the restricted network $G^0_{[i,j]}$ be connected—is supplemented by an incentive constraint, which motivates agents to achieve the lowest possible total cost.

If two consecutive agents $i$ and $i + 1$ (with $i$ preceding $i + 1$) switch positions, the resulting change in total cost is

$$c_{i+1}t_i(m_i) - c_i t_{i+1}(m_{i+1}).$$

If $i$'s urgency index $c_i/t_i(m_i)$ is strictly smaller than $i + 1$'s urgency index $c_{i+1}/t_{i+1}(m_{i+1})$, the swap reduces the total cost; otherwise, no gain is achieved. Accordingly, define the **cost saving** achievable by the direct neighbors $i$ and $i + 1$ switching positions as

$$\theta_{i,i+1}(m_i, m_{i+1}) = \max\{0, c_{i+1}t_i(m_i) - c_i t_{i+1}(m_{i+1})\}.$$

For singleton coalitions $s^i = ke^i$ with $k \in \{1, \dots, m_i\}$, define the **additional cost** incurred by choosing effort level $k$ rather than the maximum effort $m_i$ as

$$\theta_i(k) = c_i(t_i(m_i) - t_i(k)).$$
This quantity is negative for $k < m_i$ (since $t_i(\cdot)$ is strictly decreasing), is equal to zero for $k = m_i$, and it decreases as $k$ increases.

For a connected coalition $m^{[i,j]} \in \mathcal{F}(G^0)$, $i \neq j$, the optimal way to rearrange the members of $[i, j]$ is in order of decreasing urgency index. To do this, simply switch sequentially the neighbors that are not in the correct order. This leads to the following worth of $m^{[i,j]} \in \mathcal{F}(G^0)$ as the sum of gains of all possible switches in that coalition

$$v(m^{[i,j]}) = \sum_{q \in [i,j]} \sum_{\substack{p < q \\ p \in [i,j]}} \theta_{p,q}(m_p, m_q).$$

If $s^i = ke^i \in \mathcal{F}(G^0)$, then the worth is given by the additional cost

$$v(s^i) = \theta_i(k).$$

In case coalition $s \notin \mathcal{F}(G^0)$, its worth is given by the sum of the worth of its elements in $\mathcal{D}_{G^0}(s)$, that is

$$\sum_{t \in \mathcal{D}_{G^0}(s)} v(t).$$

It follows that this sequencing game is equal to the restricted game $v^{G^0}$ of the corresponding line-network multi-choice game $(v, G^0) \in \mathcal{V}^m \times \mathcal{G}^N$ given by Definition 3

$$v^{G^0}(s) = \sum_{t \in \mathcal{D}_{G^0}(s)} v(t).$$

In particular, the worth of the grand coalition $m$ is the total cost savings achieved by reorganizing its members in descending order of urgency index

$$v^{G^0}(m) = C(\rho^0, m) - \min_{\rho} C(\rho, m).$$

Applying the Myerson value $My^{KSZ}$ to the class of sequencing games, we obtain the following sharing rule of the total cost savings induced by the grand coalition.

**Theorem 3.** Let $(v, G^0) \in \mathcal{V}^m \times \mathcal{G}^N$ be a line-network game corresponding to the multi-choice sequencing situation $(m, \rho^0, (t_i, c_i)_{i \in N})$. Then,

$$\forall (i, k) \in M^+, \quad My_{ik}^{KSZ}(v, G^0) = \sum_{k'=k}^{m_i} \frac{\theta_i(k') - \theta_i(k' - 1)}{k'} + \sum_{\substack{m^{[p,q] \in \mathcal{F}(G^0)} \\ p \neq q \\ i \in [p,q]}} \frac{\theta_{p,q}(m_p, m_q)}{\sum_{j \in [p,q]} m_j}, \quad (9)$$

with the convention $\theta_i(0) = 0$ for each $i \in N$.
**Proof.** Let $(v, G^0)$ as hypothesized. By Lemma 2, $v^{G^0}$ writes

$$v^{G^0} = \sum_{s \in \mathcal{F}(G^0) \setminus \{0\}} \Delta_{v^{G^0}}(s)u_s.$$

Let us begin by computing the Harsanyi dividends $\Delta_{v^{G^0}}(ke^i)$ of the singleton coalitions $ke^i$, $i \in N$, $k \in \{1, \dots, m_i\}$.

**Claim 1:** Pick any $i \in N$ and any $k \in \{1, \dots, m_i\}$, $\Delta_{v^{G^0}}(ke^i) = \theta_i(k) - \theta_i(k-1)$ with the convention $\theta_i(0) = 0$.

The proof is by induction on the participation level $k$.

*Initialization:* If $k = 1$, then $\Delta_{v^{G^0}}(e^i) = v^{G^0}(e^i)$ where $v^{G^0}(e^i) = \theta_i(1)$, so that $\Delta_{v^{G^0}}(e^i) = \theta_i(1) - \theta_i(0)$ using the convention $\theta_i(0) = 0$.

*Hypothesis:* Assume that **Claim 1** is true up to participation level $k$, $1 \le k < m$.

*Induction:* Consider the participation level $k+1$. We have

$$\Delta_{v^{G^0}}((k+1)e^i) = v((k+1)e^i) - \sum_{k' \le k} \Delta_{v^{G^0}}(k'e^i).$$

By definition, $v^{G^0}((k+1)e^i) = \theta_i(k+1)$. Using the induction hypothesis, we get

$$\sum_{k' \le k} \Delta_{v^{G^0}}(k' e^i) = \sum_{k' \le k} (\theta_i(k') - \theta_i(k' - 1)) \\ = \theta_i(k).$$

so that $\Delta_{v^{G^0}}((k+1)e^i) = \theta_i(k+1) - \theta_i(k)$. This completes the induction step and **Claim 1** is proven.

Remark that

$$\Delta_{v^{G^0}}(m_i e^i) = -\theta_i(m_i - 1) \quad \text{and} \quad \sum_{k=1}^{m_i} \Delta_{v^{G^0}}(ke^i) = 0. \qquad (10)$$

Let us continue by computing the Harsanyi dividend $\Delta_{v^{G^0}}(m^{[i,j]})$, $i \ne j$, of the feasible coalition $m^{[i,j]} \in \mathcal{F}(G^0)$.

**Claim 2:** $\Delta_{v^{G^0}}(m^{[i,j]}) = \theta_{i,j}(m_i, m_j)$ for each feasible coalition $m^{[i,j]} \in \mathcal{F}(G^0)$, $i \ne j$.

The proof is by induction on the size $j-i+1 \ge 2$ of the group $[i, j]$.

*Initialization:* If $j-i+1 = 2$, then $j = i+1$. In such a case,

$$\Delta_{v^{G^0}}(m^{[i,i+1]}) = v^{G^0}(m^{[i,i+1]}) - \sum_{k=1}^{m_i} \Delta_{v^{G^0}}(ke^i) - \sum_{k=1}^{m_{i+1}} \Delta_{v^{G^0}}(ke^{i+1}) \\ = \theta_{i,j}(m_i, m_j),$$

where the second equality comes from the definition of $v^{G^0}(m^{[i,i+1]})$ and (10).
**Hypothesis:** Assume that **Claim 2** is true for each coalition $m^{[i,j]} \in \mathcal{F}(G^0)$ such that the size $i - j + 1$ of the group $[i, j]$ is less than or equal to $r$, $2 \le r < n$.

**Induction:** Pick any coalition $m^{[i,j]} \in \mathcal{F}(G^0)$ such that $j - i + 1 = r + 1$. By definition,

$$ \Delta_{vG^0}(m^{[i,j]}) = \sum_{q \in [i,j]} \sum_{p \le q} \theta_{p,q}(m_p, m_q) - \sum_{\substack{m^{[p,q]} \in \mathcal{F}(G^0) \\ [p,q] \subseteq [i,j] \\ p < q}} \Delta_{vG^0}(m^{[p,q]}) - \sum_{p \in [i,j]} \sum_{k=1}^{m_p} \Delta_{vG^0}(ke^p) $$

Note that the first expression of the right hand side of the above equality can be rewritten as

$$ \sum_{\substack{m^{[p,q]} \in \mathcal{F}(G^0) \\ [p,q] \subseteq [i,j] \\ p < q}} \theta_{p,q}(m_p, m_q). $$

From this, the induction hypothesis and (10), we get

$$ \Delta_{vG^0}(m^{[i,j]}) = \theta_{i,j}(m_i, m_j), $$

which concludes the induction step.

Thus, by **Claims 1-2**, $v^{G^0}$ admits the following linear decomposition

$$ v^{G^0} = \sum_{p \in N} \sum_{k'=1}^{m_p} (\theta_p(k') - \theta_p(k' - 1)) u_{k'e^p} + \sum_{\substack{m^{[p,q]} \in \mathcal{F}(G^0) \\ p < q}} \theta_{p,q}(m_p, m_q) u_{m^{[p,q]}}. $$

By definition, $My_{ik}^{KSZ}(v, G^0) = KSZ_{ik}(v^{G^0})$. By linearity of KSZ and the fact that $|B(m^{[p,q]})| = \sum_{j \in [p,q]} m_j$, we obtain expression (9). This completes the proof of Theorem 3. □

A few comments are in order. Expression (9) of $My_{ik}^{KSZ}(v, G^0)$ has two parts. The first part indicates that, for each $i \in N$ and each $m_i \ge k' \ge 2$, the quantity

$$ \theta_i(k') - \theta_i(k' - 1) = c_i(t_i(k' - 1) - t_i(k')) > 0, $$

is distributed equally among all participation levels $k \le k'$ of agent $i$. The quantity $\theta_i(k') - \theta_i(k' - 1)$ measures the cost savings achieved by $i$ by increasing its participation from $k' - 1$ to $k'$. This quantity is equally redistributed at each participation level $k \le k'$ necessary to reach $k'$, which made this gain possible. In case, $k' = 1$, $\theta_i(1) - \theta_i(0) = \theta_i(1) < 0$, measures the cost that agent $i$ must pay for not participating. Thus, the first participation level 1 pays a cost but receives from each level $k' \ge 2$ a share of the cost savings achieved by choosing $k'$. This redistribution scheme favors lower levels, which can be interpreted as a form of subsidy designed to encourage engagement in skill acquisition.<fnref n="4" />

<footnote n="4">⁴This redistribution scheme is conceptually equivalent to the seminal work of Littlechild and Owen (1973).</footnote>
The second part of the expression is a redistribution of the gain $\theta_{p,q}(m_p, m_q) \ge 0$ resulting from the switch between agents $p$ and $q$ in the connected coalition $m^{[p,q]}$ to which $i$ belongs. This gain is redistributed equally among all participation levels of the members of $[p, q]$, which made this gain possible.

# 7 Conclusion

In this paper, we introduce and study a new solution concept for multi-choice games with a communication network, providing both an axiomatic characterization and a stability result. To illustrate the practical relevance of our contribution, we apply the solution to sequencing games, where agents' effort to reduce processing times is interpreted as their participation level, resulting in an efficient and fair allocation of collective gains.

The key assumption underlying our solution is that two connected agents can cooperate only once they have reached their maximal participation level. While this interpretation captures economic and operational settings, alternative interpretations are equally meaningful.

For example, one could posit that higher participation expands an agent's communication range within the network. In a transportation context, agents could represent companies investing in machinery, where greater investment allows them to navigate further in the network. This alternative perspective aligns with recent work by Kaneko et al. (2025), who study TU-games with communication networks under the premise that agents can communicate only within a limited range. Extending this idea to multi-choice games, one can posit a direct relationship between an agent's participation level and its reach in the communication network. For example, a participation level of 1 allows cooperation with direct neighbors only, while higher levels could enable interaction with agents farther in the network.

Comparing alternative interpretations and their implications for the axiomatic design of allocation rules represents a promising direction for future research, shedding light on the interplay between participation levels, communication networks, and cooperative opportunities.

# References

* ALBIZURI, M. J. (2009): "The multichoice coalition value," *International Journal of Game Theory*, 172, 363.

* AUMANN, R. J. AND J. H. DREZE (1974): "Cooperative games with coalition structures," *International Journal of Game Theory*, 3, 217-237.
BÉAL, S., S. FERRIÈRES, AND P. SOLAL (2022): “The priority value for cooperative games with a priority structure,” *International Journal of Game Theory*, 51, 431–450.

BÉAL, S., A. LARDON, E. RÉMILA, AND P. SOLAL (2012): “The average tree solution for multi-choice forest games,” *Annals of Operations Research*, 196, 27–51.

BÉAL, S., A. NAVARRO-RAMOS, E. RÉMILA, AND P. SOLAL (2025): “Sharing the cost of hazardous transportation networks and the Priority Shapley value for multi-choice games,” *Annals of Operations Research*, 345, 59–103.

BORM, P., G. FIESTRAS-JANEIRO, H. HAMERS, E. SÁNCHEZ, AND M. VOORNEVELD (2002): “On the convexity of games corresponding to sequencing situations with due dates,” *European Journal of Operational Research*, 136, 616–634.

CURIEL, I., G. PEDERZOLI, AND S. TIJS (1989): “Sequencing games,” *European Journal of Operational Research*, 40, 344–351.

DERKS, J. AND H. PETERS (1993): “A Shapley value for games with restricted coalitions,” *International Journal of Game Theory*, 21, 351–360.

GILLES, R. P., G. OWEN, AND R. VAN DEN BRINK (1992): “Games with permission structures: the conjunctive approach,” *International Journal of Game Theory*, 20, 277–293.

GRABISCH, M. AND F. LANGE (2007): “Games on lattices, multichoice games and the Shapley value: a new approach,” *Mathematical Methods of Operations Research*, 65, 153–167.

HAMERS, H., P. BORM, AND S. TIJS (1995): “On games corresponding to sequencing situations with ready times,” *Mathematical Programming*, 69, 471–483.

HAMERS, H., F. KLIJN, AND J. SUIJS (1999): “On the balancedness of multiple machine sequencing games,” *European Journal of Operational Research*, 119, 678–691.

HERINGS, J.-J., G. VAN DER LAAN, AND D. TALMAN (2008): “The average tree solution for cycle-free graph games,” *Games and Economic Behavior*, 62, 77–92.

HSIAO, C.-R. AND T. RAGHAVAN (1992): “Monotonicity and dummy free property for multi-choice cooperative games,” *International Journal of Game Theory*, 21, 301–312.
KANEKO, T., D. LOWING, AND S. NAKADA (2025): "k-Boundedness and an Extension of the Myerson Value on Feasible Communication Structures," Available at SSRN 5290078.

KLIJN, F., M. SLIKKER, AND J. ZARZUELO (1999): "Characterizations of a multi-choice value," *International Journal of Game Theory*, 28, 521–532.

LITTLECHILD, S. C. AND G. OWEN (1973): "A simple expression for the Shapley value in a special case," *Management Science*, 20, 370–372.

LOWING, D. (2023): “Allocation rules for multi-choice games with a permission tree structure,” *Annals of Operations Research*, 320, 261–291.

LOWING, D. AND K. TECHER (2022a): “Marginalism, egalitarianism and efficiency in multi-choice games,” *Social Choice and Welfare*, 59, 815–861.

——— (2022b): “Priority relations and cooperation with multiple activity levels,” *Journal of Mathematical Economics*, 102, 102740.

LOWING, D. AND M. YOKOO (2025): “Sharing values for multi-choice games: an axiomatic approach,” *International Journal of Game Theory*, 54, 30.

MYERSON, R. B. (1977): “Graphs and cooperation in games,” *Mathematics of Operations Research*, 2, 225–229.

OWEN, G. (1977): “Values of games with a priori unions,” in *Mathematical economics and game theory: Essays in honor of Oskar Morgenstern*, Springer, 76–88.

PETERS, H. AND H. ZANK (2005): “The egalitarian solution for multichoice games,” *International Journal of Game Theory*, 137, 399–409.

SHAPLEY, L. S. (1953): “A value for n-person games,” in *Contribution to the Theory of Games*, Princeton University Press, 307–317.

SLIKKER, M. (2006): “Balancedness of multiple machine sequencing games revisited,” *European Journal of Operational Research*, 174, 1944–1949.

SMITH, W. (1953): “Various optimizers for single-stage production,” *Naval Research Logistics Quarterly*, 3, 59–66.
VAN DEN BRINK, R. (1997): "An axiomatization of the disjunctive permission value for games with a permission structure," *International Journal of Game Theory*, 26, 27–43.

——— (2017): "Games with a permission structure-A survey on generalizations and applications," *TOP*, 25, 1–33.

VAN DEN BRINK, R. AND R. P. GILLES (1996): "Axiomatizations of the conjunctive permission value for games with permission structures," *Games and Economic Behavior*, 12, 113–126.

VAN DEN BRINK, R., G. VAN DER LAAN, AND V. VASIL'EV (2007): "Component efficient solutions in line-graph games with applications," *Economic Theory*, 33, 349–364.

VAN DEN NOUWELAND, C. G. A. (1993): "Games and graphs in economic situations." PhD thesis, Tilburg University.