## 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 |