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:
On Revenue Monotonicity in Combinatorial Auctions Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Hide and Seek Game with Multiple Resources

verfasst von : Marcin Dziubiński, Jaideep Roy

Erschienen in: Algorithmic Game Theory

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We study a generalization of hide and seek game of von Neumann [14], where each player has one or more resources. We characterize the value and Nash equilibria of such games in terms of their unidimensional marginal distributions. We propose a \(\mathcal {O}(n \log (n))\) time algorithm for computing unidimensional marginal distributions of equilibrium strategies and a quadratic time algorithm for computing mixed strategies given the margins. The characterization allows us to establish a number of interesting qualitative features of equilibria.

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 Simple Games Versus Weighted Voting Games
Nächstes Kapitel An Improved Envy-Free Cake Cutting Protocol for Four Agents
Fußnoten
1
Throughout the paper, given a positive integer m we will follow the usual practice of using [m] to denote the set \(\{1,\ldots ,m\}\).
 
2
The system of equations can be easily used to obtain full characterization in the cases with multiple equilibria. We decided to leave it out of the paper due to presentation considerations.
 
Literatur
1.
Ahmadinejad, A., Dehghani, S., Hajiaghayi, M., Lucier, B., Mahini, H., Seddighin, S.: From duels to battlefields: computing equilibria of Blotto and other games. In: Schuurmans, D., Wellman, M.P. (eds.) Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, 12–17 February 2016, pp. 376–382. AAAI Press (2016)
2.
Behnezhad, S., et al.: From battlefields to elections: winning strategies of Blotto and auditing games. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7–10 January 2018, pp. 2291–2310 (2018)
3.
Behnezhad, S., Dehghani, S., Derakhshan, M., Hajiaghayi, M.T., Seddighin, S.: Faster and simpler algorithm for optimal strategies of Blotto game. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 4–9 February 2017, pp. 369–375 (2017)
4.
Birkhoff, D.: Tres observaciones sobre el algebra lineal. Universidad Nacional de Tucuman Revista Serie A 5, 147–151 (1946)
5.
Borel, É.: La Théorie du Jeu et les Équations Intégrales à Noyau Symétrique. Comptes Rendus de l’Académie des Sciences 173, 1304–1308 (1921). Translated by Savage L.J.: The theory of play and integral equations with skew symmetric kernels. Econometrica 21, 97–100 (1953)
6.
Crawford, V., Iriberri, N.: Fatal attraction: salience, naïveté, and sophistication in experimental “hide-and-seek” games. Am. Econ. Rev. 97(5), 1731–1750 (2007)CrossRef
7.
Dulmage, L., Halperin, I.: On a theorem of Frobenius-König and J. von Neumann’s game of hide and seek. Proc. Trans. R. Soc. Can. 49(3), 23–29 (1955)MATH
8.
Fisher, D.: Two person zero-sum games and fractional graph parameters. Congr. Numerantium 85, 9–14 (1991)MathSciNetMATH
9.
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)MathSciNetCrossRef
10.
Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordóñez, F., Tambe, M.: Computing optimal randomized resource allocations for massive security games. In: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, AAMAS 2009, IFAAMAS, Richland, SC, pp. 689–696 (2009)
11.
Korzhyk, D., Conitzer, V., Parr, R.: Complexity of computing optimal Stackelberg strategies in security resource allocation games. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010. AAAI Press, Menlo Park (2010)
12.
Korzhyk, D., Conitzer, V., Parr, R.: Security games with multiple attacker resources. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, pp. 273–279. AAAI Press, Menlo Park (2011)
13.
Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V., Tambe, M.: Stackelberg vs. Nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Intell. Res. 41, 297–327 (2011)MathSciNetCrossRef
14.
von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Contributions to the Theory of Games (AM-28), vol. II, pp. 5–12. Princeton University Press (1953)
15.
Scheinerman, E., Ullman, D.: Fractional Graph Theory. Wiley, New York (1997)MATH
Metadaten
Titel
Hide and Seek Game with Multiple Resources
verfasst von
Marcin Dziubiński
Jaideep Roy
Copyright-Jahr
2018
Buch
Algorithmic Game Theory

Print ISBN: 978-3-319-99659-2

Electronic ISBN: 978-3-319-99660-8

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-99660-8_8

Premium Partner

    Bildnachweise