2009/10/12 by Abhimanu Kumar, Kumar, Abhimanu, Sanjib Kumar Das +1
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #FOS: Computer and information sciences #Game Theory and Applications #Merger and Competition Analysis
paper · pdf · doi:10.48550/arxiv.0910.2113
openalex publication_date 2009/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Internet and graphs are very much related. The graphical structure of internet has been studied extensively to provide efficient solutions to routing and other problems. But most of these studies assume a central authority which controls and manages the internet. In the recent years game theoretic models have been proposed which do not require a central authority and the users are assumed to be routing their flows selfishly. The existence of Nash Equilibria, congestion and the amount of inefficiency caused by this selfish routing is a major concern in this field. A type of paradox in the selfish routing networks, Braess' Paradox, first discovered by Braess, is a major contributor to inefficiency. Several pricing mechanisms have also been provided which give a game theoretical model between users(consumers) and ISPs (Internet Service Providers or sellers) for the internet. We propose a novel pricing mechanism, based on real world Internet network architecture, which reduces the severity of Braess' Paradox in selfish routing game theoretic networks. It's a pricing mechanism between combinatorial users and ISPs. We prove that Nash equilibria exists in this network and provide bounds on inefficiency . We use graphical properties of internet to prove our result. Several interesting extensions and future work have also been discussed.