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 proceedingpeer-review

1 Citation (Scopus)


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 1n

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 1n 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
Subtitle of host publicationFirst International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings
EditorsXiaotie Deng, Yinyu Ye
PublisherSpringer-Verlag Berlin Heidelberg
Number of pages10
ISBN (Electronic)9783540322931
ISBN (Print)9783540309000
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference1st International Workshop on Internet and Network Economics, WINE 2005
CityHong Kong

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Nash Equilibrium
  • Dominant Strategy
  • Budget Balance
  • Incentive Compatible
  • Combinatorial Auction


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

Cite this