Abstract
We study taxes in the well-known game theoretic traffic model due to Wardrop. Given a network and a subset of edges, on which we can impose taxes, the problem is to find taxes inducing an equilibrium flow of minimal network-wide latency cost. If all edges are taxable, then marginal cost pricing is known to induce the socially optimal flow for arbitrary multi-commodity networks. In contrast, if only a strict subset of edges is taxable, we show NP-hardness of finding optimal taxes for general networks with linear latency functions and two commodities. On the positive side, for single-commodity networks with parallel links and linear latency function, we provide a polynomial time algorithm for finding optimal taxes.
| Original language | English |
|---|---|
| Title of host publication | Internet and Network Economics |
| Subtitle of host publication | 4th International Workshop, WINE 2008, Proceedings |
| Editors | Christos Papadimitriou, Shuzhong Zhang |
| Pages | 286-294 |
| Number of pages | 9 |
| ISBN (Electronic) | 978-3-540-92185-1 |
| DOIs | |
| Publication status | Published - 1 Dec 2008 |
| Externally published | Yes |
| Event | 4th International Workshop on Internet and Network Economics, WINE 2008: Internet And Network Economics (WINE 2008) - Shanghai, China, Shanghai, China Duration: 17 Dec 2008 → 20 Dec 2008 Conference number: 4 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 5385 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 4th International Workshop on Internet and Network Economics, WINE 2008 |
|---|---|
| Abbreviated title | WINE 2008 |
| Country/Territory | China |
| City | Shanghai |
| Period | 17/12/08 → 20/12/08 |
| Other | 17-20 Dec, 2008 |