NDLI: Worst-Case Nash Equilibria in Restricted Routing

Content Provider	Springer Nature Link
Author	Lu, Pin Yan Yu, Chang Yuan
Copyright Year	2012
Abstract	We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some weight to assign to one of the links from a subset of all the links, named his/her allowable set. The users choosing the same link suffer the same delay, which is equal to the total weight assigned to that link over its speed. A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link. To measure the performance degradation of the system due to the selfish behavior of all the users, Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA), which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution. The PoA for this restricted related model has been studied, and a linear lower bound was obtained. However in their bad instance, some users can only use extremely slow links. This is a little artificial and unlikely to appear in a real world. So in order to better understand this model, we introduce a parameter for the system, and prove a better Price of Anarchy in terms of the parameter. We also show an important application of our result in coordination mechanism design for task scheduling game. We propose a new coordination mechanism, Group-Makespan, for unrelated selfish task scheduling game with improved price of anarchy.
Starting Page	710
Ending Page	717
Page Count	8
File Format	PDF
ISSN	10009000
Journal	Journal of Computer Science and Technology
Volume Number	27
Issue Number	4
e-ISSN	18604749
Language	English
Publisher	Springer US
Publisher Date	2012-07-12
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	routing Nash equilibria price of anarchy Software Engineering Information Systems Applications (incl. Internet) Data Structures, Cryptology and Information Theory Theory of Computation Computer Science Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computer Science Applications Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Better-Than-Worst-Case Design: Progress and Opportunities

A Heuristic Algorithm for Core Selection in Multicast Routing

Problems in the information dissemination of the Internet routing

Multipath Routing of Multiple Description Coded Images in Wireless Networks

Impact of Strangers on Opportunistic Routing Performance

Introduction to the Six Leading Editors

Software-Defined Cluster

Internet of Things: Objectives and Scientific Challenges

From active to passive — Progress in testing internet routing protocols

Worst-Case Nash Equilibria in Restricted Routing

Similar Documents

Better-Than-Worst-Case Design: Progress and Opportunities

A Heuristic Algorithm for Core Selection in Multicast Routing

Problems in the information dissemination of the Internet routing

Multipath Routing of Multiple Description Coded Images in Wireless Networks

Impact of Strangers on Opportunistic Routing Performance

Introduction to the Six Leading Editors

Software-Defined Cluster

Internet of Things: Objectives and Scientific Challenges

From active to passive — Progress in testing internet routing protocols

Worst-Case Nash Equilibria in Restricted Routing