# Connection Incentives in Cost Sharing Mechanisms with Budgets

Tianyi Zhang, Dengji Zhao, Junyu Zhang, and Sizhe Gu  ShanghaiTech
UniversityShanghaiChina zhangty, zhaodj, zhangjy22022,
<EMAIL_ADDRESS>
###### Abstract.

In a cost sharing problem on a weighted undirected graph, all other nodes want
to connect to the source node for some service. Each edge has a cost denoted
by a weight and all the connected nodes should share the total cost for the
connectivity. The goal of the existing solutions (e.g. folk solution and
cycle-complete solution) is to design cost sharing rules with nice properties,
e.g. budget balance and cost monotonicity. However, they did not consider the
cases that each non-source node has a budget which is the maximum it can pay
for its cost share and may cut its adjacent edges to reduce its cost share. In
this paper, we design two cost sharing mechanisms taking into account the
nodes’ budgets and incentivizing all nodes to report all their adjacent edges
so that we can minimize the total cost for the connectivity.

Cost sharing, Mechanism design, Budgets, Truthfulness

††copyright: none

##  1\. Introduction

Cost sharing problems are popular in economics and computer science (Moulin
and Shenker, 2001; Leonardi and Schäfer, 2004; Lorenzo and Lorenzo-Freire,
2009; Trudeau and Vidal-Puga, 2020). There are a group of agents located at
different points and a source. The agents need to connect to the source
directly or indirectly in order to get a service or information (Moulin, 1999;
Gómez-Rúa and Vidal-Puga, 2017; Todo and Yokoo, 2020; Bergantiños et al.,
2022). The cost of connecting any pair of agents is known and the total cost
of connectivity has to be shared among all connected agents. This setting
models many real-world applications from telephone and cable TV to water
supply networks (Gómez-Rúa and Vidal-Puga, 2011; Trudeau and Vidal-Puga, 2017;
Trudeau, 2023).

To connect with the source, an agent may need to go through other agents. The
intermediate agents can strategically block the connection if their cost share
is reduced by doing so. However, such strategic behavior will potentially
increase the total cost of connecting all agents. Therefore, it is important
to design cost sharing mechanisms to prevent such strategic behavior so that
we can minimize the total cost of the connectivity.

To solve the problem, we propose a cost sharing mechanism where each agent
pays an average marginal cost to connect it to the source under the assumption
that each agent’s budget is unlimited. The reason for this assumption is that
in some scenarios all the agents have enough budgets to pay their cost share.
Since there exist some scenarios where the amount each agent can pay is
limited, we also consider the situation where each agent has a limited budget
for the share. Then we need to make sure that each agent can afford its cost
share. One intuitive idea is that agents with larger budgets cover more costs
than the agents with lower budgets. We need to give the agents with larger
budgets incentives to do so, otherwise they will disconnect the agents with
lower budgets. To that end, we determine their cost share in terms of their
savings which are the difference between their budgets and the total cost.

_Our contribution:_ For cost sharing problems, to incentivize agents to share
all their connections, we first design a mechanism where each agent’s budget
is unlimited that satisfies truthfulness (each agent is incentivized to offer
all its connections) and other desirable properties studied in the literature.
However, this mechanism does not satisfy budget feasibility (each agent’s
budget is larger than its cost share) when each agent’s budget is limited.
Therefore, we propose another mechanism that satisfies budget feasibility,
truthfulness and other desirable properties.

##  2\. Related Work

There is a rich literature for the cost sharing problem (Bergantios and Vidal-
Puga, 2020; Bergantiños and Lorenzo, 2021; Hernández et al., 2023) (see the
paper (Bergantios and Vidal-Puga, 2021) for a comprehensive overview).

Some treated the problem from the non-cooperative game perspective. Tijs and
Driessen (Tijs and Driessen, 1986) proposed the cost gap allocation (CGA)
method based on marginal contribution. Bird (Bird, 1976), Dutta and Kar (Dutta
and Kar, 2004), Norde et al. (Norde et al., 2004), Tijs et al. (Tijs et al.,
2006) and Hougaard et al. (Hougaard et al., 2010) provided cost sharing
policies based on the minimum spanning tree (Prim, 1957) of a graph. However,
they all cannot prevent the strategic behavior of agents since the agents can
change the minimum spanning tree to reduce their cost share.

Others treated the problem from the cooperative game perspective. They are all
based on the Shapley value and differ in the definition of the coalition
value. Kar (Kar, 2002) proposed the Kar solution and defined the value of a
coalition $S$ as the minimal cost of connecting all agents of $S$ to the
source without going through the agents outside of $S$. Bergantiños and Vidal-
Puga (Bergantiños and Vidal-Puga, 2007a) proposed the folk solution. They
first computed the irreducible cost matrix, and then based on it, they defined
the value of a coalition $S$ in the same way as the Kar solution. However, the
folk solution throws away much information of the original graph. To look for
a way to obtain a solution without throwing away as much information as the
folk solution, Trudeau (Trudeau, 2012) proposed the cycle-complete solution.
They made a less extreme transformation of the cost matrix.

These solutions all assumed that the agents in a coalition cannot use others
outside of the coalition to connect to the source. Furthermore, Bergantiños
and Vidal-Puga (Bergantiños and Vidal-Puga, 2007b) introduced the optimistic
game-based solution, where the value of a coalition $S$ is defined as the
minimal cost of connecting all agents of $S$ to the source given that agents
outside of $S$ are already connected to the source.

In summary, existing solutions are limited to complete graphs and do not
consider the scenario where each agent has a budget to pay its cost share and
has a strategic behavior. Therefore, they are inadequate for solving our
problem.

##  3\. The Model

We consider a cost sharing problem to connect all the nodes on a weighted
undirected graph $G=\langle V\cup\\{s\\},E\rangle$. Node $s$ is the source to
which all the other nodes want to connect. The weight of each edge $(i,j)\in
E$ denoted by $c_{(i,j)}\geq 0$ represents the cost to use the edge to connect
$i$ with $j$. The total cost of the connectivity has to be shared among all
connected nodes except for $s$. Each node $i\in V$ has a public budget
$B_{i}>0$ which is the maximum cost that $i$ can pay.

Consider a real scenario of the graph $G=\langle V\cup\\{s\\},E\rangle$, where
$s$ represents a power station and each node $i\in V$ represents a village. A
village can have electricity if there exists an electric transmission line
connecting $s$ to the village. All villages require electricity and they need
to share the total cost of the connectivity. Each village has a budget for the
connectivity.

Given the graph, the minimum cost of connecting all the nodes is the weight of
a minimum spanning tree. The question here is how they share the minimum cost.
We consider a natural strategic behavior that each node except for the source
can cut its adjacent edges to share less cost. An edge $(i,j)$ cannot be used
for the connectivity if either $i$ or $j$ cuts it. Our goal is to design cost
sharing mechanisms to incentivize nodes to share all their adjacent edges so
that we can use all the edges to minimize the total cost of the connectivity.

Formally, let $\theta_{i}$ $(i\in V\cup\\{s\\})$ be the set of $i$’s adjacent
edges and it is called $i$’s type. Let
$\theta=(\theta_{s},\theta_{1},\cdots,\theta_{|V|})$ be the type profile of
all nodes including the source $s$. We also write
$\theta=(\theta_{i},\theta_{-i})$, where
$\theta_{-i}=(\theta_{s},\theta_{1},\cdots,\theta_{i-1},\theta_{i+1},\cdots,\theta_{|V|})$
is the type profile of all nodes except for $i$. Let $\Theta_{i}$ be the type
space of $i$ and
$\Theta=\Theta_{s}\times\Theta_{1}\times\cdots\times\Theta_{|V|}$ be the type
profile space of all nodes.

We design cost sharing mechanisms that ask each node to report the set of its
adjacent edges that can be used for the connectivity. Let
$\theta_{i}^{\prime}\subseteq\theta_{i}$ be the report of $i$, and
$\theta^{\prime}=(\theta_{s},\theta_{1}^{\prime},\cdots,\theta_{|V|}^{\prime})$
be the report profile of all nodes. Note that the source does not behave
strategically in this setting. Given a report profile
$\theta^{\prime}\in\Theta$, the graph induced by $\theta^{\prime}$ is denoted
by $G_{\theta^{\prime}}=\langle
V\cup\\{s\\},E_{\theta^{\prime}}\rangle\subseteq\langle
V\cup\\{s\\},E\rangle$, where
$E_{\theta^{\prime}}=\\{(i,j)|(i,j)\in(\theta_{i}^{\prime}\cap\theta_{j}^{\prime})\\}\subseteq
E$.

###### Definition 3.1.

A cost sharing mechanism consists of a node selection policy
$g:\Theta\rightarrow 2^{V}$, an edge selection policy $f:\Theta\rightarrow
2^{E}$, and a cost sharing policy $x=(x_{i})_{i\in V}$ where
$x_{i}:\Theta\rightarrow\mathbb{R}$. Given a report profile
$\theta^{\prime}\in\Theta$, $g(\theta^{\prime})\subseteq V$ is the set of
connected nodes, $f(\theta^{\prime})\subseteq E_{\theta^{\prime}}$ is the set
of selected edges connecting the nodes in $g(\theta^{\prime})$, and
$x_{i}(\theta^{\prime})$ is the cost share of $i$ (it will be zero if $i\notin
g(\theta^{\prime})$).

For simplicity, we use $(g,f,x)$ to denote a cost sharing mechanism. In the
following, we introduce the desirable properties of a cost sharing mechanism.

Truthfulness requires that for each node, its cost share for the connectivity
is not decreased by cutting its adjacent edges. That is, offering all its
adjacent edges minimizes its cost share.

###### Definition 3.2.

A cost sharing mechanism $(g,f,x)$ satisfies truthfulness if

$x_{i}((\theta_{i},\theta^{\prime}_{-i}))\leq
x_{i}((\theta_{i}^{\prime},\theta^{\prime}_{-i})),$

for all $i\in g(\theta_{i},\theta^{\prime}_{-i})\cap
g(\theta_{i}^{\prime},\theta^{\prime}_{-i})$, for all
$\theta_{i}\in\Theta_{i}$, for all $\theta_{i}^{\prime}\in\Theta_{i}$, and for
all
$\theta_{-i}^{\prime}\in\Theta_{-i}=\Theta_{s}\times\Theta_{1}\times\cdots\times\Theta_{i-1}\times\Theta_{i+1}\times\cdots\times\Theta_{|V|}$.

Budget feasibility requires that each node’s cost share is not over its
budget.

###### Definition 3.3.

A cost sharing mechanism $(g,f,x)$ satisfies budget feasibility (BF) if

$x_{i}(\theta^{\prime})\leq B_{i}$

for all $i\in V$, for all $\theta^{\prime}\in\Theta$.

Cost monotonicity states that the cost share of a selected node will weakly
increase if the cost of one of its adjacent edges increases within the same
report profile.

###### Definition 3.4.

A cost sharing mechanism $(g,f,x)$ satisfies cost monotonicity (CM) if

$x_{i}(\theta^{\prime})\leq x_{i}^{+}(\theta^{\prime})$

for all $\theta^{\prime}\in\Theta$ and for all $i\in g(\theta^{\prime})$,
where $x_{i}^{+}(\theta^{\prime})$ is the cost share of $i$ when the cost of
one edge $(i,j)\in\theta_{i}^{\prime}$ increases and $i$ is still selected.

Budget balance states that the sum of all nodes’ cost share equals the total
cost of the selected edges for all report profiles. That is, the mechanism has
no profit or loss.

###### Definition 3.5.

A cost sharing mechanism $(g,f,x)$ satisfies budget balance (BB) if

$\sum_{i\in V}x_{i}(\theta^{\prime})=\sum_{(i,j)\in
f(\theta^{\prime})}c_{(i,j)}$

for all $\theta^{\prime}\in\Theta$.

Finally, positiveness states that each node’s cost share should be non-
negative.

###### Definition 3.6.

A cost sharing mechanism $(g,f,x)$ satisfies positiveness if

$x_{i}(\theta^{\prime})\geq 0$

for all $i\in V$, for all $\theta^{\prime}\in\Theta$.

In the rest of the paper, we design cost sharing mechanisms to satisfy the
above properties.

##  4\. Cost Sharing with Unlimited Budget

In this section, we first consider the case where each agent’s budget is
unlimited, i.e. they can always afford the cost share. We propose a mechanism
that satisfies truthfulness, cost monotonicity, budget balance and
positiveness.

The key ideas of the mechanism are as follows. First, we compute the minimum
cost of connecting any subset of agents to the source. Then we get the
marginal cost of adding each agent to a subset of other agents. The cost share
of each agent is set to be the average marginal cost considering all possible
joining sequences. The mechanism is formally described in Algorithm 1. A
running example is given in Example 4.1.

Algorithm 1 Average Marginal Cost Mechanism (AMCM)

Input: A report profile $\theta^{\prime}\in\Theta$
Output: The selected nodes $g(\theta^{\prime})$, the selected edges
$f(\theta^{\prime})$, the cost share $x(\theta^{\prime})$

1: Generate $G_{\theta^{\prime}}$;

2: Starting from $s$, use Prim’s algorithm (Prim, 1957) to compute a minimum
spanning tree (MST) of $G_{\theta^{\prime}}$;

3: Set $g(\theta^{\prime})$ to be all the nodes of the MST and
$f(\theta^{\prime})$ to be all the edges of the MST;

4: for each $S\subseteq g(\theta^{\prime})$ do

5: Compute $v(S)$, which is the minimum cost to connect $S$ to $s$;

6: end for

7: for each $i\in g(\theta^{\prime})$ do

8: Compute $x_{i}(\theta^{\prime})$,  (1)
$x_{i}(\theta^{\prime})=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S));$

9: end for

10: for each $i\in V\backslash g(\theta^{\prime})$ do

11: $x_{i}(\theta^{\prime})=0$;

12: end for

13: return $g(\theta^{\prime}),f(\theta^{\prime}),x(\theta^{\prime})$

Figure 1. An example of the AMCM on a graph. The left figure is
$G_{\theta^{\prime}}$ and the right figure is the minimum spanning tree of
$G_{\theta^{\prime}}$. The letter $s$ represents the source, the letters
$A,B,C,D$ represent the nodes, and the numbers on the edges represent the
cost.

###### Example 4.1.

The graph $G_{\theta^{\prime}}$ generated by a report profile
$\theta^{\prime}\in\Theta$ is shown in Figure 1(1). From the minimum spanning
tree of $G_{\theta^{\prime}}$ shown in Figure 1(2), we have

$g(\theta^{\prime})=\\{A,B,C,D\\}$

and

$f(\theta^{\prime})=\\{(s,B),(A,B),(A,C),(A,D)\\}.$

Then we compute the value function of each subset of $g(\theta^{\prime})$. For
example, we have $v(\emptyset)=0$, $v(\\{A\\})=10$, $v(\\{A,B\\})=15$,
$v(\\{A,B,C\\})=21$ and $v(\\{A,B,C,D\\})=26$. Finally, by Equation (1), the
cost share of nodes $A,B,C,D$ is

$x(\theta^{\prime})=\left(\frac{19}{6},\frac{11}{2},\frac{55}{6},\frac{49}{6}\right).$

###  4.1. Properties of AMCM

###### Theorem 4.2.

The average marginal cost mechanism satisfies truthfulness.

###### Proof.

When $i$ truthfully reports its type, its cost share is

(2) $x_{i}(\theta^{\prime})=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S)),$

where $\theta^{\prime}=(\theta_{i},\theta_{-i}^{\prime})$.

When $i$ misreports its type, its cost share is

(3) $x_{i}(\theta^{\prime\prime})=\sum_{S\subseteq
g(\theta^{\prime\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime\prime})|-|S|-1)!}{|g(\theta^{\prime\prime})|!}\cdot(v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)),$

where $\theta^{\prime\prime}=(\theta_{i}^{\prime},\theta_{-i}^{\prime})$ and
$v^{\prime}(S)$ is the value function of $S$.

According to the definition of truthfulness, we need to show
$x_{i}(\theta^{\prime})\leq x_{i}(\theta^{\prime\prime})$.

  1. (1)

When $g(\theta^{\prime})=g(\theta^{\prime\prime})$, for any given set
$S\subseteq V$, we have

(4)
$\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}=\frac{|S|!(|g(\theta^{\prime\prime})|-|S|-1)!}{|g(\theta^{\prime\prime})|!}.$

When $i$ truthfully reports its type, there are two cases for computing
$v(S)$.

     * •

Node $i$ is not visited. If $i$ misreports its type (i.e.
$\theta_{i}^{\prime}\neq\theta_{i}$), then it is still not visited. So we have
$v(S)=v^{\prime}(S)$. According to the definition of $v$, we have
$v^{\prime}(S\cup\\{i\\})\geq v(S\cup\\{i\\})$. Thus it holds that
$v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)\geq v(S\cup\\{i\\})-v(S)$.

     * •

Node $i$ is visited. Then we have $v(S\cup\\{i\\})-v(S)=0$. If $i$ misreports
its type, there are two possibilities.

       * –

If it is still visited, then $v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)=0$.

       * –

If it is not visited, by the monotonicity of value function, we have
$v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)\geq 0$.

Therefore, we have $v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)\geq
v(S\cup\\{i\\})-v(S)$. Recalling to Equation (4), we infer that
$x_{i}(\theta^{\prime})\leq x_{i}(\theta^{\prime\prime})$.

  2. (2)

When $g(\theta^{\prime})\neq g(\theta^{\prime\prime})$, then
$g(\theta^{\prime\prime})$ is a proper subset of $g(\theta^{\prime})$. For
each $S\subseteq g(\theta^{\prime\prime})$, an argument similar to the one
used in the case of $g(\theta^{\prime})=g(\theta^{\prime\prime})$ shows that
the corresponding term in Equation (2) is less than or equal to that in
Equation (3). Whereas for each $S\subseteq g(\theta^{\prime})\backslash
g(\theta^{\prime\prime})$, the corresponding term in Equation (2) equals 0. So
we have $x_{i}(\theta^{\prime})\leq x_{i}(\theta^{\prime\prime})$.

∎

###### Theorem 4.3.

The average marginal cost mechanism satisfies budget balance.

###### Proof.

According to the edge selection policy, our mechanism outputs a spanning tree
of the graph induced by $g(\theta^{\prime})\cup\\{s\\}$. Given a report
profile $\theta^{\prime}\in\Theta$, by Equation (1) and the property of
Shapley value, the sum of all nodes’ cost share equals
$v(g(\theta^{\prime}))$, i.e.

$\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})=v(g(\theta^{\prime})).$

From the definition of value function, $v(g(\theta^{\prime}))$ equals the
total cost of minimum spanning tree of the graph induced by
$g(\theta^{\prime})\cup\\{s\\}$, i.e.

$v(g(\theta^{\prime}))=\sum_{(i,j)\in f(\theta^{\prime})}c_{(i,j)}.$

Thus,

$\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})=\sum_{(i,j)\in
f(\theta^{\prime})}c_{(i,j)}.$

So the proposed mechanism satisfies budget balance. ∎

###### Theorem 4.4.

The average marginal cost mechanism satisfies cost monotonicity.

###### Proof.

Given $\theta^{\prime}\in\Theta$ and nodes $i,j\in g(\theta^{\prime})$, the
cost share of $i$ is

(5) $x_{i}(\theta^{\prime})=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S)).$

When $c_{(i,j)}$ does not change, there are two cases for computing $v(S)$.

  * •

Node $i$ is not visited. If $c_{(i,j)}$ increases, $v(S)$ does not change, and
$v(S\cup\\{i\\})$ increases or does not change. Thus $v(S\cup\\{i\\})-v(S)$
will increase or not change.

  * •

Node $i$ is visited. If $c_{(i,j)}$ increases,

    * –

node $i$ is still visited, then $v(S\cup\\{i\\})-v(S)$ does not change.

    * –

node $i$ is not visited, then $v(S\cup\\{i\\})-v(S)$ increases.

In summary, when $c_{(i,j)}$ increases, $v(S\cup\\{i\\})-v(S)$ increases or
does not change, and so does $x_{i}(\theta^{\prime})$. ∎

###### Theorem 4.5.

The average marginal cost mechanism satisfies positiveness.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for each $i\in V\backslash
g(\theta^{\prime})$, we have $x_{i}(\theta^{\prime})=0$. For each $i\in
g(\theta^{\prime})$, by the definition of value function in Algorithm 1, we
get $v(S\cup\\{i\\})-v(S)\geq 0$ for each $S\subseteq g(\theta^{\prime})$.
Therefore, according to Equation (1), each node’s cost share
$x_{i}(\theta^{\prime})$ is non-negative. ∎

In the following example, we run the AMCM and the algorithm proposed by Claus
and Kleitman (Claus and Kleitman, 1973) on a tree. Note that the latter is
only applied to trees, whereas our mechanism is applied to general graphs.

Figure 2. An example on a tree, where $s$ is the source and the numbers on the
edges represent the cost.

###### Example 4.6.

Figure 2 is generated by $\theta^{\prime}\in\Theta$. We have
$g(\theta^{\prime})=\\{A,B,C\\}$. Then it follows that $v(\\{A\\})=6$,
$v(\\{B\\})=10$, $v(\\{C\\})=11$, $v(\\{A,B\\})=10$, $v(\\{A,C\\})=11$,
$v(\\{B,C\\})=15$, $v(\\{A,B,C\\})=15$ and $v(\emptyset)=0$. By Equation (1),
we get $x_{A}(\theta^{\prime})=2$, $x_{B}(\theta^{\prime})=6$ and
$x_{C}(\theta^{\prime})=7$. Next, we compute each node’s cost share under the
algorithm proposed by Claus and Kleitman (Claus and Kleitman, 1973). According
to the algorithm, the cost of each edge on the tree is equally shared among
all nodes using it to connect to the source. Specifically, the cost of the
edge $(s,A)$ is equally shared among $A,B,C$. The cost of the edge $(A,B)$ is
shared by $B$. The cost of the edge $(A,C)$ is shared by $C$. Therefore, the
cost share of $B$ is $x_{B}(\theta^{\prime})=4+\frac{1}{3}\times 6=6$, the
cost share of $C$ is $x_{C}(\theta^{\prime})=5+\frac{1}{3}\times 6=7$ and the
cost share of $A$ is $x_{A}(\theta^{\prime})=\frac{1}{3}\times 6=2$.

In the above example, the cost share under AMCM equals that under the
algorithm proposed by Claus and Kleitman (Claus and Kleitman, 1973). Actually,
the two methods of computing cost share are equivalent on trees.

###### Theorem 4.7.

Each node’s cost share under the AMCM coincides with that under the algorithm
proposed by Claus and Kleitman (Claus and Kleitman, 1973) on trees.

###### Proof.

First, we prove that the statement holds on a line. Second, we extend the
proof to a tree.

  1. (1)

For a given set $S\subseteq V$ on a line, if $S$ has the elements of
$\\{i,i+1,\cdots,|V|\\}$, we have $v(S\cup\\{i\\})-v(S)=0$. Otherwise,
$S\subseteq\\{1,2,\cdots,i-1\\}$.

     * •

If $S=\emptyset$, then we have

$\phi_{i}=\frac{1}{|V|}(c_{s,1}+\cdots+c_{i-1,i}).$

     * •

If $S=j$ $(1\leq j\leq i-1)$, then we have

$\phi_{i}=\sum_{j=1}^{i-1}\frac{1}{|V|(|V|-1)}(c_{(j,j+1)}+\cdots+c_{(i-1,i)}).$

     * •

If the largest element in $S$ is $2$, then $S=\\{1,2\\}$. Then

$\phi_{i}=\frac{2!(|V|-3)!}{|V|!}(c_{(2,3)}+\cdots+c_{(i-1,i)}).$

     * •

$\cdots$

     * •

If the largest element in $S$ is $i-1$, we have $2\leq|S|\leq i-1$. The
$\phi_{i}$ is

$[\binom{1}{i-2}\frac{2!(|V|-3)!}{|V|!}+\cdots+\binom{i-2}{i-2}\frac{(i-1)!(|V|-i)!}{|V|!}]c_{(i-1,i)}.$

Putting the above analysis together, we obtain

(6)
$\begin{split}\phi_{i}&=\frac{1}{|V|}\cdot(c_{(s,1)}+\cdots+c_{(i-1,i)})+\cdots+[\binom{1}{i-2}\frac{2!(|V|-3)!}{|V|!}+\\\
&\cdots+\binom{i-2}{i-2}\frac{(i-1)!(|V|-i)!}{|V|!}]c_{(i-1,i)}\\\
&=\frac{1}{|V|}c_{(s,1)}+(\frac{1}{n}+\frac{1}{|V|(|V|-1)})c_{(1,2)}+[\frac{1}{|V|}+\frac{1}{|V|(|V|-1)}+\\\
&\frac{1}{|V|(|V|-1)}+\frac{2!(|V|-3)!}{|V|!}]c_{(2,3)}+\cdots\\\
&=\frac{c_{(s,1)}}{|V|}+\frac{c_{(1,2)}}{|V|-1}+\frac{c_{(2,3)}}{|V|-2}+\cdots+\frac{c_{(i-1,i)}}{|V|-i+1}.\end{split}$

Therefore, we prove that the statement holds on a line.

  2. (2)

Consider a scenario where the nodes and their edges form a tree. We denote the
path that node $i$ locates on is $l$ and there are $n$ nodes on this path.
Denote $\overline{l}$ as the set of nodes that do not belong to this path.
Then regarding the number of nodes in $\overline{l}$, we use mathematical
induction to prove the statement.

     * •

If $|\overline{l}|=1$, we assume $l=\\{a\\}$. Thus we have

$V=\\{1,\cdots,i,\cdots,n,a\\}.$

We let $N_{i}=\\{1,\cdots,i-1,i+1,\cdots,n,a\\}$. So all the subsets of
$N_{i}$ can be divided into two parts: the subsets of
$l_{i}=\\{1,\cdots,i-1,i+1,\cdots,n\\}$ and the set formed by adding $a$ to
each subset of $l_{i}$. The power set of $l_{i}$ is denoted by
$2^{l_{i}}=\\{\emptyset,\\{1\\},\cdots,\\{i-1\\},\\{i+1\\},\cdots,\\{n\\},\cdots,\\{1,\cdots,i-1,i+1,\cdots,n\\}\\}$.
The set formed by adding $a$ to each subset of $l_{i}$ is denoted by
$(2^{l_{i}})^{C}=\\{\\{a\\},\\{1,a\\},\cdots,\\{i-1,a\\},\\{i+1,a\\},\cdots,\\{n,a\\},\cdots,\\{1,\cdots,i-1,i+1,\cdots,n,a\\}\\}$.
Next, we analyze each element of $2^{l_{i}}$ and compute $\phi_{i}$.

       * –

For $\emptyset$: we have

$\phi_{i}=\frac{1}{|V|+1}(c_{(s,1)}+\cdots+c_{(i-1,i)}).$

       * –

$\cdots$

       * –

For $\\{i-1\\}$: we have

$\phi_{i}=\frac{1}{(|V|+1)|V|}c_{(i-1,i)}.$

For other subsets, we use the following method to compute $\phi_{i}$.

       * –

The subset with $2$ as the largest element, i.e. $\\{1,2\\}$. We have

$\phi_{i}=\frac{2!(|V|-2)!}{(|V|+1)!}(c_{(2,3)}+\cdots+c_{(i-1,i)}).$

       * –

$\cdots$

       * –

The subset with $i-1$ as the largest element. We have

$\phi_{i}=[\binom{1}{i-2}\frac{2!(|V|-2)!}{(|V|+1)!}+\cdots+\binom{i-2}{i-2}\frac{(i-1)!(|V|-i+1)!}{(|V|+1)!}]c_{(i-1,i)}.$

Therefore, the sum of $\phi_{i}$ is:

(7)
$\begin{split}&\frac{1}{|V|+1}(c_{(s,1)}+\cdots+c_{(i-1,i)})+\cdots+[\binom{1}{i-2}\frac{2!(|V|-2)!}{(|V|+1)!}+\\\
&\cdots+\binom{i-2}{i-2}\frac{(i-1)!(|V|-i)!}{(|V|+1)!}]c_{(i-1,i)}\\\
&=\frac{1}{|V|+1}c_{(s,1)}+\frac{1}{|V|}c_{(1,2)}+\frac{1}{|V|-1}c_{(2,3)}+\cdots+\frac{1}{|V|+2-i}c_{(i-1,i)}.\end{split}$

For all the subsets of $(2^{l_{i}})^{C}$, similarly, we get that the sum of
$\phi_{i}$ is:

(8)
$\begin{split}&\frac{1}{|V|(|V|+1)}c_{(s,1)}+[\frac{1}{|V|(|V|+1)}+\frac{2}{|V|(|V|-1)(|V|+1)}]c_{(1,2)}+\cdots\\\
&=\frac{1}{|V|(|V|+1)}c_{(s,1)}+\frac{1}{|V|(|V|-1)}c_{(1,2)}+\cdots.\end{split}$

At last, we have:

(9)
$\begin{split}\phi_{i}&=[\frac{1}{|V|+1}+\frac{1}{|V|(|V|+1)}]c_{(s,1)}+[\frac{1}{|V|}+\frac{1}{|V|(|V|-1)}]\\\
&c_{(1,2)}+[\frac{1}{|V|-1}+\frac{1}{(|V|-1)(|V|-2)}]c_{(2,3)}+\cdots\\\
&=\frac{c_{(s,1)}}{|V|}+\frac{c_{(1,2)}}{|V|-1}+\cdots+\frac{c_{(i-1,i)}}{|V|-i+1}.\end{split}$

That is, when $|\overline{l}|=1$, the statement holds.

     * •

Assume that the statement holds for $|\overline{l}|=k$. We need to prove that
it holds for $|\overline{l}|=k+1$. We assume that the newly added node is $b$
and the set of nodes not belonging to the set $\\{1,\cdots,n,b\\}$ is
$\overline{l_{k}}$. For each node $i$, we have

(10)
$\begin{split}\phi_{i}&=\sum_{S\subseteq(l\cup\overline{l_{k}}\backslash\\{i\\})}\frac{|S|!(|V|+k-|S|)!}{(k+1+|V|)!}(v(S\cup\\{i\\})-v(S))+\\\
&\sum_{S\cup\\{b\\}}\frac{(|S|+1)!(|V|+k-|S|-1)!}{(k+1+|V|)!}(v(S\cup\\{i\\})-v(S)).\end{split}$

Let

$A=\frac{|S|!(|V|+k-|S|)!}{(k+1+|V|)!}$

and

$B=\frac{(|S|+1)!(|V|+k-|S|-1)!}{(k+1+|V|)!}.$

Then we get

$A+B=\frac{|S|!(|V|+k-1-|S|)!}{(|V|+k)!}.$

Therefore,

$\phi_{i}=\sum_{S\subseteq(l\cup\overline{l_{k}}\backslash\\{i\\})}\frac{|S|!(|V|+k-|S|-1)!}{(k+|V|)!}(v(S\cup\\{i\\})-v(S)).$

According to inductive hypothesis, we get

(11)
$\begin{split}&\sum_{S\subseteq(l\cup\overline{l_{k}}\backslash\\{i\\})}\frac{|S|!(|V|+k-|S|-1)!}{(k+|V|)!}(v(S\cup\\{i\\})-v(S))\\\
&=\frac{c_{(s,1)}}{|V|}+\frac{c_{(1,2)}}{|V|-1}+\frac{c_{(2,3)}}{|V|-2}+\cdots.\end{split}$

Thus we have

$\phi_{i}=\frac{c_{(s,1)}}{|V|}+\frac{c_{(1,2)}}{|V|-1}+\frac{c_{(2,3)}}{|V|-2}+\cdots.$

That is, the statement holds for $|\overline{l}|=k+1$.

∎

##  5\. Cost Sharing with Limited Budget

Now we consider the situation that each node has a limited budget. We first
show that the AMCM defined in Algorithm 1 does not satisfy budget feasibility
by the example illustrated in Figure 3. For nodes $C$ and $D$, since
$x_{C}(\theta^{\prime})=\frac{55}{6}>7=B_{C}$ and
$x_{D}(\theta^{\prime})=\frac{49}{6}>6=B_{D}$, budget feasibility is violated.
So in this section, we propose a new cost sharing mechanism to satisfy budget
feasibility.

For the mechanism to satisfy budget feasibility (i.e. the budget of each node
should cover its cost share), we design a special node selection function
defined in Algorithm 2. When given a graph generated by a report profile and a
set of nodes, the function outputs a subset of nodes connected to the source.
To satisfy budget feasibility, we have to remove those nodes from the final
connection whose budgets are lower than their cost share. In other words, a
node is added to the group of nodes that are connected to the source if its
budget covers the minimal cost of the edges connecting to the group. Following
this principle, starting from $s$, we gradually add nodes into the connected
group until no more nodes can be added.

Algorithm 2 Selection Function $g^{*}$($\theta^{\prime}$,$S$)

Input: A report profile $\theta^{\prime}\in\Theta$, a set $S\subseteq V$

Output: A subset of $S$ connected to the source

1: Generate $G_{\theta^{\prime}}$;

2: Initialize $N=$ $\\{s\\}$;

3: Set $\hat{E}=\\{(p,q)|p\in N,q\in S\\}\subseteq E_{\theta^{\prime}}$;

4: while $\hat{E}$ is not empty do

5: Find the edge $(i,j)$ in $\hat{E}$ with the smallest weight where $i\in N$
and $j\in S\backslash N$;

6: if $B_{j}\geq c_{(i,j)}$ then

7: $N$ $=$ $N\cup\\{j\\}$;

8: $\hat{E}=\\{(p,q)|p\in N,q\in S\backslash N\\}$;

9: else

10: $\hat{E}=$ $\hat{E}\backslash\\{(i,j)\\}$;

11: end if

12: end while

13: return $N\backslash\\{s\\}$

Algorithm 3 Saving-based Cost Sharing Mechanism (SCSM)

Input: A report profile $\theta^{\prime}\in\Theta$

Output: The node selection $g(\theta^{\prime})$, the edge selection
$f(\theta^{\prime})$, the cost share $x(\theta^{\prime})$

1: Set $g(\theta^{\prime})$ = $g^{*}(\theta^{\prime},V$);

2: for each $S\subseteq g(\theta^{\prime})$ do

3: Let $S^{\prime}=g^{*}(\theta^{\prime},S$);

4: Set  (12) $v(S)=\sum_{i\in S^{\prime}}B_{i}-C(S^{\prime}),$ where
$C(S^{\prime})$ is the minimal cost of connecting $S^{\prime}$ to $\\{s\\}$;

5: end for

6: for each $i\in g(\theta^{\prime})$ do

7: Compute $\phi_{i}$,  (13) $\phi_{i}=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S));$

8: Let  (14) $x_{i}(\theta^{\prime})=B_{i}-\phi_{i};$

9: end for

10: for each $i\in V\backslash g(\theta^{\prime})$ do

11: $x_{i}(\theta^{\prime})=0$;

12: end for

13: Set $f(\theta^{\prime})=E^{MST}_{g(\theta^{\prime})}$, where
$E^{MST}_{g(\theta^{\prime})}$ is the set of edges of minimum spanning tree of
the graph induced by $g(\theta^{\prime})\cup\\{s\\}$;

14: return $g(\theta^{\prime}),f(\theta^{\prime}),x(\theta^{\prime})$

Figure 3. An example of the SCSM on a graph. The left figure is
$G_{\theta^{\prime}}$ and the right figure is the minimum spanning tree of
$G_{\theta^{\prime}}$. The letter $s$ is the source, the numbers on the edges
represent the cost and the number in the circle represents the budget of the
node.

After choosing the connected nodes, can we simply apply the AMCM to compute
their cost share to meet their budgets? The answer is no. The example given in
Figure 3 can be used to explain the reason. By Algorithm 2, nodes $C$ and $D$
are selected, but according to the definition of AMCM, they will pay more than
their budgets.

To satisfy budget feasibility, we incorporate the nodes’ budgets into the
computation of their cost share. For the set of selected nodes, we compute its
savings, which are the difference between their budgets and the total cost.
Then we allocate the savings among the nodes in the set so that those nodes
with lower budgets have lower cost shares.

The new mechanism is called saving-based cost sharing mechanism (SCSM) and is
formally described in Algorithm 3. And, it is illustrated by Example 5.1.

###### Example 5.1.

The graph $G_{\theta^{\prime}}$ generated by a report profile
$\theta^{\prime}\in\Theta$ is shown in Figure 3(1). According to Algorithm 2,
first we compare $B_{B}$ with $c_{(s,B)}$. Since $B_{B}>c_{(s,B)}$, node $B$
is selected by the mechanism. Second, since $B_{A}>c_{(A,B)}$, node $A$ is
selected by the mechanism. Similarly, nodes $C$ and $D$ are also selected by
the mechanism. So the set of nodes selected by the mechanism is
$g(\theta^{\prime})=\\{A,B,C,D\\}$ (see Figure 3(2)). For each $S\subseteq
g(\theta^{\prime})$, we compute $g^{*}(\theta^{\prime},S)$ by Algorithm 2. For
example, when $S=\\{B,C\\}$, we have $g^{*}(\theta^{\prime},S)=\\{B\\}$.
Further, by Equation (12), we get the value function of $S$. For example, we
have $v(\\{B,C\\})=\sum_{i\in
g^{*}(\theta^{\prime},\\{B,C\\})}B_{i}-C(g^{*}(\theta^{\prime},\\{B,C\\}))=2$.
By Equation (13) and Equation (14), we compute the cost shares of $A,B,C,D$,
i.e. $x(\theta^{\prime})=(8,6,6.5,5.5)$. From Figure 3(2), the set of selected
edges is

$f(\theta^{\prime})=\\{(s,B),(A,B),(A,C),(A,D)\\}.$

In the following example, we run the SCSM and another method using savings on
a tree.

Figure 4. An example on a tree, where $s$ is the source, the numbers on the
edges represent the cost and the number in each circle represents the budget
of the node.

###### Example 5.2.

Figure 4 is generated by a report profile $\theta^{\prime}\in\Theta$. Using
Algorithm 2, we get $g(\theta^{\prime})=\\{A,B,C\\}$. It follows that
$v(\emptyset)=0$, $v(\\{A\\})=2$, $v(\\{B\\})=0$, $v(\\{C\\})=0$,
$v(\\{A,B\\})=5$, $v(\\{A,C\\})=3$, $v(\\{B,C\\})=0$ and $v(\\{A,B,C\\})=6$.
So we have $\phi_{A}=4,\phi_{B}=1.5,\phi_{C}=0.5$, and thus
$x_{A}(\theta^{\prime})=4$, $x_{B}(\theta^{\prime})=5.5$,
$x_{C}(\theta^{\prime})=5.5$. Then we compute each node’s cost share using its
savings. For node $B$, its savings $B_{B}-c_{(A,B)}$ is shared among $A$ and
$B$ equally. Thus, its cost share is
$x_{B}(\theta^{\prime})=B_{B}-\frac{1}{2}\cdot(B_{B}-c_{(A,B)})=7-\frac{7-4}{2}=5.5$.
Similarly, we have
$x_{C}(\theta^{\prime})=B_{C}-\frac{1}{2}\cdot(B_{C}-c_{(A,C)})=6-\frac{6-5}{2}=5.5$.
For node $A$, its savings are not shared among other nodes. So its cost share
is
$x_{A}(\theta^{\prime})=B_{A}-(B_{A}-c_{s,A})-\frac{1}{2}\cdot(B_{C}-c_{(A,C)})-\frac{1}{2}\cdot(B_{B}-c_{(A,B)})=8-(8-6)-\frac{6-5}{2}-\frac{7-4}{2}=4$.

In the above example, the cost share under SCSM equals that under the method
using savings. In fact, the two methods of computing cost share are equivalent
on trees.

Next, we compare the AMCM with the SCSM. Under AMCM, each node should share
the total cost of the path from itself to the source. Since the AMCM does not
consider its budget at all, its cost share might be larger than its budget.
Under SCSM, each node’s savings (the difference between its budget and the
cost of the edge connecting it to its parent) should be shared among all its
ancestors. In the worst case, the savings allocated to a node is zero.
Therefore, each node’s cost share is not more than its budget.

###  5.1. Properties of SCSM

###### Theorem 5.3.

The saving-based cost sharing mechanism satisfies truthfulness.

###### Proof.

When node $i$ truthfully reports its type $\theta_{i}$ (i.e.
$\theta^{\prime}=(\theta_{i},\theta_{-i}^{\prime})$), its cost share is
$x_{i}(\theta^{\prime})=B_{i}-\phi_{i}$, where

(15) $\phi_{i}=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S)).$

When node $i$ misreports its type $\theta_{i}$ (i.e.
$\theta^{\prime\prime}=(\theta_{i}^{\prime},\theta_{-i}^{\prime})$), its cost
share is $x_{i}(\theta^{\prime\prime})=B_{i}-\phi_{i}^{\prime}$, where

(16) $\phi_{i}^{\prime}=\sum_{S\subseteq
g(\theta^{\prime\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime\prime})|-|S|-1)!}{|g(\theta^{\prime\prime})|!}\cdot(v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)),$

with $v^{\prime}(S)$ being the value function of $S$. All we need to do is to
show $\phi_{i}\geq\phi_{i}^{\prime}$.

  1. (1)

When $g(\theta^{\prime})=g(\theta^{\prime\prime})$, for each $S\subseteq
g(\theta^{\prime})\backslash\\{i\\}$, we have

$\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}=\frac{|S|!(|g(\theta^{\prime\prime})|-|S|-1)!}{|g(\theta^{\prime\prime})|!}.$

Next, we compare $(v(S\cup\\{i\\})-v(S))$ with
$(v^{\prime}(S\cup\\{i\\})-v^{\prime}(S))$ in three cases.

     * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup\\{i\\}$. In
this case, $i$ is selected and there are no more nodes in $S$ being selected
due to $i$’s participation. When $i$ truthfully reports its type, we have

$v(S\cup\\{i\\})-v(S)=B_{i}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup\\{i\\}).$

Since there is at least one edge connecting $i$ to
$g^{*}(\theta^{\prime},S)\cup\\{s\\}$ and $i$ can afford the cost of the edge,
we have

$B_{i}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup\\{i\\})\geq
0.$

When $i$ misreports its type, there are two possibilities.

       * –

$g^{*}(\theta^{\prime\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup\\{i\\}$:
since $C(g^{*}(\theta^{\prime},S))$ cannot use the nodes outside
$g^{*}(\theta^{\prime},S)$, it remains unchanged. Again, due to $i$’s
misreporting, we have

$C(g^{*}(\theta^{\prime\prime},S)\cup\\{i\\})\geq
C(g^{*}(\theta^{\prime},S)\cup\\{i\\}).$

Hence, we infer that $v(S\cup\\{i\\})-v(S)\geq
v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)$.

       * –

$g^{*}(\theta^{\prime\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)$: we have
$v(S\cup\\{i\\})-v(S)\geq v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)=0$.

     * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)$. In this case,
when $i$ truthfully reports its type, it is not selected and we get
$v(S\cup\\{i\\})-v(S)=0$. When node $i$ misreports its type, it is still not
selected since the set of available edges shrinks. Hence, we have
$v(S\cup\\{i\\})-v(S)=v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)=0$.

     * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\}$, where $S_{0}$ denotes the set of nodes that are selected in
$g^{*}(\theta^{\prime},S\cup\\{i\\})$ due to $i$’s participation. When $i$
truthfully reports its type, we have

$\begin{split}&v(S\cup\\{i\\})-v(S)\\\ &=\sum_{j\in
S_{0}\cup\\{i\\}}B_{j}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\}).\\\ \end{split}$

The cost of the edges which belong to the spanning tree generated by Algorithm
2 and which connect $S_{0}\cup\\{i\\}$ to $s$ is larger than or equal to
$C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\})-C(g^{*}(\theta^{\prime},S))$. Hence, we get
$v(S\cup\\{i\\})-v(S)\geq 0$. When node $i$ misreports its type, there are two
possibilities.

       * –

$g^{*}(\theta^{\prime\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)$: since
node $i$ is not selected by our mechanism, it holds that
$v(S\cup\\{i\\})-v(S)\geq v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)=0$.

       * –

$g^{*}(\theta^{\prime\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\}$ with $S_{0}^{{}^{\prime}}\subseteq S_{0}$:
node $i$ is still selected and its misreporting may shrink the set $S_{0}$.
Let

$\begin{split}m_{i}&=v(S\cup\\{i\\})-v(S)\\\ &=\sum_{j\in
S_{0}\cup\\{i\\}}B_{j}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\})\end{split}$

and

$\begin{split}m_{i}^{\prime}&=v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)\\\
&=\sum_{j\in
S_{0}^{{}^{\prime}}\cup\\{i\\}}B_{j}+C(g^{*}(\theta^{\prime\prime},S))-C(g^{*}(\theta^{\prime\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\}).\end{split}$

We infer that

$\begin{split}&m_{i}-m_{i}^{\prime}\\\ &=\sum_{j\in S_{0}\backslash
S_{0}^{{}^{\prime}}}B_{j}-C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\})+C(g^{*}(\theta^{\prime\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})\\\ &=\sum_{j\in S_{0}\backslash
S_{0}^{{}^{\prime}}}B_{j}-C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\})+C(g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})\\\ &-C(g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})+C(g^{*}(\theta^{\prime\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\}).\end{split}$

Since the nodes in $S_{0}\backslash S_{0}^{{}^{\prime}}$ are selected when
node $i$ reports its type truthfully, we get

$\sum_{j\in S_{0}\backslash
S_{0}^{{}^{\prime}}}B_{j}+C(g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})-C(g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\})\geq 0.$

For the nodes in $g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\}$, the cost of the minimum spanning tree of the
graph induced by $g^{*}(\theta^{\prime},S)\cup S_{0}^{{}^{\prime}}\cup\\{i\\}$
will increase when node $i$ misreports its type since the set of available
edges shrinks. Then we have

$C(g^{*}(\theta^{\prime\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})-C(g^{*}(\theta^{\prime},S)\cup
S_{0}^{{}^{\prime}}\cup\\{i\\})\geq 0.$

Thus $m_{i}-m_{i}^{\prime}\geq 0$. Further, we have $v(S\cup\\{i\\})-v(S)\geq
v^{\prime}(S\cup\\{i\\})-v^{\prime}(S)$.

Putting the above analysis together, we have $\phi_{i}\geq\phi_{i}^{\prime}$.

  2. (2)

When $g(\theta^{\prime})\neq g(\theta^{\prime\prime})$, then
$g(\theta^{\prime\prime})$ is a proper subset of $g(\theta^{\prime})$. For
each $S\subseteq g(\theta^{\prime\prime})$, an argument similar to the one
used in the case of $g(\theta^{\prime})=g(\theta^{\prime\prime})$ shows that
the corresponding term in Equation (15) is larger than or equal to that in
Equation (16). Whereas for each $S\subseteq g(\theta^{\prime})\backslash
g(\theta^{\prime\prime})$, the corresponding term in Equation (15) is larger
than or equal to 0. So we have $\phi_{i}\geq\phi_{i}^{\prime}$.

∎

###### Theorem 5.4.

The saving-based cost sharing mechanism satisfies budget feasibility.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for $i\in V\backslash
g(\theta^{\prime})$, its cost share $x_{i}(\theta^{\prime})=0$, which is less
than its budget. For $i\in g(\theta^{\prime})$, we have
$x_{i}(\theta^{\prime})=B_{i}-\phi_{i}$, where

$\phi_{i}=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S)).$

By the definition of selection function, there are three cases.

  * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)$. Since node $i$
is not selected, we have $v(S\cup\\{i\\})-v(S)=0$.

  * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup\\{i\\}$.
Since node $i$ is selected, we have
$v(S\cup\\{i\\})-v(S)=B_{i}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup\\{i\\})$.
From the proof of Theorem 5.3, we have
$B_{i}+C(g^{*}(\theta^{\prime},S))-C(g^{*}(\theta^{\prime},S)\cup\\{i\\})\geq
0$ and thus $v(S\cup\\{i\\})-v(S)\geq 0$.

  * •

$g^{*}(\theta^{\prime},S\cup\\{i\\})=g^{*}(\theta^{\prime},S)\cup
S_{0}\cup\\{i\\}$, where $S_{0}$ denotes the set of nodes that are selected in
$g^{*}(\theta^{\prime},S\cup\\{i\\})$ due to $i$’s participation. From the
proof of Theorem 5.3, we get $v(S\cup\\{i\\})-v(S)\geq 0$.

From the above analysis, it follows that for node $i\in g(\theta^{\prime})$,
$\phi_{i}$ is non-negative. So we infer that $x_{i}(\theta^{\prime})\leq
B_{i}$. ∎

###### Theorem 5.5.

The saving-based cost sharing mechanism satisfies budget balance.

###### Proof.

According to the edge selection policy, our mechanism outputs a spanning tree
of the graph induced by $g(\theta^{\prime})\cup\\{s\\}$. Given a report
profile $\theta^{\prime}\in\Theta$, by
$x_{i}(\theta^{\prime})=B_{i}-\phi_{i}$, we have

$\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})=\sum_{i\in
g(\theta^{\prime})}B_{i}-\sum_{i\in g(\theta^{\prime})}\phi_{i}.$

By the property of Shapley value, we have

$\sum_{i\in g(\theta^{\prime})}\phi_{i}=v(g(\theta^{\prime})).$

Therefore,

$\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})=\sum_{i\in
g(\theta^{\prime})}B_{i}-v(g(\theta^{\prime})).$

By the definition of mechanism, we get

$v(g(\theta^{\prime}))=\sum_{i\in
g(\theta^{\prime})}B_{i}-C(g(\theta^{\prime})).$

Thus, we get

$\begin{split}\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})&=\sum_{i\in
g(\theta^{\prime})}B_{i}-(\sum_{i\in
g(\theta^{\prime})}B_{i}-C(g(\theta^{\prime})))\\\ &=C(g(\theta^{\prime}))\\\
&=\sum_{(i,j)\in f(\theta^{\prime})}c_{(i,j)},\end{split}$

which states that our mechanism satisfies budget balance. ∎

###### Theorem 5.6.

The saving-based cost sharing mechanism satisfies cost monotonicity.

###### Proof.

Given $\theta^{\prime}\in\Theta$, for all $i\in g(\theta^{\prime})$, for all
$(i,j)\in E$, when $c_{(i,j)}$ increases, there are two possibilities.

First, $g(\theta^{\prime})$ does not change. Since
$x_{i}(\theta^{\prime})=B_{i}-\phi_{i}$ where

(17) $\phi_{i}=\sum_{S\subseteq
g(\theta^{\prime})\backslash\\{i\\}}\frac{|S|!(|g(\theta^{\prime})|-|S|-1)!}{|g(\theta^{\prime})|!}\cdot(v(S\cup\\{i\\})-v(S)),$

it suffices to show that $v(S\cup\\{i\\})-v(S)$ decreases or does not change.

  * •

If $i\notin g(\theta^{\prime})$, then $i$ is still not selected by the
mechanism. Thus $v(S\cup\\{i\\})-v(S)$ does not change.

  * •

If $i\in g(\theta^{\prime})$, for node $i$, there are two cases.

    * –

Node $i$ is not selected anymore. Its cost share becomes 0. So
$v(S\cup\\{i\\})-v(S)$ decreases.

    * –

Node $i$ is still selected. For each $S\subseteq V$, by the expression of
$v(S\cup\\{i\\})-v(S)$, it decreases.

Second, $g(\theta^{\prime})$ shrinks. We show that the cost share of $i$
weakly increases.

  * •

If $i\notin g(\theta^{\prime})$, its cost share does not change and the
statement holds.

  * •

If $i\in g(\theta^{\prime})$, then $j\notin g(\theta^{\prime})$. We infer that
$j$ connects to the source through $(i,j)$ before $g(\theta^{\prime})$
shrinks. Therefore, $i$’s savings decrease. Thus the cost share of $i$ weakly
increases.

Putting the above analysis together, when $c_{(i,j)}$ increases, the cost
share of $i$ weakly increases. ∎

##  6\. Conclusions

For cost sharing problems on graphs, we considered an important strategic
behavior of agents, i.e. cutting their adjacent edges. We proposed two
mechanisms where each agent has an unlimited budget or a limited budget
respectively. Our mechanisms can incentivize all agents to offer all their
adjacent edges so that we can minimize the total cost of connectivity by using
all the connections. One meaningful future work is to characterize all
possible such mechanisms.

###### Acknowledgements.

This work is supported by Science and Technology Commission of Shanghai
Municipality (No. 23010503000 and No. 22ZR1442200), and Shanghai Frontiers
Science Center of Human-centered Artificial Intelligence (ShangHAI).

## References

  * (1)
  * Bergantiños et al. (2022) Gustavo Bergantiños, Youngsub Chun, Eunju Lee, and Leticia Lorenzo. 2022.  The folk rule for minimum cost spanning tree problems with multiple sources.  _International Game Theory Review_ 24, 1 (2022), 2150007:1–2150007:36.
  * Bergantiños and Lorenzo (2021) Gustavo Bergantiños and Leticia Lorenzo. 2021.  Cost additive rules in minimum cost spanning tree problems with multiple sources.  _Annals Of Operations Research_ 301, 1 (2021), 5–15.
  * Bergantiños and Vidal-Puga (2007a) Gustavo Bergantiños and Juan J Vidal-Puga. 2007a.  A fair rule in minimum cost spanning tree problems.  _Journal of Economic Theory_ 137, 1 (2007), 326–352.
  * Bergantiños and Vidal-Puga (2007b) Gustavo Bergantiños and Juan J Vidal-Puga. 2007b.  The optimistic TU game in minimum cost spanning tree problems.  _International Journal of Game Theory_ 36, 2 (2007), 223–239.
  * Bergantios and Vidal-Puga (2020) G. Bergantios and J. Vidal-Puga. 2020.  Cooperative games for minimum cost spanning tree problems.  _MPRA Paper_ (2020).
  * Bergantios and Vidal-Puga (2021) Gustavo Bergantios and Juan Vidal-Puga. 2021.  A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems.  _SERIEs_ 12, 1 (2021), 73–100.
  * Bird (1976) Charles G Bird. 1976\.  On cost allocation for a spanning tree: a game theoretic approach.  _Networks_ 6, 4 (1976), 335–350.
  * Claus and Kleitman (1973) Armin Claus and Daniel J Kleitman. 1973.  Cost allocation for a spanning tree.  _Networks_ 3, 4 (1973), 289–304.
  * Dutta and Kar (2004) Bhaskar Dutta and Anirban Kar. 2004.  Cost monotonicity, consistency and minimum cost spanning tree games.  _Games and Economic Behavior_ 48, 2 (2004), 223–248.
  * Gómez-Rúa and Vidal-Puga (2011) María Gómez-Rúa and Juan Vidal-Puga. 2011.  Merge-proofness in minimum cost spanning tree problems.  _International Journal of Game Theory_ 40, 2 (2011), 309–329.
  * Gómez-Rúa and Vidal-Puga (2017) María Gómez-Rúa and Juan Vidal-Puga. 2017.  A monotonic and merge-proof rule in minimum cost spanning tree situations.  _Economic Theory_ 63, 3 (2017), 813–826.
  * Hernández et al. (2023) Penélope Hernández, Josep E. Peris, and Juan J. Vidal-Puga. 2023.  A non-cooperative approach to the folk rule in minimum cost spanning tree problems.  _European Journal of Operational Research_ 307, 2 (2023), 922–928.
  * Hougaard et al. (2010) Jens Leth Hougaard, Hervé Moulin, and Lars Peter Østerdal. 2010.  Decentralized pricing in minimum cost spanning trees.  _Economic Theory_ 44, 2 (2010), 293–306.
  * Kar (2002) Anirban Kar. 2002\.  Axiomatization of the Shapley value on minimum cost spanning tree games.  _Games and Economic Behavior_ 38, 2 (2002), 265–277.
  * Leonardi and Schäfer (2004) Stefano Leonardi and Guido Schäfer. 2004.  Cross-monotonic cost sharing methods for connected facility location games.  _Theoretical Computer Science_ 326, 1-3 (2004), 431–442.
  * Lorenzo and Lorenzo-Freire (2009) Leticia Lorenzo and Silvia Lorenzo-Freire. 2009.  A characterization of Kruskal sharing rules for minimum cost spanning tree problems.  _International Journal of Game Theory_ 38, 1 (2009), 107–126.
  * Moulin (1999) Hervé Moulin. 1999\.  Incremental cost sharing: characterization by coalition strategy-proofness.  _Social Choice and Welfare_ 16, 2 (1999), 279–320.
  * Moulin and Shenker (2001) Hervé Moulin and Scott Shenker. 2001.  Strategyproof sharing of submodular costs: budget balance versus efficiency.  _Economic Theory_ 18, 3 (2001), 511–533.
  * Norde et al. (2004) Henk Norde, Stefano Moretti, and Stef Tijs. 2004\.  Minimum cost spanning tree games and population monotonic allocation schemes.  _European Journal of Operational Research_ 154, 1 (2004), 84–97.
  * Prim (1957) Robert Clay Prim. 1957\.  Shortest connection networks and some generalizations.  _The Bell System Technical Journal_ 36, 6 (1957), 1389–1401.
  * Tijs et al. (2006) Stef Tijs, Rodica Branzei, Stefano Moretti, and Henk Norde. 2006.  Obligation rules for minimum cost spanning tree situations and their monotonicity properties.  _European Journal of Operational Research_ 175, 1 (2006), 121–134.
  * Tijs and Driessen (1986) Stef H Tijs and Theo SH Driessen. 1986.  Game theory and cost allocation problems.  _Management Science_ 32, 8 (1986), 1015–1028.
  * Todo and Yokoo (2020) Taiki Todo and Makoto Yokoo. 2020.  Split manipulations in cost sharing of minimum cost spanning tree.  In _Proceedings of the 2020 European Conference on Artificial Intelligence_. 219–226.
  * Trudeau (2012) Christian Trudeau. 2012\.  A new stable and more responsive cost sharing solution for minimum cost spanning tree problems.  _Games and Economic Behavior_ 75, 1 (2012), 402–412.
  * Trudeau (2023) Christian Trudeau. 2023\.  Minimum cost spanning tree problems as value sharing problems.  _International Journal of Game Theory_ 52, 1 (2023), 253–272.
  * Trudeau and Vidal-Puga (2017) Christian Trudeau and Juan Vidal-Puga. 2017.  On the set of extreme core allocations for minimal cost spanning tree problems.  _Journal of Economic Theory_ 169 (2017), 425–452.
  * Trudeau and Vidal-Puga (2020) Christian Trudeau and Juan J. Vidal-Puga. 2020.  Clique games: a family of games with coincidence between the nucleolus and the Shapley value.  _Mathematical Social Sciences_ 103 (2020), 8–14.


# NERULA: A Dual-Pathway Self-Supervised Learning Framework for
Electrocardiogram Signal Analysis

Gouthamaan Manimaran
Department of Health Technology
Technical University of Denmark
Copenhagen, Denmark
<EMAIL_ADDRESS>
&Sadasivan Puthusserypady
Department of Health Technology
Technical University of Denmark
Copenhagen, Denmark
<EMAIL_ADDRESS>
&Helena Domínguez
Department of Cardiology
Bisperbjerg Hospital
Copenhagen, Denmark
<EMAIL_ADDRESS>
&Adrian Atienza
Department of Health Technology
Technical University of Denmark
Copenhagen, Denmark
<EMAIL_ADDRESS>
&Jakob E. Bardram
Department of Health Technology
Technical University of Denmark
Copenhagen, Denmark
<EMAIL_ADDRESS>

###### Abstract

Electrocardiogram (ECG) signals are critical for diagnosing heart conditions
and capturing detailed cardiac patterns. As wearable single-lead ECG devices
become more common, efficient analysis methods are essential. We present
NERULA (Non-contrastive ECG and Reconstruction Unsupervised Learning
Algorithm), a self-supervised framework designed for single-lead ECG signals.
NERULA’s dual-pathway architecture combines ECG reconstruction and non-
contrastive learning to extract detailed cardiac features. Our 50% masking
strategy, using both masked and inverse-masked signals, enhances model
robustness against real-world incomplete or corrupted data. The non-
contrastive pathway aligns representations of masked and inverse-masked
signals, while the reconstruction pathway comprehends and reconstructs missing
features. We show that combining generative and discriminative paths into the
training spectrum leads to better results by outperforming state-of-the-art
self-supervised learning benchmarks in various tasks, demonstrating superior
performance in ECG analysis, including arrhythmia classification, gender
classification, age regression, and human activity recognition. NERULA’s dual-
pathway design offers a robust, efficient solution for comprehensive ECG
signal interpretation.

##  1 Introduction

In the realm of medical signal processing, the Electrocardiogram (ECG) stands
as a cornerstone for cardiac health assessment. The ECG’s capacity to non-
invasively capture the heart’s electrical activity renders it an indispensable
tool in diagnosing a wide array of cardiac conditions. However, the nuanced
interpretation of ECG signals, traditionally a domain of specialized
clinicians, presents a significant challenge. The advent of machine learning,
particularly in the field of deep learning, has opened new avenues for
automated ECG analysis, offering the potential to augment clinical expertise
with data-driven insights.

Recent advances in machine learning have predominantly leaned on supervised
learning paradigms, where models are trained on large datasets with predefined
labels. Despite their success, these methods are constrained by the
availability of high-quality, annotated datasets, which are expensive and
time-consuming to produce, especially in the medical domain. Furthermore,
supervised models often lack the ability to generalize to new, unseen data, a
limitation particularly pronounced in healthcare applications where patient
variability is high.

Enter self-supervised learning (SSL), a paradigm that learns representations
from data without explicit labels. In the context of ECG analysis, SSL
presents a promising avenue to circumvent the limitations of supervised
approaches. By leveraging the inherent structure within the ECG data, SSL
methods can unearth robust and generalizable features, paving the way for
models that are both data-efficient and adaptable to diverse patient
populations.

Our work introduces a novel approach to self-supervised representation
learning for ECG signals. At its core, our method utilizes a dual-pathway
architecture comprising an ECG reconstruction path and a non-contrastive
learning path, both originating from a shared encoder. This design is
engineered to capture the intricate patterns within ECG signals, facilitating
a comprehensive understanding of cardiac rhythms and potential anomalies.

A key innovation in our approach is the handling of input signals. By
introducing a 50% masking strategy, along with the use of the inverse of the
masked signal, our model is tasked with reconciling these two complementary
views of the same data. This strategy not only enhances the robustness of the
learned representations but also aligns closely with real-world scenarios
where incomplete or corrupted ECG data is commonplace.

The non-contrastive learning path of our model is designed to ensure that the
representations of the masked and inverse-masked signals converge, thus
learning consistent features across different transformations of the data.
Simultaneously, the ECG reconstruction path, guided by Huber loss, assists the
network in understanding and reconstructing the missing features of the ECG
signal, an aspect critical for comprehensive signal interpretation.

The contributions of our work are as follows:

  * •

We introduce NERULA, a novel method in representation learning for Time-Series
signals that merge a Generative (Signal Reconstruction) and Discriminative
(Non-Contrastive Learning) pathway that leads to more efficient learning of
latent features.

  * •

In non-contrastive learning of ECGs, we emphasize the importance of what is
chosen as positive pairs by showing improved results in random masking of
signals over other signal augmentation types like in BYOL or adjacent and non-
overlapping segments like in CLOCS.

  * •

We show that NERULA outperforms other state-of-the-art SSL methods such as
BYOL, SimCLR, and CLOCS in downstream linear evaluation tasks which include
arrhythmia classification, gender classification, age regression, and human
activity recognition benchmarks.

##  2 Related Work

In this section, we introduce some notable works in self-supervised learning
as a whole and also within the context of time-series/ECG signal processing.

Contrastive and Non-Contrastive Learning: There have been many recent works on
self-supervised learning that leverage the use of this concept of ‘positive’
and/or ‘negative’ pairs to learn meaningful features from the input. One of
the most notable works of contrastive learning in computer vision is SimCLR
[3], which uses an augmented view of the input as positive and a different
image as negative. One of the drawbacks of this method is that the choice of
these negative pairs is random across the whole dataset, and some instances,
even if they are from the same class (e.g. bird, tree, etc) might be
considered as negative thereby hindering the learning curves. To overcome
this, BYOL [9] make use of only the positive pairs and use an additional
network (prediction network) which is a moving average of the main network
(target network) to align these two predictions using a non-contrastive loss
function.

(a) Original Signal

(b) Masked Signal

(c) Signal masked in random positions

(d) Inverted-Masked Signal

Figure 1: Signal Masking Strategies for Non-Contrastive Learning

Reconstruction Learning: Meaningful latent representations can also be learned
by methods that are able to reconstruct missing parts of the input signal.
While this train of thought does wonders in the field of natural language
processing in methods like BERT [6] and ERNIE [19] that try to predict
missing/masked words in a sentence, initially there had been no impressive
work in computer vision or time-series processing that show this is a better
approach than the widely used contrastive learning. Some recent work in
computer vision shows that this approach is worth exploring and is mainly
using Masked Autoencoder (MAE) approaches like the work by He et al. [11] in
(2 dimensional) images and Feichtenhofer et al. [7] in (3 dimensional) videos.
Following these methods, there has also been a similar implementation of the
[11] method in ECG processing by Hu et al. [12], where they pass only the non-
masked patches of the ECG signal into the encoder and then pass the latent
representations of this along with the masked tokens to reconstruct the
signal. They show that this approach was able to get higher accuracies than
BYOL and SimCLR in signal classification benchmarks. A more generalized time-
series approach of the same method has been done by Li et al. [15] which we
use for comparisons in this paper.

Addressing the Gap: Both the methods mentioned above have been used
extensively in computer vision, and some methods have also been able to
incorporate learning from both these methods into one hybrid learning curve
like [23] that have loss functions flowing from two separate heads
(contrastive and reconstruction) into a single encoder. However, there has
been little to no work in combining the generative path (reconstruction) and
discriminative path (contrastive) for time-series modeling. It is also worth
noting that one cannot reconstruct a time-series signal the same way as an
image is done. Most works split the images into non-overlapping patches with
discrete but learnable positional encoding to feed into the transformer. While
this may make sense for images, time-series signals are inherently different,
not to mention a whole missing dimension (if leads are not involved in ECGs).
This can be noticed in many classification tasks like the PhysioNet 2021
challenge [1], where most of the winning solutions are convolution-based
algorithms and not transformers - this is mainly due to the continuous
temporal nature of these signals which are not suitable to be split into
patches as a preprocessing step for transformer architecture. Another
significant gap is the choice of data augmentation of a time-series signal.
Augmentations used in computer vision like the Random Crop [20] or Inverting
an axis change the inherent nature of the signals unlike in computer vision
where they still make sense. We address such gaps not only between self-
supervised methods but also the inherent difference between the domains.

##  3 Background

Self-Supervised Learning (SSL) is a form of unsupervised learning where the
data itself provides the supervision. In SSL, the model learns to predict any
part of the data from any other part of it. The general objective function can
be represented as:

$L(\theta)=\sum_{x\in\mathcal{D}}\ell(f_{\theta}(x),x),$ (1)

where $L(\theta)$ is the loss function for a model parameterized by $\theta$,
$\mathcal{D}$ represents the dataset, $f_{\theta}$ is the representation
function, and $\ell$ is a suitable loss measuring the prediction quality.

Contrastive vs Non-Contrastive Learning: In contrastive learning, models learn
to distinguish between similar (positive) and dissimilar (negative) pairs of
data points. Non-contrastive learning, on the other hand, does not explicitly
use negative pairs and focuses on learning representations that bring similar
samples closer in the embedding space. The contrastive and non-contrastive
loss functions can be described as follows:

Contrastive Loss:

$L_{ce}=-\log\frac{\exp(sim(z_{i},z_{j})/\tau)}{\sum_{k=1}^{N}\mathbb{1}_{[k\neq
i]}\exp(sim(z_{i},z_{k})/\tau)}$ (2)

Non-Contrastive Loss:

$L_{nce}=\mathbb{E}_{x,x^{+}}\left[d(f_{\theta}(x),f_{\theta}(x^{+}))\right]$
(3)

where $sim(\cdot)$ is a similarity measure, $\tau$ is a temperature scaling
parameter, $z_{i}$, $z_{j}$, and $z_{k}$ are different data representations,
and $d(\cdot)$ is a distance metric.

Non-contrastive learning is crucial in scenarios where constructing negative
pairs is challenging or may introduce biases and we argue that this is the
case for physiological time-series signals like Electrocardiograms (ECG). It
is also computationally more efficient, avoiding the need for large batches or
memory banks typically used in contrastive learning.

Signal Reconstruction is an emerging paradigm in Self-Supervised Learning
(SSL) where the primary task is to reconstruct the input signal from its
corrupted or partial version. This approach is grounded in the assumption that
a model capable of accurate reconstruction has effectively learned meaningful
and robust representations of the data.

In signal reconstruction, an input signal $x$ is first transformed into a
corrupted or partial version $\tilde{x}$, often through masking or corruption
function $C$. The model, typically an encoder-decoder architecture, then
attempts to reconstruct the original signal $x$ from $\tilde{x}$. The
objective function for signal reconstruction in SSL can be formulated as:

$L_{recon}(\theta)=\mathbb{E}_{x\in\mathcal{D},\tilde{x}=C(x)}\left[\|f_{\theta}(\tilde{x})-x\|^{2}\right]$
(4)

where $L_{recon}(\theta)$ is the reconstruction loss, $f_{\theta}$ is the
reconstruction function parameterized by $\theta$, and $\|\cdot\|^{2}$ denotes
the squared error between the reconstructed and original signals.

This approach is particularly effective in domains where the underlying
structure of the data is complex yet consistent, such as in speech, audio
processing, and time-series analysis. The key advantage of signal
reconstruction as an SSL method lies in its ability to learn intricate data
patterns without the need for explicit labels, thereby enabling models to
generalize better to unseen data.

##  4 Method

###  4.1 Temporal Input Masking

Figure 2: NERULA Structure Overview. The input to the algorithm is the raw
signal and a corresponding random binary mask. From these, we generate a pair
of signals with complimentary masks. Our encoder generates latent
representations of both these signals after which they are passed through a
non-contrastive setup and one of the signals is reconstructed with a decoder.

In this method, we mask exactly 50% of the input for both the tasks - non-
contrastive and reconstruction. In the latter task, the masked input is passed
through a shared encoder and is reconstructed to its original input. For non-
contrastive learning, the two positive pairs are both the same signal but
masked at complementary positions as shown in Fig 1 (b) and (c). The masking
strategy used here is of utmost importance. Randomly masking any 50% positions
of the signal will not contribute much to both tasks. As shown in Fig 1 (d),
we can see that even the randomly masked signal still looks like the original
signal, and can be reconstructed to a reasonable degree by just using linear
interpolation and can be greatly improved in precision if using kernels of
greater sizes. Thus, this is not the ideal strategy to mask signals. Instead,
we mask patches of a signal. The position of the patches, The length, and the
number of these patches are random, and we set the number of such patches to
be between 15-30. This was chosen as having patches that are too large,
hinders the reconstruction of the signal and it fails in such areas.

Table 1: Difference in performance based on the type of positive pairs used for non-contrastive learning. The metrics reported in this table are F1 scores. Augmentation used | SVC | Random Forest
---|---|---
BYOL | 0.45 | 0.30
CLOCS | 0.44 | 0.32
NERULA | 0.49 | 0.42

In Table 1, we show the effect of using different types of augmentation
techniques to generate positive pairs for non-contrastive learning in ECGs. In
all these experiments, we use ResNet [10] as the encoder and a non-contrastive
loss function. The following are the augmentation techniques for each method:

  1. 1.

BYOL uses standard data augmentation techniques like flipping across the x or
y axis, random crop, and gaussian noise.

  2. 2.

CLOCS uses two non-overlapping and adjacent segments from an ECG recording.

  3. 3.

NERULA uses a temporal random mask where the second signal is generated from
the inverted mask.

Through this ablation, we can see the effect of different augmentation
techniques on classification tasks, and it is clear that for ECG modeling,
random masking gives superior performance.

###  4.2 Latent Space Masking

Existing methods in Masked Image Modelling (MIM) like [11, 22, 16, 24, 8] only
pass in the visible patches to the encoder and later pass in the masks at the
correct positions for the decoding stage. We do not do this as our mask patch
sizes are not equal in length and vary in both number and size. Instead, we
pass in the whole input as a single signal - both masked and unmasked parts
into the encoder. As we want only the learned latent representations along
with masked patches at the end, we make use of masked convolutions at every
layer of the encoder. As the shape of the latent space reduces with encoder
depth, we interpolate the mask size to that of the latent vector and multiply
them to get the final masked latent representation. Thus, the relative
position of the masks does not change and the resultant latent vectors still
carry information about the unmasked regions of the signal. This whole vector
is then passed onto the decoder for reconstruction, or non-contrastive loss is
applied to these vectors.

Table 2: Cumulative Improvement in F1 Scores: Gradual Component Addition from BYOL to NERULA | Method | Accuracy | F1 score | Change in F1 Score
---|---|---|---|---
| BYOL | 0.56 | 0.30 | -
1. | +Masking as Augmentation | 0.60 | 0.42 | +12%
2. | +Feature Masking with Local-Lead Attention | 0.64 | 0.48 | +6%
3. | +Reconstruction = NERULA | 0.78 | 0.74 | +26%

####  4.2.1 Choice of Encoder

To be able to have these requirements for masking latent space, as well as a
fast and low computationally demanding encoder, we leverage the work done by
[17], which is an extension of the performer [4] model for time-series or ECG
processing. In this architecture, a sliding window is used to compute
attention weights instead of doing global processing, thus reducing the time
complexity from $O(T^{2}D+D^{2}T)$ to $O(W^{2}TD+D^{2}T)$, where $T$ is number
of time steps, $D$ is the dimension of features and $W$ is the local window
size ($\ll T$).

####  4.2.2 Non-Contrastive Modelling

Due to the masking of latent representations at every layer, we get a final
representation vector of size L (where L$=$128) with masks that are
complimentary for the two positive pairs. Thus, every position that has a
positive value in resultant vector 1, will be zero in resultant vector 2, and
vice-versa. We apply the non-contrastive loss to this pair of vectors.

Consider a data point $x$ and its two masked versions $x_{i}$ and $x_{j}$
generated through the masking strategy explained in the above sections where
if $m$ is the mask of the same length as $x$, then:

$\ x_{i}=m\times x,$ (5) $\ x_{j}=(1-m)\times x.$ (6)

Non-contrastive learning aims to learn an embedding function $f(\cdot)$ such
that the representations $f(x_{i})$ and $f(x_{j})$ are close in the embedding
space. This can be formalized as minimizing a loss function $\mathcal{L}$,
which can be defined in various ways depending on the specific method. We use
the cosine similarity measure to minimize this function:

$\mathcal{L}=-\mathbb{E}_{x,x_{i},x_{j}}\left[\frac{f(x_{i})\cdot
f(x_{j})}{\|f(x_{i})\|\|f(x_{j})\|}\right],$ (7)

where $\mathbb{E}$ denotes the expectation over the data distribution. This
formulation encourages the model to learn embeddings that are invariant to the
augmentations or masking applied to the data, thus capturing the underlying
semantics of the data without relying on contrasting with negative examples.
This approach has been shown to be effective in various tasks, such as image
and text representation learning, where constructing meaningful negative pairs
can be challenging such as in ECG processing.

###  4.3 Reconstruction Path

In the reconstruction of ECG signals, We use the Huber Loss function due to
the inherent attributes of ECG signals like noise and outliers, as different
segments in ECGs like the QRS peaks, P-wave, etc might be abnormal and may be
considered an outlier which hinders efficient learning with Mean-Squared-Error
(MSE) loss. The Huber Loss is less sensitive to outliers than the MSE loss
because it combines the properties of both the mean squared error and the mean
absolute error. It uses a squared error when the error is small and an
absolute error when the error is large, which makes it robust to outliers. The
Huber Loss for a set of predictions can be formally defined as:

$L_{\delta}(y,\hat{y})=\begin{cases}\frac{1}{2}(y-\hat{y})^{2}&\text{for
}|y-\hat{y}|\leq\delta,\\\
\delta\cdot(|y-\hat{y}|-\frac{1}{2}\delta)&\text{otherwise}.\end{cases}$ (8)

Here, $y$ represents the true value of the signal, $\hat{y}$ is the predicted
or reconstructed value, and $\delta$ is a threshold that determines the
transition point between the mean squared error and the mean absolute error.
The use of the Huber Loss in ECG signal reconstruction helps in achieving a
balance between the sensitivity to large errors and robustness to small
errors, making it particularly useful in handling anomalies and preserving the
integrity of the cardiac signal for reliable clinical analysis.

As we use a dual-pathway approach in our method, integrating both non-
contrastive learning and signal reconstruction- To balance the contributions
of these two learning paradigms, we assign weights to their respective loss
functions. Specifically, the loss from the non-contrastive pathway is weighted
by 1, and the loss from the reconstruction pathway is assigned a weight of 10.
This decision was guided by preliminary observations and theoretical
considerations about the relative importance and scale of the two loss
functions in our specific model architecture and dataset. It is important to
note that these weights were chosen based on initial intuitions and practical
considerations, rather than through exhaustive hyperparameter tuning. As such,
they represent a starting point for exploration rather than an optimized
solution. Future work may involve a more systematic investigation into the
optimal balance of these weights, potentially leading to further improvements
in the model’s performance.

##  5 Experiments and Results

###  5.1 Datasets

Training For all our analysis, we chose to train our and other algorithms on
the PhysioNet 2020 [2] dataset which consists of 43,101 12-lead ECG signals
from over 6 hospitals in 4 countries and 3 continents. Each of these
recordings can be mapped to one or more classes with a total of 27 arrhythmia
classes. However since we use this only for self-supervised pre-training, we
do not make use of the labels. Also, since this is a 12-lead dataset, we only
take the lead-II of every recording, since lead-II is the most similar to the
in-the-wild single-lead Holter monitors.

Testing To evaluate all algorithms on Cardiac Arrhythmia classes, we chose the
PhysioNet 2017 [5] dataset which has a total of three classes. This dataset
consists of 8,528 recordings and has a preset split of train and validation,
which we use to both fit the machine learning model (SVC, Random Forest, and
Logistic Regression) and get the scores(Accuracy, F1, AUC).
HAR: To complement our testing of arrhythmia classes, we also test on other
time-series signals to show the learning and generalization ability of our
method. For this, we use the human activity recognition dataset [18] which
contains data from 30 volunteers aged between 19-48, and find the activity
class from the actimetry sensor data. This dataset has 3-axis accelerometer
and gyroscope data along with 6 target classes like walking, sitting, etc.

We apply a consistent data split methodology for all our experiments, using a
train (pretraining), validation (fitting the ML model), and test (computing
final scores) split.

Table 3: Evaluation on arrhythmia classification tasks on the PhysioNet 2017 benchmark. The accuracy, F1 score, and AUC of a 1D ResNet-50 are provided for context. Bold values reflect the top-performing method among the self-supervised algorithms. | SVC | Random Forest | Logistic Regression
---|---|---|---
Method | Accuracy | F1 Score | Accuracy | F1 Score | AUC
ResNet (Supervised) | 0.76 | 0.75 | - | - | 0.89
BYOL | 0.52 | 0.45 | 0.56 | 0.30 | 0.68
SimCLR | 0.53 | 0.49 | 0.57 | 0.27 | 0.67
Ti-MAE | 0.51 | 0.50 | 0.56 | 0.25 | 0.66
CLOCS | 0.51 | 0.45 | 0.59 | 0.36 | 0.66
NERULA | 0.56 | 0.50 | 0.78 | 0.74 | 0.79

###  5.2 Evaluation

We conduct all our experiments on PyTorch and one NVIDIA GeForce RTX 4090 GPU.
The Adam [13] optimizer was used with a learning rate of $\mathrm{1e-4}$ for
all experiments. We evaluate against some of the top algorithms in contrastive
learning (SimCLR [3]), non-contrastive learning (BYOL [9]), reconstruction
learning (Ti-MAE [15]), and SSL in ECG (CMSC version of CLOCS [14]). We use
only this version of CLOCS since the other version requires multiple leads,
which is outside the scope of this work.

Table 4: Gender Classification Accuracy on PTB-XL Method | SVC | Random Forest
---|---|---
BYOL | 0.61 | 0.59
SimCLR | 0.59 | 0.58
Ti-MAE | 0.61 | 0.59
CLOCS | 0.63 | 0.61
NERULA | 0.63 | 0.64

As our work can be seen as an extension across multiple steps from the widely
used BYOL [9] network, we show all additions in our network in Table.
LABEL:cumulative_table along with in the incremental performance in F1 scores
for each increment. We can view BYOL as a standard non-contrastive learning
framework that uses data augmentations like flipping across the x and/or
y-axis, time warping, etc. Given below are each of the additions.

  1. 1.

To this method, we show that using only random masking and generating two
masked views of the input - one masked and the other with an inverted mask
leads to a 12% increase in F1 scores from BYOL.

  2. 2.

In this stage, we mask the latent features at every layer to get a masked
vector of our final representation. We also replace the encoder which was
originally a ResNet [10] with a sliding window-based transformer network with
masked convolutions [17]. This gives us an additional 6% increase in F1.

  3. 3.

Finally, we add our reconstruction network for a dual-pathway architecture
that further improves the F1 in arrhythmia classification by 26%, showing the
importance of reconstruction or generative path in representation learning.

We also show the comparison of our network with other state-of-the-art
algorithms in Table 3. We compare against BYOL [9], SimCLR [3], Ti-MAE [15],
CLOCS [14] and also provide the scores of a purely supervised learning network
(ResNet [10]) to give context.

Table 5: Age Regression metrics on PTB-XL | MLP | Random Forest
---|---|---
Method | MAE $\downarrow$ |  $R^{2}$ $\uparrow$ | MAE $\downarrow$ |  $R^{2}$ $\uparrow$
BYOL | 11.57 | 0.25 | 11.93 | 0.21
SimCLR | 12.54 | 0.12 | 11.80 | 0.22
Ti-MAE | 12.32 | 0.15 | 12.15 | 0.18
CLOCS | 12.20 | 0.16 | 11.79 | 0.22
NERULA | 10.46 | 0.38 | 10.83 | 0.34

In addition to arrhythmia detection, electrocardiogram (ECG) data encapsulate
a plethora of vital information pertinent to various other clinical
assessments. To explore the versatility and adaptability of our algorithm, we
extended our evaluation to include gender classification and age regression
tasks utilizing the PTB-XL dataset [21]. As depicted in Table 4, our proposed
method demonstrates superior performance in the gender classification tasks
compared to existing benchmarks. Furthermore, Table 5 highlights the efficacy
of our approach in age regression in both the mean absolute error (MAE) and
R-squared ($R^{2}$) metrics, underscoring the algorithm’s robustness and
accuracy in predictive modeling across diverse biomedical applications.

In an effort to assess the applicability of our algorithm across various time
series analysis tasks, we also evaluate its performance within the domain of
Human Activity Recognition (HAR). The dataset utilized for this task is
detailed in Section 5.1. Given that our training exclusively involved single-
lead ECG data, our approach involved deriving representations for each axis of
the accelerometer and gyroscope sensors separately. These representations were
then concatenated into a single vector, which subsequently served as the input
for the machine-learning model. Although this methodology diverges from
conventional practices in handling such data, our objective was to explore the
comparative performance of all models when applied to signals distinctly
different from ECG data.

Table 6 presents a comprehensive performance evaluation and comparison of our
model in the context of activity detection using Inertial Measurement Unit
(IMU) sensors. Notably, our model achieved superior scores in this task as
well, further evidencing its versatility across a spectrum of time series
analysis tasks.

Table 6: Evaluation on Human Activity Recognition (HAR) benchmark with 3-axis accelerometer and gyroscope sensors. All scores are from a Random Forest Classifier fit on top of representations trained from the PhysioNet 2020 dataset. Method | Accuracy
---|---
BYOL | 0.85
SimCLR | 0.84
Ti-MAE | 0.67
CLOCS | 0.86
NERULA | 0.87

##  6 Conclusion

In this paper, we presented NERULA, a novel self-supervised learning framework
tailored for ECG signal analysis. Our dual-pathway architecture, combining
non-contrastive learning and signal reconstruction, represents a novel method
in ECG signal processing. The unique 50% masking strategy, complemented by
inverse-masked signals, has demonstrated its effectiveness in enhancing the
robustness of the model and dealing with real-world scenarios involving
incomplete or corrupted ECG data.

One of the critical aspects of NERULA is its ability to effectively learn from
limited and unlabelled data, a common challenge in medical signal processing.
Our approach outperforms existing state-of-the-art methods such as BYOL,
SimCLR, and CLOCS in downstream linear evaluation tasks, indicating its
superiority in extracting meaningful representations from ECG signals.
Furthermore, the use of a local attention mechanism in the encoder aligns well
with the temporal nature of ECG signals, enabling efficient and focused
processing of time-series data.

However, there are several limitations and challenges that we encountered. The
choice of a 50% masking strategy, while empirically effective, was not derived
from an extensive hyperparameter tuning process. Additionally, the decision to
assign different weights to the losses from the reconstruction and non-
contrastive pathways was based on preliminary observations, rather than a
systematic exploration. These choices, while pragmatic, highlight the need for
further research to optimize these parameters.

##  7 Broader Impact

NERULA’s framework for ECG signal analysis can enhance cardiac health
monitoring by providing robust, automated interpretation of ECG data, aiding
in early detection of cardiac anomalies. This technology, suitable for
wearable devices, could improve patient outcomes and reduce healthcare burden.
However, ensuring reliability across diverse populations and maintaining data
privacy are crucial for ethical deployment and patient safety.

## References

  * Alday et al. [2020a] E. A. P. Alday, A. Gu, A. J. Shah, C. Robichaux, A.-K. I. Wong, C. Liu, F. Liu, A. B. Rad, A. Elola, S. Seyedi, Q. Li, A. Sharma, G. D. Clifford, and M. A. Reyna.  Classification of 12-lead ecgs: the physionet/computing in cardiology challenge 2020.  _Physiological Measurement_ , 41(12):124003, dec 2020a.  doi: 10.1088/1361-6579/abc960.  URL https://dx.doi.org/10.1088/1361-6579/abc960.
  * Alday et al. [2020b] E. A. P. Alday, A. Gu, A. J. Shah, C. Robichaux, A.-K. I. Wong, C. Liu, F. Liu, A. B. Rad, A. Elola, S. Seyedi, et al.  Classification of 12-lead ecgs: the physionet/computing in cardiology challenge 2020.  _Physiological measurement_ , 41(12):124003, 2020b.
  * Chen et al. [2020] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton.  A simple framework for contrastive learning of visual representations, 2020.
  * Choromanski et al. [2020] K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser, et al.  Rethinking attention with performers.  _arXiv preprint arXiv:2009.14794_ , 2020.
  * Clifford et al. [2017] G. D. Clifford, C. Liu, B. Moody, H. L. Li-wei, I. Silva, Q. Li, A. Johnson, and R. G. Mark.  Af classification from a short single lead ecg recording: The physionet/computing in cardiology challenge 2017.  In _2017 Computing in Cardiology (CinC)_ , pages 1–4. IEEE, 2017.
  * Devlin et al. [2018] J. Devlin, M. Chang, K. Lee, and K. Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  _CoRR_ , abs/1810.04805, 2018.  URL http://arxiv.org/abs/1810.04805.
  * Feichtenhofer et al. [2022] C. Feichtenhofer, H. Fan, Y. Li, and K. He.  Masked autoencoders as spatiotemporal learners, 2022.
  * Gao et al. [2022] P. Gao, T. Ma, H. Li, Z. Lin, J. Dai, and Y. Qiao.  Convmae: Masked convolution meets masked autoencoders, 2022.
  * Grill et al. [2020] J.-B. Grill, F. Strub, F. Altché, C. Tallec, P. H. Richemond, E. Buchatskaya, C. Doersch, B. A. Pires, Z. D. Guo, M. G. Azar, B. Piot, K. Kavukcuoglu, R. Munos, and M. Valko.  Bootstrap your own latent: A new approach to self-supervised learning, 2020.
  * He et al. [2015] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition, 2015.
  * He et al. [2021] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick.  Masked autoencoders are scalable vision learners, 2021.
  * Hu et al. [2023] R. Hu, J. Chen, and L. Zhou.  Spatiotemporal self-supervised representation learning from multi-lead ecg signals.  _Biomedical Signal Processing and Control_ , 84:104772, 2023.  ISSN 1746-8094.  doi: https://doi.org/10.1016/j.bspc.2023.104772.  URL https://www.sciencedirect.com/science/article/pii/S1746809423002057.
  * Kingma and Ba [2017] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization, 2017.
  * Kiyasseh et al. [2021] D. Kiyasseh, T. Zhu, and D. A. Clifton.  Clocs: Contrastive learning of cardiac signals across space, time, and patients.  In _International Conference on Machine Learning_ , pages 5606–5615. PMLR, 2021.
  * Li et al. [2023] Z. Li, Z. Rao, L. Pan, P. Wang, and Z. Xu.  Ti-mae: Self-supervised masked time series autoencoders, 2023.
  * Liu et al. [2023] Y. Liu, S. Zhang, J. Chen, K. Chen, and D. Lin.  Pixmim: Rethinking pixel reconstruction in masked image modeling, 2023.
  * Manimaran et al. [2023] G. Manimaran, S. Puthusserypady, H. Dominguez, and J. E. Bardram.  Reading between the leads: Local lead-attention based classification of electrocardiogram signals.  In _2023 Computing in Cardiology (CinC)_ , volume 50, pages 1–4, 2023.  doi: 10.22489/CinC.2023.221.
  * Reyes-Ortiz et al. [2012] J. Reyes-Ortiz, D. Anguita, A. Ghio, L. Oneto, and X. Parra.  Human Activity Recognition Using Smartphones.  UCI Machine Learning Repository, 2012.  DOI: https://doi.org/10.24432/C54S4K.
  * Sun et al. [2019] Y. Sun, S. Wang, Y. Li, S. Feng, X. Chen, H. Zhang, X. Tian, D. Zhu, H. Tian, and H. Wu.  ERNIE: enhanced representation through knowledge integration.  _CoRR_ , abs/1904.09223, 2019.  URL http://arxiv.org/abs/1904.09223.
  * Takahashi et al. [2020] R. Takahashi, T. Matsubara, and K. Uehara.  Data augmentation using random image cropping and patching for deep cnns.  _IEEE Transactions on Circuits and Systems for Video Technology_ , 30(9):2917–2931, Sept. 2020.  ISSN 1558-2205.  doi: 10.1109/tcsvt.2019.2935128.  URL http://dx.doi.org/10.1109/TCSVT.2019.2935128.
  * Wagner et al. [2020] P. Wagner, N. Strodthoff, R.-D. Bousseljot, D. Kreiseler, F. I. Lunze, W. Samek, and T. Schaeffter.  Ptb-xl, a large publicly available electrocardiography dataset.  _Scientific data_ , 7(1):154, 2020.
  * Wang et al. [2023] H. Wang, Y. Tang, Y. Wang, J. Guo, Z.-H. Deng, and K. Han.  Masked image modeling with local multi-scale reconstruction, 2023.
  * Wang et al. [2022] Y. Wang, K. Li, Y. Li, Y. He, B. Huang, Z. Zhao, H. Zhang, J. Xu, Y. Liu, Z. Wang, S. Xing, G. Chen, J. Pan, J. Yu, Y. Wang, L. Wang, and Y. Qiao.  Internvideo: General video foundation models via generative and discriminative learning, 2022.
  * Xie et al. [2022] Z. Xie, Z. Zhang, Y. Cao, Y. Lin, J. Bao, Z. Yao, Q. Dai, and H. Hu.  Simmim: A simple framework for masked image modeling, 2022.