Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players
Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players
复制标题
计算具有弧线限制和异构玩家的最佳通行费
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
G. Schäfer
中科院分区：
文献类型：
--
作者：
Tomáš Jelínek;Marcus Klaas;G. Schäfer
计算最优网络收费的问题，诱导最小总成本的纳什均衡已经在文献中深入研究，但大多是在假设这些收费是不受限制的。在这里，我们在更现实的假设下考虑这个问题，即通行费必须尊重弧线上的一些给定上限限制。最优地对子网征税的问题构成了这个问题的一个重要特例。我们研究了非原子和原子（未加权和加权）参与者的受限网络收费问题;我们的研究是第一个也包含异构参与者的研究，即，玩家对通行费的敏感度不同
对于非原子和异构的球员，我们证明了这个问题是NP难的，即使是单一商品网络和仿射延迟函数。因此，我们专注于平行弧网络，并给出了一个算法，最佳征税的子网络与仿射延迟函数。对于加权原子参与者，即使参与者是同质的，这个问题对于平行弧网络和线性延迟函数也是NP难的。相比之下，对于未加权的原子和同质玩家，我们开发了一种算法来计算并行弧网络和任意（标准）延迟函数的最佳限制通行费。同样，对于未加权的原子和异构的球员，我们推导出一个算法，最佳征税的并行弧网络和任意（标准）的延迟函数的子网络。
我们大多数研究结果的关键是得到（组合）特征的流量是诱导的限制通行费。这些特征可能是独立的利益。
The problem of computing optimal network tolls that induce a Nash equilibrium of minimum total cost has been studied intensively in the literature, but mostly under the assumption that these tolls are unrestricted. Here we consider this problem under the more realistic assumption that the tolls have to respect some given upper bound restrictions on the arcs. The problem of taxing subnetworks optimally constitutes an important special case of this problem. We study the restricted network toll problem for both non-atomic and atomic (unweighted and weighted) players; our studies are the first that also incorporate heterogeneous players, i.e., players with different sensitivities to tolls.
For non-atomic and heterogeneous players, we prove that the problem is NP-hard even for single-commodity networks and affine latency functions. We therefore focus on parallel-arc networks and give an algorithm for optimally taxing subnetworks with affine latency functions. For weighted atomic players, the problem is NP-hard already for parallel-arc networks and linear latency functions, even if players are homogeneous. In contrast, for unweighted atomic and homogeneous players, we develop an algorithm to compute optimal restricted tolls for parallel-arc networks and arbitrary (standard) latency functions. Similarly, for unweighted atomic and heterogeneous players, we derive an algorithm for optimally taxing subnetworks for parallel-arc networks and arbitrary (standard) latency functions.
The key to most of our results is to derive (combinatorial) characterizations of flows that are inducible by restricted tolls. These characterizations might be of independent interest.