Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Ordinal Approximation for Social Choice, Matching, and Facility Location Problems Given Candidate Positions Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Timing Matters: Online Dynamics in Broadcast Games

verfasst von : Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, Seeun William Umboh

Erschienen in: Web and Internet Economics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution at equilibrium. This implies that the central controller must have some control over the timing of agent arrivals and departures in order to ensure efficiency of the system at equilibrium. Indeed, we give a complementary result showing that if the central controller is allowed to restore equilibrium after every set of arrivals/departures via improving moves, the eventual equilibrium states reached have exponentially better efficiency.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Revealed Preference Dimension via Matrix Sign Rank
Nächstes Kapitel A Simple Mechanism for a Budget-Constrained Buyer
Fußnoten
1
The full version of this paper [12] provides examples illustrating these bounds.
 
2
Observe that when an agent arrives or makes an improving move, paths of other agents may become suboptimal for them.
 
3
Charikar et al. also studied a variant where arrivals happen in uniformly random order and are interleaved with adversarially ordered best response moves. For this setting, they were able to prove an upper bound of \(O(\sqrt{n}{\text {polylog}}n)\) on the quality of the equilibria reached, but did not present any lower bounds.
 
4
Another bound is the optimal Steiner tree on all vertices for which an agent arrived at some point in the dynamics. Since we can assume metric costs, we can restrict our attention to these vertices and then mst cost is within a factor of two of the cost of optimal Steiner tree.
 
5
Note that although arrivals within a single epoch are simultaneous in that every arriving player picks a best response path with respect to the equilibrium state at the beginning of the epoch, arrivals in different epochs are sequential. In this sense our model captures sequential arrivals with interleaved improving moves.
 
6
Because of this comparison against the mst, we prefer the term “broadcast game” for this setting, rather than the “multicast game”.
 
7
The existence of a cycle would imply that one of the agents can improve her cost share by switching to a different path and the current state is not an equilibrium.
 
Literatur
1.
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233 (2011)MathSciNetCrossRef
2.
3.
Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. ACM Trans. Algorithms 2(4), 640–660 (2006)MathSciNetCrossRef
4.
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)MathSciNetCrossRef
5.
Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized steiner problem. Theor. Comput. Sci. 324(2–3), 313–324 (2004)MathSciNetCrossRef
6.
Balcan, M.-F., Blum, A., Mansour, Y.: Circumventing the price of anarchy: leading dynamics to good behavior. SIAM J. Comput. 42(1), 230–264 (2013)MathSciNetCrossRef
7.
Beier, R., Czumaj, A., Krysta, P., Vöcking, B.: Computing equilibria for a service provider game with (im)perfect information. ACM Trans. Algorithms 2(4), 679–706 (2006)MathSciNetCrossRef
8.
Berman, P., Coulston, C.: On-line algorithms for steiner tree problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 344–353. ACM (1997)
9.
Bilò, V., Bove, R.: Bounds on the price of stability of undirected network design games with three players. J. Interconnect. Netw. 12(1–2), 1–17 (2011)CrossRef
10.
Bilò, V., Flammini, M., Moscardelli, L.: The price of stability for undirected broadcast network design with fair cost allocation is constant. In: FOCS, pp. 638–647 (2013)
11.
Charikar, M., Karloff, H.J., Mathieu, C., Naor, J., Saks, M.E.: Online multicast with egalitarian cost sharing. In: SPAA, pp. 70–76 (2008)
12.
13.
Chekuri, C., Chuzhoy, J., Lewin-Eytan, L., Naor, J.(Seffi), Orda, A.: Non-cooperative multicast and facility location games. IEEE J. Sel. Areas Commun. 25(6), 1193–1206 (2007)CrossRef
14.
Chen, H.-L., Roughgarden, T.: Network design with weighted players. Theory Comput. Syst. 45(2), 302–324 (2009)MathSciNetCrossRef
15.
16.
Ene, A., Chakrabarty, D., Krishnaswamy, R., Panigrahi, D.: Online buy-at-bulk network design. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17–20 October, 2015, pp. 545–562 (2015)
17.
Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 13–16 June 2004, pp. 604–612 (2004)
18.
Fanelli, A., Leniowski, D., Monaco, G., Sankowski, P.: The ring design game with fair cost allocation. Theor. Comput. Sci. 562, 90–100 (2015)MathSciNetCrossRef
19.
Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., Shabo, R.: On the price of stability for designing undirected networks with fair cost allocations. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 608–618. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11786986_​53CrossRef
20.
21.
Gupta, A., Ravi, R., Talwar, K., Umboh, S.W.: LAST but not least: online spanners for buy-at-bulk. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, 16–19 January, Hotel Porta Fira, Barcelona, Spain, pp. 589–599 (2017)
22.
Hajiaghayi, M.T., Liaghat, V., Panigrahi, D.: Online node-weighted steiner forest and extensions via disk paintings. In: FOCS, pp. 558–567 (2013)
23.
24.
Harks, T., Klimm, M.: On the existence of pure nash equilibria in weighted congestion games. Math. Oper. Res. 37(3), 419–436 (2012)MathSciNetCrossRef
25.
26.
Kawase, Y., Makino, K.: Nash equilibria with minimum potential in undirected broadcast games. Theor. Comput. Sci. 482, 33–47 (2013)MathSciNetCrossRef
27.
Lee, E., Ligett, K.: Improved bounds on the price of stability in network cost sharing games. In: EC, pp. 607–620 (2013)
28.
Li, J.: An O(log(n)/log(log(n))) upper bound on the price of stability for undirected shapley network design games. Inf. Process. Lett. 109(15), 876–878 (2009)CrossRef
29.
Milchtaich, I.: Congestion games with player-specific payoff function. Games Econ. Behav. 13, 111–124 (1996)MathSciNetCrossRef
30.
31.
Naor, J., Panigrahi, D., Singh, M.: Online node-weighted steiner tree and related problems. In: FOCS, pp. 210–219 (2011)
32.
Qian, J., Umboh, S.W., Williamson, D.P.: Online constrained forest and prize-collecting network design. Algorithmica 80(11), 3335–3364 (2018)MathSciNetCrossRef
33.
34.
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973)MathSciNetCrossRef
35.
36.
Umboh, S.: Online network design algorithms via hierarchical decompositions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1373–1387. SIAM (2015)
Metadaten
Titel
Timing Matters: Online Dynamics in Broadcast Games
verfasst von
Shuchi Chawla
Joseph (Seffi) Naor
Debmalya Panigrahi
Mohit Singh
Seeun William Umboh
Copyright-Jahr
2018
Buch
Web and Internet Economics

Print ISBN: 978-3-030-04611-8

Electronic ISBN: 978-3-030-04612-5

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-030-04612-5_6