  We consider a cost sharing problem on a weighted directed acyclic graph (DAG)
with a source node to which all the other nodes want to connect. The cost
(weight) of each edge is private information reported by multiple contractors,
and among them, only one contractor is selected as the builder. All the nodes
except for the source need to share the total cost of the used edges. However,
they may block others' connections to the source by strategically cutting their
outgoing edges to reduce their cost share, which may increase the total cost of
connectivity. To minimize the total cost of connectivity, we design a cost
sharing mechanism to incentivize each node to offer all its outgoing edges and
each contractor to report all the edges' weights truthfully, and show the
properties of the proposed mechanism. In addition, our mechanism outperforms
the two benchmark mechanisms.
