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 language | English (US) |
|---|---|
| Title of host publication | Proceedings of the ACM Conference on Electronic Commerce |
| Pages | 98-107 |
| Number of pages | 10 |
| State | Published - 2003 |
| Event | Proceedings of the 4th ACM Conference on Electronic Commerce - San Diego, CA, United States Duration: Jun 9 2003 → Jun 12 2003 |
Other
| Other | Proceedings of the 4th ACM Conference on Electronic Commerce |
|---|---|
| Country/Territory | United States |
| City | San Diego, CA |
| Period | 6/9/03 → 6/12/03 |
Keywords
- Game theory
- Nash equilibria
- Network pricing
- Selfish routing
ASJC Scopus subject areas
- Computer Science (miscellaneous)
- Business, Management and Accounting (miscellaneous)