Nash equilibria and dominant strategies in routing

Weizhao Wang*, Xiang Yang Li, Xiaowen CHU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

Nash equilibria and dominant strategies are two of the major approaches to deal with selfishness in an automated system (AS), where each agent is a selfish entity. In this paper, we consider the scenario when the receiver(s) and the relay links are both selfish, which generalizes the previous scenario in which either the relay links are selfish or the receivers are selfish. This also advances all previous studying in routing by taking into account the budget balance ratio. We prove that no mechanism can achieve budget balance ratio greater than 1/n when truthful revealing is a dominant strategy for each of the relay links and receivers. Here, n is the number of vertices in the network. In the meanwhile, we also present a mechanism that achieves the budget balance ratio 1/n and is truthful for both the receivers and relay links, which closes the bounds. When we relax the truthful revealing requirement to Nash Equilibrium for relay links, we present a mechanism that achieves an asymptotically optimal budget balance ratio.

Original languageEnglish
Title of host publicationInternet and Network Economics - First International Workshop, WINE 2005, Proceedings
PublisherSpringer Verlag
Pages979-988
Number of pages10
ISBN (Print)3540309004, 9783540309000
DOIs
Publication statusPublished - 2005
Event1st International Workshop on Internet and Network Economics, WINE 2005 - Hong Kong, China
Duration: 15 Dec 200517 Dec 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3828 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference1st International Workshop on Internet and Network Economics, WINE 2005
Country/TerritoryChina
CityHong Kong
Period15/12/0517/12/05

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Nash equilibria and dominant strategies in routing'. Together they form a unique fingerprint.

Cite this