Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints Read chapter Read first chapter

2015 | OriginalPaper | Chapter

“Beat-Your-Rival” Routing Games

Authors : Gideon Blocq, Ariel Orda

Published in: Algorithmic Game Theory

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the traditional setting of routing games, the standard assumption is that selfish agents are unconcerned with the performance of their competitors in the network. We propose an extension to this setting by modeling agents to consider a combination of their own performance as well as that of their rivals. Per agent, we parameterize this trade-off, thereby allowing agents to be partially selfish and partially malicious.
We consider two types of routing games based on the structure of the agents’ performance objectives, namely bottleneck routing games and additive routing games. For bottleneck routing games, the performance of an agent is determined by its worst-case link performance, and for additive routing games, performance is determined by the sum of its link performances. For the bottleneck routing scenario we establish the existence of a Nash equilibrium and show that the Price of Stability is equal to 1. We also prove that the Price of Anarchy is unbounded. For additive routing games, we focus on the fundamental load balancing game of routing over parallel links. For an interesting class of agents, we prove the existence of a Nash equilibrium. Specifically, we establish that a special case of the Wardrop equilibrium is likewise a Nash equilibrium. Moreover, when the system consists of two agents, this Nash equilibrium is unique, and for the general case of N agents, we present an example of its non-uniqueness.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Excluding Braess’s Paradox in Nonatomic Selfish Routing
next chapter Characterization and Computation of Equilibria for Indivisible Goods
Footnotes
1
In [5] a similar theorem was proven for a more general topology. However, they only considered selfish users (i.e., \(\forall i,~\alpha ^i=1\)).
 
2
An existence and uniqueness proof for selfish users is given in [20].
 
Literature
1.
Altman, E., Basar, T., Jiménez, T., Shimkin, N.: Competitive routing in networks with polynomial cost. In: Proceedings of INFOCOM 2000, pp. 1586–1593 (2000)
2.
Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)MathSciNetCrossRefMATH
3.
Azad, A.P., Altman, E., Azouzi, R.E.: Routing games : from egoism to altruism. In: Proceedings of WiOpt 2010, pp. 528–537 (2010)
4.
Babaioff, M., Kleinberg, R., Papadimitriou, C.H.: Congestion games with malicious players. Games Econ. Behav. 67(1), 22–35 (2009)MathSciNetCrossRefMATH
5.
Banner, R., Orda, A.: Bottleneck routing games in communication networks. IEEE J. Sel. Areas Commun. 25(6), 1173–1179 (2007)CrossRef
6.
7.
Blocq, G., Orda, A.: Worst-case coalitions in routing games. CoRR abs/1310.3487 (2013)
8.
9.
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Papaioannou, E.: The impact of altruism on the efficiency of atomic congestion games. In: Wirsing, M., Hofmann, M., Rauschmayer, A. (eds.) TGC 2010, LNCS, vol. 6084, pp. 172–188. Springer, Heidelberg (2010) CrossRef
10.
Chen, P., de Keijzer, B., Kempe, D., Schäfer, G.: Altruism and its impact on the price of anarchy. ACM Trans. Econ. Comput. 2(4), 17:1–17:45 (2014)CrossRef
11.
Chen, P., Kempe, D.: Altruism, selfishness, and spite in traffic routing. In: Proceedings EC 2008, pp. 140–149 (2008)
12.
Cole, R., Dodis, Y., Roughgarden, T.: Bottleneck links, variable demand, and the tragedy of the commons. Networks 60(3), 194–203 (2012)MathSciNetCrossRefMATH
13.
Correa, J.R., Moses, N.E.S.: Wardrop equilibria. Wiley Encyclopedia of Operations Research and Management Science (2010)
14.
Harks, T.: Stackelberg strategies and collusion in network games with splittable flow. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 133–146. Springer, Heidelberg (2009) CrossRef
15.
Hoefer, M., Skopalik, A.: Altruism in atomic congestion games. ACM Trans. Econ. Comput. 1(4), 21 (2013)CrossRefMATH
16.
17.
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, p. 404. Springer, Heidelberg (1999) CrossRef
18.
La, R.J., Anantharam, V.: Optimal routing control: repeated game approach. IEEE Trans. Autom. Control 47, 437–450 (2002)MathSciNetCrossRef
19.
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007) CrossRefMATH
20.
Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Trans. Networking 1, 510–521 (1993)CrossRef
21.
22.
Roth, A.: The price of malice in linear congestion games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 118–125. Springer, Heidelberg (2008) CrossRef
23.
Roughgarden, T.: Stackelberg scheduling strategies. In: Proceedings of STOC 2001, pp. 104–113 (2001)
24.
Roughgarden, T.: Algorithmic game theory. Commun. ACM 53(7), 78–86 (2010)CrossRef
25.
26.
27.
Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Part II, vol. 1, pp. 325–378 (1952)
Metadata
Title
“Beat-Your-Rival” Routing Games
Authors
Gideon Blocq
Ariel Orda
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Algorithmic Game Theory

Print ISBN: 978-3-662-48432-6

Electronic ISBN: 978-3-662-48433-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48433-3_18

Premium Partner

    Image Credits