Nash equilibria and dominant strategies in routing

Weizhao Wang; Xiang-Yang Li; Xiaowen CHU

doi:10.1007/11600930_99

Nash equilibria and dominant strategies in routing

Weizhao Wang^*, Xiang-Yang Li, Xiaowen CHU

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 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 language	English
Title of host publication	Internet and Network Economics
Subtitle of host publication	First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings
Editors	Xiaotie Deng, Yinyu Ye
Publisher	Springer-Verlag Berlin Heidelberg
Pages	979-988
Number of pages	10
Edition	1st
ISBN (Electronic)	9783540322931
ISBN (Print)	9783540309000
DOIs	https://doi.org/10.1007/11600930_99
Publication status	Published - 2005
Event	1st International Workshop on Internet and Network Economics, WINE 2005 - Hong Kong, China Duration: 15 Dec 2005 → 17 Dec 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3828
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Workshop on Internet and Network Economics, WINE 2005
Country/Territory	China
City	Hong Kong
Period	15/12/05 → 17/12/05

Scopus Subject Areas

Theoretical Computer Science
Computer Science(all)

User-Defined Keywords

Nash Equilibrium
Dominant Strategy
Budget Balance
Incentive Compatible
Combinatorial Auction

Access to Document

10.1007/11600930_99

Cite this

Wang, W., Li, X.-Y., & CHU, X. (2005). Nash equilibria and dominant strategies in routing. In X. Deng, & Y. Ye (Eds.), Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings (1st ed., pp. 979-988). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3828). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/11600930_99

Wang, Weizhao ; Li, Xiang-Yang ; CHU, Xiaowen. / Nash equilibria and dominant strategies in routing. Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings. editor / Xiaotie Deng ; Yinyu Ye. 1st. ed. Springer-Verlag Berlin Heidelberg, 2005. pp. 979-988 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{dbbb2baefbd64006bd16756df8b0a70f,

title = "Nash equilibria and dominant strategies in routing",

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 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.",

keywords = "Nash Equilibrium, Dominant Strategy, Budget Balance, Incentive Compatible, Combinatorial Auction",

author = "Weizhao Wang and Xiang-Yang Li and Xiaowen CHU",

note = "Publisher copyright: {\textcopyright} 2005 Springer-Verlag Berlin Heidelberg All rights reserved. ; 1st International Workshop on Internet and Network Economics, WINE 2005 ; Conference date: 15-12-2005 Through 17-12-2005",

year = "2005",

doi = "10.1007/11600930_99",

language = "English",

isbn = "9783540309000",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "979--988",

editor = "Xiaotie Deng and Yinyu Ye",

booktitle = "Internet and Network Economics",

edition = "1st",

}

Wang, W, Li, X-Y & CHU, X 2005, Nash equilibria and dominant strategies in routing. in X Deng & Y Ye (eds), Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings. 1st edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3828, Springer-Verlag Berlin Heidelberg, pp. 979-988, 1st International Workshop on Internet and Network Economics, WINE 2005, Hong Kong, China, 15/12/05. https://doi.org/10.1007/11600930_99

Nash equilibria and dominant strategies in routing. / Wang, Weizhao; Li, Xiang-Yang; CHU, Xiaowen.
Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings. ed. / Xiaotie Deng; Yinyu Ye. 1st. ed. Springer-Verlag Berlin Heidelberg, 2005. p. 979-988 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3828).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Nash equilibria and dominant strategies in routing

AU - Wang, Weizhao

AU - Li, Xiang-Yang

AU - CHU, Xiaowen

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - Nash Equilibrium

KW - Dominant Strategy

KW - Budget Balance

KW - Incentive Compatible

KW - Combinatorial Auction

UR - http://www.scopus.com/inward/record.url?scp=33744934218&partnerID=8YFLogxK

U2 - 10.1007/11600930_99

DO - 10.1007/11600930_99

M3 - Conference proceeding

AN - SCOPUS:33744934218

SN - 9783540309000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 979

EP - 988

BT - Internet and Network Economics

A2 - Deng, Xiaotie

A2 - Ye, Yinyu

PB - Springer-Verlag Berlin Heidelberg

T2 - 1st International Workshop on Internet and Network Economics, WINE 2005

Y2 - 15 December 2005 through 17 December 2005

ER -

Wang W, Li XY, CHU X. Nash equilibria and dominant strategies in routing. In Deng X, Ye Y, editors, Internet and Network Economics: First International Workshop, WINE 2005, Hong Kong, China, December 15-17, 2005, Proceedings. 1st ed. Springer-Verlag Berlin Heidelberg. 2005. p. 979-988. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11600930_99

Nash equilibria and dominant strategies in routing

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this