# There is a Singularity in the Loss Landscape

Mark Lowell<EMAIL_ADDRESS>National Geospatial-Intelligence Agency

###### Abstract

Despite the widespread adoption of neural networks, their training dynamics
remain poorly understood. We show experimentally that as the size of the
dataset increases, a point forms where the magnitude of the gradient of the
loss becomes unbounded. Gradient descent rapidly brings the network close to
this singularity in parameter space, and further training takes place near it.
This singularity explains a variety of phenomena recently observed in the
Hessian of neural network loss functions, such as training on the edge of
stability and the concentration of the gradient in a top subspace. Once the
network approaches the singularity, the top subspace contributes little to
learning, even though it constitutes the majority of the gradient.

##  1 Introduction

Despite neural networks’ enormous empirical success, the underlying reasons
behind their superior generalization remain mysterious. Deep networks have
enough capacity to express functions that perfectly match a training set while
being perfectly wrong on a test set [26], but do not land on those functions
when trained in practice. This implies that the training process plays a role
in why deep networks generalize so well.

Neural network training is usually analyzed as a dynamical system [13]. We
think of the space of possible network parameters as a landscape, where the
height at a point $\theta$ is the training loss
$\widetilde{\mathcal{L}}(\theta)$. During training the network is rolling
downhill, following the gradient of the loss. Because we cannot solve the
dynamical system
$\frac{d\theta}{dt}=-\nabla_{\theta}\widetilde{\mathcal{L}}(\theta)$ exactly,
we discretize the process into steps. At each step, we move in the direction
$-\nabla_{\theta}\widetilde{\mathcal{L}}(\theta)$, with the length of our step
proportional to a learning rate $\eta$. Provided that $\eta$ is small enough,
this procedure should be a good approximation of the exact solution to the
dynamical system.

Recent work, however, has called this interpretation into question. The
maximum stable learning rate, which we denote $\eta^{*}$, is determined by the
curvature of the loss landscape. If the learning rate $\eta$ equals or exceeds
$\eta^{*}$, then our step overshoots; conceptually, we jump to the other side
of a valley instead of rolling down into its interior. [2] showed
experimentally that, during training, the curvature rises until
$\eta\approx\eta^{*}$, _regardless of the choice of $\eta$_, which they called
training on the edge of stability. If training is on the edge of stability,
then it no longer approximates the solution of the dynamical system. The
optimization process is instead a difference system; the network is bouncing
from point to point on the landscape, instead of rolling smoothly downhill.

In this work, we show experimentally that training on the edge of stability is
caused by a singularity that forms in the loss as the size of the dataset
increases. A submanifold emerges near which
$||\nabla_{\theta}\widetilde{\mathcal{L}}(\theta)||_{2}$ is unbounded. The
network is attracted to this singularity during training, and subsequent
training takes place near its surface. This singularity explains a variety of
recently observed phenomena such as training on the edge of stability seen in
[2] and the concentration of the gradient in a top subspace seen in [5].

We make four novel claims:

  * •

Neural network training is on the edge of stability across $n_{c}-1$
eigenvectors, not just 1 eigenvector, where $n_{c}$ is the number of classes
in the dataset.

  * •

The network enters the edge of stability simultaneously with the gradient
concentrating in the top subspace.

  * •

Once the network enters the edge of stability, further reduction in the
training loss comes from the smaller bulk component of the gradient, not the
top.

  * •

All of these phenomena are caused by the network encountering a singularity in
the training loss that forms as the size of the dataset asymptotes to
infinity.

In Section 2, we review related work on the Hessian of the training loss and
modeling training as a dynamical system. In Section 3, we describe our
methodology, including how we calculate $\eta^{*}$ and the eigenvalues and
eigenvectors. In Section 4, we describe the experiments we conducted. In
Section 5, we show the results of these experiments. In Section 6, we discuss
implications of our results. In Section 7, we review and describe directions
for future research.

Code will be released.

##  2 Related Work

The Hessian of the training loss has been studied for some time for its
connections to both optimization and generalization. Modern empirical
exploration of the Hessian begins with [18] and [19], which showed that the
eigenvalues of the Hessian matrix tends to separate during training into a few
high-magnitude top eigenvalues and a larger set of lower-magnitude bulk
eigenvalues, but their experiments were limited to shallow networks. [15] and
[16] extended this work to deep networks of meaningful capacity. [5] showed
that the gradients of the network tend to concentrate in a top component
corresponding to those top eigenvalues, which consist of the top $n_{c}$
eigenvectors of the Hessian matrix, where $n_{c}$ is the number of classes.
The authors concluded that this implies that learning happens within a low-
dimensional subspace of the parameter space. Finally, [2] showed that, in non-
stochastic gradient descent, the top eigenvalue rises until the learning rate
approximately equals the maximum learning rate, regardless of the value of the
learning rate. They showed that this occurred for a commendably wide array of
network architectures, activation functions, loss functions, tasks, and other
hyperparameters. However, they showed only that this phenomenon occurred on
the single largest eigenvector, and they did not connect it to the existence
of a singularity.

On the theoretical side, there have been many attempts to incorporate training
dynamics into a theory of generalization [13]. It is common in these works to
take the limit as the width of the network approaches infinity and study the
resulting system through mean field theory. The Neural Tangent Kernel (NTK),
probably the most successful of these approaches, is based on interpreting the
infinite-width limit of the network as a kernel function [7]. NTK has been
successfully extended to convolutional networks [20], recurrent networks [1],
networks with skip connections [12], and generative adversarial networks [4].
However, the NTK scales only the width of the networks, and assumes the other
parameters are fixed.

##  3 Methodology

###  3.1 Defining a Singularity

The term “singularity” is somewhat overloaded. Within the neural network
literature, it has been used to refer to a region where the Hessian matrix
becomes singular, for example [18], or where the Jacobian of the network
outputs becomes degenerate, as in [14]. In mathematics, it often refers to a
point where the function is non-differentiable. For clarity, in this paper, we
define a singularity as:

######  Definition 3.1.

A singularity of a function $F:U\to V$ is a point $p\in U$ such that, for any
real numbers $\epsilon,M>0$, there exists a point $p^{\prime}\in U$ such that
$||p-p^{\prime}||_{2}<\epsilon$ and $||\nabla F(p^{\prime})||_{2}>M$.

This definition excludes the fold in a ReLU activation, but would include a
vertical cusp such as $x=0$ for $F(x)=|x|^{1/2}$.

###  3.2 The Role of the Hessian Matrix in Training

Suppose there is a space $\mathcal{X}$ of data points and a space
$\mathcal{Y}$ of labels, with a label function $u:\mathcal{X}\to\mathcal{Y}$.
For example, $x\in\mathcal{X}$ might be images, and $u(x)=y\in\mathcal{Y}$
might be the category “cat,” “dog,” and so on. We have no direct access to
$u$, but we are given a finite training dataset of pairs
$\mathcal{T}=\\{(x_{1},y_{1}),(x_{2},y_{2}),...\\}$, where $u(x_{j})=y_{j}$.
We wish to use $\mathcal{T}$ to find a function $f:\mathcal{X}\to\mathcal{Y}$
so that $f(x)=u(x)$ even for $x$ not found in $\mathcal{T}$.

We parameterize $f$ by a neural network $f(x,\theta)$, where $\theta$ is the
vector of network weights. We define $l(x,y,\theta)$ to be a criterion
measuring the difference between the prediction $f(x,\theta)$ and the label
$y=u(x)$. The most commonly used criterion is the softmax-cross-entropy loss:

$l_{\mbox{\tiny
ce}}(x,y,\theta)=-\log\left(\frac{\exp(f(x,\theta))_{y}}{\sum_{c}\exp(f(x,\theta))_{c}}\right)$

where $c$ indexes the outputs of $f$. We define the training loss
$\widetilde{\mathcal{L}}(\theta)$ as the expectation of the criterion over the
training dataset:

$\widetilde{\mathcal{L}}(\theta)=\mathbb{E}_{(x,y)\sim\mathcal{T}}l(x,y,\theta)$

where, by abuse of notation, we use $\mathcal{T}$ to denote a random sampling
from the dataset $\mathcal{T}$. Then, given a change in the weights
$\Delta\theta$, the order-2 Taylor approximation of the change in the training
loss is:

$\widetilde{\mathcal{L}}(\theta+\Delta\theta)-\widetilde{\mathcal{L}}(\theta)=\Delta\theta\cdot
g_{\theta}+\frac{1}{2}\Delta\theta^{T}H_{\theta}\Delta\theta+\mathcal{O}(||\Delta\theta||^{3})$

where $g_{\theta}=\nabla_{\theta}\widetilde{\mathcal{L}}(\theta)$ is the
gradient of the training loss $\widetilde{\mathcal{L}}(\theta)$, $H_{\theta}$
is the Hessian matrix of $\widetilde{\mathcal{L}}(\theta)$, and
$\mathcal{O}(||\Delta\theta||^{3})$ is an error term. In the case of non-
stochastic gradient descent without momentum, we have $\Delta\theta=-\eta
g_{\theta}$, where $\eta\in\mathbb{R}$ is the learning rate. The above
equation then becomes:

$\widetilde{\mathcal{L}}(\theta+\Delta\theta)-\widetilde{\mathcal{L}}(\theta)=-\eta||g_{\theta}||_{2}^{2}\\\
+\frac{1}{2}\eta^{2}g_{\theta}^{T}H_{\theta}g_{\theta}+\mathcal{O}(\eta^{3})$

Because the Hessian matrix is symmetric, its eigenvalues $\lambda_{i}$ are all
real and it has an orthonormal basis of eigenvectors $h_{i}$, where $i$
indexes the parameters in $\theta$. We order $\lambda_{i}$ such that
$\lambda_{0}\geq\lambda_{1}\geq\lambda_{2}\geq...$ If we parameterize
$g_{\theta}$ in terms of the basis $h_{i}$ with coordinates $d_{i}$,
$g_{\theta}=\sum_{i}d_{i}h_{i}$, then
$H_{\theta}g_{\theta}=\sum_{i}\lambda_{i}d_{i}h_{i}$, and the above equation
becomes:

$\widetilde{\mathcal{L}}(\theta+\Delta\theta)-\widetilde{\mathcal{L}}(\theta)=\eta\sum_{i}d_{i}^{2}\left(\frac{1}{2}\eta\lambda_{i}-1\right)+\mathcal{O}(\eta^{3})$

Then, for every eigenvalue $\lambda_{i}$, from [11] we have a corresponding
maximum learning rate:

$\eta^{*}_{i}=\frac{2}{\lambda_{i}}$ $\eta^{*}=\min\eta^{*}_{i}$

In practice $\mathcal{O}(\eta^{3})$ is small enough that it can be neglected,
so that we are guaranteed
$\widetilde{\mathcal{L}}(\theta+\Delta\theta)<\widetilde{\mathcal{L}}(\theta)$
if $\eta<\eta^{*}$. If $\eta>\eta^{*}$, then the change in the loss cannot be
predicted, but usually increases. For any eigenvector $h_{i}$ such that
$\eta\approx\eta_{i}^{*}$, we say that the gradient is on the edge of
stability along $h_{i}$. To ease comparisons between networks trained with
different $\eta$, we define $\rho_{i}=\eta/\eta_{i}^{*}$.

To return to our landscape metaphor, at every moment in training,
$\lambda_{i}$ is proportional to the curvature in the direction $h_{i}$. If we
separate our step $\Delta\theta$ into its components in each direction
$h_{i}$, then if $\rho_{i}\ll 1$, the component of our motion in the direction
$h_{i}$ is carrying us smoothly downhill. If $\rho_{i}\approx 1$, we are
landing on the opposite side of a valley, at the same elevation that we
started at, making no progress. If $\rho_{i}\gg 1$, then we are landing on the
opposite side of the valley at a _higher_ elevation, making our loss worse.

We refer to the subspace spanned by the largest $n_{c}-1$ eigenvectors, where
$n_{c}$ is the number of classes, as the top subspace. We refer to the
subspace spanned by the remaining eigenvectors, orthogonal to the top
subspace, as the bulk subspace. Our terminology differs slightly from [5],
where the top subspace is the space spanned by the top $n_{c}$ eigenvectors.
We define $P_{\mbox{\tiny top}}v$ to be the projection of a vector $v$ onto
the top subspace, and $P_{\mbox{\tiny bulk}}v$ to be the projection onto the
bulk subspace.

###  3.3 Calculating the Eigenvalues

Because neural networks typically have millions of parameters, the Hessian
matrix cannot be explicitly calculated. Instead, we obtain Hessian-vector
products using the PyTorch autograd engine [17], and find the largest $k$
eigenvalues and associated eigenvectors using the power iteration method [24].
The power iteration method returns the $k$ largest eigenvalues by absolute
value. However, in practice, we find that the positive eigenvalues invariably
have greater magnitude than the negative eigenvalues in the Hessian of the
training loss.

##  4 Experiments

We perform all of our experiments using the CIFAR-10 training dataset [9], a
set of 50,000 $32\times 32$ images in 10 classes. We initialize all networks
with the Kaiming initialization [6] and train them using non-stochastic
gradient descent without momentum.

###  4.1 Exploring the Edge of Stability

We begin by training a large number of networks with a variety of
hyperparameters to explore the edge of stability. We train AlexNets [10] and
non-normalized VGG-16s [21] with ReLU and tanh activation functions, using a
selection of learning rates $\\{0.003,0.001,0.0003,0.0001\\}$. We train the
networks until the training loss drops below 0.1 or we reach $40\eta^{-1}$
iterations. Every $\eta^{-1}$ iterations, we pause training and collect a
variety of telemetry:

  * •

We calculate the largest 20 eigenvalues $\lambda_{i}$ and eigenvectors
$h_{i}$, and use them to calculate the maximum learning rates
$\eta_{1}^{*},...,\eta_{20}^{*}$ and the ratios $\rho_{1},...,\rho_{20}$.

  * •

We calculate the training gradient $g_{\theta}$ and use the eigenvectors
$h_{i}$ to calculate its projections $P_{\mbox{\tiny top}}g_{\theta}$ and
$P_{\mbox{\tiny bulk}}g_{\theta}$.

  * •

Using these projections, we calculate the change in the training loss caused
by taking a single optimization step in the direction of $P_{\mbox{\tiny
top}}g_{\theta}$ and $P_{\mbox{\tiny bulk}}g_{\theta}$. We do this by
adjusting the weights and recalculating the loss, not by using the Taylor
approximation.

Networks trained with the tanh activation at $\eta=0.003$ are omitted from our
analyses because they failed to converge. The VGG-16-tanh network at
$\eta=0.0001$ converged so quickly that we had run these analyses only twice
before training terminated.

We additionally perform several sub-experiments to explore specific elements
of the behavior of the system:

  * •

To determine the effect of the number of classes in the dataset, we train
networks where we drop classes in CIFAR-10 to form datasets with 2, 3, or 5
classes.

  * •

To capture the moment the network enters the edge of stability, we train a
network where we run our analysis every 10 iterations instead of every $\eta$
iterations, but only train for $2000$ iterations.

We perform these additional experiments using AlexNet networks with ReLU
activation at $\eta=0.001$.

###  4.2 Solving the Dynamical System Exactly

In addition to these experiments to explore the edge of stability, we also
trained a set of networks where we attempted to solve the dynamical system
$\frac{d\theta}{dt}=-g_{\theta}$ exactly. We calculated the eigenvalue
$\lambda_{1}$ at every iteration, and set the learning rate to
$\min(0.001,0.5/\lambda_{1})$. Since $\lambda_{1}$ is the largest eigenvalue,
this will ensure that $\eta$ will always lie well below the edge of stability
for all eigenvectors. We pick this value to be less than the optimal value
$\lambda_{1}^{-1}$ because we are expecting to enter a region where the
curvature itself is changing very rapidly. This procedure should ensure that
we remain close to the actual exact solution of the gradient flow. We trained
a set of AlexNet networks with ReLU and tanh activations on subsets of
CIFAR-10 of varying size $n_{D}$ using this process.

##  5 Results

###  5.1 The Gradient Is on the Edge of Stability Across $n_{c}-1$
Eigenvectors

We plot $\rho_{9}$ and $\rho_{10}$ for our main series of experiments from
Section 4.1 in Figure 1. Because $\rho_{i}\geq\rho_{i+1}$, $\rho_{9}$ lower-
bounds $\rho_{i}$ for the top subspace, and $\rho_{10}$ upper-bounds
$\rho_{i}$ for the bulk subspace. For the high learning rate $\eta=0.003$, or
close to the end of training, $\rho_{10}$ may be close to or on the edge of
stability. But as we decrease the learning rate, $\rho_{10}$ falls steadily
toward zero. $\rho_{9}$ reaches the edge of stability almost instantly no
matter how much we shrink $\eta$. At our lowest learning rate $\eta=0.0001$,
across all of our architectures, $\rho_{10}$ never exceeds 0.246 at any point,
while $\rho_{9}$ always reaches at least 0.693.

This implies that the curvature along the direction of $h_{10}$ and the
corresponding maximum learning rate $\eta^{*}_{10}$ are independent of $\eta$.
The curvature along $h_{9}$ increases, and the maximum learning rate
$\eta_{9}^{*}$ decreases, as we shrink $\eta$, meaning that the network lies
on the edge of stability on $h_{1},...,h_{9}$.

Figure 1: Edge of Stability: The vertical axis represents $\rho$ while the
horizontal axis represents $t=n\eta$, where $n$ is the iteration. Solid curves
represent $\rho_{9}=\eta/\eta^{*}_{9}$, while dotted curves represent
$\rho_{10}=\eta/\eta_{10}^{*}$. Different colors represent different learning
rates, and each subfigure represents a different network architecture and
activation function.

We plot the results of our experiments where we varied the number of classes
in Figure 2. Once again we see a clear separation between $\rho_{n_{c}-1}$ and
$\rho_{n_{c}}$, implying that the number of eigenvectors on the edge of
stability is consistently $n_{c}-1$.

Figure 2: Edge of Stability and $n_{c}$: Solid curves represent
$\rho_{n_{c}-1}=\eta/\eta^{*}_{n_{c}-1}$, while dotted curves represent
$\rho_{n_{c}}=\eta/\eta_{n_{c}}^{*}$. Different colors represent different
numbers of classes in the dataset. The horizontal axis is $t=n\eta$, where $n$
is the iteration.

###  5.2 Concentration of the Gradient in the Top Subspace Occurs
Simultaneously with the Edge of Stability

Figure 3: Gradient Concentration: Solid curves represent $||P_{\mbox{\tiny
top}}g_{\theta}||_{2}$, while dotted curves represent $||P_{\mbox{\tiny
bulk}}g_{\theta}||_{2}$. Different colors represent different learning rates
$\eta$. Different subfigures represent different architectures. The horizontal
axis is $t=n\eta$, where $n$ is the iteration.

In Figure 3, we graph the magnitude of the projection of $g_{\theta}$ onto the
top subspace $||P_{\mbox{\tiny top}}g_{\theta}||_{2}$, along with the
magnitude of the projection onto the bulk $||P_{\mbox{\tiny
bulk}}g_{\theta}||_{2}$. We observe that the magnitude of the bulk component
remains roughly constant with learning rate, while the magnitude of the top
component increases as $\eta$ shrinks.

In Figure 4, we plot the result of the experiment where we ran our analysis
every 10 iterations. We observe that the gradient magnitude explodes at the
same iteration the eigenvector enters the edge of stability.

Figure 4: Entering the Edge of Stability: The left subfigure shows
$\rho_{1},...,\rho_{9}$, while the right subfigure shows $|d_{i}|=|h_{i}\cdot
g_{\theta}|$, for an AlexNet-ReLU trained at $\eta=0.001$. Different colors
represent different eigenvalues $\lambda_{i}$ and eigenvectors $d_{i}$. The
horizontal axis is $t=n\eta$, where $n$ is the iteration.

###  5.3 Learning Occurs in the Bulk, Not the Top

We show the mean and standard deviation of the change in the training loss
caused by a step in the direction of $P_{\mbox{\tiny top}}g_{\theta}$ versus a
step in the direction of $P_{\mbox{\tiny bulk}}g_{\theta}$ in Table 1. We
limit our calculations to iterations where the network is indisputably on the
edge of stability, as shown by $\rho_{9}>0.7$, and we omit combinations of
hyperparameters where this left us with fewer than three iterations to use in
this calculation. We consistently see that the change in the loss caused by
the top component is either positive or very close to 0, while the standard
deviation is large. The change caused by the bulk is consistently negative,
with low standard deviation.

$\eta$ | Architecture | Mean $\Delta\widetilde{\mathcal{L}}$ from $P_{\mbox{\tiny top}}g_{\theta}$ (std) | Mean $\Delta\widetilde{\mathcal{L}}$ from $P_{\mbox{\tiny bulk}}g_{\theta}$ (std)
---|---|---|---
0.003 | AlexNet-ReLU | 0.0043 (0.0172) | -0.0041 (0.0010)
0.001 | AlexNet-ReLU | 0.0064 (0.0133) | -0.0014 (0.0007)
0.0003 | AlexNet-ReLU | -0.0001 (0.0046) | -0.0003 (0.0001)
0.0001 | AlexNet-ReLU | -0.0012 (0.0043) | -0.0001 (0.000)
0.001 | AlexNet-Tanh | 0.0025 (0.0048) | -0.0017 (0.0010)
0.0003 | AlexNet-Tanh | 0.0007 (0.0031) | -0.0004 (0.0001)
0.003 | VGG-16-ReLU | 0.0710 (0.0645) | -0.0256 (0.0111)
0.001 | VGG-16-ReLU | 0.0208 (0.0142) | -0.0072 (0.0035)
0.0001 | VGG-16-ReLU | 0.0011 (0.0064) | -0.0008 (0.0006)
Table 1: Learning Occurs in the Bulk, not the Top

###  5.4 The Trajectory of $\theta$ Lies Near a Singularity

The loss landscape does not change when we change $\eta$, only the trajectory
of $\theta$ through it. As $\eta$ decreases, the eigenvalues
$\lambda_{1},...,\lambda_{n_{c}-1}$ remain near $2/\eta$, while the magnitude
of the top component of the gradient $||P_{\mbox{\tiny
top}}(g_{\theta})||_{2}$ increases. Suppose we could allow $\eta$ to reach 0,
so that we are solving the dynamical system $\frac{d\theta}{dt}=-g_{\theta}$
exactly; this suggests that $\lambda_{1},....,\lambda_{n_{c}-1}$ and
$||P_{\mbox{\tiny top}}g_{\theta}||_{2}$ would all approach infinity over the
course of training. This can occur only if either $\theta\to\infty$ or if
there exists a point in whose neighborhood $||g_{\theta}||_{2}$ is unbounded —
in other words, a singularity in $\widetilde{\mathcal{L}}(\theta)$. In all of
our experiments, $||\theta||_{2}$ increased by much less than $1\%$, even
though we used no regularization, so we can conclude that
$\theta\not\to\infty$.

Strictly speaking, the $\lambda_{i},g_{\theta}$ of a finite-size network with
bounded weights trained on a finite dataset must be finite. If we reduced
$\eta$ enough, eventually training would be below the edge of stability. But
it is common in theory to make the simplifying assumption that various
parameters limit to infinity, for example [7]. If $n_{D}=1$, so that training
is achieved by simply scaling the outputs, then the gradients and curvature
are trivial, so we hypothesize that a singularity forms as $n_{D}\to\infty$.

To test this hypothesis, we attempted to train networks by solving the
gradient flow exactly, as discussed in Section 4.2. We plot $\lambda_{1}$
versus time for each of these experiments in Figure 5. With ReLU activation,
peak $\lambda_{1}$ rises linearly with the size of the dataset. A linear
regression between the size of the dataset $n_{D}$ and peak $\lambda_{1}$ has
an $R^{2}$ of $99.91\%$. The picture is more complicated with tanh activation,
where there is an initial spike in $\lambda_{1}$ to a consistent level of
about 30,000, literally one iteration after training begins. For small
datasets, this initial spike overwhelms the later peak in $\lambda_{1}$ — but
we see the peak forming as the dataset size increases, once again rising
linearly with dataset size, although at a slower rate than with the ReLU
activation.

We saved model snapshots every 100 iterations during training. For our
AlexNet-ReLU networks, we reloaded the model weights to the peak curvature,
which we denote $\theta^{*}$, and calculated the top eigenvector $h_{1}$. We
then sampled a large number of $\Delta$ between -0.003 and 0.003, adjusted the
weights by $\Delta h_{1}$, and calculated the change in the training loss, as
shown in the left subfigure of Figure 6. We see a vertical cusp forming as
$n_{D}\to\infty$.

Figure 5: Peak Curvature: Each curve represents $\lambda_{1}$ over the course
of training an AlexNet on a subset of CIFAR-10, adaptively scaling the
learning rate to approximate the exact solution of the differential equations
$\frac{d\theta}{dt}=-g_{\theta}$. Different colors represent differently-sized
subsets. The left figure uses a ReLU activation, while the right figure uses
the tanh activation. The horizontal axis is $t$. Figure 6: Cusp Formation:
Each curve shows the change in $\widetilde{\mathcal{L}}(\theta)$ along the
direction $h_{1}$ in a neighborhood of the point $\theta^{*}$ of peak
$\lambda_{1}$. The horizontal axis is the displacement in the direction
$h_{1}$, while the vertical axis is the change in the loss,
$\widetilde{\mathcal{L}}(\theta^{*}+\Delta
h_{1})-\widetilde{\mathcal{L}}(\theta^{*})$.

##  6 Discussion

The existence of this singularity has direct implications for understanding
generalization in terms of the training process, especially the Neural Tangent
Kernel (NTK) [7]. First, this confirms that training _is_ a dynamical system,
not a difference system. Second, NTK and other mean-field approaches take the
limit as the width of the network approaches infinity. Under this assumption,
the Hessian of the training loss does not evolve during training. In practice,
the scaling of neural networks generally involves scaling the depth, input
dimension, and dataset size as well as the width [23][22]. If multiple terms
are asymptoting to infinity, then the assumption that the Hessian will not
change during training may not hold, as we have shown here.

This result also has implications for optimization. There has been
considerable interest recently in sharpness-aware optimizers (for example
[3]). This result indicates that minimizing sharpness in the top direction is
not possible and probably not desirable, while leaving open the possibility
that minimizing sharpness in the bulk directions may still be valuable. We
might also speculate on a connection to the tendency of adaptive optimizers
such as Adam [8] to have lower generalization performance than stochastic
gradient descent [25] and to the instabilities that famously plague the
training of generative adversarial networks.

##  7 Conclusion

We have shown that, as the size of the dataset increases, a singularity forms
in the loss landscape, and training occurs on a trajectory near the surface of
the singularity. This singularity causes training to occur on the edge of
stability in the top subspace and the gradient in the top subspace to become
very large. Despite this, once the network enters the edge of stability, the
top component of the gradient contributes very little to improving the loss,
with most learning occurring in the bulk component.

In future research, we plan to further explore the connections between the
training gradient, the curvature of the loss landscape, and generalization. In
particular, decomposing the gradient and the curvature on a layer-by-layer
basis is likely a necessary pre-condition for developing a mathematical theory
of generalization in deep learning, as is investigating the connection between
the training gradient and the _test_ gradient.

Acknowledgements: This work was supported in part by high-performance computer
time and resources from the DoD High Performance Computing Modernization
Program.

## References

  * [1] Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk.  The recurrent neural tangent kernel.  2021\.
  * [2] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar.  Gradient descent on neural networks typically occurs at the edge of stability.  2021\.
  * [3] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur.  Sharpness-aware minimization for efficiently improving generalization.  2020\.
  * [4] Jean-Yves Franceschi, Emmanuel de Bézenac, Ibrahim Ayed, Mickaël Chen, Sylvain Lamprier, and Patrick Gallinari.  A neural tangent kernel perspective of GANs.  2021\.
  * [5] Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer.  Gradient descent happens in a tiny subspace.  2018\.
  * [6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification.  2015\.
  * [7] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  2018\.
  * [8] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  2015\.
  * [9] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  2009\.
  * [10] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  ImageNet classification with deep convolutional neural networks.  25, 2012.
  * [11] Yann LeCun, Leon Bottou, Genevieve Orr, and Klaus-Robert Muller.  Efficient backprop.  Lecture Notes in Computer Science, pages 9–50, 1998.
  * [12] Yuqing Li, Tao Luo, and Nung Kwan Yip.  Towards and understanding of residual networks using neural tangent hierarchy (NTH).  2020\.
  * [13] Guan-Horng Liu and Evangelos Theodorou.  Deep learning theory review: An optimal control and dynamical systems perspective.  2019\.
  * [14] Eiji Mizutani and Stuart Dreyfus.  An analysis on negative curvature induced by singularity in multi-layer neural-network learning.  2010\.
  * [15] Vardan Papyan.  The full spectrum of deepnet hessians at scale: Dynamics with SGD training and sample size.  2018\.
  * [16] Vardan Papyan.  Measurement of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians.  2019\.
  * [17] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  PyTorch: An imperative style, high-performance deep learning library, 2019.
  * [18] Levent Sagun, Léon Bottou, and Yann LeCun.  Eigenvalues of the hessian in deep learning: Singularity and beyond.  2016\.
  * [19] Levent Sagun, Utku Evci, V. Uğur Güney, Yann Dauphin, and Léon Bottou.  Empirical analysis of the hessian of over-parameterized neural networks.  2018\.
  * [20] Arora Sanjeev, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  2019\.
  * [21] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  2015\.
  * [22] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta.  Revisiting unreasonable effectiveness of data in deep learning era.  2017\.
  * [23] Mingxing Tan and Quoc V. Le.  EfficientNet: Rethinking model scaling for convolutional neural networks.  2019\.
  * [24] Richard von Mises and Hilda Pollaczek-Geiringer.  Praktische verfahren der gleichungsauflösung.  Zeitschrift fü Angewandte Mathematik und Mechanik, 1929.
  * [25] Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht.  The marginal value of adaptive gradient methods in machine learning.  30, 2017.
  * [26] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  2017\.


# On egalitarian values for cooperative games with level structures111This
work is part of the R+D+I project grants MTM2017-87197-C3-1-P, MTM2017-87197-
C3-3-P, PID2021-124030NB-C31 and PID2021-124030NB-C32, funded by
MCIN/AEI/10.13039/501100011033/ and by ”ERDF A way of making Europe”/EU. This
research was also funded by Grupos de Referencia Competitiva ED431G-2019/01,
ED431C-2020/14 and ED431C-2021/24 from the Consellería de Cultura, Educación e
Universidades, Xunta de Galicia. During the completion of this work, J. C.
Gonçalves-Dosantos is a ”Margarita Salas” postdoctoral researcher, carrying
out a research stay at the CIO, Centro de Investigación Operativa of the
Miguel Hernández University of Elche (Spain), to which he is grateful for the
welcome.

J.M. Alonso-Meijide1, J. Costa2,
I. García-Jurado3, J.C. Gonçalves-Dosantos4

###### Abstract

In this paper we extend the equal division and the equal surplus division
values for transferable utility cooperative games to the more general setup of
transferable utility cooperative games with level structures. In the case of
the equal surplus division value we propose three possible extensions, one of
which has already been described in the literature. We provide axiomatic
characterizations of the values considered, apply them to a particular cost
sharing problem and compare them in the framework of such an application.

11footnotetext: Universidade de Santiago de Compostela, Grupo MODESTYA,
CITMAga and Departamento de Estatística, Análise Matemática e Optimización,
Facultade de Ciencias, Campus de Lugo, 27002 Lugo, Spain.22footnotetext:
Universidade da Coruña, Grupo MODES, Departamento de Matemáticas, Campus de
Elviña, 15071 A Coruña, Spain.33footnotetext: Universidade da Coruña, Grupo
MODES, CITMAga and Departamento de Matemáticas, Campus de Elviña, 15071 A
Coruña, Spain.44footnotetext: Universidade da Coruña, Grupo MODES, CITIC and
Departamento de Matemáticas, Campus de Elviña, 15071 A Coruña, Spain.

Keywords: cooperative games, level structures, equal division value, equal
surplus division value.

##  1 Introduction

In many practical situations, when a group of agents are faced with sharing
the costs of a project they are jointly developing, they use an egalitarian
approach to cost sharing. Egalitarian sharing is a clear criterion,
computationally simple and easily acceptable to all as a non-conflict
generating procedure. Selten (1972) indicates that egalitarian considerations
explain in a successful way observed outcomes in experimental cooperative
games.

Cooperative game theory, which is concerned, among other things, with the
study of fair distributions of the outcomes of cooperation, has analysed
various distribution rules based on egalitarian criteria. For instance, van
den Brink (2007) provides a comparison of the equal division value and the
Shapley value, and Casajus and Hüttner (2014) compare those two solutions with
the equal surplus division value (studied first in Driessen and Funaki, 1991).

More recently, egalitarian solutions have been studied in the context of
coalition-structured cooperative games. More specifically, Alonso-Meijide et
al. (2020) extend the equal division and the equal surplus division values for
cooperative games with a priori unions; in the case of the equal surplus
division value Alonso-Meijide et al. (2020) propose three possible extensions.
Hu and Li (2021) extend the equal surplus division value for cooperative games
with level structures. Level structures were introduced in Owen (1977) and
further studied in Winter (1989). A level structure is a collection of nested
partitions of the set of players that conditions their negotiation. When
instead of a collection of nested partitions we have a single partition, the
level structure is called an a priori union structure. The Hu and Li’s equal
surplus division value for cooperative games with level structures turns out
to be an extension of one of the three equal surplus division values for
cooperative games with a priori unions introduced in Alonso-Meijide et al.
(2020).

In this paper we extend to the case with levels the other two equal surplus
division values for cooperative games with a priori unions introduced in
Alonso-Meijide et al. (2020), as well as the equal division value. Moreover we
provide new insights and axiomatic characterizations of all the values
considered here, including the Hu and Li value, and illustrate their interest
with a motivating example.

The structure of the paper is as follows. In Section 2 we elaborate a
particular cost sharing problem to motivate the informal presentation, and
discussion, of various egalitarian values in the context of cooperative games
with level structures. In Section 3 we describe the model of cooperative games
with level structures and define four egalitarian values. In Section 4 we
provide axiomatic characterizations of the previous values. Finally, Section 5
is devoted to the concluding remarks.

##  2 An example

Housing legislation in most democratic states includes regulations on how to
share the costs of improving common elements in homeowners’ associations. In
some cases, such regulations recommend the use of equal sharing criteria. For
example, in the Netherlands, each of the owners of the dwellings involved in
an improvement of the common elements of a building must share equally in the
debts and costs involved, unless the internal community agreements provide for
a different proportion of participation.

In this section we deal with an example that arises in the sharing of the
ordinary maintenance costs of a parking area serving two residential
buildings. The specific characteristics of the example are as follows. We
consider a small residential complex consisting of two buildings that share an
underground parking area. The first building is a two-storey building with one
dwelling on each floor. The second building is also two-storey with one
dwelling on the first floor and two dwellings on the second floor. From the
parking area there is a lift to the first building and another lift to the
second building. The owners of the dwellings in the residential complex have
entrusted the maintenance of the common parking area (where each owner has one
parking place) to a company which is responsible for the cleaning and security
of the parking area, as well as for the maintenance of the lifts.

The company in charge of maintenance has a standard monthly fee for each
community of owners which has two parts: a fixed part of 50 euros, and a
variable part consisting of 50 euros for each lift, 4 euros times the highest
floor the lift should reach (for each lift) and 10 euros for each parking
place. Accordingly, the community in this example should pay the following
monthly amount in euros (broken down as the sum of the fee components):

$50+50\cdot 2+4\cdot 2\cdot 2+10\cdot 5=216.$

Now the question is how to distribute this fee in an equitable way among the
five owners involved. Below are several proposals.

  * •

One proposal is to divide the total fee equally between the five owners.
Accordingly, each of them would have to pay 43.2 euros.

  * •

Another proposal is to take into account that not all owners would have the
same individual fee; by individual fee we mean the fee that each owner would
have to pay if only he had access to the parking area. According to this
proposal each owner should pay his individual fee plus the remainder of the
total fee divided equally among the owners; by the remainder of the total fee
we mean the difference between the total fee and the sum of the individual
fees (notice that this remainder may be a negative amount). Table 1 shows the
individual fee of each owner. Therefore, each owner must pay his individual
fee plus $\frac{1}{5}(216-582)$, resulting in the following distribution
vector: $(40.8,44.8,40.8,44.8,44.8)$.

Owner | Individual Fee
---|---
1 | $50+50\cdot 1+4\cdot 1\cdot 1+10\cdot 1=114$
2 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 1=118$
3 | $50+50\cdot 1+4\cdot 1\cdot 1+10\cdot 1=114$
4 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 1=118$
5 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 1=118$
Table 1: Owners’ individual fees

The two proposals above do not take into account that, in setting the monthly
fee, it would be appropriate to take into account that the owners participate
in the residential complex according to a nested structure. Firstly, the
owners are grouped according to the lifts that serve them; secondly, they are
grouped according to the floor on which their property is located. The nested
structure of the owners is shown in Figure 1. Next we describe four other
proposals for distributing the total fee that do take into account the nested
structure of the owners.

Figure 1: The nested structure of the property owners

  * •

The first of these four proposals is an equal division at each level of the
nested structure; i.e. first we divide the 216 euros equally between the two
lifts, then we divide the amount allocated to each lift equally between the
floors it serves; finally, we divide the amount allocated to each lift and
floor equally between the corresponding owners. We say that the total fee is
divided equally between the owners, but taking into account their nested
structure. This proposal results in the following distribution vector:
$(54,54,54,27,27)$.

The following three proposals take into account the nested structure of the
owners, but also the individual fees that the owners, floors and lifts would
have to pay if being alone. The latter can be done in various ways, resulting
in three different proposals.

  * •

One proposal is to calculate the individual fee for each lift and share it
equally among the owners it serves taking into account the nested structure.
The remainder of the total fee is then divided equally among the owners taking
again into account the nested structure. The individual fees for the lifts
would be $128$ and $138$, respectively. The remainder of the total fee is
$-50$. Then, for instance, the forth component of the corresponding
distribution vector is

$\frac{138}{2\cdot 2}-\frac{50}{2\cdot 2\cdot 2}=28.25$

and the complete distribution vector is $(51.5,51.5,56.5,28.25,28.25)$.

  * •

Another proposal is to calculate the individual fee for each owner, for each
floor and for each lift and then allocate to each owner his individual fee,
plus the remainder of the individual fee for his floor divided equally among
the owners of his floor (taking into account the nested structure), plus the
remainder of the individual fee for his lift divided equally among the owners
of his lift (taking into account the nested structure), plus the remainder of
the total fee divided equally among the owners (taking into account the nested
structure). Table 2 shows the individual fees of floors and lifts. Then, for
instance, the forth component of the corresponding distribution vector is

$118+\frac{128-2\cdot 118}{2}+\frac{138-114-128}{2\cdot
2}+\frac{216-128-138}{2\cdot 2\cdot 2}=31.75$

and the complete distribution vector is $(49.5,53.5,49.5,31.75,31.75)$.

| Individual Fee
---|---
Floor 1, Lift 1 | $50+50\cdot 1+4\cdot 1\cdot 1+10\cdot 1=114$
Floor 2, Lift 1 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 1=118$
Floor 1, Lift 2 | $50+50\cdot 1+4\cdot 1\cdot 1+10\cdot 1=114$
Floor 2, Lift 2 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 2=128$
Lift 1 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 2=128$
Lift 2 | $50+50\cdot 1+4\cdot 2\cdot 1+10\cdot 3=138$
Table 2: Floor’s and lifts’ individual fees

  * •

The last proposal we put forward is to allocate to each owner his individual
fee plus the remainder of the total fee divided equally among the owners
taking into account the nested structure. Then, for instance, the forth
component of the corresponding distribution vector is

$118+\frac{216-114-118-114-118-118}{2\cdot 2\cdot 2}=72.25$

and the complete distribution vector is $(22.5,26.5,22.5,72.25,72.25)$.

Table 3 shows the six proposed fee allocations among the owners that we have
calculated above. All of them are adaptations of the equal share criterion and
all seem reasonable, at least theoretically. However, in practice, they are
not all equally reasonable; for instance, in this example, the distribution of
Proposal 6 seems difficult for the fourth and fifth owners to accept.

In order to decide in which cases it is more appropriate to use each of the
six proposals it is necessary to analyse them mathematically. The first two
proposals correspond to the equal division rule and the equal surplus division
rule, which have been studied for example in van den Brink (2007) and in
Casajus and Hüttner (2014), respectively. The other four will be analysed in
the following sections of this article. Proposal 5 has been introduced and
studied in Xu and Li (2021), but in this article we obtain a new axiomatic
characterization for it.

| 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
Proposal 1 | 43.2 | 43.2 | 43.2 | 43.2 | 43.2
Proposal 2 | 40.8 | 44.8 | 40.8 | 44.8 | 44.8
Proposal 3 | 54 | 54 | 54 | 27 | 27
Proposal 4 | 51.5 | 51.5 | 56.5 | 28.25 | 28.25
Proposal 5 | 49.5 | 53.5 | 49.5 | 31.75 | 31.75
Proposal 6 | 22.5 | 26.5 | 22.5 | 72.25 | 72.25
Table 3: The six proposals

##  3 Four egalitarian values for cooperative games with level structures

Transferable utility games (abbreviated, TU-games) are probably the most
studied model of cooperative game theory. A TU-game is defined by a finite set
of players $N=\\{1,2,\ldots,n\\}$ and a real-valued function
$v:2^{N}\rightarrow\mathbb{R}$, called a characteristic function, where $v(S)$
is the worth of $S\subseteq N$, that is, the benefits (or costs) that
coalition $S$ is able to generate. By convention, $v(\emptyset)=0$. A TU-game
with a priori unions is a triplet $(N,v,\mathcal{C})$, where
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{m}\\}$ is a partition of the player set
$N$ into unions.

A level structure $\mathcal{L}$ is a sequence of nested partitions of the set
of players $N$,
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$.
Level zero comprises each player $i\in N$ as a union,
$\mathcal{C}_{0}=\\{\\{i\\}:i\in N\\}$. At each level $l\geq 1$, the partition
is obtained by aggregation of unions from level $l-1$; if
$C\in\mathcal{C}_{l}$ then
$C=\bigcup_{C^{\prime}\in\hat{\mathcal{C}}_{l-1}}C^{\prime}$, where
$\hat{\mathcal{C}}_{l-1}\subseteq\mathcal{C}_{l-1}$. Finally,
$\mathcal{C}_{k+1}$ is the trivial partition with the grand coalition $N$ as
the sole union, $\mathcal{C}_{k+1}=\\{N\\}$. A level game is a triplet
$(N,v,\mathcal{L})$, where $(N,v)$ is a TU-game and $\mathcal{L}$ is a level
structure. A TU-game with a priori unions can be viewed as a particular case
of a level game with $k=1$.

For every player $i\in N$ and level $l\in\\{0,1,\ldots,k+1\\}$, we denote by
$C_{l}(i)$ the union in $\mathcal{C}_{l}\in\mathcal{L}$ containing $i$, that
is, $i\in C_{l}(i)\in\mathcal{C}_{l}$. Also, for every level
$l\in\\{1,2,\ldots,k+1\\}$ and union $C\in\mathcal{C}_{l}\in\mathcal{L}$, we
denote by $\lfloor C\rfloor$ the set of all unions in $\mathcal{C}_{l-1}$
contained in $C$. We can refer to these unions as the direct subordinates of
$C$.

$\lfloor
C\rfloor=\\{C^{\prime}\in\mathcal{C}_{l-1}\in\mathcal{L}:C^{\prime}\subseteq
C\\}.$

By a value, we mean a map $g$ that assigns to every level game
$(N,v,\mathcal{L})$ a vector $g(N,v,\mathcal{L})\in\mathbb{R}^{N}$ with
components $g_{i}(N,v,\mathcal{L})$ for all $i\in N$. Each component
represents the player’s payoff according to $g$. Alonso-Meijide et al. (2020)
define and study values for games with a priori unions using an egalitarian
approach. Next, we propose four values that extend the previous ones to the
context of level games. The third value has already been introduced in Hu and
Li (2021).

The first proposal divides the worth of the grand coalition, $v(N)$, equally
among the players at each level of the level structure, that is, for a player
$i\in N$, the value divides $v(N)=v(C_{k+1}(i))$ by the cardinals of the
direct subordinates of all unions containing $i$. We call this an equitable
allocation among the players, but taking into account the level structure.

###### Definition 3.1

The LED-value is defined for every $(N,v,\mathcal{L})$ and $i\in N$ by

$LED_{i}=\frac{v(C_{k+1}(i))}{\Pi_{l=1}^{k+1}|\lfloor C_{l}(i)\rfloor|}.$

The second proposal is to calculate the worth of each union at level $k$ (the
last non-trivial partition) and share it equally among its players, but taking
into account the level structure. The remainder of the total worth is then
divided equally among the players taking again into account the level
structure.

###### Definition 3.2

The LESD1-value is defined for every $(N,v,\mathcal{L})$ and $i\in N$ by

$LESD^{1}_{i}=\frac{v(C_{k}(i))}{\Pi_{l=1}^{k}|\lfloor
C_{l}(i)\rfloor|}+\frac{v(C_{k+1}(i))-\sum_{C\in\lfloor
C_{k+1}(i)\rfloor}v(C)}{\Pi_{l=1}^{k+1}|\lfloor C_{l}(i)\rfloor|}.$

The third proposal is to allocate to each player its individual worth, plus
the remainder of the worth of the union to which it belongs on level 1 divided
equally among the members of the union, but taking into account the level
structure, and so on.

###### Definition 3.3

The LESD2-value is defined for every $(N,v,\mathcal{L})$ and $i\in N$ by

$LESD^{2}_{i}=v(i)+\sum_{l=1}^{k+1}\frac{v(C_{l}(i))-\sum_{C\in\lfloor
C_{l}(i)\rfloor}v(C)}{\Pi_{l^{\prime}=1}^{l}|\lfloor
C_{l^{{}^{\prime}}}(i)\rfloor|}.$

The fourth and last proposal is to allocate to each player its individual
worth, plus the remainder of the worth of the grand coalition divided equally
among the players, but taking into account the level structure.

###### Definition 3.4

The LESD3-value is defined for every $(N,v,\mathcal{L})$ and $i\in N$ by

$LESD^{3}_{i}=v(i)+\frac{v(C_{k+1}(i))-\sum_{j\in
N}v(j)}{\Pi_{l=1}^{k+1}|\lfloor C_{l}(i)\rfloor|}.$

To conclude this section, we introduce a few new concepts that we will need in
the next section, in which we provide axiomatic characterizations of the four
values. Given a level game $(N,v,\mathcal{L})$ and level
$l\in\\{0,1,\ldots,k\\}$, we define $v^{l}$, a new characteristic function on
$\mathcal{C}_{l}$, as

$v^{l}(S)=v\left(\bigcup_{C\in S}C\right)\text{ for all
}S\subseteq\mathcal{C}_{l}.$

The $l$-th quotient game $(\mathcal{C}_{l},v^{l})$ is induced from
$(N,v,\mathcal{L})$ by treating unions of $\mathcal{C}_{l}\in\mathcal{L}$ as
players.

Given a level structure
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$
and level $l\in\\{0,1,\ldots,k\\}$, we define the $l$-th truncation of
$\mathcal{L}$, denoted by $\mathcal{L}^{l}$, as a new level structure in which
the set of players is $\mathcal{C}_{l}\in\mathcal{L}$ and
$\mathcal{L}^{l}=\\{\mathcal{C}_{0}^{l},\mathcal{C}_{1}^{l},\ldots,\mathcal{C}_{k-l+1}^{l}\\}$,
with

  * •

$\mathcal{C}_{0}^{l}=\\{\\{S\\}:S\in\mathcal{C}_{l}\\}$.

  * •

$\mathcal{C}_{j}^{l}=\\{\\{T\in\mathcal{C}_{0}^{l}:T\subseteq
Q\\}:Q\in\mathcal{C}_{l+j}\\}$, $j=1,2,\ldots,k-l+1$.

We call $(\mathcal{C}_{l},v^{l},\mathcal{L}^{l})$ the $l$-th truncated game.

Given a TU-game $(N,v)$ and players $i,j\in N$, we say that $i,j$ are
indistinguishable in $(N,v)$ if $v(S\cup i)=v(S\cup j)$ for all $S\subseteq
N\backslash\\{i,j\\}$. We say that $i$ is a nullifying player in $(N,v)$ if
$v(S\cup i)=0$ for all $S\subseteq N$. We say that $i$ is a dummifying player
in $(N,v)$ if $v(S\cup i)=\sum_{j\in S\cup i}v(j)$ for all $S\subseteq N$. The
above definitions extend to level games in a natural way; thus, for example,
we say that $i,j$ are indistinguishable in $(N,v,\mathcal{L})$ if they are
indistinguishable in $(N,v)$. Finally, we denote the restriction of $(N,v)$ on
$S\subset N$ as $(S,v)$.

##  4 Axiomatic characterizations

In this section we provide axiomatic characterizations of the four values
defined in Section 3.

We show below a set of properties that characterizes the first proposal. The
first two properties are standard in the literature. The property of symmetry
among unions on each level says that two indistinguishable coalitions at a
particular level, both included in the same coalition at the next level,
receive the same. The nullifying player property states that a nullifying
player receives zero.

Efficiency. A value $g$ for level games satisfies efficiency if, for all
$(N,v,\mathcal{L})$, it holds that

$\sum_{i\in N}g_{i}(N,v,\mathcal{L})=v(N).$

Additivity. A value $g$ for level games satisfies additivity if, for all
$(N,v,\mathcal{L})$ and $(N,w,\mathcal{L})$, it holds that

$g(N,v,\mathcal{L})+g(N,w,\mathcal{L})=g(N,v+w,\mathcal{L}).$

Symmetry among unions on each level. A value $g$ for level games satisfies
symmetry among unions on each level if, for all $(N,v,\mathcal{L})$, with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$,
$l\in\\{0,1,\ldots,k\\}$ and $C,C^{\prime}\in\mathcal{C}_{l}$, with $C\cup
C^{\prime}\subseteq C^{\prime\prime}\in\mathcal{C}_{l+1}$, indistinguishable
in $(\mathcal{C}_{l},v^{l},\mathcal{L}^{l})$, it holds that

$\sum_{i\in C}g_{i}(N,v,\mathcal{L})=\sum_{j\in
C^{\prime}}g_{j}(N,v,\mathcal{L}).$

Nullifying player property. A value $g$ for level games satisfies the
nullifying player property if, for all $(N,v,\mathcal{L})$ and all $i\in N$
nullifying player in $(N,v,\mathcal{L})$, it holds that

$g_{i}(N,v,\mathcal{L})=0.$

###### Theorem 4.1

The LED-value is the unique value for level games that satisfies efficiency,
additivity, symmetry among unions on each level and nullifying player
property.

###### Proof.

It is immediate to check that the LED-value satisfies efficiency, additivity,
symmetry among unions on each level and nullifying player property. To prove
the unicity, consider a value $g$ for level games satisfying efficiency,
additivity, symmetry among unions on each level and nullifying player
property. Fix $N$ and define, for all $\alpha\in\mathbb{R}$ and all non-empty
$T\subseteq N$, the TU-game $(N,e_{T}^{\alpha})$ given by
$e_{T}^{\alpha}(S)=\alpha$ if $S=T$ and $e_{T}^{\alpha}(S)=0$ if $S\neq T$. If
$T=N$, since $g$ satisfies efficiency and symmetry among unions on each level,
it is clear that

$g_{i}(N,e_{N}^{\alpha},\mathcal{L})=\frac{\alpha}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}$

for any $i\in N$ and
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$,
because all unions in $\mathcal{C}_{l}$ are indistinguishable in
$(\mathcal{C}_{l},(e_{N}^{\alpha})^{l},\mathcal{L}^{l})$, with
$l\in\\{0,1,\ldots,k\\}$. If $T\subset N$, notice that all players in
$N\setminus T$ are nullifying players in $(N,e_{T}^{\alpha})$ and then, since
$g$ satisfies efficiency and nullifying player property,

$\sum_{i\in T}g_{i}(N,e_{T}^{\alpha},\mathcal{L})=\sum_{i\in
N}g_{i}(N,e_{T}^{\alpha},\mathcal{L})=e_{T}^{\alpha}(N)=0.$

Then, since $g$ satisfies symmetry among unions on each level it is not
difficult to check that $g_{i}(N,e_{T}^{\alpha},\mathcal{L})=0$ for all $i\in
N$. Finally, the additivity of $g$ and the fact that $v=\sum_{T\subseteq
N}e_{T}^{v(T)}$ imply that

$g_{i}(N,v,\mathcal{L})=\sum_{T\subseteq
N}g_{i}(N,e_{T}^{v(T)},\mathcal{L})=g_{i}(N,e_{N}^{v(N)},\mathcal{L})=\frac{v(N)}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}$

and thus

$g(N,v,\mathcal{L})=LED(N,v,\mathcal{L}).$

∎

The property of dummifying level/nullifying player property says that if a
player of a dummifying union in the last non trivial partition is a nullifying
player in the game restricted to this union, receives zero. This property
replaces the nullifying player property in the characterization of the first
proposal.

Dummifying level/nullifying player property. A value $g$ for level games
satisfies the dummifying level/nullifying player property if, for all
$(N,v,\mathcal{L})$, with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$,
and all $i\in N$ nullifying player in $(C_{k}(i),v)$ such that $C_{k}(i)$ is a
dummifying player in $(\mathcal{C}_{k},v^{k})$, then it holds that

$g_{i}(N,v,\mathcal{L})=0.$

###### Theorem 4.2

The LESD1-value is the unique value for level games that satisfies efficiency,
additivity, symmetry among unions on each level and dummifying
level/nullifying player property.

###### Proof.

It is immediate to check that the LESD1-value satisfies efficiency,
additivity, symmetry among unions on each level and dummifying
level/nullifying player property. To prove the unicity, consider a value $g$
for level games satisfying efficiency, additivity, symmetry among unions on
each level and dummifying level/nullifying player property. Take
$(N,v,\mathcal{L})$ with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$
and $\mathcal{C}_{k}=\\{C_{1},C_{2},\ldots,C_{m}\\}$. Now, define the TU-game
$(N,v^{*})$ given by

$v^{*}(S)=\sum_{C\in\mathcal{C}_{k}:C\subseteq
S}v(C)=\sum_{j=1}^{m}v^{C_{j}}(S)$

for all $S\subseteq N$, where $v^{C_{j}}(S)=v(C_{j})$ if $C_{j}\subseteq S$
and $v^{C_{j}}(S)=0$ otherwise. Take $C_{r}\in\mathcal{C}_{k}$. Since $g$
satisfies efficiency, then

$\sum_{i\in N}g_{i}(N,v^{C_{r}},\mathcal{L})=v^{C_{r}}(N)=v(C_{r}).$

All unions $C_{j}\in\mathcal{C}_{k}$ are dummifying players in
$(\mathcal{C}_{k},(v^{C_{r}})^{k})$ and all players $i\in C_{j}$, with $j\neq
r$, are nullifying players in $(C_{k}(i),v^{C_{r}})$. By dummifying
level/nullifying player property, $g_{i}(N,v^{C_{r}},\mathcal{L})=0$ for all
$i\notin C_{r}$. For each level $l\in\\{0,1,\ldots,k-1\\}$, unions
$C,C^{\prime}\in\mathcal{C}_{l}$, with $C\cup C^{\prime}\subseteq
C^{\prime\prime}\in\mathcal{C}_{l+1}$ and $C\cup C^{\prime}\subseteq C_{r}$,
are indistinguishable in $(\mathcal{C}_{l},(v^{C_{r}})^{l},\mathcal{L}^{l})$,
then symmetry among unions on each level implies that, for all $i\in C_{r}$,

$g_{i}(N,v^{C_{r}},\mathcal{L})=\frac{v(C_{r})}{\Pi_{l=1}^{k}|\lfloor
C_{l}(i)\rfloor|}=\frac{v(C_{k}(i))}{\Pi_{l=1}^{k}|\lfloor C_{l}(i)\rfloor|}.$

Using the additivity of $g$, for all $i\in N$,

$g_{i}(N,v^{*},\mathcal{L})=\frac{v(C_{k}(i))}{\Pi_{l=1}^{k}|\lfloor
C_{l}(i)\rfloor|}.$ (1)

Define now the characteristic functions $v^{**}=v-v^{*}$ and, for all
$\alpha\in\mathbb{R}$ and all non-empty $T\subseteq N$, $e_{T}^{\alpha}$ given
by $e_{T}^{\alpha}(S)=\alpha$ if $S=T$ and $e_{T}^{\alpha}(S)=0$ if $S\neq T$.
It is clear that $v^{**}=\sum_{T\subseteq N}e^{v^{**}(T)}_{T}$. If $T=N$,
since $g$ satisfies efficiency and symmetry among unions on each level, it is
clear that, for all $i\in N$, $g_{i}(N,e^{v^{**}(N)}_{N},\mathcal{L})$ is
given by

$\frac{{v^{**}(N)}}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}=\frac{v(N)-\sum_{C\in\mathcal{C}_{k}}v(C)}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}=\frac{v(C_{k+1}(i))-\sum_{C\in\lfloor
C_{k+1}(i)\rfloor}v(C)}{\Pi_{l=1}^{k+1}|\lfloor C_{l}(i)\rfloor|}.$

If $T\subset N$, consider two cases:

  * •

Take $T=\cup_{C\in R}C$, with $\emptyset\subset R\subset\mathcal{C}_{k}$. For
all $C_{j}\in\mathcal{C}_{k}$, if $T\neq C_{j}$ then
$e_{T}^{v^{**}(T)}(C_{j})=0$ and if $T=C_{j}$ then
$e_{T}^{v^{**}(T)}(C_{j})=v^{**}(C_{j})=0$. Hence, it is easy to see that all
unions in $\mathcal{C}_{k}\setminus R$ are dummifying players in
$(\mathcal{C}_{k},(e_{T}^{v^{**}(T)})^{k})$. Also, since all players $i\in
N\setminus T$ are nullifying players in $(C_{k}(i),e^{v^{**}(T)}_{T})$,
dummifying level/nullifying player property implies that
$g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=0$ for all $i\in N\setminus T$. Notice
that since all unions in $R$ are indistinguishable in
$(\mathcal{C}_{k},(e_{T}^{v^{**}(T)})^{k},\mathcal{L}^{k})$, then by symmetry
among unions on each level, $\sum_{i\in
C}g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=\sum_{i\in
C^{\prime}}g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})$ for all $C,C^{\prime}\in
R$; notice also that, since

$\sum_{i\in T}g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=\sum_{i\in
N}g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=e^{v^{**}(T)}_{T}(N)=0,$

then $\sum_{i\in C}g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=0$ for all $C\in R$.
To conclude, symmetry among unions on each level implies that
$g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=0$ for all $i\in C\in R$, and
therefore for all $i\in T$.

  * •

For any other $T\subset N$ that is not in the previous case, the game
$(\mathcal{C}_{k},(e_{T}^{v^{**}(T)})^{k})$ satisfies that
$(e_{T}^{v^{**}(T)})^{k}(R)=0$ for all $R\subseteq\mathcal{C}_{k}$ and, thus,
all unions in $\mathcal{C}_{k}$ are indistinguishable and dummifying players
in $(\mathcal{C}_{k},(e_{T}^{v^{**}(T)})^{k})$. If $i\in N\setminus T$, then
$i$ is a nullifying player in $(C_{k}(i),e^{v^{**}(T)}_{T})$ and dummifying
level/nullifying player property implies that
$g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=0$. Analogously as in the previous
case, symmetry among unions on each level implies that
$g_{i}(N,e^{v^{**}(T)}_{T},\mathcal{L})=0$ for all $i\in T$.

Now additivity implies that, for all $i\in N$,

$g_{i}(N,v^{**},\mathcal{L})=\sum_{T\subseteq
N}g_{i}(N,e_{T}^{v^{**}(T)},\mathcal{L})=\frac{{v^{**}(N)}}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}.$ (2)

Finally, from (1), (2), additivity and $v=v^{*}+v^{**}$ it is clear that

$g(N,v,\mathcal{L})=LESD^{1}(N,v,\mathcal{L}).$

∎

To characterize the third proposal, we use the same set of properties included
in the previous theorems to characterize the first and second proposal, with a
unique modification. The property of dummifying unions for a player replaces
the nullifying player property of the first proposal or the dummifying
level/nullifying player property of the second. The dummifying unions for a
player property states that if the union containing a particular player is a
dummifying union at every level, then this player receives his/her individual
worth.

Dummifying unions for a player property. A value $g$ for level games satisfies
the dummifying unions for a player property if, for all $(N,v,\mathcal{L})$
with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$,
and all $i\in N$ such that $C_{l}(i)\in\mathcal{C}_{l}$ is a dummifying player
in $(\mathcal{C}_{l},v^{l})$ for all $l\in\\{0,1,\ldots,k\\}$, then it holds
that

$g_{i}(N,v,\mathcal{L})=v(i).$

###### Theorem 4.3

The LESD2-value is the unique value for level games that satisfies efficiency,
additivity, symmetry among unions on each level and dummifying unions for a
player property.

###### Proof.

It is immediate to check that the LESD2-value satisfies efficiency,
additivity, symmetry among unions on each level and dummifying unions for a
player property. To prove the unicity, consider a value $g$ for level games
that satisfies efficiency, additivity, symmetry among unions on each level and
dummifying unions for a player property. Take $(N,v,\mathcal{L})$ with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$
and define $v^{a}$, for all $S\subseteq N$, by

$v^{a}(S)=\sum_{i\in S}v(i).$

Define $\tilde{v}$, for all $S\subseteq N$, by

$\tilde{v}(S)=(v-v^{a})(S)-\sum_{C\in\mathcal{C}_{k}:C\subseteq
S}(v-v^{a})(C).$

Now define $v^{*}_{l}$, for all $l\in\\{1,2,\ldots,k\\}$ with
$\mathcal{C}_{l}=\\{C_{l,1},C_{l,2},\ldots,C_{l,|\mathcal{C}_{l}|}\\}$, by

$v^{*}_{l}(S)=\sum_{C\in\mathcal{C}_{l}:C\subseteq
S}\left(v(C)-\sum_{C^{\prime}\in\mathcal{C}_{l-1}:C^{\prime}\subseteq
C}v(C^{\prime})\right)=\sum_{j=1}^{|\mathcal{C}_{l}|}v^{C_{l,j}}_{l}(S)$

for all $S\subseteq N$, where
$v^{C_{l,j}}_{l}(S)=v(C_{l,j})-\sum_{C^{\prime}\in\mathcal{C}_{l-1}:C^{\prime}\subseteq
C_{l,j}}v(C^{\prime})$ if $C_{l,j}\subseteq S$ and $v^{C_{l,j}}_{l}(S)=0$
otherwise. For all $l\in\\{0,1,\ldots,k\\}$, $C_{l}(i)\in\mathcal{C}_{l}$ is a
dummifying player in $(\mathcal{C}_{l},(v^{a})^{l})$; hence, dummifying unions
for a player property implies that, for all $i\in N$,

$g_{i}(N,v^{a},\mathcal{L})=v^{a}(i)=v(i).$ (3)

Take now $l\in\\{1,2,\ldots,k\\}$ and $C_{r}\in\mathcal{C}_{l}$. Since $g$
satisfies efficiency, then

$\sum_{i\in
N}g_{i}(N,v^{C_{r}}_{l},\mathcal{L})=v^{C_{r}}_{l}(N)=v(C_{r})-\sum_{C^{\prime}\in\mathcal{C}_{l-1}:C^{\prime}\subseteq
C_{r}}v(C^{\prime}).$

For all $l^{\prime}\in\\{0,1,\ldots,l\\}$, all unions
$C\in\mathcal{C}_{l^{\prime}}$ such that $C\nsubseteq C_{r}$ are dummifying
players in $(\mathcal{C}_{l^{\prime}},(v^{C_{r}}_{l})^{l^{\prime}})$. By
dummifying unions for a player property,
$g_{i}(N,v^{C_{r}}_{l},\mathcal{L})=v^{C_{r}}_{l}(i)=0$ for all $i\notin
C_{r}$. And since all players in $C_{r}$ are indistinguishable in
$(N,v^{C_{r}}_{l},\mathcal{L})$, then symmetry among unions on each level
implies that, for all $i\in C_{r}$,

$g_{i}(N,v^{C_{r}}_{l},\mathcal{L})=\frac{v^{C_{r}}_{l}(C_{r})}{\Pi_{l^{\prime}=1}^{l+1}|\lfloor
C_{l^{\prime}}(i)\rfloor|}.$

Using additivity, for all $i\in N$,

$g_{i}(N,v^{*}_{l},\mathcal{L})=\frac{v^{C_{l}(i)}_{l}(C_{l}(i))}{\Pi_{l^{\prime}=1}^{l+1}|\lfloor
C_{l^{\prime}}(i)\rfloor|}.$ (4)

Define, for all $\alpha\in\mathbb{R}$ and all non-empty $T\subseteq N$, the
TU-game $(N,e_{T}^{\alpha})$ given by $e_{T}^{\alpha}(S)=\alpha$ if $S=T$ and
$e_{T}^{\alpha}(S)=0$ if $S\neq T$. Take now into account that
$\tilde{v}=\sum_{T\subseteq N}e^{\tilde{v}(T)}_{T}$. If $T=N$, since $g$
satisfies efficiency and symmetry among unions on each level, it is clear that
for all $i\in N$,

$g_{i}(N,e^{\tilde{v}(N)}_{N},\mathcal{L})=\frac{{\tilde{v}(N)}}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}.$

If $T\subset N$, consider two cases:

  * •

Take $T=\cup_{C\in R}C$, with $\emptyset\subset R\subset\mathcal{C}_{k}$. For
all $C_{j}\in\mathcal{C}_{k}$, if $T\neq C_{j}$ then
$e_{T}^{\tilde{v}(T)}(C_{j})=0$ and if $T=C_{j}$ then
$e_{T}^{\tilde{v}(T)}(C_{j})=\tilde{v}(C_{j})=0$. Also, if
$Q\subseteq\mathcal{C}_{k}$ with $(\mathcal{C}_{k}\setminus R)\cap
Q\neq\emptyset$, then $e_{T}^{\tilde{v}(T)}(\cup_{C\in Q}C)=0$. For all $i\in
N\setminus T$ and $l\in\\{0,1,\ldots,k\\}$, $C_{l}(i)\in\mathcal{C}_{l}$ is a
dummifying player in
$(\mathcal{C}_{l},(e^{\tilde{v}(T)}_{T})^{l},\mathcal{L}^{l})$, then
dummifying unions for a player property implies that
$g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=e^{\tilde{v}(T)}_{T}(i)=0$. Notice
that all unions in $R$ are indistinguishable in
$(\mathcal{C}_{k},(e^{\tilde{v}(T)}_{T})^{k},\mathcal{L}^{k})$, then by
symmetry among unions on each level, $\sum_{i\in
C}g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=\sum_{i\in
C^{\prime}}g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})$ for all $C,C^{\prime}\in
R$; and notice also that, since

$\sum_{i\in T}g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=\sum_{i\in
N}g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=e^{\tilde{v}(T)}_{T}(N)=0,$

then $\sum_{i\in C}g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=0$ for all $C\in
R$. Hence, symmetry among unions on each level implies that
$g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=0$ for all $i\in T$.

  * •

For any other $T\subset N$ that is not in the previous case, notice that
$e_{T}^{\tilde{v}(T)}(\cup_{C\in Q}C)=0$ for all $Q\subseteq\mathcal{C}_{k}$.
If $i\in N\setminus T$, union $C_{l}(i)\in\mathcal{C}_{l}$ is a dummifying
player in $(\mathcal{C}_{l},(e^{\tilde{v}(T)}_{T})^{l},\mathcal{L}^{l})$ for
all $l\in\\{0,1,\ldots,k\\}$, then by dummifying unions for a player property,
$g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=e^{\tilde{v}(T)}_{T}(i)=0$.
Analogously as in the previous case, symmetry among unions on each level
implies that $g_{i}(N,e^{\tilde{v}(T)}_{T},\mathcal{L})=0$ for all $i\in T$.

Now additivity implies that, for all $i\in N$,

$g_{i}(N,\tilde{v},\mathcal{L})=\sum_{T\subseteq
N}g_{i}(N,e_{T}^{\tilde{v}(T)},\mathcal{L})=\frac{{\tilde{v}(N)}}{\Pi_{l=1}^{k+1}|\lfloor
C_{l}(i)\rfloor|}.$ (5)

Finally, from (3), (4), (5), additivity and
$v=v^{a}+\tilde{v}+\sum_{l=1}^{k}v^{*}_{l}$ it is clear that

$g(N,v,\mathcal{L})=LESD^{2}(N,v,\mathcal{L}).$

∎

Finally, we present a set of properties that characterize the last proposal.
Efficiency and additivity are common to the previous characterizations. The
two new properties are: weak symmetry among unions on each level and
dummifying player property. The dummifying player property states that a
dummifying player receives his/her individual worth. Similar to the nullifying
player of the first proposal, this property only takes into account the
characteristic function of the game, and does not depend on the level
structure. The weak symmetry among unions property on each level is a weaker
version of the symmetry among unions property on each level (used to
characterize the first proposal) because only indistinguishable coalitions
formed by players with individual worth equal to zero receive the same. It is
clear that if a value satisfies the property of symmetry among unions on each
level, it also satisfies the weak property of symmetry among unions on each
level. Then, there is not exist a value that satisfies efficiency, additivity,
symmetry among unions on each level and dummifying player property.

Dummifying player property. A value $g$ for level games satisfies the
dummifying player property if, for all $(N,v,\mathcal{L})$ and all $i\in N$
dummifying player in $(N,v,\mathcal{L})$, it holds that

$g_{i}(N,v,\mathcal{L})=v(i).$

Weak symmetry among unions on each level. A value $g$ for level games
satisfies weak symmetry among unions on each level if, for all
$(N,v,\mathcal{L})$, with
$\mathcal{L}=\\{\mathcal{C}_{0},\mathcal{C}_{1},\ldots,\mathcal{C}_{k+1}\\}$
and $v(i)=0$ for all $i\in N$, $l\in\\{0,1,\ldots,k\\}$ and
$C,C^{\prime}\in\mathcal{C}_{l}$, with $C\cup C^{\prime}\subseteq
C^{\prime\prime}\in\mathcal{C}_{l+1}$, indistinguishable in
$(\mathcal{C}_{l},v^{l},\mathcal{L}^{l})$, it holds that

$\sum_{i\in C}g_{i}(N,v,\mathcal{L})=\sum_{j\in
C^{\prime}}g_{j}(N,v,\mathcal{L}).$

###### Theorem 4.4

The LESD3-value is the unique value for level games that satisfies efficiency,
additivity, weak symmetry among unions on each level and dummifying player
property.

###### Proof.

It is immediate to check that the LESD3-value satisfies efficiency,
additivity, weak symmetry among unions on each level and dummifying player
property. To prove the unicity, consider a value $g$ for level games
satisfying efficiency, additivity, weak symmetry among unions on each level
and dummifying player property. Take $(N,v,\mathcal{L})$ and define $v^{a}$,
for all $S\subseteq N$, by

$v^{a}(S)=\sum_{i\in S}v(i).$

Define $v^{0}=v-v^{a}$. Additivity implies that

$g(N,v,\mathcal{L})=g(N,v^{a},\mathcal{L})+g(N,v^{0},\mathcal{L}).$ (6)

Since $i$ is a dummifying player in $(N,v^{a})$, for all $i\in N$, then
dummifying player property implies that

$g_{i}(N,v^{a},\mathcal{L})=v^{a}(i)=v(i).$ (7)

Now, using for $(N,v^{0},\mathcal{L})$ analogous arguments as those used in
the proof of Theorem 4.1, it is easy to see that efficiency, additivity, weak
symmetry among unions on each level and dummifying player property imply that

$g(N,v^{0},\mathcal{L})=LED(N,v^{0},\mathcal{L}).$ (8)

Finally, from (6), (7) and (8) it is clear that

$g(N,v,\mathcal{L})=LESD^{3}(N,v,\mathcal{L}).$

∎

##  5 Concluding remarks

In this article we have extended the equal division value and the equal
surplus division value to level games. In the latter case, we have relied on
three extensions of such a value for cooperative games with a priori unions
described in Alonso-Meijide et al. (2020). In Gonçalves-Dosantos and Alonso-
Meijide (2021) two new variants of the equal surplus value for cooperative
games with a priori unions are proposed. A topic for future work is the
extension of these two variants to games with levels.

One of the advantages of the values based on the equal sharing criterion is
that they are generally calculable in moderate times even for games with many
players, because they do not make use of the full characteristic function of
the game. In any case, in order for managers to be able to make use of the
values considered here, it would be convenient to make available to the
community a computer tool developed in free software to calculate them. In the
near future it would be interesting to generate such a tool.

## References

Alonso-Meijide JM, Costa J, García-Jurado I, Gonçalves-Dosantos JC (2020). On
egalitarian values for cooperative games with a priori unions. TOP 28,
672-688.
Casajus A, Hüttner F (2014). Null, nullifying, or dummifying players: The
difference between the Shapley value, the equal division value, and the equal
surplus division value. Economics Letters 122, 167-169.
Driessen TSH, Funaki Y (1991). Coincidence of and collinearity between game
theoretic solutions. OR Spectrum 13, 15-30.
Gonçalves-Dosantos JC, Alonso-Meijide JM (2021). New results on egalitarian
values for games with a priori unions. To appear in Optimization, DOI:
10.1080/02331934.2021.1995731
Hu XF, Li DF (2021). The equal surplus division value for cooperative games
with a level structure. Group Decision and Negotiation 30, 1315-1341.
Owen G (1977) Values of games with a priori unions. In: Mathematical Economics
and Game Theory (R Henn, O Moeschlin, eds.), Springer, 76-88.
Selten R (1972). Equal share analysis of characteristic function experiments.
In: Contributions to Experimental Economics III. (Sauermann H, ed.), Mohr
Siebeck, 130-165.
van den Brink R (2007). Null or nullifying players: the difference between the
Shapley value and equal division solutions. Journal of Economic Theory 136,
767-775.
Winter E (1989). A value for cooperative games with levels structure of
cooperation. International Journal of Game Theory 18, 227-240.