Thumbnail
Access Restriction
Open

Author Kumar, Abhimanu ♦ Das, Sanjib Kumar
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2009-10-12
Language English
Subject Domain (in DDC) Computer science, information & general works
Subject Keyword Computer Science - Computer Science and Game Theory ♦ cs
Abstract 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.
Educational Use Research
Learning Resource Type Article
Page Count 12


Open content in new tab

   Open content in new tab