论文标题
与预算的连通性共享成本共享
Cost Sharing for Connectivity with Budget
论文作者
论文摘要
我们考虑了一个成本分享问题，可以在加权的无向图中连接所有节点，其中每个边缘的重量代表使用连接的边缘的成本，并且必须在所有连接的节点之间共享成本。有一个名为“来源”的节点，所有其他节点都想连接，并且没有共享连接性的成本。由于节点可能需要通过其他节点来达到源，因此中间节点可能会通过切割与它们相邻的边缘来战略性地阻止连接。为了防止这种战略行为，我们设计了成本共享机制，以激励所有节点，以免削减任何优势，以便我们可以最大程度地减少连接所有节点的总成本。
We consider a cost sharing problem to connect all nodes in a weighted undirected graph, where the weight of each edge represents the cost to use the edge for the connectivity and the cost has to be shared among all connected nodes. There is one node called the source to which all the other nodes want to connect and it does not share the costs of the connectivity. As a node may need to go through other nodes to reach the source, the intermediate nodes may behave strategically to block the connection by cutting the edges adjacent to them. To prevent such strategical behavior, we design cost sharing mechanisms to incentivize all nodes not to cut any edge so that we can minimize the total cost for connecting all the nodes.
