ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 817 ShanghaiTech
University China ShanghaiTech University China ShanghaiTech University China
ShanghaiTech University China

# Cost Sharing under Private Valuation and Connection Control

Tianyi Zhang∗<EMAIL_ADDRESS>,  Junyu Zhang∗
<EMAIL_ADDRESS>,  Sizhe Gu<EMAIL_ADDRESS>and
Dengji Zhao<EMAIL_ADDRESS>
###### Abstract.

We consider a cost sharing problem on a weighted undirected graph, where all
the nodes want to connect to a special node called source, and they need to
share the total cost (weights) of the used edges. Each node except for the
source has a private valuation of the connection, and it may block others’
connections by strategically cutting its adjacent edges to reduce its cost
share, which may increase the total cost. We aim to design mechanisms to
prevent the nodes from misreporting their valuations and cutting their
adjacent edges. We first show that it is impossible for such a mechanism to
further satisfy budget balance (cover the total cost) and efficiency (maximize
social welfare). Then, we design two feasible cost sharing mechanisms that
incentivize each node to offer all its adjacent edges and truthfully report
its valuation, and also satisfy either budget balance or efficiency.

###### Key words and phrases:

Cost sharing; Mechanism design; Truthfulness

**footnotetext: The authors have equal contributions.

##  1\. Introduction

In the classic cost sharing problem, there are a group of agents at different
locations and a source. All the agents want to connect to the source via the
connections (edges) between the locations, but each connection has a cost
Claus and Kleitman (1973); Granot and Huberman (1981); Lorenzo and Lorenzo-
Freire (2009). The goal is to allocate the total connection cost among the
agents. This problem exists in many real-world applications such as cable TV,
electricity, and water supply networks Bergantiños and Gómez-Rúa (2010);
Gómez-Rúa and Vidal-Puga (2011); Trudeau and Vidal-Puga (2017). It has been
well-studied and many solutions have been proposed to achieve different
properties Kar (2002); Bergantiños and Vidal-Puga (2007b); Trudeau (2012) (we
survey them in Section 2).

However, these solutions do not consider two natural strategic behaviors of
the agents. First, to connect to the source, an agent may need to go through
some intermediate agents. These agents may block the connection by
strategically cutting their adjacent edges if their cost share is reduced by
doing so Zhao (2022) (see an example in Section 2), which will potentially
increase the total cost of connecting the agents. Second, each agent has a
private valuation for connecting to the source (i.e., the maximum cost that it
is willing to share). To maximize social welfare (i.e., the difference between
the agents’ valuations and the total connection cost), the agents need to
report their valuations, but they may misreport for their own interest.

To minimize the total connection cost and maximize social welfare, we design
cost sharing mechanisms on general networks that can prevent the two strategic
behaviors. One difficulty lies in the conflict that the mechanism designer
wants to use all the edges to minimize the total connection cost, but agents
have the motivation to cut their adjacent edges to reduce their cost share.
This essentially reflects the conflict between the system’s optimality and the
agents’ self-interests. Another difficulty lies in the conflict that the
mechanism designer wants to use truthful valuations to select agents with
maximum social welfare, while agents have the motivation to misreport their
valuations to reduce their cost share.

To combat the challenges, we first show that if we further require efficiency
(the set of selected agents has the maximal social welfare) and budget balance
(the sum of all agents’ cost share equals the total cost), then it is
impossible to prevent the above manipulations. However, we could achieve
efficiency and budget balance separately.

Therefore, we propose two mechanisms to prevent new manipulations and to
achieve either efficiency or budget balance. The first mechanism selects the
agents based on their social welfare inspired by the Vickrey-Clarke-Groves
(VCG) mechanism Vickrey (1961); Clarke (1971); Groves (1973) and each agent
pays the minimum reported valuation that enables it to be selected. The second
selects the agents iteratively and the total connection cost in each iteration
is shared equally among the agents selected in this iteration. We also show
that these mechanisms satisfy other desirable properties studied in the
literature Bogomolnaia and Moulin (2010); Bergantiños and Vidal-Puga (2015);
Gómez-Rúa and Vidal-Puga (2017); Norde (2019); Todo and Yokoo (2020).

##  2\. Related Work

There is rich literature on the classic cost sharing problem, which did not
consider private valuation and connection control. Some studies treated the
problem from the perspective of a non-cooperative game. Bergantiños and
Lorenzo Bergantiños and Lorenzo (2004) studied the Nash equilibrium of the
problem and further they Bergantiños and Lorenzo (2008) studied the Nash
equilibrium with budget restriction. Tijs and Driessen Tijs and Driessen
(1986) proposed the cost gap allocation (CGA) method, but it only applies to
complete graphs. 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 mechanisms based on the minimum
spanning tree of a graph.

However, they do not satisfy truthfulness since the agents can change the
minimum spanning tree by cutting their adjacent edges to reduce their cost
share. We take the Bird rule Bird (1976) for an example to show the problem.
Under the Bird rule, the cost share of an agent is the cost of the edge that
connects it to the (growing) spanning tree by Prim’s algorithm Prim (1957)
starting from the source. Consider Figure 1, when the agent $b$ does not cut
the edge $(a,b)$, its cost share is 3. When it cuts the edge, its cost share
is $2<3$.

Figure 1. The $s$ represents the source, $a,b,c$ represent the agents, and the
numbers on the edges represent the cost for the connectivity.

Other solutions treated the problem from the cooperative game perspective.
They are all based on the Shapley value Shapley (1953) and differ in the
definition of the value of each coalition. We briefly describe them in the
following.

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$. However, the Kar solution does not
satisfy core selection.

To satisfy core selection, Bergantiños and Vidal-Puga Bergantiños and Vidal-
Puga (2007a) proposed the folk solution. They first compute the irreducible
cost matrix, and then define the value of a coalition $S$ in the same way as
the Kar solution. However, the folk solution throws away most information of
the original graph.

To obtain a core allocation 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.

Bergantiños and Vidal-Puga Bergantiños and Vidal-Puga (2007b) proposed 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 and the agents in
$S$ can connect to the source through them.

In summary, the existing solutions for the classic cost sharing problem on
complete graphs do not consider the situation where agents need to report
their valuations and adjacent edges, as is shown before, they do not guarantee
to satisfy feasibility and truthfulness.

##  3\. The Model

We consider a cost sharing problem to connect the nodes in a weighted
undirected graph $G=\langle V\cup\\{s\\},E\rangle$. The weight of the edge
$(i,j)\in E$ denoted by $c_{(i,j)}\geq 0$ represents the cost to use the edge
to connect $i$ and $j$. All the nodes in set $V$ want to connect to the source
node $s$. The total cost of the connectivity has to be shared among all
connected nodes except for $s$. Each node $i\in V$ has a private valuation
$v_{i}\geq 0$, which is the maximum cost that it is willing to share.

Given the graph, the minimum cost of connecting the nodes is the weight of the
minimum Steiner tree Mehlhorn (1988) (we assume that the graph is connected).
The minimum Steiner tree of a set of nodes is a tree with the minimum weight
that contains these nodes (it may include the nodes outside the set). The
question here is how the nodes share this cost. We also consider two natural
strategic behaviors of each node except for the source, i.e., cutting its
adjacent edges and misreporting its valuation. An edge $(i,j)$ cannot be used
for connectivity if $i$ or $j$ cuts it. Our goal is to design cost sharing
mechanisms to incentivize nodes to report their valuations truthfully and also
offer all their adjacent edges so that we can use all the edges to minimize
the total cost of the connectivity.

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

We design a cost sharing mechanism that asks each node to report its valuation
and the set of its adjacent edges that can be used for the connectivity. Let
$\theta_{i}^{\prime}=(e_{i}^{\prime},v_{i}^{\prime})$ be the report of $i$
where $e_{i}^{\prime}\subseteq e_{i}$ and $v_{i}^{\prime}\geq 0$, and
$\theta^{\prime}=(\theta_{1}^{\prime},\cdots,\theta_{|V|+1}^{\prime})$ be the
report profile of all nodes. 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})\\}$.
Finally, let $r_{i}(\theta^{\prime})\subseteq V$ be the set of $i$’s neighbour
nodes.

######  Definition .

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:\Theta\rightarrow\mathbb{R}^{|V|}$. Given
a report profile $\theta^{\prime}\in\Theta$, $g(\theta^{\prime})\subseteq V$
selects the nodes to be connected, $f(\theta^{\prime})\subseteq
E(\theta^{\prime})$ selects the edges to connect the selected nodes
$g(\theta^{\prime})$, and $x(\theta^{\prime})=(x_{i}(\theta^{\prime}))_{i\in
V}$, where $x_{i}(\theta^{\prime})$ is the cost share of $i$, which is zero if
$i\notin g(\theta^{\prime})$.

For simplicity, we use $(g,f,x)$ to denote a cost sharing mechanism. Given a
report profile $\theta^{\prime}\in\Theta$, the utility of a node $i\in V$
under $(g,f,x)$ is defined as

$u_{i}(\theta^{\prime})=\begin{cases}v_{i}-x_{i}(\theta^{\prime})&\text{if
$i\in g(\theta^{\prime})$,}\\\ 0&\text{otherwise.}\end{cases}$

In the following, we introduce the desirable properties of a cost sharing
mechanism.

Feasibility requires that the cost share of each node is not over its reported
valuation.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies feasibility if
$x_{i}(\theta^{\prime})\leq v_{i}^{\prime}$ for all $i\in V$, for all
$\theta^{\prime}\in\Theta$.

Truthfulness states that each node cannot increase its utility by cutting its
adjacent edges and misreporting its valuation. Note that the source does not
behave strategically in this setting.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies truthfulness if
$u_{i}((\theta_{i},\theta^{\prime}_{-i}))\geq
u_{i}((\theta_{i}^{\prime},\theta^{\prime}_{-i})),$ for all $i\in V$, for all
$\theta_{i},\theta_{i}^{\prime}\in\Theta_{i}$, and for all
$\theta_{-i}^{\prime}\in\Theta_{-i}=\Theta\setminus\Theta_{i}$.

Individual rationality requires that each node’s utility is non-negative when
it reports its type truthfully no matter what the others do.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies individual rationality (IR) if
$u_{i}(\theta_{i},\theta_{-i}^{\prime})\geq 0$ for all $i\in V$, for all
$\theta_{i}\in\Theta_{i}$, and for all
$\theta_{-i}^{\prime}\in\Theta_{-i}=\Theta\setminus\Theta_{i}$.

Utility monotonicity states that for each selected node, its utility will
weakly decrease if the cost of one of its adjacent edges increases under the
same report profile.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies utility monotonicity (UM) if
$u_{i}(\theta^{\prime})\geq u_{i}^{+}(\theta^{\prime})$ for all
$\theta^{\prime}\in\Theta$ and for all $i\in V$, where
$u_{i}^{+}(\theta^{\prime})$ is $i$’s utility when the cost of the edge
$(i,j)\in\theta_{i}^{\prime}$ increases.

We also require that the sum of all nodes’ cost share equals the total cost of
the selected edges for any report profile. That is, the mechanism has no
profit or loss.

######  Definition .

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$.

The ranking property requires that for any nodes $i$ and $j$ that have the
same reported valuations and the same neighbour nodes except for $i$ and $j$,
if the cost of the edge $(i,k)$ is less expensive than the edge $(j,k)$ for
any neighbour node $k$, then the utility of $i$ should be larger than $j$.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies ranking if for all
$\theta^{\prime}\in\Theta$, for all $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}^{\prime}=v_{j}^{\prime}$ (assume $v_{i}^{\prime}=v_{i}$ and
$v_{j}^{\prime}=v_{j}$), we have $c_{(i,k)}\leq c_{(j,k)}$ for all $k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$ implies $u_{i}(\theta^{\prime})\geq
u_{j}(\theta^{\prime})$.

Symmetry says nodes that play the same role obtain the same utility.

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies symmetry if for all
$\theta^{\prime}\in\Theta$, for all $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}^{\prime}=v_{j}^{\prime}$ (assume $v_{i}^{\prime}=v_{i}$ and
$v_{j}^{\prime}=v_{j}$), we have $c_{(i,k)}=c_{(j,k)}$ for all $k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$ implies
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})$.

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

######  Definition .

A cost sharing mechanism $(g,f,x)$ satisfies positiveness if
$x_{i}(\theta^{\prime})\geq 0$ for all $i\in V$ and for all
$\theta^{\prime}\in\Theta$.

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

##  4\. Impossibility Results

In this section, we establish some impossibility results. We first introduce
some extra notions.

######  Definition .

For a given subset $S\subseteq V$, the social welfare (SW) of $S$ is

$SW(S)=\sum_{i\in S}v_{i}^{\prime}-C(S),$

where $v_{i}^{\prime}$ is the reported valuation of node $i$ and $C(S)$ is the
minimum cost of connecting all the nodes in $S$ (i.e., the weight of the
minimum Steiner tree of $S\cup\\{s\\}$).

Intuitively, social welfare represents the profit of the selected nodes.

######  Definition .

Given $\theta^{\prime}\in\Theta$, a mechanism $(g,f,x)$ satisfies efficiency
if it selects $g(\theta^{\prime})\subseteq V$ such that its social welfare is
maximized, i.e.,

$SW(g(\theta^{\prime}))={\underset{\forall S\subseteq V}{{\max}\ SW(S)}.}$

For simplicity, we use $\delta(V)$ to denote a subset of $V$ that has the
maximal social welfare, i.e.,

$\delta(V)={\underset{\forall S\subseteq V}{{\arg\max}\ SW(S)}.}$

The computation of $\delta(V)$ is described as follows.

Algorithm 1: Compute $\delta(V)$

Input: A report profile $\theta^{\prime}$ and a set of nodes V

  1. (1)

Set: $\delta(\emptyset)=\emptyset$, $SW(\emptyset)=0$, and
Set: $P(V)$ to be the power set of $V$.

  2. (2)

Sort all the elements of $P(V)$ in an ascending order by their cardinalities.

  3. (3)

For $S\in P(V)\setminus\\{\emptyset\\}$:

     * •

Get $Q(S)=\\{S^{\prime}|S^{\prime}\subset S,|S^{\prime}|=|S|-1\\}$.

     * •

Let $\delta(S)=\mathop{\arg\max}\limits_{S^{\prime}\in
Q(S)}SW(\delta(S^{\prime}))$.

     * •

If $\sum_{i\in S}v_{i}^{\prime}-C(S)\geq SW(\delta(S))$, set $\delta(S)=S$.

     * •

Get $SW(\delta(S))=\sum_{i\in\delta(S)}v_{i}^{\prime}-C(\delta(S))$.

Output: The subset $\delta(V)$,
Output:: the maximum social welfare $SW(\delta(V))$

Figure 2. The $s$ represents the source, $a$ and $b$ represent the nodes, the
numbers in the circles represent the reported valuations of nodes, and the
numbers on the edges represent the cost for the connectivity.

A running example of Algorithm 1 is given in Figure 2. Assume
$c_{(s,a)}=2,c_{(s,b)}=4,c_{(a,b)}=3,v_{a}^{\prime}=3,v_{b}^{\prime}=3$. By
Algorithm 1, we have $\delta(\\{a\\})=\\{a\\},\delta(\\{b\\})=\emptyset$ and
$\delta(\\{a,b\\})=\\{a,b\\}$.

###### Proposition

There exists no cost sharing mechanism which satisfies truthfulness,
feasibility, efficiency, and budget balance simultaneously.

Figure 3. The $s$ represents the source and $a,b$ are the nodes with the
valuations $v_{a},v_{b}$ respectively. The cost of the edges $(s,a)$ and
$(a,b)$ are $m$ and $n$ respectively.

###### Proof.

We only need to consider a simple line graph in Figure 3. We show that when
feasibility, efficiency, and budget balance are satisfied, truthfulness will
be violated. Assume that $v_{a}>m$ and $v_{b}>m+n$. By efficiency, when $a$
and $b$ truthfully report $v_{a}^{\prime}=v_{a},v_{b}^{\prime}=v_{b}$, $a$ and
$b$ are both selected by the mechanism since $(v_{a}+v_{b})-(m+n)>v_{a}-m$.

  * •

When $x_{a}(\theta^{\prime})>0$, if node $a$ reports $v_{a}^{\prime\prime}=0$,
by feasibility, we have $x_{a}(\theta^{\prime\prime})=0$ and the utility of
$a$ increases. Hence, node $a$ has the motivation to misreport.

  * •

When $x_{a}(\theta^{\prime})=0$, by budget balance, we have
$x_{b}(\theta^{\prime})=m+n$. If node $b$ reports $v_{b}^{\prime\prime}=n$, by
feasibility and budget balance, we have $x_{b}(\theta^{\prime\prime})=n$, and
the utility of $b$ increases. Hence, node $b$ has the motivation to misreport.

Therefore, node $a$ or node $b$ has the motivation to misreport its valuation,
i.e., truthfulness is violated. ∎

We further show that when truthfulness, feasibility, and budget balance are
satisfied, the maximal social welfare cannot be approximated.

######  Definition .

A mechanism is $\alpha^{lb}$-approximate ($\alpha^{lb}\in(0,1)$) to the social
welfare if $SW(g(\theta^{\prime}))\geq\alpha^{lb}\cdot SW^{*}(S)$, where
$SW^{*}(S)$ is the maximal social welfare given
$\forall\theta^{\prime}\in\Theta$ and $lb$ represents that $\alpha^{lb}$ is a
lower bound of the ratio $\frac{SW(g(\theta^{\prime}))}{SW^{*}(S)}$.

######  Definition .

A mechanism is $\beta^{ub}$-approximate ($\beta^{ub}\in(0,1)$) to the social
welfare if $SW(g(\theta^{\prime}))\leq\beta^{ub}\cdot SW^{*}(S)$, where
$SW^{*}(S)$ is the maximal social welfare given
$\forall\theta^{\prime}\in\Theta$ and $ub$ represents that $\beta^{ub}$ is an
upper bound of the ratio $\frac{SW(g(\theta^{\prime}))}{SW^{*}(S)}$.

###### Proposition

There exists no cost sharing mechanism that satisfies truthfulness, budget
balance, feasibility, and $\alpha^{lb}$-approximation
($\beta^{ub}$-approximation) simultaneously.

###### Proof.

It suffices to consider a simple line graph in Figure 3. Without loss of
generality, assume that $v_{a}>m,v_{b}=n+p(p>0),c_{(s,a)}=m$ and
$c_{(a,b)}=n$. When $a$ and $b$ are both selected by the mechanism, the
maximum social welfare is ($v_{a}-m+p$).

Next, we show when truthfulness, feasibility, and budget balance are
satisfied, $\alpha^{lb}$-approximation and $\beta^{ub}$-approximation will be
violated. By Proposition 4, any mechanism cannot select both $a$ and $b$ and
it can only select $a$. Then the social welfare is $(v_{a}-m)$. Hence, the
ratio equals $\frac{v_{a}-m}{v_{a}-m+p}$. Letting $p\rightarrow\infty$, then
the ratio approaches 0. Therefore, the required $\alpha^{lb}$ does not exist.
Again letting $p\rightarrow 0$, then the ratio approaches $1$, which means
that the required $\beta^{ub}$ does not exist.

Therefore, any cost sharing mechanism cannot satisfy truthfulness, budget
balance, feasibility, and $\alpha^{lb}$-approximation
($\beta^{ub}$-approximation) simultaneously. ∎

We further consider the deficit of any mechanism that satisfies truthfulness,
feasibility, and efficiency. We introduce a concept called budget balance
ratio to evaluate it.

######  Definition .

A mechanism has a budget balance ratio (BBR) called $\gamma\in(0,1]$ if
$\sum_{i\in g(\theta^{\prime})}x_{i}(\theta^{\prime})\geq\gamma\cdot
C(g(\theta^{\prime}))$, $\forall\theta^{\prime}\in\Theta$.

###### Proposition

A cost sharing mechanism that satisfies truthfulness, feasibility and
efficiency does not have a BBR.

Figure 4. The $s$ represents the source and $a,b$ are the nodes with the
valuation $m$. The cost of the edges $(s,a)$, $(a,b)$ and $(s,b)$ are $m,0,m$
respectively.

###### Proof.

According to Definition 4, a cost sharing mechanism having a BBR
$\gamma\in(0,1]$ needs to satisfy the following:
$\forall\theta^{\prime}\in\Theta$, $\frac{\sum_{i\in
g(\theta^{\prime})}x_{i}(\theta^{\prime})}{C(g(\theta^{\prime}))}\geq\gamma>0$.
So, to prove the proposition, it suffices to find a $\theta^{\prime}$ such
that $\frac{\sum_{i\in
g(\theta^{\prime})}x_{i}(\theta^{\prime})}{C(g(\theta^{\prime}))}=0$.

Without loss of generality, as shown in Figure 4, we assume $V=\\{a,b\\}$,
$v_{a}=v_{b}=m$, $c_{(s,a)}=c_{(s,b)}=m$, $c_{(a,b)}=0$. By efficiency, the
mechanism should select both $a$ and $b$. By truthfulness, each node offers
all its adjacent edges and reports its valuation truthfully. By feasibility
and truthfulness, we have $x_{a}(\theta^{\prime})=x_{b}(\theta^{\prime})=0$.
Thus, we have $\frac{\sum_{i\in
g(\theta^{\prime})}x_{i}(\theta^{\prime})}{C(g(\theta^{\prime}))}=\frac{0}{m}=0$.
∎

Note that there exists a trivial cost sharing mechanism where each node pays 0
and all the nodes in $V$ are selected by the mechanism. This mechanism
satisfies truthfulness and feasibility but does not satisfy efficiency and
budget balance.

By Proposition 4, a cost sharing mechanism cannot simultaneously satisfy
truthfulness, feasibility, efficiency, and budget balance. Therefore, we
propose two feasible mechanisms satisfying truthfulness, respectively together
with efficiency and budget balance in the following sections.

We summarize the impossibility results and our mechanisms in Table 1.

Table 1. ”Null” means that there exists no mechanism satisfying all the marked
properties in the column. Our mechanisms RSM and CVM satisfy the marked
properties in the column.

Truthfulness | Feasibility | Budget Balance | Efficiency | Mechanism
---|---|---|---|---
✓ | ✓ | ✓ | ✓ | NULL
✓ | ✓ | ✓ |  $\alpha^{lb}$($\beta^{ub}$) | NULL
✓ | ✓ | $\gamma$ | ✓ | NULL
✓ | ✓ |  | ✓ | CVM
✓ | ✓ | ✓ |  | RSM

##  5\. Critical Value Based Mechanism

In this section, we propose a cost sharing mechanism that satisfies
truthfulness, feasibility, and efficiency but does not satisfy budget balance.
In addition, we show that it also satisfies other desirable properties.

The key ideas of the mechanism are as follows. First, find out the node set
which has maximal social welfare. Second, for each node in the set, compute
its critical value (CV), i.e., the minimal reported valuation that keeps it in
the set.

Finally, let the cost share of the node in the set equal its critical value
and the others’ cost share is 0.

The computation of the minimum reported valuation of each node $i\in
g(\theta^{\prime})$ is as follows. We first compute
$\delta(g(\theta^{\prime})\setminus\\{i\\})$, the set of nodes that maximizes
the social welfare when node $i$ is not considered. Then we compute the social
welfare of $g(\theta^{\prime})$ and
$\delta(g(\theta^{\prime})\setminus\\{i\\})$. Next, we find out the minimum
reported valuation of $i$ that keeps it in $g(\theta^{\prime})$ and guarantees
$SW(g(\theta^{\prime}))=SW(\delta(g(\theta^{\prime})\setminus\\{i\\}))$.

The mechanism is formally described as follows. A running example is given
after the algorithm.

Critical Value Based Mechanism (CVM)

Input: A report profile $\theta^{\prime}$ and a graph $G(\theta^{\prime})$

  1. (1)

Run Algorithm 1 and get $g(\theta^{\prime})=\delta(V)$.

  2. (2)

Compute the minimum Steiner tree of $g(\theta^{\prime})\cup\\{s\\}$ and
set $f(\theta^{\prime})$ to be the set of edges in the tree.

  3. (3)

For $i\in g(\theta^{\prime})$:

     * •

Compute node $i$’s critical value

$\begin{split}CV_{i}(\theta^{\prime})=&(\sum_{j\in\delta(g(\theta^{\prime})\setminus\\{i\\})}v_{j}^{\prime}-C(\delta(g(\theta^{\prime})\setminus\\{i\\})))\\\
&-(\sum_{k\in
g(\theta^{\prime})\setminus\\{i\\}}v_{k}^{\prime}-C(g(\theta^{\prime}))),\\\
\end{split}$ (1)

where $\delta(\cdot)$ is defined in Algorithm 1.

  4. (4)

Set $x_{i}(\theta^{\prime})=CV_{i}(\theta^{\prime})$.

Output: The selected nodes $g(\theta^{\prime})$, the selected edges
$f(\theta^{\prime})$, the cost sharing $x(\theta^{\prime})$

Figure 5. The left figure is $G(\theta^{\prime})$ and the right figure is the
minimum Steiner tree of $g(\theta^{\prime})\cup\\{s\\}$.

###### Example

The graph $G(\theta^{\prime})$ generated by a report profile
$\theta^{\prime}\in\Theta$ is shown in Figure 5(1). First, run Algorithm 1 and
obtain $\delta(S)$ for all $S\subseteq V$. Especially, we have
$g(\theta^{\prime})=\delta(V)=\\{a,b,c,d\\}$ and
$f(\theta^{\prime})=\\{(s,b),(a,b),(a,c),(a,d)\\}$. Then we compute each
node’s cost share. Taking the node $a$ for an example, we have
$\delta(g(\theta^{\prime})\setminus\\{a\\})=\\{b\\}$ and by Equation (1),
$x_{a}(\theta^{\prime})=v_{b}^{\prime}-c_{(s,b)}-(v_{b}^{\prime}+v_{c}^{\prime}+v_{d}^{\prime}-c_{(s,b)}-c_{(a,b)}-c_{(a,c)}-c_{(a,d)})=9-7-(9+6+7-7-8-6-5)=6$.
Similarly, we have $x_{b}(\theta^{\prime})=5,x_{c}(\theta^{\prime})=6$ and
$x_{d}(\theta^{\prime})=5$. Thus we have $x(\theta^{\prime})=(6,5,6,5)$.

###  5.1. Properties of CVM

Now we show some nice properties of the critical value based mechanism.

The critical value based mechanism satisfies truthfulness.

###### Proof.

First, we prove that each node $i\in V$ will report its valuation truthfully
(i.e., $v_{i}^{\prime}=v_{i}$). When $i$ truthfully reports its valuation,
there are two cases.

  * •

$i\notin g(\theta^{\prime})$. We have $u_{i}(\theta^{\prime})=0$. If node $i$
reports $v_{i}^{\prime}<v_{i}$, it is still not selected and the utility does
not change. Otherwise ($v_{i}^{\prime}>v_{i}$), there are two possibilities.

    * –

It is still not selected and the utility does not change.

    * –

It is selected. By the proposed mechanism, since $i$’s critical value is
larger than $v_{i}$, its utility is negative. Thus the utility decreases.

  * •

$i\in g(\theta^{\prime})$. We have $u_{i}(\theta^{\prime})\geq 0$. If node $i$
reports $v_{i}^{\prime}>v_{i}$, it is still selected and the utility does not
change. Otherwise ($v_{i}^{\prime}\leq v_{i}$), there are two possibilities.

    * –

It is still selected. The utility does not change.

    * –

It is not selected and its utility is 0. So the utility decreases.

Second, we prove that each node $i\in V$ will report its adjacent edges
truthfully (i.e., $e_{i}^{\prime}=e_{i}$). When $i$ truthfully reports its
adjacent edges, there are two cases.

  * •

$i\notin g(\theta^{\prime})$. We have $u_{i}(\theta^{\prime})=0$. If node $i$
reports $e_{i}^{\prime}\neq e_{i}$, its cost share will weakly increase and
thus it is still not selected. Hence, the utility does not change.

  * •

$i\in g(\theta^{\prime})$. We have $u_{i}(\theta^{\prime})\geq 0$. If node $i$
reports $e_{i}^{\prime}\neq e_{i}$, there are two possibilities.

    * –

It is not selected. Obviously, its utility decreases.

    * –

It is still selected. For simplicity, let
$S_{1}=g(\theta^{\prime}),S_{2}=g(\theta^{\prime\prime}),S_{3}=S_{1}\setminus\delta(S_{1}\setminus\\{i\\}),S_{4}=S_{2}\setminus\delta(S_{2}\setminus\\{i\\})$
where
$\theta^{\prime\prime}=((e_{i}^{\prime},v_{i}^{\prime}),\theta^{\prime}_{-i})$
and $\theta^{\prime}=((e_{i},v_{i}^{\prime}),\theta^{\prime}_{-i})$. Then by
Equation (1) we have

$\displaystyle CV_{i}(\theta^{\prime})$
$\displaystyle=C(S_{1})-C(\delta(S_{1}\setminus\\{i\\}))-\sum_{j\in
S_{3}\setminus\\{i\\}}v_{j}^{\prime},$ $\displaystyle
CV_{i}(\theta^{\prime\prime})$
$\displaystyle=C^{\prime}(S_{2})-C^{\prime}(\delta(S_{2}\setminus\\{i\\}))-\sum_{j\in
S_{4}\setminus\\{i\\}}v_{j}^{\prime},$

where $C^{\prime}(\cdot)$ denotes the value function when $i$ misreports
$e_{i}^{\prime}$. Since $S_{1}$ maximizes the social welfare under
$\theta^{\prime}$, we have

$\begin{split}\sum_{j\in
S_{3}}v_{j}^{\prime}-(C(S_{1})-C(\delta(S_{1}\setminus\\{i\\})))&\\\
\geq\sum_{j\in
S_{4}}v_{j}^{\prime}-(C(S_{2})-C(\delta(S_{2}\setminus\\{i\\}))).\end{split}$

For the set $S_{4}$, the increment of SW will decrease since the set of
available edges of $S_{4}$ is reduced. Then we have

$\begin{split}\sum_{j\in
S_{4}}v_{j}^{\prime}-(C(S_{2})-C(\delta(S_{2}\setminus\\{i\\})))&\\\
\geq\sum_{j\in
S_{4}}v_{j}^{\prime}-(C^{\prime}(S_{2})-C^{\prime}(\delta(S_{2}\setminus\\{i\\}))).\end{split}$

Therefore,

$\begin{split}\sum_{j\in
S_{3}}v_{j}^{\prime}-(C(S_{1})-C(\delta(S_{1}\setminus\\{i\\})))&\\\
\geq\sum_{j\in
S_{4}}v_{j}^{\prime}-(C^{\prime}(S_{2})-C^{\prime}(\delta(S_{2}\setminus\\{i\\}))).\end{split}$

Eliminating $v_{i}^{\prime}$, we have $CV_{i}(\theta^{\prime})\leq
CV_{i}(\theta^{\prime\prime})$.

So the cost share of $i$ weakly increases when misreporting its adjacent
edges. Therefore, $i$’s utility weakly decreases when misreporting its
adjacent edges. ∎

The critical value based mechanism satisfies feasibility.

###### Proof.

According to the mechanism and Algorithm 1, the participation of each selected
node can increase social welfare. Because the critical value is the minimum
reported valuation that keeps the node being selected, its cost share is less
than or equal to its reported valuation. For the other nodes, their cost share
is 0, which is less than their reported valuation. ∎

The critical value based mechanism satisfies individual rationality.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for each node $i\in
V\setminus g(\theta^{\prime})$, we have $u_{i}(\theta^{\prime})=0$. For each
node $i\in g(\theta^{\prime})$, by Theorem 5.1, we have
$x_{i}(\theta^{\prime})\leq v_{i}^{\prime}$. According to Theorem 5.1,
$v_{i}^{\prime}=v_{i}$. Hence,
$u_{i}(\theta^{\prime})=v_{i}-x_{i}(\theta^{\prime})\geq 0$. ∎

The critical value based mechanism satisfies efficiency.

###### Proof.

According to the mechanism, it is obvious that the set of selected nodes can
maximize the social welfare. ∎

The critical value based mechanism satisfies positiveness.

###### Proof.

We prove the statement by contradiction. According to the mechanism and
Equation (1), we have

$\begin{split}x_{i}(\theta^{\prime})=CV_{i}(\theta^{\prime})=(C(g(\theta^{\prime}))-C(\delta(g(\theta^{\prime})\setminus\\{i\\})))-\Delta.\\\
\end{split}$

where

$\Delta=\sum_{k\in
g(\theta^{\prime})\setminus\\{i\\}}v_{k}^{\prime}-\sum_{j\in\delta(g(\theta^{\prime})\setminus\\{i\\})}v_{j}^{\prime}$

If $x_{i}(\theta^{\prime})\leq 0$, then we have

$C(g(\theta^{\prime}))-C(\delta(g(\theta^{\prime})\setminus\\{i\\}))\leq\Delta$

Since

$C(g(\theta^{\prime})\setminus\\{i\\})\leq C(g(\theta^{\prime})),$

we have

$C(g(\theta^{\prime})\setminus\\{i\\})-C(\delta(g(\theta^{\prime})\setminus\\{i\\}))\leq\Delta$

Therefore, the nodes in
$(g(\theta^{\prime})\setminus\\{i\\}-\delta(g(\theta^{\prime})\setminus\\{i\\}))$
can be selected by the mechanism. By the definition of $\delta(\cdot)$, they
cannot be selected by the mechanism. This leads to a contradiction. ∎

The critical value based mechanism satisfies symmetry.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$ and $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}=v_{j}$, $c_{(i,k)}=c_{(j,k)}$ ($\forall k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$) implies
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})$. If $i,j\notin
g(\theta^{\prime})$, we have
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})=0$. If $i,j\in
g(\theta^{\prime})$, by the condition of symmetry, we have
$x_{i}(\theta^{\prime})=x_{j}(\theta^{\prime})$. Since $v_{i}=v_{j}$, we have
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})$. ∎

The critical value based mechanism satisfies utility monotonicity.

###### Proof.

For any node $i\in V$, given $\theta^{\prime}\in\Theta$, $j\in V$ such that
$(i,j)\in E$, we use $g^{+}(\theta^{\prime})$ to denote the set of selected
nodes when $c_{(i,j)}$ increases.

If $i\notin g(\theta^{\prime})$, then $u_{i}(\theta^{\prime})=0$, and $i\notin
g^{+}(\theta^{\prime})$ according to CVM. So its utility does not change.

If $i\in g(\theta^{\prime})$, then $u_{i}(\theta^{\prime})\geq 0$. There are
two cases.

  * •

$i\notin g^{+}(\theta^{\prime})$. Then its utility weakly decreases.

  * •

$i\in g^{+}(\theta^{\prime})$. Its cost share becomes

$(\sum_{j\in\delta(g^{+}(\theta^{\prime})\setminus\\{i\\})}v_{j}-C(\delta(g^{+}(\theta^{\prime})\setminus\\{i\\})))-(\sum_{k\in
g^{+}(\theta^{\prime})\setminus\\{i\\}}v_{k}-C(g^{+}(\theta^{\prime}))).$

By the similar analysis to the second part in the proof of Theorem 5.1, we
know the utility of $i$ weakly decreases.

∎

The critical value based mechanism satisfies ranking.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$ and $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}=v_{j}$, $c_{(i,k)}\leq c_{(j,k)}$ ($\forall k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$) implies $u_{i}(\theta^{\prime})\geq
u_{j}(\theta^{\prime})$. For nodes $i$ and $j$, there are three cases.

  * •

$i,j\notin g(\theta^{\prime})$. We have
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})=0$.

  * •

$i\in g(\theta^{\prime})$ but $j\notin g(\theta^{\prime})$. By individual
rationality, we have $u_{i}(\theta^{\prime})\geq 0=u_{j}(\theta^{\prime})$.

  * •

$i,j\in g(\theta^{\prime})$. Since $v_{i}=v_{j}$, it suffices to prove
$x_{i}(\theta^{\prime})\leq x_{j}(\theta^{\prime})$. From Equation (1), we
know the last two terms of the expressions of $x_{i}(\theta^{\prime})$ and
$x_{j}(\theta^{\prime})$ are equal. Next, we compare
$\sum_{j\in\delta(g(\theta^{\prime})\setminus\\{i\\})}v_{j}-C(\delta(g(\theta^{\prime})\setminus\\{i\\}))$
with
$\sum_{i\in\delta(g(\theta^{\prime})\setminus\\{j\\})}v_{i}-C(\delta(g(\theta^{\prime})\setminus\\{j\\}))$.
The former represents the maximum social welfare of
$g(\theta^{\prime})\setminus\\{i\\}$ and the latter represents the maximum
social welfare of $g(\theta^{\prime})\setminus\\{j\\}$. By the symmetry of $i$
and $j$ in the graph, the condition of ranking, and the proof of Theorem 5.1,
the latter is larger than or equal to the former. Therefore, we have
$x_{i}(\theta^{\prime})\leq x_{j}(\theta^{\prime})$.

∎

##  6\. Repeated Selection Mechanism

The CVM defined in Section 5 satisfies truthfulness, feasibility, and
efficiency but does not satisfy budget balance. In this section, we propose
another cost sharing mechanism that satisfies truthfulness, feasibility, and
budget balance but does not satisfy efficiency. Moreover, we show that it also
satisfies other desirable properties.

We use the method of iterative optimization. In the first round (stage) of
optimization, we find a subset of nodes and the minimum satisfying the
constraints of feasibility and budget balance as the cost share of these
nodes. In the following rounds of optimization, we consider the remaining
nodes and add an extra constraint that the optimizing variable is larger than
or equal to the cost share of the last round, which guarantees the
truthfulness of the mechanism. The iterative process is repeated until all the
nodes are considered.

The proposed mechanism is called Repeated Selection Mechanism (RSM) formally
described in the following.

Repeated Selection Mechanism (RSM)

Input: A report profile $\theta^{\prime}$ and a graph $G(\theta^{\prime})$

  1. (1)

For stage $t$ ($t=0,1,2,\dots$), we introduce:

     * •

$S^{t}$ : the set of nodes selected in stage $t$,

     * •

$M^{t}$ : the union of $S^{0},S^{1},\cdots,S^{t}$,

     * •

$X^{t}$ : the cost share of every node in $S^{t}$,

     * •

$W^{t}$ : the set of nodes which will not be considered after stage $t$,

     * •

$N^{t}$ : the set of remaining nodes after stage $t$, and

     * •

$\mathcal{E}^{t}$: the set of edges of the minimum Steiner tree of $S^{t}$.

$\mathcal{E}$ is the set of selected edges during the process, i.e., the union
of $\mathcal{E}^{0},\mathcal{E}^{1},\cdots,\mathcal{E}^{t}$.

  2. (2)

Stage 0:

Set $X^{0}=0$, $N^{0}=V$, $M^{0}=\emptyset$, $W^{0}=\emptyset$, and
$\mathcal{E}=\emptyset$.

  3. (3)

For $t=1,2,\dots:$

Stage $t$:

$\displaystyle Solve\quad\quad\mathop{min}\limits_{S^{t}\subseteq N^{t-1}}$
$\displaystyle X^{t}$ $\displaystyle s.t.\quad$ $\displaystyle X^{t}\geq
X^{t-1}$ $\displaystyle X^{t}\cdot|S^{t}|=C(S^{t})$ $\displaystyle
v_{i}^{\prime}\geq X^{t},\forall i\in S^{t}$

     * •

If there is a solution, set $x_{i}(\theta^{\prime})=X^{t}$ ($\forall i\in
S^{t}$).
Then, update:

$W^{t}=\\{i|v_{i}^{\prime}<X^{t}\\},$ $N^{t}=N^{t-1}\setminus\\{S^{t}\cup
W^{t}\\},$ $M^{t}=M^{t-1}\cup S^{t}.$

Set:

$c_{(i,j)}=0,\forall i,j\in M^{t}\cup\\{s\\},i\neq j,$
$\mathcal{E}=\mathcal{E}\cup\mathcal{E}^{t}.$

Note that ”$c_{(i,j)}=0$” means that the remaining nodes can use the edge
$(i,j)$ without paying cost.

     * •

Else, set $g(\theta^{\prime})=M^{t-1}$ and $f(\theta^{\prime})=\mathcal{E}$.
Break the loop.

Output: The selected nodes $g(\theta^{\prime})$, the selected edges
$f(\theta^{\prime})$, the cost sharing $x(\theta^{\prime})$

A running example is given as follows.

###### Example

The graph $G(\theta^{\prime})$ generated by a report profile
$\theta^{\prime}\in\Theta$ is shown in Figure 6. For stage 1, we have
$X^{1}=3$ and $S^{1}=\\{b\\}$. Hence,
$\mathcal{E}=\mathcal{E}^{1}=\\{(s,b)\\}$. For stage 2, we have $X^{2}=4$ and
$S^{2}=\\{a\\}$. Hence, $\mathcal{E}^{2}=\\{(a,b)\\}$ and
$\mathcal{E}=\mathcal{E}^{1}\cup\mathcal{E}^{2}=\\{(s,b),(a,b)\\}$. For stage
3, we have $X^{3}=5$ and $S^{3}=\\{c,d,e\\}$. Hence,
$\mathcal{E}^{3}=\\{(a,d),(a,c),(b,e)\\}$ and
$\mathcal{E}=\mathcal{E}^{1}\cup\mathcal{E}^{2}\cup\mathcal{E}^{3}=\\{(s,b),(a,b),(a,d),(c,d),(b,e)\\}$.
Since there does not exist $X^{4}$ satisfying the constraints, the proposed
algorithm ends and we have
$g(\theta^{\prime})=\\{a,b,c,d,e\\},x(\theta^{\prime})=(3,4,5,5,5)$ and
$f(\theta^{\prime})=\\{(s,b),(a,b),(a,d),(c,d),(b,e)\\}$.

Figure 6. The left figure is $G(\theta^{\prime})$. The red line in the right
figure denotes the selected edge in the first stage, the green line denotes
the selected edge in the second stage and the blue lines denote the selected
edges in the third stage.

###  6.1. Properties of RSM

We show the properties of RSM in this section. The repeated selection
mechanism satisfies truthfulness.

###### Proof.

Firstly, we prove that each node $i\in V$ will report its adjacent edges
truthfully. Denote two report profile by
$\theta^{\prime}=((e_{i}^{\prime},v_{i}^{\prime}),\theta_{-i}^{\prime})$ where
$e_{i}^{\prime}=e_{i}$ and
$\theta^{\prime\prime}=((e_{i}^{\prime\prime},v_{i}^{\prime}),\theta_{-i}^{\prime})$.
When $i$ truthfully reports its adjacent edges, there are two cases.

  1. (1)

$i\notin g(\theta^{\prime})$. Then we have $u_{i}(\theta^{\prime})=0$. If $i$
reports $e_{i}^{\prime\prime}\subset e_{i}$, for any $S(i\in S)$, $C(S)$ will
increase since the set of available edges shrinks. Hence, $i\notin
g(\theta^{\prime\prime})$ and the utility does not change.

  2. (2)

$i\in g(\theta^{\prime})$. Then
$u_{i}(\theta^{\prime})=v_{i}-x_{i}(\theta^{\prime})\geq 0$. Assume that $i\in
S^{t}$. If $i$ reports $e_{i}^{\prime\prime}\subset e_{i}$, we first prove the
set of selected nodes before stage $t$ does not change due to $i$’s
misreporting, i.e., $M^{t-1}=\hat{M}^{t-1}$, where $\hat{M}^{t-1}$ is the set
of selected nodes before stage $t$ given $\theta^{\prime\prime}$. If node $i$
belongs to the minimum Steiner tree of $S^{r}$ in the stage $r$ ($r<t$), then
it should have been selected in stage $r$, which leads to a contradiction to
$i\in S^{t}$. Therefore, we know node $i$ does not belong to the minimum
Steiner tree of $S^{r}$ for any stage $r$ ($r<t$). Then the selected edges of
$M^{t-1}$ and $\hat{M}^{t-1}$ are the same, i.e., $M^{t-1}=\hat{M}^{t-1}$.

Then we prove the utility of node $i$ weakly decreases due to $i$’s
misreporting. Based on the above analysis, there are two cases for node $i$.

     * •

Node $i\in g(\theta^{\prime\prime})$. Let $C^{\prime}(S)$ denote the minimum
cost of any set $S$ under $\theta^{\prime\prime}$. Since $C^{\prime}(S)\geq
C(S)$, we have $\frac{C^{\prime}(S)}{|S|}\geq\frac{C(S)}{|S|}$. Hence,
$x_{i}(\theta^{\prime\prime})\geq x_{i}(\theta^{\prime})$ and
$u_{i}(\theta^{\prime\prime})\leq u_{i}(\theta^{\prime})$.

     * •

Node $i\notin g(\theta^{\prime\prime})$. Then we have
$u_{i}(\theta^{\prime\prime})=0\leq u_{i}(\theta^{\prime})$.

Secondly, we prove that each node $i\in V$ will report its valuation
truthfully. Denote two report profile by
$\theta^{\prime}=((e_{i}^{\prime},v_{i}^{\prime}),\theta_{-i}^{\prime})$ where
$v_{i}^{\prime}=v_{i}$ and
$\theta^{\prime\prime}=((e_{i}^{\prime},v_{i}^{\prime\prime}),\theta_{-i}^{\prime})$.
When $i$ truthfully reports its valuation, there are two cases.

  1. (1)

$i\in S^{t}\subseteq g(\theta^{\prime})$. If $i$ reports
$v_{i}^{\prime\prime}>v_{i}$, it is still selected in stage $t$ and
$X^{t}=\hat{X}^{t}$, where $\hat{X}^{t}$ denotes the cost share in stage $t$
given $\theta^{\prime\prime}$. Hence,
$u_{i}(\theta^{\prime\prime})=v_{i}-\hat{X}^{t}=v_{i}-X^{t}=u_{i}(\theta^{\prime})$.
If $i$ reports $v_{i}^{\prime\prime}<v_{i}$, there are two possibilities.

     * •

$X^{t}\leq v_{i}^{\prime\prime}<v_{i}$. Then it is still selected and
$u_{i}(\theta^{\prime\prime})=u_{i}(\theta^{\prime})$.

     * •

$v_{i}^{\prime\prime}<X^{t}$. Then it is not selected and
$u_{i}(\theta^{\prime\prime})=0\leq u_{i}(\theta^{\prime})$.

  2. (2)

$i\notin g(\theta^{\prime})$. If $i$ reports $v_{i}^{\prime\prime}<v_{i}$,
then it is still not selected and the utility does not change. If $i$ reports
$v_{i}^{\prime\prime}>v_{i}$, there are two possibilities.

     * •

$i\notin g(\theta^{\prime\prime})$. Then the utility does not change.

     * •

$i\in S^{t}\subseteq g(\theta^{\prime\prime})$. Then
$x_{i}(\theta^{\prime})=\frac{C(S^{t})}{|S^{t}|}$. Since node $i$ cannot be
selected given $\theta^{\prime}$, we have $v_{i}<\frac{C(S^{t})}{|S^{t}|}$.
Hence,
$u_{i}(\theta^{\prime\prime})=v_{i}-\frac{C(S^{t})}{|S^{t}|}<0=u_{i}(\theta^{\prime})$.

Therefore, $u_{i}(\theta^{\prime})\geq u_{i}(\theta^{\prime\prime})$, i.e.,
$i$’s utility is maximized when $i$ reports its valuation truthfully. ∎

The repeated selection mechanism satisfies budget balance.

###### Proof.

Given $\theta^{\prime}\in\Theta$, in stage $t$, the sum of all nodes’ cost
share in $S^{t}$ equals the total cost of connecting all the nodes in $S^{t}$,
i.e., $X^{t}\cdot|S^{t}|=C(S^{t})$. Then for all the stages, the sum of all
selected nodes’ cost share in $g(\theta^{\prime})$ equals the total cost of
connecting all nodes in $g(\theta^{\prime})$, i.e.,
$\sum_{t}X^{t}\cdot|S^{t}|=\sum_{t}C(S^{t})=\sum_{(i,j)\in
f(\theta^{\prime})}c_{(i,j)}$. Hence, the mechanism satisfies budget balance.
∎

The repeated selection mechanism satisfies feasibility.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for each node $i\in
V\setminus g(\theta^{\prime})$, we have $x_{i}(\theta^{\prime})=0\leq
v_{i}^{\prime}$. For each node $i\in g(\theta^{\prime})$, by the proposed
mechanism, $x_{i}(\theta^{\prime})=X^{t}\leq v_{i}^{\prime}$ for the stage
$t$. So we have $x_{i}(\theta^{\prime})\leq v_{i}^{\prime}$. Therefore, the
mechanism satisfies feasibility. ∎

The repeated selection mechanism satisfies individual rationality.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for each node $i\in
V\setminus g(\theta^{\prime})$, we have $u_{i}(\theta^{\prime})=0$. For each
node $i\in g(\theta^{\prime})$, by the proposed mechanism, we have
$x_{i}(\theta^{\prime})\leq v_{i}^{\prime}$. By Theorem 6.1, we have
$v_{i}^{\prime}=v_{i}$. Hence, we have
$u_{i}(\theta^{\prime})=v_{i}-x_{i}(\theta^{\prime})\geq 0$. So the mechanism
satisfies individual rationality. ∎

The repeated selection mechanism satisfies positiveness.

###### Proof.

Given a report profile $\theta^{\prime}\in\Theta$, for each node $i\in
V\setminus g(\theta^{\prime})$, we have $x_{i}(\theta^{\prime})=0$. For each
node $i\in g(\theta^{\prime})$, without loss of generality, we assume that it
is selected in stage $t$. Obviously, according to the proposed mechanism, its
cost share $X^{t}(\theta^{\prime})$ is non-negative. Therefore, the mechanism
satisfies positiveness. ∎

The repeated selection mechanism satisfies symmetry.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$ and $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}=v_{j}$, $c_{(i,k)}=c_{(j,k)}$ ($\forall k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$) implies
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})$.

By the proposed mechanism, nodes $i$ and $j$ are either both selected in the
same stage or they are not selected. If they are not selected, we have
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})=0$. Without loss of generality,
if they are both selected in stage $t$, by the proposed mechanism, we have
$x_{i}(\theta^{\prime})=x_{j}(\theta^{\prime})=X^{t}$. Since $v_{i}=v_{j}$, we
have $u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})$. So the mechanism
satisfies symmetry. ∎

The repeated selection mechanism satisfies ranking.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$ and $i,j\in V$ with
$r_{i}(\theta^{\prime})\setminus\\{j\\}=r_{j}(\theta^{\prime})\setminus\\{i\\}$
and $v_{i}=v_{j}$, $c_{(i,k)}\leq c_{(j,k)}$ ($\forall k\in
r_{i}(\theta^{\prime})\setminus\\{j\\}$) implies $u_{i}(\theta^{\prime})\geq
u_{j}(\theta^{\prime})$. For nodes $i$ and $j$, there are three cases.

  * •

$i,j\notin g(\theta^{\prime})$. Obviously, we have
$u_{i}(\theta^{\prime})=u_{j}(\theta^{\prime})=0$.

  * •

$i\in g(\theta^{\prime}),j\notin g(\theta^{\prime})$. By individual
rationality, we have $u_{i}(\theta^{\prime})\geq 0=u_{j}(\theta^{\prime})$.

  * •

$i,j\in g(\theta^{\prime})$. Let $t_{i}$ and $t_{j}$ denote the stages where
nodes $i$ and $j$ are selected respectively. For any set $S$ with $i,j\notin
S$, we have $C(S\cup\\{i\\})\leq C(S\cup\\{j\\})$. So we have $t_{i}\leq
t_{j}$. Since the later the selected stage is, the higher the cost share will
be, we have $X^{t_{i}}\leq X^{t_{j}}$. Since $v_{i}=v_{j}$, we have
$u_{i}(\theta^{\prime})-u_{j}(\theta^{\prime})=x_{j}(\theta^{\prime})-x_{i}(\theta^{\prime})=X^{t_{j}}-X^{t_{i}}\geq
0$.

Therefore, the mechanism satisfies ranking. ∎

The repeated selection mechanism satisfies utility monotonicity.

###### Proof.

Given $\theta^{\prime}\in\Theta$ and nodes $i,j\in V$ such that the edge
$(i,j)\in E$, there are two cases for node $i$.

  * •

$i\notin g(\theta^{\prime})$. Then $u_{i}(\theta^{\prime})=0$. When
$c_{(i,j)}$ increases, $i$ cannot be selected and the utility remains
unchanged.

  * •

$i\in g(\theta^{\prime})$. Then
$u_{i}(\theta^{\prime})=v_{i}-x_{i}(\theta^{\prime})$. When $c_{(i,j)}$
increases, let $g^{+}(\theta^{\prime})$ denote the set of selected nodes.

    * –

$i\notin g^{+}(\theta^{\prime})$. Then its utility is $0$. So the utility
weakly decreases.

    * –

$i\in g^{+}(\theta^{\prime})$. According to Theorem 6.1, it is easy to show
the utility of $i$ weakly decreases.

Hence, when $c_{(i,j)}$ increases, the utility of $i$ weakly decreases, i.e.,
the mechanism satisfies utility monotonicity. ∎

##  7\. Conclusions

In this paper, we study the cost sharing problem under private valuation and
connection control on general graphs. We consider two important strategic
behaviors of a node (i.e., cutting its adjacent edges and misreporting its
valuation). We show that it is impossible for a mechanism to satisfy
truthfulness, feasibility, efficiency, and budget balance simultaneously. We
also prove that there exists no approximate ratio for efficiency and budget
balance. Then we propose two truthful and feasible cost sharing mechanisms
that satisfy efficiency or budget balance.

In the future, we try to characterize all possible cost sharing mechanisms
that incentivize nodes to share their connections and reveal their valuations.

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 and Gómez-Rúa (2010) Gustavo Bergantiños and María Gómez-Rúa. 2010\.  Minimum cost spanning tree problems with groups.  _Economic Theory_ 43, 2 (2010), 227–262.
  * Bergantiños and Lorenzo (2004) Gustavo Bergantiños and Leticia Lorenzo. 2004.  A non-cooperative approach to the cost spanning tree problem.  _Mathematical Methods of Operations Research_ 59, 3 (2004), 393–403.
  * Bergantiños and Lorenzo (2008) Gustavo Bergantiños and Leticia Lorenzo. 2008.  Noncooperative cost spanning tree games with budget restrictions.  _Naval Research Logistics (NRL)_ 55, 8 (2008), 747–757.
  * Bergantiños and Vidal-Puga (2015) Gustavo Bergantiños and Juan Vidal-Puga. 2015.  Characterization of monotonic rules in minimum cost spanning tree problems.  _International Journal of Game Theory_ 44, 4 (2015), 835–868.
  * 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.
  * Bird (1976) Charles G Bird. 1976\.  On cost allocation for a spanning tree: a game theoretic approach.  _Networks_ 6, 4 (1976), 335–350.
  * Bogomolnaia and Moulin (2010) Anna Bogomolnaia and Hervé Moulin. 2010.  Sharing a minimal cost spanning tree: Beyond the Folk solution.  _Games and Economic Behavior_ 69, 2 (2010), 238–248.
  * Clarke (1971) Edward H Clarke. 1971\.  Multipart pricing of public goods.  _Public choice_ 11, 1 (1971), 17–33.
  * 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.
  * Granot and Huberman (1981) Daniel Granot and Gur Huberman. 1981.  Minimum cost spanning tree games.  _Mathematical programming_ 21, 1 (1981), 1–18.
  * Groves (1973) Theodore Groves. 1973\.  Incentives in teams.  _Econometrica: Journal of the Econometric Society_ (1973), 617–631.
  * 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.
  * 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.
  * Mehlhorn (1988) Kurt Mehlhorn. 1988\.  A faster approximation algorithm for the Steiner problem in graphs.  _Inform. Process. Lett._ 27, 3 (1988), 125–128.
  * Norde (2019) Henk Norde. 2019\.  The degree and cost adjusted folk solution for minimum cost spanning tree games.  _Games and Economic Behavior_ 113 (2019), 734–742.
  * 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.
  * Shapley (1953) Lloyd S Shapley. 1953\.  A Value for n-person Games.  _Contributions to the Theory of Games_ 2, 28 (1953), 307–317.
  * 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 _ECAI 2020_. IOS Press, 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 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.
  * Vickrey (1961) William Vickrey. 1961\.  Counterspeculation, auctions, and competitive sealed tenders.  _The Journal of finance_ 16, 1 (1961), 8–37.
  * Zhao (2022) Dengji Zhao. 2022\.  Mechanism design powered by social interactions: a call to arms. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_. 5831–5835.