Document Open Access Logo

An Improved Tax Scheme for Selfish Routing

Authors Te-Li Wang, Chih-Kuan Yeh, Ho-Lin Chen

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.61.pdf
  • Filesize: 477 kB
  • 12 pages

Document Identifiers

Author Details

Te-Li Wang
Chih-Kuan Yeh
Ho-Lin Chen

Cite As Get BibTex

Te-Li Wang, Chih-Kuan Yeh, and Ho-Lin Chen. An Improved Tax Scheme for Selfish Routing. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.61

Abstract

We study the problem of routing traffic for independent selfish users in a congested network to minimize the total latency. The inefficiency of selfish routing motivates regulating the flow of the system to lower the total latency of the Nash Equilibrium by economic incentives or penalties. When applying tax to the routes, we follow the definition of [Christodoulou et al, Algorithmica, 2014] to define ePoA as the Nash total cost including tax in the taxed network over the optimal cost in the original network. We propose a simple tax scheme consisting of step functions imposed on the links. The tax scheme can be applied to routing games with parallel links, affine cost functions and single-commodity networks to lower the ePoA to at most 4/3 - epsilon, where epsilon only depends on the discrepancy between the links. We show that there exists a tax scheme in the two link case with an ePoA upperbound less than 1.192 which is almost tight. Moreover, we design another tax scheme that lowers ePoA down to 1.281 for routing games with groups of links such that links in the same group are similar to each other and groups are sufficiently different.

Subject Classification

Keywords
  • selfish routing
  • price of anarchy
  • tax

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yossi Azar, Lisa Fleischer, Kamal Jain, Vahab Mirrokni, and Zoya Svitkina. Optimal coordination mechanisms for unrelated machine scheduling. Operations Research, 2015. Google Scholar
  2. Martin Beckmann, C. B. McGuire, and Christopher B. Winsten. Studies in the economics of transportation. Technical report, 1956. Google Scholar
  3. David Bernstein and Tony E. Smith. Equilibria for networks with lower semicontinuous costs: With an application to congestion pricing. Transportation Science, 28(3):221-235, 1994. Google Scholar
  4. Vincenzo Bonifaci, Mahyar Salek, and Guido Schäfer. Efficiency of restricted tolls in non-atomic network routing games. Springer, 2011. Google Scholar
  5. Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica, 66(3):512-540, 2013. Google Scholar
  6. Ho-Lin Chen and Tim Roughgarden. Network design with weighted players. Theory of Computing Systems, 45(2):302-324, 2009. Google Scholar
  7. George Christodoulou, Elias Koutsoupias, and Akash Nanavati. Coordination mechanisms. Theoretical Computer Science, 410(36):3327-3336, 2009. Google Scholar
  8. Giorgos Christodoulou, Kurt Mehlhorn, and Evangelia Pyrga. Improving the price of anarchy for selfish routing via coordination mechanisms. Algorithmica, 69(3):619-640, 2014. Google Scholar
  9. Richard Cole, Yevgeniy Dodis, and Tim Roughgarden. How much can taxes help selfish routing? In Proceedings of the 4th ACM conference on Electronic commerce, pages 98-107. ACM, 2003. Google Scholar
  10. Richard Cole, Yevgeniy Dodis, and Tim Roughgarden. Pricing network edges for heterogeneous selfish users. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 521-530. ACM, 2003. Google Scholar
  11. Lisa Fleischer. Linear tolls suffice: New bounds and algorithms for tolls in single source networks. Theoretical Computer Science, 348(2):217-225, 2005. Google Scholar
  12. Lisa Fleischer, Kamal Jain, and Mohammad Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 277-285. IEEE, 2004. Google Scholar
  13. Randolph Hall. Handbook of transportation science, volume 23. Springer Science &Business Media, 2012. Google Scholar
  14. Nicole Immorlica, Li Erran Li, Vahab S. Mirrokni, and Andreas S. Schulz. Coordination mechanisms for selfish scheduling. Theoretical Computer Science, 410(17):1589-1598, 2009. Google Scholar
  15. George Karakostas and Stavros G. Kolliopoulos. Edge pricing of multicommodity networks for heterogeneous selfish users. In FOCS, volume 4, pages 268-276, 2004. Google Scholar
  16. George Karakostas and Stavros G. Kolliopoulos. The efficiency of optimal taxes. In Combinatorial and Algorithmic Aspects of Networking, pages 3-12. Springer, 2005. Google Scholar
  17. Konstantinos Kollias. Non-preemptive coordination mechanisms for identical machine scheduling games. In Structural Information and Communication Complexity, pages 197-208. Springer, 2008. Google Scholar
  18. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS 99, pages 404-413. Springer, 1999. Google Scholar
  19. Michael Patriksson. The Traffic Assignment Problem: Models and Methods. Courier Dover Publications, 2015. Google Scholar
  20. Arthur Cecil Pigou. The economics of welfare. Palgrave Macmillan, 2013. Google Scholar
  21. Lili Qiu, Yang Richard Yang, Yin Zhang, and Scott Shenker. On selfish routing in internet-like environments. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 151-162. ACM, 2003. Google Scholar
  22. Tim Roughgarden. The price of anarchy is independent of the network topology. Journal of Computer and System Sciences, 67(2):341-364, 2003. Google Scholar
  23. Tim Roughgarden. Selfish routing and the price of anarchy, volume 174. MIT press Cambridge, 2005. Google Scholar
  24. Tim Roughgarden. On the severity of braess’s paradox: designing networks for selfish users is hard. Journal of Computer and System Sciences, 72(5):922-953, 2006. Google Scholar
  25. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact