Approximation algorithms for routing and scheduling problems on networks

我们将网络上的路由和调度问题视为一个以网络上所有参与者的社会福利最大化为目标的组合拍卖问题，并研究了所有参与者都同意的稳定解（纳什均衡）的存在性。当所有参与者的估价都满足对称和次可加性时，我们给出了这种组合拍卖中存在纳什均衡的刻画。通过这一表征，我们得到了一个判定纳什均衡存在的算法。进一步证明了如果所有参与者的估值都满足对称和次模性质，则纳什均衡总是存在的，并且我们可以在多项式时间内找到这样的纳什均衡。

We considered routing and scheduling problems on a network as a combinatorial auction problem for maximizing the social welfare of all participants on the network and investigated the existence of a stable solution (Nash equilibrium) which all participants agree on. We gave a characterization for the existence of a Nash equilibrium in such a combinatorial auction when valuations by all participants satisfy symmetric and subadditive properties. By this characterization, we obtained an algorithm for deciding a Nash equilibrium exists. Furthermore, we showed that, if valuations by all participants satisfy symmetric and submodular properties, Nash equilibrium always exists and we can find such a Nash equilibrium in polynomial time.