How much can taxes help selfish routing?

Richard Cole, Yevgeniy Dodis, Tim Roughgarden

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Economic incentives for influencing selfish behavior in networks were studied. A model of selfish routing was considered in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. It was proved that in a large class of networks, marginal cost taxes do not improve the cost of the Nash equilibrium, the best-possible benefit from arbitrary taxes does not exceed that of edge removal, and that strong inapproximability results known for network design carry over to the problem of computing optimal taxes, proving this problem computationally intractable.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM Conference on Electronic Commerce
Pages98-107
Number of pages10
StatePublished - 2003
EventProceedings of the 4th ACM Conference on Electronic Commerce - San Diego, CA, United States
Duration: Jun 9 2003Jun 12 2003

Other

OtherProceedings of the 4th ACM Conference on Electronic Commerce
CountryUnited States
CitySan Diego, CA
Period6/9/036/12/03

Keywords

  • Game theory
  • Nash equilibria
  • Network pricing
  • Selfish routing

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Business, Management and Accounting (miscellaneous)

Fingerprint Dive into the research topics of 'How much can taxes help selfish routing?'. Together they form a unique fingerprint.

Cite this